Solving the resource constrained project scheduling problem with quantum annealing

Pérez Armas, Luis Fernando; Creemers, Stefan; Deleplanque, Samuel

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1038/s41598-024-67168-6

Title :

Solving the resource constrained project scheduling problem with quantum annealing

Author(s) :

Pérez Armas, Luis Fernando [Auteur]
Lille économie management - UMR 9221 [LEM]
Creemers, Stefan [Auteur]

Lille économie management - UMR 9221 [LEM]
Deleplanque, Samuel [Auteur]
Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 [IEMN]
JUNIA [JUNIA]
Acoustique - IEMN [ACOUSTIQUE - IEMN]

Journal title :

Scientific Reports

Pages :

16784

Publisher :

Nature Publishing Group

Publication date :

2024-07-22

ISSN :

2045-2322

English keyword(s) :

Resource constrained project scheduling problem
Quantum optimization
Quantum annealing

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing ...
Show more >Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.Show less >

Language :

Anglais

Popular science :

Non

Collections :

Lille Économie Management (LEM) - UMR 9221

Source :

Harvested from HAL

Files

document
Open access
Access the document

s41598-024-67168-6.pdf
Open access
Access the document

Solving the resource constrained project ... BibTeX CSV Excel RIS

Files

Solving the resource constrained project ...

BibTeX

CSV

Excel

RIS