Minimizing the total completion time in a unit-time open shop with release times

Minimizing the total completion time in a unit-time open shop with release times

0.00 Avg rating0 Votes
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: ,
Abstract:

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(n2) algorithm for the considered problem which is based on dynamic programming. The result is applied to solve a previously open problem with a special resource constraint raised by De Werra et al.

Reviews

Required fields are marked *. Your email address will not be published.