On-line scheduling with non-crossing constraints

Lele Zhang; Kwanniti Khammuang; Andrew Wirth

doi:10.1016/j.orl.2008.04.005

On-line scheduling with non-crossing constraints

Lele Zhang, Kwanniti Khammuang, Andrew Wirth

Research output: Contribution to journal › Article › Research › peer-review

11 Citations (Scopus)

Abstract

We consider the problem of on-line scheduling with non-crossing constraints. The objective is to minimize the latest completion time. We provide optimal competitive ratio heuristics for the on-line list and on-line time problems with unit processing times, and a 3-competitive heuristic for the general on-line time problem.

Original language	English
Pages (from-to)	579 - 583
Number of pages	5
Journal	Operations Research Letters
Volume	36
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2008.04.005
Publication status	Published - 2008
Externally published	Yes

Access to Document

10.1016/j.orl.2008.04.005

Cite this

@article{8663c9c98dcb486e8cfd7164f7da1da4,

title = "On-line scheduling with non-crossing constraints",

abstract = "We consider the problem of on-line scheduling with non-crossing constraints. The objective is to minimize the latest completion time. We provide optimal competitive ratio heuristics for the on-line list and on-line time problems with unit processing times, and a 3-competitive heuristic for the general on-line time problem.",

author = "Lele Zhang and Kwanniti Khammuang and Andrew Wirth",

year = "2008",

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

language = "English",

volume = "36",

pages = "579 -- 583",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - On-line scheduling with non-crossing constraints

AU - Zhang, Lele

AU - Khammuang, Kwanniti

AU - Wirth, Andrew

PY - 2008

Y1 - 2008

N2 - We consider the problem of on-line scheduling with non-crossing constraints. The objective is to minimize the latest completion time. We provide optimal competitive ratio heuristics for the on-line list and on-line time problems with unit processing times, and a 3-competitive heuristic for the general on-line time problem.

AB - We consider the problem of on-line scheduling with non-crossing constraints. The objective is to minimize the latest completion time. We provide optimal competitive ratio heuristics for the on-line list and on-line time problems with unit processing times, and a 3-competitive heuristic for the general on-line time problem.

UR - http://www.sciencedirect.com/science/article/pii/S0167637708000539#

U2 - 10.1016/j.orl.2008.04.005

DO - 10.1016/j.orl.2008.04.005

M3 - Article

VL - 36

SP - 579

EP - 583

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -

On-line scheduling with non-crossing constraints

Abstract

Access to Document

Other files and links

Cite this