| Article ID: | iaor20102877 |
| Volume: | 36 |
| Issue: | 5 |
| Start Page Number: | 579 |
| End Page Number: | 583 |
| Publication Date: | Sep 2008 |
| Journal: | Operations Research Letters |
| Authors: | Wirth Andrew, Khammuang Kwanniti, Zhang Lele |
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.