科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we study two problems of scheduling a set of linear deteriorating non-resumable jobs on a single machine with a mandatory maintenance. The maintenance has to be started prior to a given deadline. Not only the jobs but also the maintenance are required to be scheduled. Two goals are investigated. One is to minimize the makespan and the other is to minimize the total completion time. For both objectives, we show that two problems are weakly NP-hard and propose fully polynomial time approximation schemes respectively.
