Modeling and Solution of Chemical Batch Scheduling Problems Using Timed Automata

Scheduling problems in the chemical and process industries are frequently tackled by mathematical programs. An alternative approach that has been discussed recently is by reachability analysis of timed automata (TA). The problem entities (units, recipes, etc.) are modeled as sets of TA in a modular fashion. The individual modules are composed to form the complete model of the problem. The schedules are computed using algorithms from the domain of graph theory. The TA-based approach to tackle scheduling problems in chemical batch plants with additional complicated features has not been investigated before.In this work generic and efficient approaches to model scheduling problems in the batch industries with complicated features such as recipes with various intermediate storage policies, changeover procedures and several realistic objective functions using timed automata are presented. Methods to enhance the efficiency of the reachability algorithm by state space reduction techniques are proposed. In addition to this an effective reduction of the search space can be realized by computing lower bounds of the cost-to-go and performing a comparison with the upper bounds. To handle problems with non-intermediate storage policy and with changeovers two schemes to compute lower bounds are proposed: 1) an extended hybrid algorithm that embeds a linear program (LP) in the reachability analysis and 2) a computationally cheap bounding scheme called the minimum remaining processing time (MRPT).Computational experiments on several problem instances demonstrate the performance of the LP-based and the MRPT-based bounding schemes. The comparison of the performance of the two schemes shows that the MRPT-based bounding reduces the space complexity and the time complexity required to obtain the optimal solution and is robust and efficient compared to the LP-based bounding scheme. Experiments on several challenging industrial case-studies exhibit the performance of the proposed modeling approaches and the applicability of the approaches to model industrial scale problems with complicated characteristics. As a generic conclusion, for scheduling problems where problem-specific modifications of the model or the algorithm are often necessary and when feasible solutions are needed quickly or relatively good solutions are needed within reasonable time, the TA-based approach is preferable.