Solving the Resource-Constrained Project Scheduling Problem (RCPSP) with Quantum Annealing - Institut d'électronique, de microélectronique et de nanotechnologie Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2024

Solving the Resource-Constrained Project Scheduling Problem (RCPSP) with Quantum Annealing

Résumé

Quantum annealing emerges as a viable solution for solving complex problems such as the resource-constrained project scheduling problem (RCPSP). We analyze 12 Mixed Integer Linear Programming (MILP) formulations for solving the RCPSP, and convert the most qubit-efficient formulation into a Quadratic Unconstrained Binary Optimization (QUBO) model. We solve this QUBO model using the D-Wave Advantage 6.3 Quantum Annealing machine and compare its performance with that of classical computer solvers. This pioneering effort marks the first use of quantum annealing for RCPSP, showing promising results, especially for smaller to medium-sized instances.
Fichier principal
Vignette du fichier
ssrn-4689017.pdf (3.38 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04605491 , version 1 (07-06-2024)

Identifiants

Citer

Luis Fernando Pérez Armas, Stefan Creemers, Samuel Deleplanque. Solving the Resource-Constrained Project Scheduling Problem (RCPSP) with Quantum Annealing. 2024. ⟨hal-04605491⟩
9 Consultations
3 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More