A generalisation model of learning and deteriorating effects on a single-machine scheduling with past-sequence-dependent setup times

Abstract

This article introduces a general single-machine setup times scheduling model with learning effect and deteriorating jobs simultaneously which is a generalisation of some existing models in the literature. The setup times are proportional to the length of the already processed jobs, i.e. the setup times are past-sequence-dependent (p-s-d). By the effects of learning and deterioration, we mean that the actual processing time of a job depends not only on the starting time of the job but also on its scheduled position. The article shows that the problems to minimise the makespan, sum of the kth power of completion times, total lateness and sum of earliness penalties (with common due date) are polynomially solvable under the proposed model. It further shows that the problems to minimise total weighted completion time, maximum lateness, maximum tardiness, total tardiness and total weighted earliness penalties (with common due date) are polynomially solvable under certain conditions.

Keywords:

• scheduling
• single-machine
• learning effect
• deteriorating jobs

Acknowledgements

The authors would like to express our warmest thanks to the referees for their interest in our work and their valuable comments for improving the article. This article was supported in part by the Natural Science Foundation for Young Scholars of Jiangxi, China (2010GQS0003); in part by the Science Foundation of Education Committee for Young Scholars of Jiangxi, China (GJJ11143) and in part by the NSC under grant number NSC 99-2221-E-035-057-MY3.