Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities

Abstract

This paper addresses a single-machine scheduling problem with simultaneous consideration of due-date assignment, generalised position-dependent deteriorating jobs, and deteriorating maintenance activities. It is assumed that the actual processing time of a job is a general non-decreasing function depending on the number of maintenance activities performed before it and its position in a sequence. Moreover, the machine may be subject to several maintenance activities up to a limit over the scheduling horizon. The maintenance activities do not necessarily restore the machine fully to its original perfect state and the duration of a maintenance activity depends on its start time. The objective is to find jointly the optimal job sequence, maintenance frequency and maintenance positions to minimise an objective function that includes the cost of due-date assignment, the cost of discarding jobs that cannot be completed by their due dates and the earliness of the scheduled jobs under the popular CON and SLK due-date assignment methods. We provide polynomial-time solution algorithms for various versions of the problem.

Keywords:

• scheduling
• deteriorating jobs
• deteriorating multi-maintenance activities
• due-date assignment

Acknowledgments

We are thankful to the Editor and two anonymous referees for their valuable comments and suggestions that help improve our paper.