Consider the following problem:
Description:
There are n jobs J1...Jn with cycle times C1....Cn. Find a time quantum and a scheduling table considering that:
- any element of the table contains at most one job
- the job handler will process an element at a time, i.e. execute the job (if any) then, after a time quantum passes, moves to the next element.
- the job handler will loop-back, i.e. after the last element it will continue with the first.
- the ciclicity must be maintained, i.e. the distance between any two consecutive (including loop-back) occurances of job Jk (k = 1,n) must be equal to Ck / time quantum.
- the table must be as short as possible.
Example:
- J1 - 4 seconds ciclicity
- J2 - 6 seconds ciclicity
- J3 - 8 seconds ciclicity
Example solution:
time quantum = 1s
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 seconds
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|J1|J2|J3| |J1| | |J2|J1| |J3| |J1|J2| | |J1| |J3|J2|J1| | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
My feeling is that this belongs to the family of scheduling problems and that it may be a special case of a more general problem. Is this so? I tried to search for it online but didn't find anything that looks similar. Since I don't have any experience with scheduling problems I'm not even sure what to search for.
From what I see:
- the total duration of the schedluing table should be the smallest common multiple of C1...Cn.
- the time quantum should be at least GCD(C1,...,Cn) / n. - This is not necessarly the optimal solution.
This leads me to believe that there is a straight forward solution and not one involving dynamic programming. Is this so?
Can somebody point me to some resources, maybe even an algorithm, for this problem?
I'm also curious about variations where there the jobs can be distributed between more than one scheduling tables.
GCD = Greatest Common Divider
Edit: I'm not asking how to schedule N jobs with given cycle times; I'm sure there are more dynamic ways to do this as some suggested. My problem is "Find a time quantum and a scheduling table considering that:[...]". It's even possible that it may have it's roots in some parts of mathematics.