0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think "machine scheduling problem", maybe "bin packing problem", ... $\endgroup$ – usul Oct 24 '13 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 '13 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 '13 at 16:30
0
$\begingroup$

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.

$\endgroup$

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.