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


TC1 Scheduling 2
June 10, 2021  12:30 PM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.