Single-machine rescheduling with deterioration and learning effects against the maximum sequence disruption

Abstract

In this paper, we study the issue of single-machine rescheduling with linear deteriorating jobs and position-based learning effects simultaneously in response to an unexpected arrival of new jobs. The scheduling efficiency is measured in terms of the makespan, while the cost of disruption is measured in terms of the maximum difference in processing orders of the original jobs before and after disruption. By introducing the effects of deterioration and learning, the job actual processing time is defined by an increasing function of its starting time, meanwhile a decreasing function of its position. Two types of problems are considered. For the first one, the makespan is minimised subject to a limit on the maximum sequence disruption; while in the second one, a linear combination of the makespan and the maximum sequence disruption is minimised. For each problem, the polynomial solvability is demonstrated, and an efficient algorithm is then developed. Finally, extensive computational experiments are conducted to show the efficiency and running behaviours of the proposed algorithms.

Keywords:

• rescheduling
• disruption
• single-machine
• learning effect
• deteriorating jobs
• makespan

Acknowledgements

The authors are grateful to the referees for their helpful comments on an earlier version of this paper. This study is financially supported by the Natural Science Foundation of China under Grant No. 71071008.

Additional information

Notes on contributors

Le Liu

Le Liu received his MS degree in management science and engineering from Shandong Normal University, Jinan, China, in 2009, and his PhD degree in management science and engineering from Beihang University, Beijing, China, in 2013. He is currently a lecturer in the School of Management at University of Jinan, Jinan, China. His research interests include production scheduling/rescheduling and intelligent computation.

Hong Zhou

Hong Zhou received his PhD degree in systems engineering from Shanghai Jiaotong University, Shanghai, China, in 1994. Currently, he is a professor of the School of Economics and Management, Beihang University (BUAA), Beijing, China. His main research interests include advanced meta-heuristics, production planning and scheduling, logistic systems optimisation, discrete system simulation with applications, etc.