<p>I found the solution of the solution of this algorithm in this book: <a href="http://rads.stackoverflow.com/amzn/click/1584883979" rel="nofollow">Handbook of Scheduling: Algorithms, Models, and Performance Analysis</a> . </p>

<ul>
<li>In Theorem 3.4, they show an optimal algorithm for the preemptive case.</li>
<li>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</li>
</ul>

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

CC BY-SA 3.0
2013-10-26T05:11:36.407Z
2013-10-26T05:43:59.293Z
2013-10-26T05:43:59.293Z
Masood_mj
<p>I think this should be a famous problem but I could not find its name.</p>

<p>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.</p>

<p>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. </p>

<p>Is there any greedy algorithm (with approximation bound) for this generalized version?</p>

CC BY-SA 3.0
2013-10-24T20:45:13.523Z
I think "machine scheduling problem", maybe "bin packing problem", ...
usul
CC BY-SA 3.0
2013-10-24T20:53:02.720Z
It seems that it is called "Job Shop problem" http://en.wikipedia.org/wiki/Job_shop_scheduling. But all the papers I found are about online planning but I need an OFFLINE algorithm.
Masood_mj
CC BY-SA 3.0
2013-10-25T16:30:49.623Z
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).
Saeed
<approximation-algorithms><partition-problem><greedy-algorithms>
Planning jobs as partition problem
Masood_mj
# Planning jobs as partition problem

(Asked by: username_0 on 2013-10-24)

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?

**Tags:** approximation-algorithms, partition-problem, greedy-algorithms
> **Comments:**
> **username_1**: I think "machine scheduling problem", maybe "bin packing problem", ...  
> **username_0**: It seems that it is called "Job Shop problem" http://en.wikipedia.org/wiki/Job_shop_scheduling. But all the papers I found are about online planning but I need an OFFLINE algorithm.  
> **username_2**: 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).  

---

## 1 answers

### Answer by username_0 on 2013-10-26. Score: 0 | Accepted answer

I found the solution of the solution of this algorithm in this book: [Handbook of Scheduling: Algorithms, Models, and Performance Analysis](http://rads.stackoverflow.com/amzn/click/1584883979) .

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


---

