Does anybody recognize this scheduling problem? Is there an algorithm for it?

Question

Consider the following problem:

---

Description:

There are n jobs J₁...J_n with cycle times C₁....C_n. 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 J_k (k = 1,n) must be equal to C_k / time quantum.
• the table must be as short as possible.

Example:

• J₁ - 4 seconds ciclicity
• J₂ - 6 seconds ciclicity
• J₃ - 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 C₁...C_n.
• the time quantum should be at least GCD(C₁,...,C_n) / 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.

Answer 1

You could determine the best schedule using a priority queue. Where are the decision moments in scheduling? It is when you have more than one cycle to start on any given second.

You'll need to have a "schedule" data type representing a possible schedule (the data you've written above is a perfect example of the data you'd represent here).

Therefore the pseudo algorithm should be the following:

Add each cycle type to its own schedule and push each schedule onto a priority queue, prioritizing by smallest GCD*(C1,...,Cn) / n value.

Then, starting with the schedule with the smallest GCD*(C1,...,Cn) / n value, create new schedules from the old by appending new cycles to launch.

Continue for as much as you like.

You decide when the schedule should end, and since it is a priority queue, you're guaranteed that the first element is the optimal in terms of GCD*(C1,...,Cn) / n at any given point.

Hope that helps.