A Fluid Heuristic for Minimizing Makespan in Job Shops

J. G. Dai () and Gideon Weiss ()
Additional contact information
J. G. Dai: School of Industrial and Systems Engineering and School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, 30332-0205
Gideon Weiss: Department of Statistics, Haifa University, Mount Carmel, Haifa 31905, Israel

Operations Research, 2002, vol. 50, issue 4, 692-707

Abstract: We describe a simple online heuristic for scheduling job shops. We assume there is a fixed set of routes for the jobs, and many jobs, say N , on each route. The heuristic uses safety stocks and keeps the bottleneck machine busy at almost all times, while the other machines are paced by the bottleneck machine. We perform a probabilistic analysis of the heuristic, under some assumptions on the distributions of the processing times. We show that our heuristic produces makespan, which exceeds the optimal makespan by no more than c log N with a probability that exceeds 1-1/ N for all N (ge) 1, where c is some constant independent of N .

Keywords: Production/scheduling; sequencing; stochastic: job shop; makespan; re-entrant. Production/scheduling; approximations; heuristic: fluid model; performance bound; bottleneck stations (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.4.692.2860 (application/pdf)

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:inm:oropre:v:50:y:2002:i:4:p:692-707

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().