views:

64

answers:

1

At work, we are given a set of constraints of the form (taskname, frequency) where frequency is an integer number which means the number of ticks between each invocation of the task "taskname". Two tasks cannot run concurrently, and each task invocation takes one tick to complete. Our goal is to find the best schedule in terms of matching the set of constraints.

For example, if we are given the constraints {(a, 2), (b,2)} the best schedule is "ab ab ab..." On the other hand, if we are given the constraints ({a,2}, {b, 5}, {c, 5}) the best schedule is probably "abaca abaca abaca..."

Currently we find the best schedule by running a genetic algorithm which tries to minimize the distance between actual frequencies and the given constrains. It actually works pretty well, but I wonder if there's some algorithm which better suits this kind of problem. I've tried to search Google but I seem to lack the right words (scheduling is usually about completing tasks :(). Can you help?

+1  A: 

First off, consider the merits of jldupont's comment! :)

Second, I think 'period' is the accurate description of the second element of the tuple, e.g. {Name, Period[icity]}.

That said, look to networking algorithms. Some variant of weighted queuing is probably applicable here.

For example, given N tasks, create N queues corresponding to tasks T0...Tn, and in each cycle ("tick") based on the period of the task, queue an item to the corresponding queue.

The scheduler algorithm would then aim for minimizing (on average) the total number of waiters in the queues. Simple starting off point would be to simply dequeue from the quene Qx which has the highest number of items. (A parameter on queued item to indicate 'age' would assist in prioritization.)

Yep, period is the right term.That's a good idea, but I have the privilege of predetermining the schedule offline, while weighted queuing seems to be greedy online algorithm.
r0u1i
Predetermining the schedule implies that you would arrive at a scheduling pattern that is applied repeatedly (and indefinitely). That sounds like a number theory problem, and intuitively, I am not sure that there is a provable solution for a general case (but that's just my gut feeling). E.g. its not clear if there is a finite pattern (of arbitrary length) that is provably the best solution. Regardless, you can still apply a set of greedy algorithms in a simulation (ala your GAs) and arrive at the best solution.