A fluid heuristic for minimizing makespan in job shops
成果类型：
Article
署名作者：
Dai, JG; Weiss, G
署名单位：
University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology; University of Haifa
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.50.4.692.2860
发表日期：
2002
页码：
692-707
关键词：
摘要：
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 buoy at almost all times, while the other machines are paced by the bottleneck machine. We perforin 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 greater than or equal to 1. where c is some constant independent of N.