| Article ID: | iaor20033139 |
| Country: | China |
| Volume: | 20 |
| Issue: | 1 |
| Start Page Number: | 33 |
| End Page Number: | 37 |
| Publication Date: | Mar 2002 |
| Journal: | Journal of Hubei Institute for Nationalities (Natural Science Edition) |
| Authors: | Shi Ling |
An open shop scheduling problem with delays is considered in this paper. For an arbitrary number of machines, a simple greedy algorithm can produce a schedule whose makespan is at most twice that of the optimal one in the worst case. The worst case ratio is proved to be for m = 2 (m is the number of machines).