LP-based heuristics for scheduling chemical batch processes

A mixed-integer linear programming (MILP) model for scheduling chemical batch processes is presented. Since computational times are prohibitive for most problems of realistic size, a two-stage solution procedure is suggested. In the first stage, an initial solution is derived by use of an LP-based heuristic. The proposed heuristic defines a time grid that includes only a limited number of feasible periods in which a processing task is allowed to start. Thus, the size of the original multi-period MILP model is reduced in a controlled manner and optimal solutions to the relaxed model are obtained within reasonable computational time. The second stage consists of an improvement step that aims to compress the initial schedule by left-shifting operations over the time-axis. In order to evaluate the applicability of the heuristics a number of numerical experiments were performed. It is shown that near-optimal solutions are obtained for large-size problems with only modest computational effort.