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?
Planning jobs as partition problem
approximation algorithms;partition problem;greedy algorithms
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 caseI will apply this largest processing time first to the general case and see how it works in practice.