Flexible job-shop scheduling problems (FJSPs) represent one of the most complex combinatorial optimization challenges. Modern production systems and control processes demand rapid decision-making in scheduling. To address this challenge, we propose a quantum computing approach for solving FJSPs. We propose a quadratic unconstrained binary optimization (QUBO) model to minimize the makespan of FJSPs, with the scheduling scheme encoded in the ground state of the Hamiltonian operator. The model is solved using a coherent Ising machine (CIM). Numerical experiments are conducted to evaluate and validate the performance and effectiveness of the CIM. The results demonstrate that quantum computing holds significant potential for solving FJSPs more efficiently than traditional computational methods.
Flexible job-shop scheduling problems (FJSPs) represent one of the most complex combinatorial optimization challenges. Modern production systems and control processes demand rapid decision-making in scheduling. To address this challenge, we propose a quantum computing approach for solving FJSPs. We propose a quadratic unconstrained binary optimization (QUBO) model to minimize the makespan of FJSPs, with the scheduling scheme encoded in the ground state of the Hamiltonian operator. The model is solved using a coherent Ising machine (CIM). Numerical experiments are conducted to evaluate and validate the performance and effectiveness of the CIM. The results demonstrate that quantum computing holds significant potential for solving FJSPs more efficiently than traditional computational methods.
Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.
Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.
Flexible Job Shop Scheduling is one of the most difficult optimization problems known. In addition, modern production planning and control strategies require continuous and process-parallel optimization of machine allocation and processing sequences. Therefore, this paper presents a new method for process parallel Flexible Job Shop Scheduling using the concept of quantum computing based optimization. A scientific benchmark and the application to a realistic use-case demonstrates the good performance and practicability of this new approach. A managerial insight shows how the approach for process parallel flexible job shop scheduling can be integrated in existing production planning and control IT-infrastructure.
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.
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.