Viewpoint on “A note on unrelated parallel machine scheduling with time-dependent processing times”

Abstract

In a recent article, Kuo et al study an unrelated parallel machine scheduling problem in which the processing time of a job is a linear function of its start time and the objective is to minimize the sum of job completion times (Kuo et al, 2008). They show that the problem is polynomial-time solvable when the number of machines is fixed. However, the computational complexity of their solution method is high. We provide here a modified solution method with an improved running time complexity.