Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

Abstract

In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.

Keywords:

• scheduling
• single machine
• deteriorating jobs
• total absolute differences in waiting times
• heuristic algorithm

Acknowledgements

We are grateful to the anonymous referees for their helpful comments on an earlier version of this paper. This research was supported by the Science Research Foundation of the Educational Department of Liaoning Province, China, under Grant number 20060662. This research was also supported by the Science Research Foundation of State Key Laboratory for Manufacturing Systems Engineering and Key Laboratory of the Ministry of Education on Process Control and Efficiency, Xi’an Jiaotong University, China.