A continuous-time tightened formulation for single-stage batch scheduling with sequence dependent changeovers

Abstract

This work presents a new mixed-integer linear programming (MILP) continuous-time approach for the shortterm scheduling of single-stage multiproduct batch plants with parallel units and sequence-dependent changeovers. It uses a unit-specific precedence-based representation, combined with effective, nontrivial tightening constraints, to develop a very efficient problem formulation. The additional cuts account for the updated information provided by allocation and sequencing binary variables to systematically reduce the solution space of the corresponding LP at every node of the enumeration tree. In this way, close bounds for key variables like makespan, task earliness, and task starting/completion times are generated and continually improved throughout the search in order to accelerate the node pruning process. Alternative problem objectives like the minimum total earliness or the shortest makespan can be managed. To make a thorough comparison with previous continuous-time scheduling approaches, several benchmark examples have been solved. Results show that the proposed approach usually presents the best computational performance.