Scheduling step-deteriorating jobs to minimise the total weighted tardiness on a single machine

ABSTRACT

This paper addresses the scheduling problem of minimising the total weighted tardiness on a single machine with step-deteriorating jobs. With the assumption of deterioration, the job processing times are modelled by step functions of job starting times and pre-specified job deteriorating dates. The introduction of step-deteriorating jobs makes the single-machine total weighted tardiness problem more intractable. Until now, the computational complexity of this problem under consideration was not determined. In this study, it is proved to be strongly NP-hard. Then, a linear ordering mixed-integer programming model is derived for solving the problem instances optimally. In order to tackle large-sized problems, seven dispatching heuristic procedures are developed for near-optimal solutions. Meanwhile, the solutions delivered by the proposed heuristics are further improved by a pairwise swap movement. Computational results are presented to reveal the performance of all proposed approaches.

KEYWORDS:

• scheduling
• single machine
• total weighted tardiness
• step-deteriorating jobs
• heuristics
• NP-hardness

Acknowledgements

This work is supported by the National Natural Science Foundation of China (No. 51405403) and the Fundamental Research Funds for the Central Universities (No. 2682014BR019).

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [grant number 51405403]; the Fundamental Research Funds for the Central Universities [grant number 2682014BR019].

Notes on contributors

Peng Guo

Peng Guo obtained his BS degree in Industrial Engineering and PhD degree in Mechanical Engineering from Southwest Jiaotong University in 2009 and 2014, respectively. He is currently a lecturer with School of Mechanical Engineering, Southwest Jiaotong University. His research interests include engineering optimization, production scheduling and service operation management.

Wenming Cheng

Wenming Cheng received his PhD degree in Mechanical Engineering from Southwest Jiaotong University, China in 2000. He is presently a professor in School of Mechanical Engineering, Southwest Jiaotong University. His research interests include industrial engineering, logistics facility, mechanical system design and reliability engineering.

Yi Wang

Yi Wang earned his second PhD in Mathematics from West Virginia University, USA in 2003, and his first PhD in Mechanical Engineering from Southwest Jiaotong University, China in 1997. He is a professor of mathematics in the Department of Mathematics and Computer Science, Auburn University at Montgomery. His current research interests include optimization problems in engineering, reliability analysis, and signal and image processing.