2
$\begingroup$

I have a scenario, in which I have m independent jobs to be schedule on n workers parallely. Time required by each of these jobs is known. The problem is how to distribute these m independent jobs such that the total run time of completion of all the m jobs by the n workers is minimum.

One ad-hoc greedy approach I can think of is to sort the jobs by their run time and assign the jobs to workers such that each of them have almost similar run time for job completion.Is there a better approach? Thanks

$\endgroup$
  • $\begingroup$ This is an NP-complete problem. Do you want a faster algorithm, or a more correct algorithm? $\endgroup$ – Pål GD Jul 3 '18 at 21:56
  • $\begingroup$ I would like to evaluate all the options . So would like to explore both faster and more correct approach . $\endgroup$ – Always_Beginner Jul 4 '18 at 6:48
  • $\begingroup$ Well, you have to be more specific in your request. A faster algorithm is simply greedy without sorting. An exact algorithm you can get by brute force. There is also the concept of approximation algorithms (e.g with constant factor) that you haven't addressed yet. $\endgroup$ – Pål GD Jul 5 '18 at 15:37

Your Answer

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

Browse other questions tagged or ask your own question.