EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3856. Quantum annealing approach for scheduling a job shop with availability constraints

Invited abstract in session MB-42: Decomposition methods for Quantum Optimization, stream Quantum Computing Optimization.

Monday, 10:30-12:00
Room: 98 (building: 306)

Authors (first author is the speaker)

1. Riad Aggoune
Luxembourg Institute of Science and Technology
2. Samuel Deleplanque
Univ. Lille, CNRS, Centrale Lille, Junia, Univ. Polytechnique Hauts-de-France, UMR 8520 - IEMN - Lille, France

Abstract

Quantum optimization represents a rapidly evolving domain of research. It involves leveraging quantum computing systems and algorithms to address NP-hard problems. It generally requires the modeling of these problems in the form of Quadratic Unconstrained Binary Optimization (QUBO) models. The limitations of current quantum computers, particularly in terms of number of available qubits and their ability to handle variables, make it significantly challenging to develop optimization models that accurately reflect real-world constraints.
In this paper, we consider the job shop scheduling problem subject to machine availability constraints. We propose a quantum annealing solution adaptable to both scenarios where machine unavailability periods are predetermined and when they are variable. It is based on a mathematical representation of the job shop scheduling problem formulated as a QUBO model [1]. The latter is derived from the first quantum annealing solution targeting the minimization of the makespan, introduced in [2].

[1] Aggoune, R. and S. Deleplanque. A Quantum Annealing Solution to the Job Shop Scheduling Problem. ICCSA 2023. Lecture Notes in Computer Science, vol 14104. Springer. https ://doi.org/10.1007/978-3-031-37105-928

[2] Venturelli, D. and Marchand, D. J. and Rojo, G. Quantum annealing implementation of job-shop scheduling. arXiv preprint :1506.08479, 2015.

Keywords

Status: accepted

Back to the list of papers