Scheduling parallel assembly workstations to minimize a shared pool of labor

The problem of scheduling jobs on several identical parallel assembly workstations that constitute a production facility and share a common pool of labor within a factory environment is discussed. Labor requirements vary on each workstation depending upon the job being processed, and the workstation is paced so as to maintain a constant cycle time. The labor needed at any point in time is the sum of the labor requirements over all workstations at that instant. The workforce size is defined as the maximum level of labor required at any point during the schedule. A two-stage approach is proposed to find a schedule that minimizes workforce size: the first stage is a mixed integer linear programming model that determines starting times, and the second is a polynomial-time procedure to assign jobs to specific assembly workstations. Moreover, it is shown that the two stages yield decisions that are jointly optimal for an integrated model that determines starting times and assignments simultaneously. A heuristic procedure is then proposed for scheduling jobs such that each job is assigned a starting time according to the effect on current workforce profile, a strategy described as resource fit. A lower bound on the maximum workforce size is given by the average workforce requirement over the planning horizon. The numerical performance of both the integer programming model and the heuristics are tested on two sets of problems. Tradeoffs between the total workforce and deadline for makespan suggested by this type of scheduling problem are discussed.