Scheduling around a small common due date

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

    Research output: Contribution to journalArticleAcademicpeer-review

    105 Citations (Scopus)
    1 Downloads (Pure)


    A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space.
    Original languageEnglish
    Pages (from-to)237-242
    Number of pages6
    JournalEuropean Journal of Operational Research
    Issue number2
    Publication statusPublished - 1991

    Fingerprint Dive into the research topics of 'Scheduling around a small common due date'. Together they form a unique fingerprint.

    Cite this