An O (n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

Zhongjun Tian; Chi To Ng; Edwin Tai Chiu Cheng

doi:10.1007/s10951-006-7039-6

An O (n²) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

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

Abstract

In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem.

Original language	English
Pages (from-to)	343-364
Number of pages	22
Journal	Journal of Scheduling
Volume	9
Issue number	4
DOIs	https://doi.org/10.1007/s10951-006-7039-6
Publication status	Published - 1 Jan 2006

Keywords

Equal-length jobs
Preemptive scheduling
Release date
Single machine
Total tardiness

ASJC Scopus subject areas

Software
General Engineering
Management Science and Operations Research
Artificial Intelligence

More information

10.1007/s10951-006-7039-6

Cite this

@article{56b012381e9940448a68b355eb219434,

title = "An O (n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness",

abstract = "In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem.",

keywords = "Equal-length jobs, Preemptive scheduling, Release date, Single machine, Total tardiness",

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

year = "2006",

month = jan,

day = "1",

doi = "10.1007/s10951-006-7039-6",

language = "English",

volume = "9",

pages = "343--364",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - An O (n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

AU - Tian, Zhongjun

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2006/1/1

Y1 - 2006/1/1

N2 - In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem.

AB - In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem.

KW - Equal-length jobs

KW - Preemptive scheduling

KW - Release date

KW - Single machine

KW - Total tardiness

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

U2 - 10.1007/s10951-006-7039-6

DO - 10.1007/s10951-006-7039-6

M3 - Journal article

SN - 1094-6136

VL - 9

SP - 343

EP - 364

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 4

ER -