5

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.

  • if this is a homework assignment, first thing to search would be not online, but course materials. Did you check these? Did you ask your tutor, what did they say? – gnat May 20 '14 at 13:57
  • @gnat It is not a homework assignement. In my case the jobs are the sending of cyclic messages on CAN bus. – DonComo May 20 '14 at 14:01
  • 2
    @gnat I don't agree with your edit. I specifically written the question in the form of a general problem. It's nature has nothing specific to CAN communication. The title is especially misleading. – DonComo May 20 '14 at 14:32
  • as long as you're looking for someone to recognize a problem, it would increase your chances to find someone who already has dealt with this kind of application – gnat May 20 '14 at 14:37
  • 2
    @gnat I would argue the other way, you are making it more specialized. The CAN protocol is used mostly in the automotive industry and I'm sure they are a minority here. As I said the problem is not specific to CAN communications, I've encountered it at other times. – DonComo May 20 '14 at 14:42
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.