Group sequencing around a common due date

Edwin Tai Chiu Cheng; Mikhail Y. Kovalyov; Chi To Ng; S. S. Lam

doi:10.1016/j.disopt.2006.04.003

Group sequencing around a common due date

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov, Chi To Ng, S. S. Lam

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

9 Citations (Scopus)

Abstract

The problem of scheduling groups of jobs on a single machine under the group technology assumption is studied. Jobs of the same group are processed contiguously and a sequence independent setup time precedes the processing of each group. All jobs have a common fixed due date, which can be either unrestrictively large or restrictively small. The objective is to minimize the total weighted earliness-tardiness. Properties of optimal solutions are established, and dynamic programming algorithms are derived to solve several special cases of this problem. Computational experiments show that the algorithms can easily solve problems with 500 groups of jobs and each group has 10 to 50 jobs on a standard PC.

Original language	English
Pages (from-to)	594-604
Number of pages	11
Journal	Discrete Optimization
Volume	5
Issue number	3
DOIs	https://doi.org/10.1016/j.disopt.2006.04.003
Publication status	Published - 1 Aug 2008

Keywords

Dynamic programming
Earliness-tardiness
Group technology
Single machine scheduling

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

More information

10.1016/j.disopt.2006.04.003

http://hdl.handle.net/10397/1263

Cite this

@article{59600500aaba49dfa74fe8553d84b676,

title = "Group sequencing around a common due date",

abstract = "The problem of scheduling groups of jobs on a single machine under the group technology assumption is studied. Jobs of the same group are processed contiguously and a sequence independent setup time precedes the processing of each group. All jobs have a common fixed due date, which can be either unrestrictively large or restrictively small. The objective is to minimize the total weighted earliness-tardiness. Properties of optimal solutions are established, and dynamic programming algorithms are derived to solve several special cases of this problem. Computational experiments show that the algorithms can easily solve problems with 500 groups of jobs and each group has 10 to 50 jobs on a standard PC.",

keywords = "Dynamic programming, Earliness-tardiness, Group technology, Single machine scheduling",

author = "Cheng, {Edwin Tai Chiu} and Kovalyov, {Mikhail Y.} and Ng, {Chi To} and Lam, {S. S.}",

year = "2008",

month = aug,

day = "1",

doi = "10.1016/j.disopt.2006.04.003",

language = "English",

volume = "5",

pages = "594--604",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Group sequencing around a common due date

AU - Cheng, Edwin Tai Chiu

AU - Kovalyov, Mikhail Y.

AU - Ng, Chi To

AU - Lam, S. S.

PY - 2008/8/1

Y1 - 2008/8/1

N2 - The problem of scheduling groups of jobs on a single machine under the group technology assumption is studied. Jobs of the same group are processed contiguously and a sequence independent setup time precedes the processing of each group. All jobs have a common fixed due date, which can be either unrestrictively large or restrictively small. The objective is to minimize the total weighted earliness-tardiness. Properties of optimal solutions are established, and dynamic programming algorithms are derived to solve several special cases of this problem. Computational experiments show that the algorithms can easily solve problems with 500 groups of jobs and each group has 10 to 50 jobs on a standard PC.

AB - The problem of scheduling groups of jobs on a single machine under the group technology assumption is studied. Jobs of the same group are processed contiguously and a sequence independent setup time precedes the processing of each group. All jobs have a common fixed due date, which can be either unrestrictively large or restrictively small. The objective is to minimize the total weighted earliness-tardiness. Properties of optimal solutions are established, and dynamic programming algorithms are derived to solve several special cases of this problem. Computational experiments show that the algorithms can easily solve problems with 500 groups of jobs and each group has 10 to 50 jobs on a standard PC.

KW - Dynamic programming

KW - Earliness-tardiness

KW - Group technology

KW - Single machine scheduling

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

U2 - 10.1016/j.disopt.2006.04.003

DO - 10.1016/j.disopt.2006.04.003

M3 - Journal article

SN - 1572-5286

VL - 5

SP - 594

EP - 604

JO - Discrete Optimization

JF - Discrete Optimization

IS - 3

ER -

Group sequencing around a common due date

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this