Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects

Abstract

We consider single machine scheduling problems with deteriorating jobs and SLK/DIF due window assignment, where the deteriorating rates of jobs are assumed to be job-dependent. We consider two different objectives under SLK and DIF due window assignment, respectively. The first objective is to minimise total costs of earliness, tardiness, due window location and due window size, while the second objective is to minimise a cost function that includes number of early jobs, number of tardy jobs and the costs for due window location and due window size. We study the optimality properties for all problems and develop algorithms for solving these problems in polynomial time.

Keywords:

• scheduling
• due window assignment
• SLK/DIF rule
• job-dependent deteriorating rate

Acknowledgements

The authors thank the editor and the anonymous reviewers for their helpful comments and suggestions on earlier versions of the paper. This work is supported in part by NSF of China (Grants No.71125003, 71421002), and Specialized Research Fund for the Doctoral Program of High Education (20130073110066).