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.


number of machines
processing times
zoom x2