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.
|Pages (from-to)||579 - 583|
|Number of pages||5|
|Journal||Operations Research Letters|
|Publication status||Published - 2008|