Parallel-machine scheduling problems with earliness and tardiness penalties

Edwin Tai Chiu Cheng; Z. L. Chen

doi:10.1057/jors.1994.106

Parallel-machine scheduling problems with earliness and tardiness penalties

Edwin Tai Chiu Cheng, Z. L. Chen

Research output: Journal article publication › Journal article › Academic research › peer-review

80 Citations (Scopus)

Abstract

We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.

Original language	English
Pages (from-to)	685-695
Number of pages	11
Journal	Journal of the Operational Research Society
Volume	45
Issue number	6
DOIs	https://doi.org/10.1057/jors.1994.106
Publication status	Published - 1 Jan 1994

Keywords

NP-completeness
Parallel-machine
Scheduling
Sequencing

ASJC Scopus subject areas

Management Information Systems
Strategy and Management
Management Science and Operations Research
Marketing

More information

10.1057/jors.1994.106

Cite this

@article{3bc28c17064946f2ae2cc4171818e204,

title = "Parallel-machine scheduling problems with earliness and tardiness penalties",

abstract = "We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.",

keywords = "NP-completeness, Parallel-machine, Scheduling, Sequencing",

author = "Cheng, {Edwin Tai Chiu} and Chen, {Z. L.}",

year = "1994",

month = jan,

day = "1",

doi = "10.1057/jors.1994.106",

language = "English",

volume = "45",

pages = "685--695",

journal = "Journal of the Operational Research Society",

issn = "0160-5682",

publisher = "Palgrave Macmillan Ltd.",

number = "6",

}

TY - JOUR

T1 - Parallel-machine scheduling problems with earliness and tardiness penalties

AU - Cheng, Edwin Tai Chiu

AU - Chen, Z. L.

PY - 1994/1/1

Y1 - 1994/1/1

N2 - We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.

AB - We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.

KW - NP-completeness

KW - Parallel-machine

KW - Scheduling

KW - Sequencing

UR - http://www.scopus.com/inward/record.url?scp=0028445470&partnerID=8YFLogxK

U2 - 10.1057/jors.1994.106

DO - 10.1057/jors.1994.106

M3 - Journal article

VL - 45

SP - 685

EP - 695

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 6

ER -

Parallel-machine scheduling problems with earliness and tardiness penalties

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Cite this