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

T. Tautenhahn, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    9 Citations (Scopus)

    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 (1994) 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. (1991).
    Original languageEnglish
    Pages (from-to)207-212
    Number of pages6
    JournalOperations Research Letters
    Volume20
    Issue number5
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'Minimizing the total completion time in a unit-time open shop with release times'. Together they form a unique fingerprint.

  • Cite this