Single-Machine Scheduling with Due-Window Assignment and Rate-Modifying-Activities under a Deteriorating Maintenance

摘要

This paper studies single-machine scheduling problems with a due-window assignment and a rate-modifying activity under a deteriorating maintenance consideration simultaneously. Jobs completed within the due-window incur no penalties, other jobs incur either earliness or tardiness penalties. The maintenance activity can be scheduled immediately after any one of the completed jobs. We assume that once the maintenance activity has been completed, the machine efficiency will be improved and the machine maintenance duration depends on its starting time. The objective is to find the optimal maintenance position as well as the optimal size and location of the due-window, and the sequence of jobs to minimize a cost function based on the window size and window location and the earliness and tardiness of the jobs. We propose a polynomial time algorithm to solve the problem optimally.