Resource-Constrained Scheduling of Parallel Production Lines Using Asynchronous Slots

Abstract

Many semicontinuous plants use several production lines and shared resources to make multiple products for various due dates. Short-term scheduling of such plants with sequence-dependent transitions, minimum campaign lengths, inventory costs, safety stock penalties, and backorder penalties has not been addressed so far in the literature. In this paper, we propose a novel approach that models the continuous-time domains of parallel lines using slots that are asynchronous across lines and have variable lengths. Furthermore, it employs carefully selected "checkpoints" to ensure the validity of resource constraints at all times. Using this strategy, we develop and evaluate four alternate mixed-integer linear programming formulations for this difficult resource-constrained scheduling problem. Unlike an existing approach using synchronized slots on all lines to preclude usage violations of shared resources, the proposed strategy reduces binary variables significantly and improves computational efficiency considerably on several test problems. Our work confirms that the use of continuous transition variables and their exact linearizations yields superior formulations. Finally, of our four models, the one with the fewest binary variables appears to be the best.