Scheduling a worker with overlapping periodic tasks

Question

With one worker, who can only perform one task at a time (but can switch between tasks instantly)

Given a list of tasks,
-- defined as "n seconds, every m seconds" (eg, 5 seconds every 3600 seconds)

How could I find the best starting times and count for each task?

If every task were "1 second, every 60 seconds", each would have an unique starting second, and the count would be infinite (steady state).
If it was "1 second every 4 seconds" and "1 second every 3 seconds", the result would be: " 0, infinite and 3, 3 times"

-- Hopefully simplest form

If already I have a list of tasks, elaborated with "start second and number of times", what would a function that returns: {start, count} for an additional {n seconds every m seconds} task look like?

-- (Slightly more complex form --
if instead of "n seconds every m seconds",
the tasks were defined as "n seconds every l..o seconds",
where I could pick a number m in the range l - o (but would have to commit to that m until the task was finished),
would that allow better worker utilization?
How would I choose the best 'm' ?

Answer 1

This type of problem is hard to solve, but relatively easy to optimize. Take a look at Simulated Annealing, Great Deluge, or Genetic Algorithms.

Answer 2

Hmmm, here's a little suggestion: if the greatest common divisor of the m's is greater than or equal to the sum of the n's, the solution is steady state.

I would go for the set of tasks which has maximum sum of the n's, such that the gcd of the m's is greater than or equal to that sum.

Answer 3

I think it depends on how you define 'best'. For instance, if you wanted tasks to run every m seconds "on average", there's an easy way to do it using the same sort of algorithm as the Bresenham method to draw lines (a task that's 'n seconds every m seconds' is much like scattering n vertical steps among m horizontal steps when drawing a line). Assign each task a counter and a step value (for "1 second every 3 seconds" the step would be 1/3). Then add the step to the counter every 'cycle' through. When a counter goes above zero that task should run (and subtract 1 from the counter). If you have several counters above zero, choose the largest one. That may give you a solution that is "good enough" for the slightly more complex form as well.

The "1/4" and "1/3" example though sounds like you have a requirement to run the tasks "exactly" m seconds apart. Starting from a list and adding a new task to maximize the count is not a difficult search problem - but I do not think this is what you need. The A(1/4) B(1/4) C(1/2) example would give A B x x A B x x after adding A then B. Then C could not be added,

I think there are obvious candidates for fitness functions - a table of n,m,start can have a fitness function which is the portion of the time where no more than one task is scheduled. GA/annealing would have a good chance of finding a steady state solution if one exists. But in cases like (1/4), (1/3) wwhere there appears to be no steady state solution, defining 'best' should also define your fitness function.

Answer 4

Hmmmm. How about ... you do your own homework!

Answer 5

See w:Scheduling (computing). The link includes a nice list of scheduling strategies:

[Scheduling] refers to the way processes are assigned priorities in a priority queue. This assignment is carried out by software known as a scheduler. The scheduler is concerned mainly with:

• CPU utilization - to keep the CPU as busy as possible.
• Throughput - number of process that complete their execution per time unit.
• Turnaround - amount of time to execute a particular process.
• Waiting time - amount of time a process has been waiting in the ready queue.
• Response time - amount of time it takes from when a request was submitted until the first response is produced.