A hybrid column generation-based heuristic for solving the parallel machine scheduling problem with sequence-dependent set-up times
- 11 December 2025
- journal article
- Published by The Royal Society in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 383 (2310)
Abstract
This study explores the application of a hybrid quantum-classical algorithm for solving the parallel machine scheduling problem (PMSP) with sequence-dependent set-up times, a pivotal scheduling problem that has applications in multiple industries. Using a column generation-based approach, we propose a heuristic that combines a classical linear relaxation for the master problem with quantum annealing (QA) for solving the pricing subproblem (PSP). Whereas the PSP generates columns (i.e. a sequence of jobs that are assigned to a machine), the master problem selects which columns to use in order to minimize the makespan of the schedule. To generate columns, the PSP solves a travelling salesman problem (TSP) that is formulated as a quadratic unconstrained binary optimization (QUBO) problem. The big advantage thereof is that subtours can be eliminated by use of quadratic terms in the objective function. In addition, our approach also leverages the quantum annealer’s capability to generate many high-quality solutions (i.e. columns) in a very short time. To assess the performance of our hybrid column generation-based heuristic, we perform a computational experiment. The results of this experiment demonstrate the synergy of hybrid methods for tackling complex decision-making problems, achieving competitive high-quality solutions and computational advantages when compared with classical solution methods. This article is part of the theme issue ‘Quantum theory and topology in models of decision making (Part 2)’.Keywords
This publication has 47 references indexed in Scilit:
- Addressing Machine Unavailability in Job Shop Scheduling: A Quantum Computing Approach2024
- Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: a surveyArtificial Intelligence Review, 2022
- Integer Programming Techniques for Minor-Embedding in Quantum Annealers2020
- A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point methodMathematical Programming, 2016
- A case study in programming a quantum annealer for hard operational planning problemsQuantum Information Processing, 2014
- Solving the electricity production planning problem by a column generation based heuristicJournal of Scheduling, 2012
- Heuristic and exact algorithms for a min–max selective vehicle routing problemComputers & Operations Research, 2011
- A simulated annealing approach to makespan minimization on identical parallel machinesThe International Journal of Advanced Manufacturing Technology, 2005
- A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup timesInternational Journal of Production Economics, 1996
- Beweis des AdiabatensatzesThe European Physical Journal A, 1928