Parallel machine scheduling problems with proportionally deteriorating jobs

This article considers two scheduling problems on parallel identical machines with deteriorating jobs, in which the processing time of job is proportional function of its starting times to be processed. Namely, for job j, pj = bjt, where bj > 0 is its deterioration rate, t = t0 > 0 is its starting time and t0 is a given constant. The criteria of optimality are minimising the makespan and maximising the minimum machine completion time. It has been proved that the first problem is NP-hard; we prove that the second problem is also NP-hard. For both problems heuristic algorithms are constructed and their performance is analysed.