Article ID: | iaor20013909 |
Country: | Netherlands |
Volume: | 128 |
Issue: | 1 |
Start Page Number: | 159 |
End Page Number: | 174 |
Publication Date: | Jan 2001 |
Journal: | European Journal of Operational Research |
Authors: | Strusevich Vitaly A., Drobouchevitch Inna G. |
Keywords: | computational analysis |
It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless