A Probabilistic Characterization of Allocation Performance in a Worker-Constrained Job Shop

Benjamin J. Lobo (), T. J. Thoney (), Russell E. King () and James R. Wilson ()
Additional contact information
Benjamin J. Lobo: North Carolina State University
T. J. Thoney: North Carolina State University
Russell E. King: North Carolina State University
James R. Wilson: North Carolina State University

Chapter 13 in Essays in Production, Project Planning and Scheduling, 2014, pp 301-341 from Springer

Abstract: Abstract We analyze a dual resource constrained (DRC) job shop in which both machines and workers are limited, and we seek to minimize L max, the maximum job lateness. An allocation of workers to machine groups is required to generate a schedule, and determining a schedule that minimizes L max is NP-hard. This chapter details a probabilistic method for evaluating the quality of a specific (but arbitrary) allocation in a given DRC job shop scheduling problem based on two recent articles by Lobo et al. (2013a) The first article Lobo et al. (2013b) describes a lower bound on L max given an allocation, and an algorithm to find an allocation yielding the smallest such lower bound, while the second article Lobo et al. (2013b) establishes criteria for verifying the optimality of an allocation. For situations where the optimality criteria are not satisfied, Lobo et al. (2013c) presents HSP, a heuristic search procedure to find allocations enabling the Virtual Factory (a heuristic scheduler developed by Hodgson et al. in 1998) to generate schedules with smaller L max than can be achieved with allocations yielding article 1’s final lower bound. From simulation replications of the given DRC job shop scheduling problem, we estimate the distribution of the difference between (a) the “best” (smallest) L max value achievable with a Virtual Factory–generated schedule, taken over all feasible allocations; and (b) the final lower bound of Lobo et al. (2013b). To evaluate the quality of a specific allocation for the given problem, we compute the difference between L max for the Virtual Factory–generated schedule based on the specific allocation, and the associated lower bound (b) for the problem; then we refer this difference to the estimated distribution to judge the likelihood that the specific allocation yields the Virtual Factory’s “best” schedule (a) for the given problem. We present several examples illustrating the usefulness of our approach, and summarize the lessons learned in this work.

Keywords: Staffing Level; Machine Group; Lower Endpoint; Simulation Replication; Virtual Factory (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-1-4614-9056-2_13

Ordering information: This item can be ordered from
http://www.springer.com/9781461490562

DOI: 10.1007/978-1-4614-9056-2_13

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().