There are $n$ jobs with different processing times, and they should be scheduled on $m$ identical machines such that the smallest completion time is as large as possible. This problem is NP-hard even for $m=2$, by reduction from partition. I am looking for an FPTAS for it.

I found an FPTAS for a very similar problem: making the largest completion time (the "makespan") as small as possible. It is in this paper:

Sartaj K. Sahni (1976). Algorithms for Scheduling Independent Tasks. Journal of the ACM. 23 (1): 116–127.

There is an algorithm that finds a schedule with makespan at most $1+\epsilon$ of the minimum in time $O(n\cdot (n^2 / \epsilon)^{m-1})$. This is an FPTAS for any fixed $m$.

For the original problem, which is to make the smallest finish time as large as possible, I only found a PTAS:

Gerhard Woeginger (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters. 20 (4): 149-154.

But the author considers it "impractical". Is there an FPTAS for this problem?

Alternatively, since the 1976 paper is quite hard for me to understand: is there a simpler FPTAS for minimizing the makespan, or a paper that explains the above FPTAS in a simpler way?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.