Filtering Algorithms for Batch Processing with Sequence Dependent Setup Times

Proceedings Of The Sixth International Conference On Artificial Intelligence Planning And Scheduling

Volume

Proceedings Of The Sixth International Conference On Artificial Intelligence Planning And Scheduling

Contents

Domain filtering is a powerful technique for reduction of the search space during solving combinatorial problems like scheduling. In this paper we present several filtering algorithms designed specifically for scheduling in batch processing environments with sequence dependent setup times. We extend two known algorithms, namely edge finding and not-first/not-last technique, and we present a new filtering algorithm called not-before/not-after. Each of these algorithms removes some inconsistencies that are not detected by the other two algorithms. Thus, all the algorithms are assumed to run together to achieve better pruning.