On-line scheduling with non-crossing constraints

Lele Zhang, Kwanniti Khammuang, Andrew Wirth

Research output: Contribution to journalArticleResearchpeer-review

10 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 languageEnglish
Pages (from-to)579 - 583
Number of pages5
JournalOperations Research Letters
Volume36
Issue number5
DOIs
Publication statusPublished - 2008
Externally publishedYes

Cite this