Polynomially solvable cases for scheduling deteriorating jobs with rejection

This paper considers the problem of scheduling proportionally deteriorating jobs with rejection on a single machine. Deteriorating job means that its actual processing time is a increasing function on its execution starting time. In this setting, jobs can be rejected by paying penalties. The objective is to minimize the makespan plus the total penalty incurred by rejecting jobs. It is known that this problem is NP-hard [13]. We show some polynomial-time solvable cases and propose the corresponding algorithm. Then we explore an modified criterion which can be solved polynomially.