Scheduling Mixed Deteriorating Jobs on a Single Machine for Makespan Minimization

A set of jobs has to be scheduled on a single machine starting from a non-zero time. The processing time of one job from the set is a quadratic non-decreasing function of its start time, while the processing times of the other jobs are proportional non-decreasing functions of their start times. The objective is to minimize the makespan. We present a criterion for optimally scheduling a job with proportional processing time alongside the job with quadratic processing time. We identify some polynomially solvable cases and provide for the remaining cases an upper bound on the starting time of the job with quadratic processing time. Additionally, we establish the NP-hardness of this problem and propose a pseudo-polynomial-time optimal algorithm and a fully polynomial-time approximation scheme.