Article ID: | iaor19982719 |
Country: | Netherlands |
Volume: | 20 |
Issue: | 5 |
Start Page Number: | 207 |
End Page Number: | 212 |
Publication Date: | Jun 1997 |
Journal: | Operations Research Letters |
Authors: | Woeginger Gerhard J., Tautenhahn Thomas |
We consider the problem of minimizing the total completion time in a unit-time open shop with release times where the number of machines is constant. Brucker and Krämer proved that this problem is solvable in polynomial time. However, the time complexity of the algorithm presented there is a polynom of a very high degree and, thus, the algorithm is not practicable even for a small number of machines. We give an O(