An Efficient Filtering Algorithm for the Unary Resource Constraint with Transition Times and Optional Activities

Sascha Cauwelaert (), Cyrille Dejemeppe () and Pierre Schaus ()
Additional contact information
Sascha Cauwelaert: UCLouvain
Cyrille Dejemeppe: n-Side
Pierre Schaus: UCLouvain

Journal of Scheduling, 2020, vol. 23, issue 4, No 2, 449 pages

Abstract: Abstract This paper describes a unified global constraint to model scheduling problems with unary resources, i.e., each resource can process only a single activity at a time. In addition, the constraint enforces sequence-dependent transition times between activities. It often happens that activities are grouped into families with zero transition times within a family. Moreover, some of the activities might be optional from the resource viewpoint (typically in the case of alternative resources). The global constraint unifies reasoning with both optional activities and families of activities. The scalable filtering algorithms we discuss keep a low time complexity of $$\mathcal {O}(n \cdot \log (n) \cdot \log (f))$$ O ( n · log ( n ) · log ( f ) ) , where n is the number of tasks on the resource and f is the number of families. This results from the fact that we extend the $$\varTheta $$ Θ -tree data structure used for the Unary Resource constraint without transition times. Our experiments demonstrate that our global constraint strengthens the pruning of domains as compared with existing approaches, leading to important speedups. Moreover, our low time complexity allows maintaining a small overhead, even for large instances. These conclusions are particularly true when optional activities are present in the problem.

Keywords: Constraint programming; scheduling; Global constraint; Unary resource; Transition times; Optional activities; Scalability (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00632-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:23:y:2020:i:4:d:10.1007_s10951-019-00632-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-019-00632-8

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().