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

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))\), 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.