0
$\begingroup$

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?

$\endgroup$
3
  • $\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.
    Commented Feb 24, 2017 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
    Commented Feb 25, 2017 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.
    Commented Feb 25, 2017 at 17:52

1 Answer 1

1
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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