# How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

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?

• 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. – D.W. Feb 24 '17 at 23:50
• @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) – Indo Ubt Feb 25 '17 at 7:32
• 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! – D.W. Feb 25 '17 at 17:52

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