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 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.
Quantum-inspired optimization (QIO) has emerged as a promising paradigm for solving complex combinatorial problems in industrial scheduling. While most existing studies focus on algorithmic developments and classical implementations, recent advances in nanoscale computing, including memristor-based Ising machines, photonic computing systems, and oscillatory neural networks, have created new opportunities for implementing QUBO- and Ising-based optimization through physical hardware dynamics. This survey provides a comprehensive review of QIO techniques for industrial scheduling, with a particular emphasis on their compatibility with emerging nanoscale computing platforms. We first introduce how representative scheduling problems, including job shop, flexible job shop, and resource-constrained scheduling, can be reformulated into quadratic unconstrained binary optimization (QUBO) models. We then categorize QIO methods into annealing- and Ising-based methods, evolutionary and population-based methods, hybrid quantum-classical and decomposition methods, and emerging learning-augmented approaches, and examine their computational characteristics and compatibility with QUBO or Ising hardware. Beyond algorithmic perspectives, this work highlights the potential role of specialized Ising hardware in enabling highly parallel and potentially energy-efficient optimization. We discuss how QUBO and Ising formulations can be mapped to physical energy-minimization processes in nanoscale devices, thereby providing a computational framework that connects classical optimization, quantum-inspired algorithms, and nanoscale hardware systems. Finally, we identify key challenges, including scalability, penalty calibration, and system integration, and outline future research directions toward hybrid quantum-classical computing ecosystems incorporating nanoscale optimization hardware. This survey positions QIO as a promising paradigm for next-generation intelligent manufacturing, in which optimization algorithms and nanoscale hardware are jointly developed to support low-latency and energy-efficient decision-making.
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.
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.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
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.