arrow
Return

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

delete2007-08-01
delete4
PRE
AI
M
Min Ji
何
何勇 (Yong He)
T
T.C.E. Cheng *
DOI:10.1016/j.cor.2005.09.011delete
deleteOriginal
deleteShare
deleteSave
Abstract

Abstract

En 中文
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. (c) 2005 Elsevier Ltd. All rights reserved.
Keywords:
scheduling
approximation algorithm
worst-case ratio

Journal

C
Computers and Operations Research
IF:
4.3
Papers:
6.5K
Citations:
2.3W

Organization

No organization information available
Cited Papers

Cited Papers

Autonomous mobile robots with lights
err2016-01-01
err0
errOAAI
errShantanu Das; Paola Flocchini; Giuseppe Prencipe; Nicola Santoro; Masafumi Yamashita
errShare
errSave
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help
err2004-01-01
err0
PREAI
errMarek Chrobak; Wojciech Jawor; Jiří Sgall; Tomáš Tichý
errShare
errSave