New lower and upper bounds for on-line scheduling

B. Chen, A. Vliet, van, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    69 Citaten (Scopus)
    11 Downloads (Pure)


    We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.
    Originele taal-2Engels
    Pagina's (van-tot)221-230
    Aantal pagina's10
    TijdschriftOperations Research Letters
    Nummer van het tijdschrift4
    StatusGepubliceerd - 1994


    Duik in de onderzoeksthema's van 'New lower and upper bounds for on-line scheduling'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit