Allocating job-shop manpower to minimize Lmax: Optimality criteria, search heuristics, and probabilistic quality metrics

We address questions raised by Lobo et al. in 2012 regarding the NP-hard problem of finding an optimal allocation of workers to machine groups in a job shop so as to minimize Lmax, the maximum job lateness. Lobo et al. formulated a lower bound on Lmax given a worker allocation, and an algorithm to find an allocation yielding the smallest such lower bound. In this article we establish optimality criteria to verify that a given allocation corresponds to a schedule that yields the minimum value of Lmax. For situations in which the optimality criteria are not satisfied, we present the Heuristic Search Procedure (HSP), which sequentially invokes three distinct search heuristics, the Local Neighborhood Search Strategy (LNSS), Queuing Time Search Strategy 1 (QSS1), and Queuing Time Search Strategy 2 (QSS2), before delivering the best allocation encountered by LNSS, QSS1, and QSS2. HSP is designed to find allocations allowing a heuristic scheduler to generate schedules with a smaller value of Lmax than that achieved via the allocation yielding the final lower bound of Lobo et al. Comprehensive experimentation indicated that HSP delivered significant reductions in Lmax. We also estimate a probability distribution for evaluating the quality (closeness to optimality) of an allocation delivered by a heuristic search procedure such as HSP. This distribution permits assessing the user's confidence that a given allocation will enable the heuristic scheduler to generate its best possible schedule-i.e., the schedule with the heuristic scheduler's smallest achievable Lmax value.