Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started can be used again only after it's job is done. What's the optimal way to schedule these jobs on the machines?

  • $\begingroup$ What algorithm design paradigms have you considered? Have you tried greedy algorithms? Have you tried dynamic programming? This looks like a nice exercise, but you should do your own exercises. We want you to try everything you can and show us in the question what effort you've made and where you got stuck. Take a look at cs.stackexchange.com/tags/dynamic-programming/info and cs.stackexchange.com/q/59964/755. $\endgroup$ – D.W. Feb 24 '17 at 23:50
  • $\begingroup$ @D.W. I think the solution is to go greedy and take the machine available with the least time. But I have no idea if it's right or how to go with it's implementation (what data structure etc) $\endgroup$ – Indo Ubt Feb 25 '17 at 7:32
  • $\begingroup$ See the question I linked to (cs.stackexchange.com/q/59964/755) for an explanation of how to tell whether your idea is right or not! $\endgroup$ – D.W. Feb 25 '17 at 17:52

This problem lends itself to Mixed Integer Programming. The trick is to consider that there are multiple versions of each job for each machine, and you have to cover each job once.

So you can have $c_{j,m}$ as the indicator variables that say if a job is assigned to a machine. You have to introduce a constraint that says $$\sum_m c_{j,m} \geq 1.$$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.