Effective Batch Scheduling with Sequence-dependent Changeovers Using Reachability Analysis of Timed Automata Combined with Lower Bound Computations

In this contribution we discuss an extension of a recent approach to solve batch scheduling problems using reachability analysis for timed automata (TA) with embedded lower bound computations. We propose two bounding procedures embedded in the reachability algorithm to handle scheduling problems with sequence-dependent changeovers: (i) a MILP formulation (originally proposed by Manne 1960) extended with additional constraints to model setup and changeover operations and (ii) an improved minimum remaining processing time (MRPT) procedure. The efficiency of the proposed bounding procedures is evaluated on job shop problems with sequence-dependent changeovers. The comparative study shows that the MRPT-based bounding procedure is efficient and increases the overall performance significantly in comparison to the MILP-based bounding procedure.