Single machine group scheduling with learning effects and past-sequence-dependent setup times

Abstract

In most studies, the learning effect model applied in a scheduling problem assumes that the actual processing time of a job is a function of its scheduled position or the sum of the normal processing times of the jobs already scheduled. In this article, we introduce a learning effect model and a past-sequence-dependent (psd) setup time into a single machine group scheduling problem. The actual processing time of a job in each group is a function of the sum of the normal processing times of the jobs already scheduled and the position of the corresponding job group in the sequence. It shows that the addressed problem remains polynomially solvable for the objectives: minimisation of the makespan and the total completion time. It also shows that the smallest processing time rule provides the optimal jobs sequence in each group and the optimal group sequence for the addressed problem, respectively.

Keywords:

• single-machine
• time-dependent
• learning effect
• group scheduling
• SPT rule