Efficient Scheduling of Batch Plants Using Reachability Tree Search for Timed Automata with Lower Bound Computations

In this paper we discuss an extension of a recent approach to solve batch scheduling problems using reachability analysis for timed automata (TA) by embedding lower bound computations in the reachability algorithm. We propose an extension of the embedded LP-formulation to handle scheduling problems with NIS policy and an improved minimum remaining processing time (MRPT) procedure to compute the lower bounds. The proposed bounding procedures are tested on typical batch scheduling problems. The comparative study shows that the MRPT-based bounding procedure is efficient and increases the overall performance significantly in comparison to the LP-based bounding procedure.