Single-Machine Scheduling Problems with a Sum-of-Processing-Time-Based Learning Function

Abstract EN

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≥1 remains polynomially solvable under the proposed model.

For the case of 0