UET-scheduling with chain-type precedence constraints

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    4 Citaten (Scopus)
    1 Downloads (Pure)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)915-920
    Aantal pagina's6
    TijdschriftComputers & Operations Research
    Volume22
    Nummer van het tijdschrift9
    DOI's
    StatusGepubliceerd - 1995

    Vingerafdruk

    Duik in de onderzoeksthema's van 'UET-scheduling with chain-type precedence constraints'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit