Efficient Precedence-Based Multistage Batch Scheduling Formulation with Nontrivial Tightening Constraints

An efficient continuous-time precedence-based formulation is proposed to address scheduling problems in multistage multiproduct batch plants. The approach is based on the concept of unit-dependent general precedence, which requires sequencing binary variables to be defined for each pair of distinct batches and potentially shared unit. Despite big-M constraints are still needed, this sequencing scheme allows to introduce several nontrivial tightening constraints to make the feasible region more compact. The new constraints can be interpreted either as valid relations between allocation and sequencing decisions or as valid estimations of process variables, such as the starting times, the completion times, and the makespan. As other precedence-based methodologies, sequence-dependent changeovers are handled. The proposed model is based on the underlying idea that the relaxed value of binary variables, even if somewhere between 0 and 1, can he regarded as a decision partially made. The information available on the allocation and sequencing variables is used to generate better lower and upper bounds that tighten the feasible space in order to accelerate the solution process. The proposed approach is applied to three large multistage examples with a remarkable computational efficiency.