Overload-Checking and Edge-Finding for Robust Cumulative Scheduling
Hamed Fahimi, Claude-Guy Quimper
INFORMS Journal on Computing · 2023 · Volume 35 · Issue 6
Abstract
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 𝑟 r out of 𝑛 n 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 Θ ( 𝑟 2 𝑛 l o g ( 𝑛 ) ) Θ ( r 2 n log ( n ) ) and 𝑂 ( 𝑟 2 𝑧 𝑛 l o g ( 𝑛 ) ) O ( r 2 z n log ( n ) ) , respectively, where 𝑧 z 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 𝑟 r is constant. Experiments illustrate that our algorithms scale, with respect to 𝑛 n and 𝑟 r . 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 .
Keywords
constraint programming, constraint propagation, filtering algorithms, robust cumulative scheduling, uncertainty, data structure
Enable JavaScript for citation tools and additional paper interactions.