A note on minimizing the sum of quadratic completion times on two identical parallel machines

We consider the problem of minimizing the sum of quadratic completion times on two parallel machines and we discuss the approximation ratio of the generalized shortest processing time (GSPT) priority rule according to which the jobs are sorted in non-decreasing processing time order and the next job on the list is assigned to the earliest available machine. We show that the approximation ratio of the GSPT   rule is bounded above by 5+25+1≈1.309 and below by 6+26+1≈1.290. Extensions to the parallel m-machine problem are also discussed.

► Generalized shortest processing time (GSPT) is an index priority rule for machine scheduling. ► We discuss the approximation ratio of GSPT when minimizing the sum of quadratic completion times on parallel machines. ► For two machines the approximation ratio of GSPT is bounded above by 1.309 and below by 1.290. ► For m machines the optimality gap of GSPT is more than 3% for large problems with as many as 1000 machines.