Scheduling parallel production lines with resource constraints. 2. Decomposition algorithm

In the preceding paper, we presented a mixed-integer linear programming model (MILP) for scheduling operation in a multiproduct facility comprising multiple parallel semicontinuous production lines. In this part, we first perform a critical analysis of the model structure and its various constraints and the various solver options. Because, even after that effort, the model remains computationally expensive for large-scale industrial applications, we use it to develop an efficient two-step decomposition algorithm. The main idea behind this algorithm is to first generate several good, feasible item combinations by repeatedly solving the model with a minimum number of slots and then to compose a schedule using these item combinations. A computationally easier new model for sequencing and scheduling item combinations is derived from the original model. When applied to an industrial problem from a detergent plant, the new algorithm gives near-optimal solutions in far less time than the original model.