IEEE International Symposium on Computational Intelligence and Informatics (CINTI)
Hybrid Quantum Approximate Algorithms for Solving Flow Shop Scheduling Problem
Wojciech Bożejko, Radosław Marcin Idzikowski, Dariusz Jagielski, Ryszard Klempous, Sergii Trotskyi, Mateusz Tykierko, Mariusz Uchroński, Mieczysław Wodecki
There is currently a large gap between the theoretical advantages of quantum computing and the practical use of quantum computers. This is due to the small number of qubits currently available. Rapid technological progress allows us to assume that in the near future, it will be possible to solve problems that are currently a challenge for algorithms running on classical computers. Using the example of an NP-hard flow problem, we present the application of the Qiskit optimization package performed on an IBM quantum computer. This problem is well-studied in classical computing, important for theoretical and practical reasons. The use of quantum optimization will undoubtedly affect the more efficient use of many resources in management, production, logistics, and medicine (duty plans, classification problems, etc.).
There is currently a large gap between the theoretical advantages of quantum computing and the practical use of quantum computers. This is due to the small number of qubits currently available. Rapid technological progress allows us to assume that in the near future, it will be possible to solve problems that are currently a challenge for algorithms running on classical computers. Using the example of an NP-hard flow problem, we present the application of the Qiskit optimization package performed on an IBM quantum computer. This problem is well-studied in classical computing, important for theoretical and practical reasons. The use of quantum optimization will undoubtedly affect the more efficient use of many resources in management, production, logistics, and medicine (duty plans, classification problems, etc.).
In recent years, quantum computing has emerged as a rapidly advancing interdisciplinary field, attracting growing attention from both academia and industry owing to its fundamentally novel approach to information processing and its potential to achieve computational capabilities beyond the reach of classical systems. This paper presents a structured review of quantum computing approaches applied to scheduling problems, which are among the most challenging NP-hard optimization problems. We first introduce fundamental principles of quantum computing, including gate-based models, quantum annealing, and hybrid frameworks. We then explore how various scheduling problems such as job-shop, flow-shop, and project scheduling-are encoded into quantum models, particularly using QUBO formulations suitable for current quantum devices. Finally, we discuss key limitations such as hardware constraints and model scalability, and we identify research directions to advance quantumenhanced scheduling methods. By grounding theory in empirical case studies and highlighting near-term deployable solutions, this study bridges the gap between quantum algorithm development and practical scheduling demands, offering a roadmap for researchers and practitioners in quantum optimization.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them -- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks: genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximate optimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digital annealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizes both tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealing through the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications to job-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. The consistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallow achievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubit count, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classical heuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic, online scheduling as the field's clearest open problems.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them-- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks:genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximateoptimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digitalannealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizesboth tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealingthrough the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications tojob-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. Theconsistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallowachievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubitcount, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classicalheuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic,online scheduling as the field's clearest open problems.
Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.
Quantum Evolutionary Algorithm(QEA) is a distinctive type of algorithm for optimization currently,and the theoretical basis of QEA is quantum computation.The algorithm takes advantage of intervention and parallelism of quantum bit thoroughly,which enables QEA to solve combinatorial optimization problems.While solving scheduling problems,QEA has defects that it converges slowly and doesn’t use other immature individual.Hybrid Quantum Algorithm(HQA) is formed and it sucks Particle Swarm Optimization algorithm(PSO) and evolutionary computation into QEA.Classical flow shop problem is employed to test the algorithm,and the result shows that the hybrid algorithm overcomes the defects of QEA and it has universality to solve scheduling problems.
Recent advancements in quantum computing technology have heralded a new era of computational capabilities, outpacing classical simulations in solving complex problems. This remarkable progress has sparked a burgeoning interest in quantum algorithms across various sectors, with optimization emerging as a particularly vibrant field of study. A focal point of this field is the development and refinement of optimization algorithms that are suitable for current and emerging capability of quantum computers. These advancements are crucial as they offer practical ways to apply quantum computing to real-world challenges. Among these applications, personnel and task execution scheduling is a compelling use case for quantum computing as applied to solve complex optimization problems critical to business and industrial operations. In this paper, we explore the utilization of quantum computers to address this class of optimization problems. Employing a range of advanced techniques, including a novel method that improves efficiency, our method demonstrates the capability of quantum computing to provide effective solutions for intricate optimization problems. We particularly focus on the application of IBM's 127 -qubit quantum devices to manage scheduling tasks in workforce management, involving 500 to 874 binary decision variables and over 1000 constraints. This exploration serves not only as a proof of concept for the practical applications of quantum computing but also as a testament to its evolving role in solving business-critical optimization challenges.