Optimal Solving of a Scheduling Problem Using Quantum Annealing Metaheuristics on the D-Wave Quantum Solver

• Published in: IEEE transactions on systems, man, and cybernetics. Systems man, and cybernetics. Systems, 2025-01, Vol.55 (1), p.196-208
• Main Authors: Bozejko, Wojciech, Klempous, Ryszard, Pempera, Jaroslaw, Rozenblit, Jerzy, Smutnicki, Czeslaw, Uchronski, Mariusz, Wodecki, Mieczyslaw
• Format: Article
• Language: English
• Subjects: Annealing; Companies; Computers; Costs; Exact algorithm; Linear programming; Logic gates; Processor scheduling; Quantum annealing; Quantum computing; scheduling; Single machine scheduling
• ISSN: 2168-2216; 2168-2232
• DOI: 10.1109/TSMC.2024.3458873

Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.