Overload-Checking and Edge-Finding for Robust Cumulative Scheduling
针对资源中断等扰动下仍保持有效的鲁棒累积调度问题，提出了两种新的过滤算法，分别基于过载检查和边缘查找规则，并证明了其复杂度与现有算法相当，实验验证了其可扩展性和有效性。
Scheduling frameworks are not necessarily stable. The aim is to introduce schedules resistant to disruptions such as when resources become unavailable, the supply chain for them breaks down, etc. A schedule is robust if it absorbs some level of unforeseen events when at most a certain number of activities are delayed. Taking advantage of constraint programming, we present two new filtering algorithms for a constraint that models cumulative scheduling problems in robust contexts where up to [Formula: see text] out of [Formula: see text] tasks can be concurrently delayed while keeping the schedule valid. We adapt the overload-checking and edge-finding filtering rules for this framework. We show that our robust versions of these algorithms run in [Formula: see text] and [Formula: see text], respectively, where [Formula: see text] denotes the number of distinct capacities of all tasks. This achievement implies that the complexities of the state-of-the-art algorithms for these techniques are invariable when [Formula: see text] is constant. Experiments illustrate that our algorithms scale, with respect to [Formula: see text] and [Formula: see text]. As a practical application, the experimental results on a special case of crane assignment problem also verify a stronger filtering for these methods in terms of backtrack numbers as well as computation times when used in conjunction with time tabling. Finally, in order to show that our CP-based algorithms improve to solve a robust scheduling problem, we make a comparison against temporal protection as an external robust scheduling approach. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: H. Fahimi received funding from Shahid Chamran University of Ahvaz with [Grant number SCU.MC1402.44132]. C.-G. Quimper was funded by a NSERC Discovery Grant from Canada. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0138 .