Scheduling around a small common due date

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

doi:10.1016/0377-2217(91)90228-N

Scheduling around a small common due date

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

Stochastic Operations Research

Research output: Contribution to journal › Article › Academic › peer-review

113 Citations (Scopus)

1 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	237-242
Number of pages	6
Journal	European Journal of Operational Research
Volume	55
Issue number	2
DOIs	https://doi.org/10.1016/0377-2217(91)90228-N
Publication status	Published - 1991

Access to Document

10.1016/0377-2217(91)90228-N

Cite this

@article{40d41b0057a741c5a4e162ed28642a88,

title = "Scheduling around a small common due date",

abstract = "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.",

author = "J.A. Hoogeveen and {Velde, van de}, S.L.",

year = "1991",

doi = "10.1016/0377-2217(91)90228-N",

language = "English",

volume = "55",

pages = "237--242",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Scheduling around a small common due date

AU - Hoogeveen, J.A.

AU - Velde, van de, S.L.

PY - 1991

Y1 - 1991

N2 - 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.

AB - 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.

U2 - 10.1016/0377-2217(91)90228-N

DO - 10.1016/0377-2217(91)90228-N

M3 - Article

SN - 0377-2217

VL - 55

SP - 237

EP - 242

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Scheduling around a small common due date

Abstract

Access to Document

Fingerprint

Cite this