O. Ősz, M. Hegyháti
The S-graph framework is a combinatorial approach for batch process scheduling. It utilizes a branch-and-bound algorithm to find the optimal schedule. While this determines the general frame of the search, there are several parts in the algorithm that can be carried out in many different ways: how to choose the next node of the search, what scheduling decisions should be made to branch out from a node, how to calculate the bound, and when to use what heuristic to find an incumbent solution. This study examines some of the possibilities regarding these options. One investigated approach uses a more complex bound calculation to obtain a tighter bound. Due to the tradeoff between the quality and computational need of the bound, this bounding function should not be used at every node, only at strategic points of the search, offering even more fine-tuning options. Another approach that was investigated is to guide the search by prioritizing assignment decisions over sequencing decisions. The effects of these improvement approaches were demonstrated by computational tests on literature problems and randomly generated instances.
Keywords: scheduling, combinatorial optimization, branch-and-bound
Scheduled
TC1 Scheduling 2
June 10, 2021 12:30 PM
1 - GB Dantzig
