Graham's 4/3-approximation for makespan on parallel machines,
or P||Cmax
We are given n jobs. Each job j has a
processing
time pj. We wish to find a schedule
for m parallel machines, which minimizes the maximal
completion time. This problem is unary NP-hard, but there is a polynomial time
approximation scheme (PTAS) but with high complexity,
and for a fixed number of machines even a fully polynomial time approximation scheme (FPTAS).
Algorithm by Graham:
Process jobs in order of decreasing processing times and
place them on the least charged machine.
Input
Output