Article ID Journal Published Year Pages File Type
1142691 Operations Research Letters 2008 5 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On-line scheduling with non-crossing constraints
Authors
, , ,