Single Machine Slack Due-Window Assignment and Scheduling of Linear Time-Dependent Deteriorating Jobs and a Deteriorating Maintenance Activity

摘要

In this paper, we consider the slack due-window assignment model and study asingle machine scheduling problem of linear time-dependent deteriorating jobsand a deteriorating maintenance activity. The cost for each job consists offour components: earliness, tardiness, window location and window size. Theobjective is to schedule the jobs and to assign the maintenance activity anddue-windows such that the total cost among all the jobs is minimized. Apolynomial-time algorithm with the running time not exceeding $O(n^2logn)$ togive a solution to this problem is introduced, where $n$ is the number of jobs.