15,663,399 members
Home / Discussions / Algorithms

# Algorithms

 Re: Help to predict the output of this code Daniel Pfeffer9-Jan-19 21:48 Daniel Pfeffer 9-Jan-19 21:48
 Re: Help to predict the output of this code ChrisFromWales1-May-19 0:14 ChrisFromWales 1-May-19 0:14
 Dinic’s algorithm for Maximum Flow AshishKhuraishy6-Dec-18 3:56 AshishKhuraishy 6-Dec-18 3:56
 Re: Dinic’s algorithm for Maximum Flow Patrice T25-Dec-18 16:15 Patrice T 25-Dec-18 16:15
 Vector representation of the code. Member 1406583326-Nov-18 7:50 Member 14065833 26-Nov-18 7:50
 Re: Vector representation of the code. Gerry Schmitz27-Nov-18 9:19 Gerry Schmitz 27-Nov-18 9:19
 Re: Vector representation of the code. shooky561-Dec-18 5:04 shooky56 1-Dec-18 5:04
 Optimal Task Scheduling with Complete Knowledge Member 140435574-Nov-18 12:11 Member 14043557 4-Nov-18 12:11
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:
1. The work is uniform (all Task units are exactly the same).
2. "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?
 Re: Optimal Task Scheduling with Complete Knowledge Mycroft Holmes4-Nov-18 19:31 Mycroft Holmes 4-Nov-18 19:31
 Re: Optimal Task Scheduling with Complete Knowledge Member 140435575-Nov-18 1:37 Member 14043557 5-Nov-18 1:37
 Re: Optimal Task Scheduling with Complete Knowledge Gerry Schmitz12-Nov-18 8:20 Gerry Schmitz 12-Nov-18 8:20
 Chess Futility pruning GM Fafkorn5-Oct-18 22:13 GM Fafkorn 5-Oct-18 22:13
 Algorithms help Member 139775798-Sep-18 7:36 Member 13977579 8-Sep-18 7:36
 Start with a group of size X, divide it into Y groups, Z times, minimize overlap Member 139396526-Aug-18 5:08 Member 13939652 6-Aug-18 5:08
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Stefan_Lang7-Aug-18 23:29 Stefan_Lang 7-Aug-18 23:29
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Gerry Schmitz8-Aug-18 8:38 Gerry Schmitz 8-Aug-18 8:38
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Stefan_Lang8-Aug-18 21:12 Stefan_Lang 8-Aug-18 21:12
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Gerry Schmitz9-Aug-18 9:52 Gerry Schmitz 9-Aug-18 9:52
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Stefan_Lang9-Aug-18 21:42 Stefan_Lang 9-Aug-18 21:42
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Kenneth Haugland9-Aug-18 22:25 Kenneth Haugland 9-Aug-18 22:25
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Gerry Schmitz11-Aug-18 9:19 Gerry Schmitz 11-Aug-18 9:19
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Gerry Schmitz10-Aug-18 7:38 Gerry Schmitz 10-Aug-18 7:38
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Stefan_Lang27-Aug-18 0:25 Stefan_Lang 27-Aug-18 0:25
 Re: Start with a group of size X, divide it into Y groups, Z times, minimize overlap Patrice T1-Sep-18 16:42 Patrice T 1-Sep-18 16:42
 Simplex Downhill... User 110609793-Aug-18 9:35 User 11060979 3-Aug-18 9:35
 Last Visit: 31-Dec-99 18:00     Last Update: 29-May-23 5:46 Refresh ᐊ Prev1...17181920212223242526 Next ᐅ

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.