Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities
研究单机调度中同时考虑到期日分配、作业加工时间随位置和维修次数恶化、以及维修时间随开始时间恶化的问题，为不同版本提供多项式时间算法。
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.