| Article ID: | iaor20022779 |
| Country: | China |
| Volume: | 17 |
| Issue: | 1 |
| Start Page Number: | 121 |
| End Page Number: | 128 |
| Publication Date: | Jan 2001 |
| Journal: | Acta Mathematicae Applicatae Sinica |
| Authors: | Chen Bo, Yu Wenci |
In this paper, we study a class of simple and easy-to-construct shop schedules, known as dense schedules. We present tight bounds on the maximum deviation in makespan of dense flow-shop and job-shop schedules from their optimal ones. For dense open-shop schedules, we do the same for the special case of four machines and thus add a stronger supporting case for proving a standing conjecture.