Quantum computing (QC) holds great promise to open up a new era of computing and has been receiving significant attention recently. To overcome the performance limitations of near-term QC, utilizing the current quantum computers to complement classical techniques for solving real-world problems is of utmost importance. In this paper, we develop QC-based solution strategies that exploit quantum annealing and classical optimization techniques for solving large-scale scheduling problems in manufacturing systems. The applications of the proposed algorithms are illustrated through two case studies in production scheduling. First, we present a hybrid QC-based solution approach for the job-shop scheduling problem. Second, we propose a hybrid QC-based parametric method for the multi-purpose batch scheduling problem with a fractional objective. The proposed hybrid algorithms can tackle optimization problems formulated as mixed-integer linear and mixed-integer fractional programs, respectively, and provide feasibility guarantees. Performance comparison between state-of-the-art exact and heuristic solvers and the proposed QC-based hybrid solution techniques is presented for both job-shop and batch scheduling problems. Unlike conventional classical solution techniques, the proposed hybrid frameworks harness quantum annealing to supplement established deterministic optimization algorithms and demonstrate performance efficiency over standard off-the-shelf optimization solvers.
Quantum computing (QC) holds great promise to open up a new era of computing and has been receiving significant attention recently. To overcome the performance limitations of near-term QC, utilizing the current quantum computers to complement classical techniques for solving real-world problems is of utmost importance. In this paper, we develop QC-based solution strategies that exploit quantum annealing and classical optimization techniques for solving large-scale scheduling problems in manufacturing systems. The applications of the proposed algorithms are illustrated through two case studies in production scheduling. First, we present a hybrid QC-based solution approach for the job-shop scheduling problem. Second, we propose a hybrid QC-based parametric method for the multi-purpose batch scheduling problem with a fractional objective. The proposed hybrid algorithms can tackle optimization problems formulated as mixed-integer linear and mixed-integer fractional programs, respectively, and provide feasibility guarantees. Performance comparison between state-of-the-art exact and heuristic solvers and the proposed QC-based hybrid solution techniques is presented for both job-shop and batch scheduling problems. Unlike conventional classical solution techniques, the proposed hybrid frameworks harness quantum annealing to supplement established deterministic optimization algorithms and demonstrate performance efficiency over standard off-the-shelf optimization solvers.
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.
Abstract The advent of quantum computing has introduced transformative potential for solving complex optimization problems, particularly in the field of manufacturing. This paper presents the Quantum-Adaptive Flex Scheduler (QAFS), a hybrid algorithm that leverages Quantum Annealing (QA) to address the Flexible Job Shop Scheduling Problem (FJSSP) with multiple objectives. QAFS integrates quantum mechanics with traditional heuristic methods to efficiently navigate the vast solution space of FJSSP, overcoming the computational limitations faced by classical algorithms. Our computational study demonstrates that QAFS significantly improves key performance metrics: it reduces makespan by 10–15%, enhances workload distribution by 5–10%, and achieves priority adherence 10–20% more effectively than Classical Scheduling Algorithms (CSA). Moreover, QAFS achieves superior solution quality, attaining an 85% C-metric coverage and a HyperVolume Ratio (HVR) of 0.92, underscoring its capability to generate Pareto-efficient solutions in multi-objective scenarios. These findings highlight the practical potential of QAFS to revolutionize production planning and control in manufacturing, offering a scalable and adaptive solution that responds effectively to real-time constraints and fluctuating market demands.
This work is a benchmark study for quantum-classical computing method with a real-world optimization problem from industry. The problem involves scheduling and balancing jobs on different machines, with a non-linear objective function. We first present the motivation and the problem description, along with different modeling techniques for classical and quantum computing. The modeling for classical solvers has been done as a mixed-integer convex program, while for the quantum-classical solver we model the problem as a binary quadratic program, which is best suited to the D-Wave Leap's Hybrid Solver. This ensures that all the solvers we use are fetched with dedicated and most suitable model(s). Henceforth, we carry out benchmarking and comparisons between classical and quantum-classical methods, on problem sizes ranging till approximately 150,000 variables. We utilize an industry grade classical solver and compare its results with D-Wave Leap's Hybrid Solver. The results we obtain from D-Wave are highly competitive and sometimes offer speedups, compared to the classical solver.
Abstract Quantum Annealing (QA) is a metaheuristic for solving optimization problems in a time-efficient manner. Therefore, quantum mechanical effects are used to compute and evaluate many possible solutions of an optimization problem simultaneously. Recent studies have shown the potential of QA for solving such complex assignment problems within milliseconds. This also applies for the field of job shop scheduling, where the existing approaches however focus on small problem sizes. To assess the full potential of QA in this area for industry-scale problem formulations, it is necessary to consider larger problem instances and to evaluate the potentials of computing these job shop scheduling problems while finding a near-optimal solution in a time-efficient manner. Consequently, this paper presents a QA-based job shop scheduling. In particular, flexible job shop scheduling problems in various sizes are computed with QA, demonstrating the efficiency of the approach regarding scalability, solutions quality, and computing time. For the evaluation of the proposed approach, the solutions are compared in a scientific benchmark with state-of-the-art algorithms for solving flexible job shop scheduling problems. The results indicate that QA has the potential for solving flexible job shop scheduling problems in a time efficient manner. Even large problem instances can be computed within seconds, which offers the possibility for application in industry.
Flexible Job Shop Scheduling (FJSSP) is a challenging optimization problem with multiple conflicting objectives used to model and compute real-world process scheduling tasks. In order for a manufacturing system to remain competitive, it is necessary to compute such optimization problems quickly and efficiently. The limitations of conventional optimization methods frequently stem from a delicate balance between solution quality and computation time. Consequently, a pressing need for solution algorithms arises that can effectively transcend these limitations. This paper presents a novel Quantum Annealing-based solving algorithm (QASA) for computing FJSSP, leveraging the power of Quantum Annealing combined with classical techniques. The proposed approach aims to optimize a multi-criterial FJSSP considering makespan, total workload, and job priority simultaneously. QASA employs a Hamiltonian formulation with Lagrange parameters to integrate the problem's constraints and objectives. By assigning appropriate weights to the objectives, the method allows the prioritization of certain objectives over others. To handle the computational complexity of large FJSSP instances, the problem is decomposed into smaller subproblems, and a decision logic based on bottleneck factors is employed to select critical jobs for computation combined with variable pruning techniques. To evaluate the effectiveness of the proposed approach, experiments are conducted on benchmark problems, considering makespan, total workload, and priority objectives. Therefore, QASA combining tabu search, simulated annealing, and Quantum Annealing is used for efficient computation and is compared with a classical solving algorithm (CSA) combining tabu search and simulated annealing. The results demonstrate that QASA outperforms CSA in terms of solution quality, as measured by set coverage and hypervolume ratio metrics. Furthermore, computational efficiency analysis reveals that QASA achieves superior Pareto solutions compared to the classical approach, with a reasonable increase in computation time.
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.