| Article ID: | iaor19991179 |
| Country: | Netherlands |
| Volume: | 83 |
| Issue: | 1 |
| Start Page Number: | 253 |
| End Page Number: | 270 |
| Publication Date: | Oct 1998 |
| Journal: | Annals of Operations Research |
| Authors: | Strusevich V.A. |
The paper presents an improved version of the greedy open shop approximation algorithm with pre-ordering of jobs. It is shown that the algorithm compares favorably with the greedy algorithm with no pre-ordering by reducing either its absolute or relative error. In the case of three machines, the new algorithm creates a schedule with the makespan that is at most 3/2 times the optimal value.