Single-machine scheduling problems with a sum-of-processing-time-based learning function (Q606421)

Summary: Recently, learning scheduling problems have received increasing attention. However, the majority of the research assume that the actual job processing time is a function of its position. This paper deals with the single-machine scheduling problem with a sum-of-processing-time-based learning effect. By the effect of sum-of-processing-time-based learning, we mean that the processing time of a job is defined by total normal processing time of jobs in front of it in the sequence. We show that the single-machine makespan problem remains polynomially solvable under the proposed model. We show that the total completion time minimization problem for \(a\geq 1\) remains polynomially solvable under the proposed model. For the case of \(0<a<1\), we show that an optimal schedule of the total completion time minimization problem is \(V\)-shaped with respect to normal job processing times.