New lower and upper bounds for scheduling around a small common due date

J.A. Hoogeveen, H. Oosterhout, S.L. Velde, van de

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    22 Citaten (Scopus)
    2 Downloads (Pure)


    We consider the single-machine problem of scheduling n jobs to minimize the sum of the deviations of the job completion times from a given small common due date. For this NP-hard problem, we develop a branch-and-bound algorithm based on Lagrangian lower and upper bounds that are found in O(n log n) time. We identify conditions under which the bounds concur; these conditions can be expected to be satisfied by many instances with n not too small. In our experiments with processing times drawn from a uniform distribution, the bounds concur for n 40. For the case where the bounds do not concur, we present a refined lower bound that is obtained by solving a subset-sum problem of small dimension to optimality. We further develop a 4/3-approximation algorithm based upon the Lagrangian upper bound.
    Originele taal-2Engels
    Pagina's (van-tot)102-110
    Aantal pagina's9
    TijdschriftOperations Research
    Nummer van het tijdschrift1
    StatusGepubliceerd - 1994


    Duik in de onderzoeksthema's van 'New lower and upper bounds for scheduling around a small common due date'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit