Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic
This paper presents a scalable Model Predictive Control (MPC) algorithm for task scheduling and real time re-scheduling. The use case motivating the work is given by the problem of managing the integration activities involved in the final assembly of the Vega rocket at the European space center in K...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10843846/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832586875725938688 |
|---|---|
| author | Francesco Liberati Manuel Donsante Chiara Maria Francesca Cirino Andrea Tortorelli |
| author_facet | Francesco Liberati Manuel Donsante Chiara Maria Francesca Cirino Andrea Tortorelli |
| author_sort | Francesco Liberati |
| collection | DOAJ |
| description | This paper presents a scalable Model Predictive Control (MPC) algorithm for task scheduling and real time re-scheduling. The use case motivating the work is given by the problem of managing the integration activities involved in the final assembly of the Vega rocket at the European space center in Kourou, French Guiana. There are two main objectives. The algorithm shall suggest to the planning operators an optimized scheduling of the activities, i.e., one which minimizes the total completion time (the makespan), while satisfying all the applicable constraints. In addition, the algorithm shall provide in real time an update of the planning, in case some unforeseen events require a re-scheduling of the activities. While a standard application of mixed-integer optimization would not be feasible in practice due to the combinatorial complexity of the problem, the scalable MPC algorithm proposed in this paper retains all the flexibility and modelling power of optimization-based techniques, and is almost as fast as the state of the art scheduling heuristics, which in real scenarios can provide a sub-optimal solution in few seconds, or less. Extensive simulations on randomly generated realistic scenarios are carried out to validate the proposed approach. On average, the proposed MPC algorithm decreased by nearly 2% the makespan, compared to a state of the art scheduling heuristic, while having a comparable solving time, in the order of milliseconds, and while retaining (contrary to heuristics) all the flexibility and modelling power of the optimization based approaches (which took several hours to run on the test scenarios). |
| format | Article |
| id | doaj-art-92f41beb0f5045f7bc1540b522ca0772 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-92f41beb0f5045f7bc1540b522ca07722025-01-25T00:01:36ZengIEEEIEEE Access2169-35362025-01-0113144991451510.1109/ACCESS.2025.352990910843846Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based HeuristicFrancesco Liberati0https://orcid.org/0000-0001-9170-2304Manuel Donsante1https://orcid.org/0009-0009-8632-2716Chiara Maria Francesca Cirino2Andrea Tortorelli3https://orcid.org/0000-0002-7908-7035Dipartimento di Ingegneria Informatica, Automatica e Gestionale “Antonio Ruberti” (DIAG), Sapienza University of Rome, Rome, ItalyDipartimento di Ingegneria Informatica, Automatica e Gestionale “Antonio Ruberti” (DIAG), Sapienza University of Rome, Rome, ItalyDipartimento di Ingegneria Informatica, Automatica e Gestionale “Antonio Ruberti” (DIAG), Sapienza University of Rome, Rome, ItalyDipartimento di Scienze Teoriche e Applicate (DiSTA), eCampus University, Novedrate, ItalyThis paper presents a scalable Model Predictive Control (MPC) algorithm for task scheduling and real time re-scheduling. The use case motivating the work is given by the problem of managing the integration activities involved in the final assembly of the Vega rocket at the European space center in Kourou, French Guiana. There are two main objectives. The algorithm shall suggest to the planning operators an optimized scheduling of the activities, i.e., one which minimizes the total completion time (the makespan), while satisfying all the applicable constraints. In addition, the algorithm shall provide in real time an update of the planning, in case some unforeseen events require a re-scheduling of the activities. While a standard application of mixed-integer optimization would not be feasible in practice due to the combinatorial complexity of the problem, the scalable MPC algorithm proposed in this paper retains all the flexibility and modelling power of optimization-based techniques, and is almost as fast as the state of the art scheduling heuristics, which in real scenarios can provide a sub-optimal solution in few seconds, or less. Extensive simulations on randomly generated realistic scenarios are carried out to validate the proposed approach. On average, the proposed MPC algorithm decreased by nearly 2% the makespan, compared to a state of the art scheduling heuristic, while having a comparable solving time, in the order of milliseconds, and while retaining (contrary to heuristics) all the flexibility and modelling power of the optimization based approaches (which took several hours to run on the test scenarios).https://ieeexplore.ieee.org/document/10843846/Task schedulingassembly linesmakespan reductionmodel predictive controlglobal optimizationmixed-integer programming |
| spellingShingle | Francesco Liberati Manuel Donsante Chiara Maria Francesca Cirino Andrea Tortorelli Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic IEEE Access Task scheduling assembly lines makespan reduction model predictive control global optimization mixed-integer programming |
| title | Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic |
| title_full | Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic |
| title_fullStr | Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic |
| title_full_unstemmed | Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic |
| title_short | Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic |
| title_sort | fast task scheduling with model predictive control integrating a priority based heuristic |
| topic | Task scheduling assembly lines makespan reduction model predictive control global optimization mixed-integer programming |
| url | https://ieeexplore.ieee.org/document/10843846/ |
| work_keys_str_mv | AT francescoliberati fasttaskschedulingwithmodelpredictivecontrolintegratingaprioritybasedheuristic AT manueldonsante fasttaskschedulingwithmodelpredictivecontrolintegratingaprioritybasedheuristic AT chiaramariafrancescacirino fasttaskschedulingwithmodelpredictivecontrolintegratingaprioritybasedheuristic AT andreatortorelli fasttaskschedulingwithmodelpredictivecontrolintegratingaprioritybasedheuristic |