A Hybrid Column Generation-Based Heuristic for Solving the Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times

Luis Fernando Pérez Armas (), Samuel Deleplanque, Riad Aggoune and Stefan Creemers ()
Additional contact information
Stefan Creemers: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3335, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: This study explores the application of a hybrid quantum-classical algorithm for solving the parallel machine scheduling problem with sequence-dependent setup 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 for solving the pricing sub-problem. Whereas the pricing sub-problem 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 pricing sub-problem solves a traveling salesman problem that is formulated as a quadratic unconstrained binary optimization 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 to classical solution methods.

Keywords: Quantum Annealing; Hybrid Algorithms; Column Generation; Scheduling (search for similar items in EconPapers)
Pages: 27
Date: 2025-09-01
Note: In: Philosophical Transactions A, 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3335

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().