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

Abstract

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 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 ’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 , an improved version of , to yield an approximation to the quasi-optimality gap. Based on comprehensive experimentation, it is concluded that the -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.

Keywords:

• Job shop scheduling
• dual resource constrained system
• worker allocation
• maximum job lateness

Additional information

Notes on contributors

Benjamin J. Lobo

Benjamin J. Lobo is a Research Associate in the Predictive Technology Laboratory (PTL) in the Systems and Information Engineering Department of the University of Virginia. Prior to joining the PTL he worked for 2 years as an Industrial Engineer for the U.S. Army Research Laboratory at Aberdeen Proving Grounds, MD. He received a Ph.D. in Industrial Engineering and a master’s in Operations Research from North Carolina State University. His research interests include scheduling, production planning, and logistics.

James R. Wilson

James R. Wilson is a Professor of the Edward P. Fitts Department of Industrial and Systems Engineering at North Carolina State University. His current research interests are focused on probabilistic and statistical issues in the design and analysis of simulation experiments, with special emphasis on applications in healthcare and production. He is a member of ACM, ASA, and SCS; and he is a Fellow of IIE and INFORMS. His Web page is http://www.ise.ncsu.edu/jwilson.

Kristin A. Thoney

Kristin A. Thoney is an Associate Professor in the Textile and Apparel, Technology and Management Department at North Carolina State University (NCSU). She earned a Ph.D. in Industrial Engineering and Operations Research, as well as an M.S. in Operations Research from NCSU. She also has a B.S. in Mathematics from Valparaiso University. Her research interests include production scheduling, inventory management, logistics, and supply chain modeling.

Thom J. Hodgson

Thom J. Hodgson is a Distinguished University Professor at North Carolina State University. He received a B.S.E., an M.B.A. and a Ph.D., all from the University of Michigan. His research interests include scheduling, logistics, production/inventory control, manufacturing systems, and applied and military OR. He is a Fellow of IIE and INFORMS and a member of the National Academy of Engineering. He is a former Editor-in-Chief (1984–1988) of IIE Transactions. He is a handball player and a former skydiving instructor.

Russell E. King

Russell E. King is the Edward P. Fitts Distinguished Professor of Industrial and Systems Engineering at North Carolina State University (NCSU). He is Co-Director of the Center for Additive Manufacturing and Logistics and serves as the Director of Graduate Programs for the Supply Chain Engineering and Management program. He is both Alumni Distinguished Graduate Professor and Alumni Distinguished Undergraduate Professor at NCSU and is a Fellow of the Institute of Industrial Engineers. He received a Ph.D. in Industrial Engineering from the University of Florida. His research interests include analysis, control, and scheduling of production and logistics systems.