Filtering Algorithms for Batch Processing with Sequence Dependent Setup Times

Petr Vilím and Roman Barták

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.