UET-scheduling with chain-type precedence constraints

K. Jansen, G.J. Woeginger, Zhongliang Yu

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    We consider a special case of the precedence constrained scheduling problem of n unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.
    Original languageEnglish
    Pages (from-to)915-920
    Number of pages6
    JournalComputers & Operations Research
    Volume22
    Issue number9
    DOIs
    Publication statusPublished - 1995

    Fingerprint Dive into the research topics of 'UET-scheduling with chain-type precedence constraints'. Together they form a unique fingerprint.

  • Cite this