A simple linear time algorithm for scheduling with step-improving processing times

Min Ji; Yong He; Edwin Tai Chiu Cheng

doi:10.1016/j.cor.2005.09.011

A simple linear time algorithm for scheduling with step-improving processing times

Min Ji, Yong He, Edwin Tai Chiu Cheng

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

4 Citations (Scopus)

Abstract

We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line approximation algorithm and prove its worst-case performance guarantee.

Original language	English
Pages (from-to)	2396-2402
Number of pages	7
Journal	Computers and Operations Research
Volume	34
Issue number	8
DOIs	https://doi.org/10.1016/j.cor.2005.09.011
Publication status	Published - 1 Aug 2007

Keywords

Approximation algorithm
Scheduling
Worst-case ratio

ASJC Scopus subject areas

Information Systems and Management
Management Science and Operations Research
Applied Mathematics
Modelling and Simulation
Transportation

More information

10.1016/j.cor.2005.09.011

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

Cite this

@article{b9629134bcba4bf79250e645dd170d8a,

title = "A simple linear time algorithm for scheduling with step-improving processing times",

abstract = "We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line approximation algorithm and prove its worst-case performance guarantee.",

keywords = "Approximation algorithm, Scheduling, Worst-case ratio",

author = "Min Ji and Yong He and Cheng, {Edwin Tai Chiu}",

year = "2007",

month = aug,

day = "1",

doi = "10.1016/j.cor.2005.09.011",

language = "English",

volume = "34",

pages = "2396--2402",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "8",

}

TY - JOUR

T1 - A simple linear time algorithm for scheduling with step-improving processing times

AU - Ji, Min

AU - He, Yong

AU - Cheng, Edwin Tai Chiu

PY - 2007/8/1

Y1 - 2007/8/1

N2 - We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line approximation algorithm and prove its worst-case performance guarantee.

AB - We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line approximation algorithm and prove its worst-case performance guarantee.

KW - Approximation algorithm

KW - Scheduling

KW - Worst-case ratio

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

U2 - 10.1016/j.cor.2005.09.011

DO - 10.1016/j.cor.2005.09.011

M3 - Journal article

SN - 0305-0548

VL - 34

SP - 2396

EP - 2402

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 8

ER -

A simple linear time algorithm for scheduling with step-improving processing times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this