I think this should be a famous problem but I could not find its name.

I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines. How can I assign jobs to machines to minimize the maximum finish time.

I know that when the offering times $t_i$s are equal, this is a partition problem as it balances the jobs over machines. Also I know that there are approximation algorithms for that.

Is there any greedy algorithm (with approximation bound) for this generalized version?

  • $\begingroup$ I think "machine scheduling problem", maybe "bin packing problem", ... $\endgroup$
    – usul
    Oct 24, 2013 at 20:45
  • $\begingroup$ It seems that it is called "Job Shop problem" en.wikipedia.org/wiki/Job_shop_scheduling. But all the papers I found are about online planning but I need an OFFLINE algorithm. $\endgroup$
    – Masood_mj
    Oct 24, 2013 at 20:53
  • 1
    $\begingroup$ Seems this is a variation of minimum makespan scheduling (actually jobs start time is may be a new variation, but it has many variations). And there is a simple greedy algorithm of factor 2, when all jobs are available at time 0. Also there is a PTAS if machines are same as each other (by using dynamic programming on bin packing with error , you can find it in vazirani's approximation algorithm book). $\endgroup$
    – Saeed
    Oct 25, 2013 at 16:30

1 Answer 1


I found the solution of the solution of this algorithm in this book: Handbook of Scheduling: Algorithms, Models, and Performance Analysis .

  • In Theorem 3.4, they show an optimal algorithm for the preemptive case.
  • The largest processing time first algorithm has worst case bound of $\frac{4}{3} − \frac{1}{3k} $ if $t_i=0, \forall i$ for non-preemptive case

I will apply this largest processing time first to the general case and see how it works in practice.


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.