An effective lower bound on Lmax in a worker‐constrained job shop

An effective lower bound on Lmax in a worker‐constrained job shop

0.00 Avg rating0 Votes
Article ID: iaor20125438
Volume: 40
Issue: 1
Start Page Number: 328
End Page Number: 343
Publication Date: Jan 2013
Journal: Computers and Operations Research
Authors: , , , ,
Keywords: combinatorial optimization, scheduling, networks: flow, heuristics
Abstract:

A common industrial operation is a dual resource constrained job shop where: (a) the objective is to minimize L max equ1, the maximum job lateness; (b) machines are organized into groups; and (c) each worker is assigned to a specific machine group. Because this problem is NP‐hard, finding optimal solutions by enumeration is impractical. This paper details a procedure to compute a lower bound on L max equ2 that will be used in follow‐up work to effectively evaluate the absolute performance of heuristic solutions. Given an allocation of workers to machine groups, a lower bound on L max equ3 is first computed for each machine group using a network‐flow formulation. The lower bound on L max equ4 for the job shop is the largest of the lower bounds for the machine groups. A search algorithm then finds a worker allocation yielding the smallest such lower bound on L max equ5 for the job shop; and the latter quantity is our proposed lower bound on L max equ6. Given a worker allocation, we use the Virtual Factory (a heuristic scheduler developed by Hodgson et al. in 1998) to generate a schedule. Experiments with a wide variety of job shops indicated that the proposed lower bound on L max equ7 could often be achieved by a Virtual Factory schedule based on the worker allocation yielding this lower bound. However, there were problem instances for which other worker allocations enabled the Virtual Factory to generate better schedules. Follow‐up work provides optimality criteria, and heuristics to find improved allocations if these criteria are not satisfied.

Reviews

Required fields are marked *. Your email address will not be published.