Solving the resource constrained project scheduling problem with quantum annealing
- Others:
- Lille économie management - UMR 9221 (LEM) ; Université d'Artois (UA)-Université catholique de Lille (UCL)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
- Acoustique - IEMN (ACOUSTIQUE - IEMN) ; Institut d'Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN) ; Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-JUNIA (JUNIA) ; Université catholique de Lille (UCL)-Université catholique de Lille (UCL)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-JUNIA (JUNIA) ; Université catholique de Lille (UCL)-Université catholique de Lille (UCL)
- JUNIA (JUNIA) ; Université catholique de Lille (UCL)
- Institut d'Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN) ; Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-JUNIA (JUNIA) ; Université catholique de Lille (UCL)-Université catholique de Lille (UCL)
Description
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.
Abstract
International audience
Additional details
- URL
- https://hal.science/hal-04659116
- URN
- urn:oai:HAL:hal-04659116v2
- Origin repository
- UNICA