The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect

摘要

In this paper, we analyse the single machine maximum lateness minimization scheduling problem with the processing time based aging effect, where the processing time of each job is described by a non-decreasing function dependent on the sum of the normal processing times of preceded jobs. The computational complexity of this problem was not determined. However, we show it is strongly NP-hard by proving the strong NP-hardness of the single machine maximum completion time minimization problem with this aging model and job deadlines. Furthermore, we determine the boundary between polynomially solvable and NP-hard cases.