Allocating Manpower to Minimize Lmax in a Job Shop

A dual resource constrained job shop problem with objective of minimizing maximum lateness, Lmax, is considered in which machines are grouped together into machine groups (departments) and each worker is assigned to operate the machines in a specific machine group. A network flow formulation is presented to compute a lower bound on L max for each machine group given a specific allocation of workers, and an optimal search algorithm is described that determines the worker allocation with the optimum lower bound on L max for the entire job shop. The Virtual Factory (a heuristic scheduler developed by Hodgson et al. in 1998) is then used to generate schedules for the job shop for given worker allocations. Extensive experimental results indicated that across the entire due-date range for a particular job shop type and staffing level, there was a nearly constant average difference between the following: (a) the Virtual Factory solution corresponding to the allocation that optimizes the lower bound; and (b) the best Virtual Factory solution over all allocations. Furthermore, this difference was, on average, less than a single expected operation processing time.;We also address a number of questions regarding how to find the best allocation of workers to machine groups (departments) in a job shop such that Lmax is minimized. A set of optimality criteria is formulated by which the allocation that yields the tightest lower bound on L max can be declared optimal; moreover, a methodology is developed to determine a probability distribution for evaluating the quality of an allocation. Finally, three heuristic search strategies are developed to search for allocations that allow schedules to be generated using the Virtual Factory that are better than the schedule associated with the allocation yielding the tightest lower bound on Lmax. The results of comprehensive experimentation indicated that when the heuristic search strategies were used, significant improvements in the L max value were achieved.