Evaluating the job shop scheduling problem on a D-wave quantum annealer

Area of Science:

• Operations Research
• Quantum Computing
• Computational Optimization

Background:

• Job Shop Scheduling (JSS) is a critical combinatorial optimization problem in production, often intractable for classical computers due to its complexity.
• Quantum Annealing (QA) presents a novel computational paradigm with potential for enhanced scalability and solution quality in optimization tasks.

Purpose of the Study:

• To investigate the application of Quantum Annealing for solving the Job Shop Scheduling problem.
• To compare the performance of QA with classical solvers and identify practical challenges in its implementation.

Main Methods:

• Formulation of the JSS problem for Quantum Annealer.
• Fine-tuning of the quantum annealer parameters.
• Evaluation of solution quality against classical solvers.
• Analysis of computational overhead, qubit requirements, and chain break mitigation strategies.
• Exploration of advanced techniques like reverse annealing.

Main Results:

• Quantum Annealing demonstrates potential for JSS but faces significant challenges in problem representation and hardware limitations.
• Overlooked aspects like computational cost, qubit requirements, and chain breaks critically impact performance.
• Advanced tools such as reverse annealing show effectiveness but require further research.

Conclusions:

• The study identifies key research questions and areas for improvement in applying Quantum Annealing to Job Shop Scheduling.
• Further development is needed to overcome current limitations and fully leverage QA's potential for complex scheduling tasks.