The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

Q. Q. Nong; Chi To Ng; Edwin Tai Chiu Cheng

doi:10.1016/j.orl.2007.01.007

The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

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

Abstract

We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of frac(5, 2) for the non-identical job size model will be derived.

Original language	English
Pages (from-to)	61-66
Number of pages	6
Journal	Operations Research Letters
Volume	36
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2007.01.007
Publication status	Published - 1 Jan 2008

Keywords

Approximation algorithm
Batching
Family
Single-machine scheduling
Worst-case analysis

ASJC Scopus subject areas

Management Science and Operations Research
Statistics, Probability and Uncertainty
Discrete Mathematics and Combinatorics
Modelling and Simulation

More information

10.1016/j.orl.2007.01.007

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

Cite this

@article{f489c4d27a46468b8b18f80c8aae52bf,

title = "The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan",

abstract = "We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of frac(5, 2) for the non-identical job size model will be derived.",

keywords = "Approximation algorithm, Batching, Family, Single-machine scheduling, Worst-case analysis",

author = "Nong, \{Q. Q.\} and Ng, \{Chi To\} and Cheng, \{Edwin Tai Chiu\}",

year = "2008",

month = jan,

day = "1",

doi = "10.1016/j.orl.2007.01.007",

language = "English",

volume = "36",

pages = "61--66",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

AU - Nong, Q. Q.

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2008/1/1

Y1 - 2008/1/1

N2 - We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of frac(5, 2) for the non-identical job size model will be derived.

AB - We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of frac(5, 2) for the non-identical job size model will be derived.

KW - Approximation algorithm

KW - Batching

KW - Family

KW - Single-machine scheduling

KW - Worst-case analysis

UR - https://www.scopus.com/pages/publications/37049035556

U2 - 10.1016/j.orl.2007.01.007

DO - 10.1016/j.orl.2007.01.007

M3 - Journal article

SN - 0167-6377

VL - 36

SP - 61

EP - 66

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this