| Article ID: | iaor1999180 |
| Country: | United States |
| Volume: | 9 |
| Issue: | 4 |
| Start Page Number: | 351 |
| End Page Number: | 362 |
| Publication Date: | Sep 1997 |
| Journal: | INFORMS Journal On Computing |
| Authors: | Lenstra Jan Karel, Aarts Emile H.L., Korst Jan |
| Keywords: | heuristics |
We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of identical processors, assuming that some slack is allowed in the time between successive executions of a periodic task. We prove that the problem is NP-hard in the strong sense. Necessary and sufficient conditions are derived for scheduling two periodic tasks on a single processor, and for combining two periodic tasks into one larger task. Based on these results, we propose an approximation algorithm.