Scheduling Periodic Tasks with Slack
Jan Korst, Emile Aarts, Jan Karel Lenstra
INFORMS Journal on Computing · 1997 · Volume 9 · Issue 4
Abstract
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.
Keywords
job shop scheduling, local search, heuristic search
Enable JavaScript for citation tools and additional paper interactions.