| Article ID: | iaor1993996 |
| Country: | Netherlands |
| Volume: | 12 |
| Issue: | 5 |
| Start Page Number: | 293 |
| End Page Number: | 295 |
| Publication Date: | Nov 1992 |
| Journal: | Operations Research Letters |
| Authors: | Keil J. Mark |
The paper considers the problem of scheduling tasks with a discrete set of possible starting times, on a single processor. It shows the problem NP-complete even when all tasks require the same execution time and each task has at most three possible starting times. The paper also presents a polynomially solvable case.