# Planning jobs as partition problem

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?

• I think "machine scheduling problem", maybe "bin packing problem", ...
– usul
Oct 24 '13 at 20:45
• 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. Oct 24 '13 at 20:53
• 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). Oct 25 '13 at 16:30

## 1 Answer

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.