A practical method for evaluating worker allocations in large-scale dual resource constrained job shops

In two recent articles, Lobo et al. present algorithms for allocating workers to machine groups in a Dual Resource Constrained (DRC) job shop so as to minimize L-max, the maximum job lateness. Procedure LBSA delivers an effective lower bound on L-max, while the heuristic HSP delivers an allocation whose associated schedule has a (usually) near-optimal L-max value. To evaluate an HSP-based allocation's quality in a given DRC job shop, the authors first compute the gap between HSP's associated L-max value and LBSA's lower bound. Next they refer this gap to the distribution of a quasi-optimality gap that is generated as follows: (i) independent simulation replications of the given job shop are obtained by randomly sampling each job's characteristics; and (ii) for each replication, the associated quasi-optimality gap is computed by enumerating all feasible allocations. Because step (ii) is computationally intractable in large-scale problems, this follow-up article formulates a revised step (ii) wherein each simulation invokes HSP2, an improved version of HSP, to yield an approximation to the quasi-optimality gap. Based on comprehensive experimentation, it is concluded that the HSP2-based distribution did not differ significantly from its enumeration-based counterpart; and the revised evaluation method was computationally tractable in practice. Two examples illustrate the use of the revised method.