Production scheduling with capacity‐constrained transportation activities

This article presents a model for scheduling activities that are required to manufacture a product batch in a multistage process. The activities include setups, operations, and load movements between operations. In this model, setups may or may not require a unit from the preceding operation; each operation must be performed continuously on the batch once it has started, and capacity constraints apply to transportation activities. Within this context, two productivity‐related objectives are sought. The primary objective is to minimize the total production time for the batch; the secondary is to minimize the number of load movements. Considering the capacity constraints, a maximum number of units per load is specified for each “vehicle” and one vehicle is dedicated to each transportation activity. The simplicity of the vehicle restriction facilitates the examination of scheduling interactions among activities, and the results of the research into this model may serve as a foundation for treating more general representations of capacity constraints. The model is used to investigate the scheduling implications of capacity‐constrained load movements. It brings into focus interactions between these movements and the other activities in the process. After each operation, units must be grouped and moved in the fewest loads that permit the succeeding operation to begin as soon as possible, while observing setup and continuity requirements for this operation. Further, the departure times of loads depend on the availability of units and the vehicle. The formation of loads that must conform with the vehicle's capacity limit affects the times at which the loads are ready for movement, while the scheduling of previous movements from the operation affects the times at which the vehicle is available. A procedure is developed for scheduling activities that have this complex set of interactions. Computational requirements on test problems indicate that practical‐sized applications can be handled with this procedure. These applications would be designed to assist in making production planning decisions by experimenting with factors such as vehicle capacity limits and sequencing of operations to determine their effect on production time requirements and numbers of load movements. The article develops a branch‐and‐bound routine to solve subproblems of scheduling transportation activities. The efficiency of this routine that results from exploiting the specific structure of the subproblems is critical for the success of the overall procedure. While the subproblems can be solved as zero‐one mixed‐integer programs, this approach is too computationally burdensome for all but the smallest of problems.