Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

Zhongjun Tian; Chi To Ng; Edwin Tai Chiu Cheng

doi:10.1016/j.orl.2009.04.004

Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

Zhongjun Tian, Chi To Ng, Edwin Tai Chiu Cheng

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

6 Citations (Scopus)

Abstract

We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is N P-hard in the ordinary sense by showing that it is N P-hard, and deriving a pseudo-polynomial algorithm for it.

Original language	English
Pages (from-to)	368-374
Number of pages	7
Journal	Operations Research Letters
Volume	37
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2009.04.004
Publication status	Published - 1 Sept 2009

Keywords

Preemptive scheduling
Single machine
Total tardiness

ASJC Scopus subject areas

Management Science and Operations Research
Applied Mathematics
Industrial and Manufacturing Engineering
Software

More information

10.1016/j.orl.2009.04.004

Cite this

@article{9cb65769779341088a2e5274503f7738,

title = "Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness",

abstract = "We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is N P-hard in the ordinary sense by showing that it is N P-hard, and deriving a pseudo-polynomial algorithm for it.",

keywords = "Preemptive scheduling, Single machine, Total tardiness",

author = "Zhongjun Tian and Ng, \{Chi To\} and Cheng, \{Edwin Tai Chiu\}",

year = "2009",

month = sep,

day = "1",

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

language = "English",

volume = "37",

pages = "368--374",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

AU - Tian, Zhongjun

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2009/9/1

Y1 - 2009/9/1

N2 - We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is N P-hard in the ordinary sense by showing that it is N P-hard, and deriving a pseudo-polynomial algorithm for it.

AB - We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is N P-hard in the ordinary sense by showing that it is N P-hard, and deriving a pseudo-polynomial algorithm for it.

KW - Preemptive scheduling

KW - Single machine

KW - Total tardiness

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

U2 - 10.1016/j.orl.2009.04.004

DO - 10.1016/j.orl.2009.04.004

M3 - Journal article

SN - 0167-6377

VL - 37

SP - 368

EP - 374

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this