We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Open-shop dense schedules: properties and worst-case performance ratio.
- Authors
Chen, Rongjun; Huang, Wanzhen; Men, Zhongxian; Tang, Guochun
- Abstract
Dense schedules are easy to construct and can be used as heuristic solutions for open-shop problems. It is conjectured that in the worst-case a dense schedule will result in a makespan no more than $(2-\frac{1}{m})$ times of the makespan of the optimal schedule, where m is the number of machines. Different approaches have been used in proofs for different number of machines. The conjecture has been proved for the number of machines m≤6, and for some special types of dense schedules. In this paper, we first summarize some useful properties of dense schedules, and then provide some special types of dense schedules that make the conjecture hold. Finally, we give complete proofs of the conjecture for m=7 and 8.
- Subjects
PRODUCTION scheduling; WORST-case circuit analysis; SHIFT systems; ADVANCED planning &; scheduling; TIME perspective; PREDICTION models
- Publication
Journal of Scheduling, 2012, Vol 15, Issue 1, p3
- ISSN
1094-6136
- Publication type
Article
- DOI
10.1007/s10951-009-0128-6