Overload-Checking and Edge-Finding for Robust Cumulative Scheduling

Hamed Fahimi () and Claude-Guy Quimper ()
Additional contact information
Hamed Fahimi: Department of Computer Science, Faculty of Mathematical Sciences and Computer, Shahid Chamran University of Ahvaz, Ahvaz 6135783151, Iran
Claude-Guy Quimper: Département d’informatique et de génie logiciel, Faculté des sciences et de génie, Université Laval, Québec G1V 0A6, Canada

INFORMS Journal on Computing, 2023, vol. 35, issue 6, 1419-1438

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 Θ ( r 2 n log ( n ) ) and 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.

Keywords: constraint programming; constraint propagation; filtering algorithms; robust cumulative scheduling; uncertainty; data structure (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.0138 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:6:p:1419-1438

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().