MINIMIZING THE TOTAL COMPLETION-TIME IN A UNIT-TIME OPEN SHOP WITH RELEASE TIMES

We consider the problem of minimizing the total completion time in a u nit-time open shop with release times where the number of machines is constant. Brucker and Kramer (1994) proved that this problem is solvab le in polynomial time. However, the time complexity of the algorithm p resented there is a polynom of a very high degree and, thus, the algor ithm is not practicable even for a small number of machines. We give a n O(n(2)) algorithm for the considered problem which is based on dynam ic programming. The result is applied to solve a previously open probl em with a special resource constraint raised by De Werra et al. (1991) . (C) 1997 Elsevier Science B.V.