Scheduling with job release dates, delivery times and preemption penalties

Zhaohui Liu; Edwin Tai Chiu Cheng

doi:10.1016/S0020-0190(01)00251-4

Scheduling with job release dates, delivery times and preemption penalties

Zhaohui Liu, Edwin Tai Chiu Cheng

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

31 Citations (Scopus)

Abstract

The single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties was discussed. Such problems require a job-dependent setup to take place each time a job is started. It was proved that the problem is strongly NP-hard. A dynamic programming algorithm and a polynomial time approximation scheme were also presented for solving the problem.

Original language	English
Pages (from-to)	107-111
Number of pages	5
Journal	Information Processing Letters
Volume	82
Issue number	2
DOIs	https://doi.org/10.1016/S0020-0190(01)00251-4
Publication status	Published - 30 Apr 2002

Keywords

Approximation scheme
Preemption penalty
Scheduling
Setup time

ASJC Scopus subject areas

Computational Theory and Mathematics

More information

10.1016/S0020-0190(01)00251-4

Cite this

@article{793b51fa8b5e45f6b7e2459821e699eb,

title = "Scheduling with job release dates, delivery times and preemption penalties",

abstract = "The single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties was discussed. Such problems require a job-dependent setup to take place each time a job is started. It was proved that the problem is strongly NP-hard. A dynamic programming algorithm and a polynomial time approximation scheme were also presented for solving the problem.",

keywords = "Approximation scheme, Preemption penalty, Scheduling, Setup time",

author = "Zhaohui Liu and Cheng, {Edwin Tai Chiu}",

year = "2002",

month = apr,

day = "30",

doi = "10.1016/S0020-0190(01)00251-4",

language = "English",

volume = "82",

pages = "107--111",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Scheduling with job release dates, delivery times and preemption penalties

AU - Liu, Zhaohui

AU - Cheng, Edwin Tai Chiu

PY - 2002/4/30

Y1 - 2002/4/30

N2 - The single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties was discussed. Such problems require a job-dependent setup to take place each time a job is started. It was proved that the problem is strongly NP-hard. A dynamic programming algorithm and a polynomial time approximation scheme were also presented for solving the problem.

AB - The single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties was discussed. Such problems require a job-dependent setup to take place each time a job is started. It was proved that the problem is strongly NP-hard. A dynamic programming algorithm and a polynomial time approximation scheme were also presented for solving the problem.

KW - Approximation scheme

KW - Preemption penalty

KW - Scheduling

KW - Setup time

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

U2 - 10.1016/S0020-0190(01)00251-4

DO - 10.1016/S0020-0190(01)00251-4

M3 - Journal article

SN - 0020-0190

VL - 82

SP - 107

EP - 111

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Scheduling with job release dates, delivery times and preemption penalties

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this