Fast Task Scheduling With Model Predictive Control Integrating a Priority-Based Heuristic

作     者：Liberati, Francesco Donsante, Manuel Cirino, Chiara Maria Francesca Tortorelli, Andrea 

作者机构：Sapienza Univ Rome Dipartimento Ingn Informat Automat & Gestionale An I-00185 Rome Italy eCampus Univ Dipartimento Sci Teor & Applicate DiSTA I-22060 Novedrate Italy 

出 版 物：《IEEE ACCESS》 (IEEE Access)

年 卷 期：2025年第13卷

页      面：14499-14515页

核心收录：

基　　金：European Union Energy and Context Aware AI-Enabled Decision Support System for Optimizing Pre and Post Launch Operations (ENAI) Project through the Centre National d'etudes Spatiales (CNES) SAPIENZA-ATENEO 2023 Advanced Predictive and AI-Based Control Algorithms With Application to Logistic Management and eHealth [RM123188F7C85F26] 

主　　题：Task scheduling assembly lines makespan reduction makespan reduction model predictive control model predictive control global optimization global optimization mixed-integer programming mixed-integer programming scheduling heuristic scheduling heuristic greatest rank positional weight greatest rank positional weight greatest rank positional weight 

摘      要：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).