Worst-case error bounds for parallel machine scheduling problems with bounded sequence-dependent setup times

The authors consider minimizing makespan (Cmax) and maximum lateness (Lmax) on parallel identical machines with sequence-dependent setup times. They show that the optimal schedule need not be a list schedule. Motivated by a practical scheduling problem, the authors study the class of problems where setup times are bounded by processing times and develop tight worst case error bounds for list scheduling algorithms to minimize Cmax and Lmax.