Sawakatsu Inoue
Research Mentor(s): Alauddin Ahmed
Mentor Department: University of Michigan
Authors: Alauddin Ahmed, Sawakatsu Inoue
Session: Session 1 (9:00am – 9:50am)
Presentation Type: Poster 29
Abstract
Job shop scheduling is a critical optimization challenge in modern manufacturing, determining how N jobs are assigned to M machines while considering constraints such as job precedence and machine availability. Efficient scheduling directly impacts production efficiency and flexibility in increasingly automated environments. Traditional optimization solvers struggle with the combinatorial complexity of large scheduling problems, prompting exploration of alternative approaches such as quantum annealing and classical simulated annealing. In this study, we formulate the job shop scheduling problem as a Quadratic Unconstrained Binary Optimization (QUBO) model, a framework compatible with both D-Wave’s quantum annealer and classical annealing solvers. Our approach encodes job precedence and machine capacity constraints as penalty terms within the QUBO model, ensuring that feasible schedules emerge from the annealing process. We evaluate both methods by solving scheduling instances of varying sizes and comparing performance metrics, including solution quality, computational efficiency, and scalability. Preliminary results indicate that while quantum annealing shows promise for exploring complex solution landscapes efficiently, classical simulated annealing remains competitive due to current quantum hardware limitations in scale and precision. This study provides insights into the potential and limitations of annealing-based approaches for scheduling problems, offering guidance for future research and industrial applications in optimization-driven manufacturing.
