Improved algorithms for single machine scheduling with release dates and rejections

Cheng He; Joseph Y.T. Leung; Kangbok Lee; Michael L. Pinedo

doi:10.1007/s10288-016-0303-5

Improved algorithms for single machine scheduling with release dates and rejections

Cheng He, Joseph Y.T. Leung, Kangbok Lee, Michael L. Pinedo

Computer Science

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

21 Scopus citations

Abstract

We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.

Original language	English (US)
Pages (from-to)	41-55
Number of pages	15
Journal	4OR
Volume	14
Issue number	1
DOIs	https://doi.org/10.1007/s10288-016-0303-5
State	Published - Mar 1 2016

All Science Journal Classification (ASJC) codes

Management Information Systems
Theoretical Computer Science
Management Science and Operations Research
Computational Theory and Mathematics

Keywords

Approximation algorithm
Makespan
Rejection
Release date
Scheduling
Total rejection penalty

Access to Document

10.1007/s10288-016-0303-5

Cite this

@article{c5b8af3e2a034bee943a88003e0bcf58,

title = "Improved algorithms for single machine scheduling with release dates and rejections",

abstract = "We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.",

keywords = "Approximation algorithm, Makespan, Rejection, Release date, Scheduling, Total rejection penalty",

author = "Cheng He and Leung, {Joseph Y.T.} and Kangbok Lee and Pinedo, {Michael L.}",

note = "Publisher Copyright: {\textcopyright} 2016, Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = mar,

day = "1",

doi = "10.1007/s10288-016-0303-5",

language = "English (US)",

volume = "14",

pages = "41--55",

journal = "4OR",

issn = "1619-4500",

publisher = "Springer Verlag",

number = "1",

}

TY - JOUR

T1 - Improved algorithms for single machine scheduling with release dates and rejections

AU - He, Cheng

AU - Leung, Joseph Y.T.

AU - Lee, Kangbok

AU - Pinedo, Michael L.

PY - 2016/3/1

Y1 - 2016/3/1

N2 - We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.

AB - We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.

KW - Approximation algorithm

KW - Makespan

KW - Rejection

KW - Release date

KW - Scheduling

KW - Total rejection penalty

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

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

U2 - 10.1007/s10288-016-0303-5

DO - 10.1007/s10288-016-0303-5

M3 - Article

AN - SCOPUS:84959132028

SN - 1619-4500

VL - 14

SP - 41

EP - 55

JO - 4OR

JF - 4OR

IS - 1

ER -

Improved algorithms for single machine scheduling with release dates and rejections

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this