Hi all,
I’m hoping someone can help me out with an algorithm question I got stuck on, while contemplating optimal scheduling algorithms (as one does lol).
Consider a basic task scheduling system, where there’s a queue of “Tasks” that need to get done, a pool of “Workers” that can execute work (one at a time), and a scheduler that pulls work form the queue and assigns to the workers in some fashion.
( [Task1] [Task2] [Task3] ... [TaskT] ) ---[Scheduler]=== ( [Worker1] [Worker2] ... [WorkerN] )
I’ve been thinking about various optimal scheduling algorithms for such a system, with various parameters.
For this discussion, let’s assume:
- The work is uniform (all Task units are exactly the same).
- “Optimal Scheduling” just means “If I add a bunch of work to the queue, all of it will be completed ASAP.”
The Trivial Case
If, in addition to tasks being uniform, all workers are perfectly uniform, it’s easy to see that assigning the work to the first available free worker is optimal, and that the scheduler can just be a dumb round-robin allocator of work.
The Heterogeneous Worker Case
Suppose we have an added constraint: Not all workers are the same; they take different amounts of time to perform a work unit. Maybe they run on a heterogeneous fleet, and some are on better hardware…
In that case, if we want optimal scheduling, we can do so greedily, by always assigning to the worker that will become available the soonest given one more unit of work (i.e. “store workers in a priority queue sorted by ‘when it will be done with all its work, given one more unit of work’”)
The Heterogeneous Worker with Scheduled Work Case
Ok, THIS is the one I am stuck on.
Suppose, in addition to the workers being different, we ALSO have a constraint where each unit of work becomes available at a specific time t into the execution.
The aforementioned greedy approach won’t work anymore. Consider this example:
Workers:
- W1 takes 8 minutes to finish a work item.
- W2 takes 10 minutes to finish a work item.
Work:
- Task1 is available immediately (t = 0)
- Task2 is available one minute in (t = 1)
With the greedy algorithm: T1 will be assigned to W1, and T2 will be assiged to W2 one minute in, resulting in all work completing after 11 minutes.
However, the optimal solution is, T1 gets assigned to W2, and T2 gets assigned to W1, making T1 the long pole, and allowing the work to complete in only 10 minutes.
Intuitively, it kind of feels like this has to become a search/backtracking problem, perhaps with heavy pruning of nonsensical choices, but… is there a simpler solution I’m missing? I keep getting the sense that there’s a viable DP approach, if we’re generous with things like declaring all times are integers, and throwing everything at the slowest worker is guaranteed to take less than some reasonably small amount of time…
… or maybe there IS a greedy solution, and I’m just not seeing it…
Any thoughts/direction here?