科研之友
微信
新浪微博
Facebook
分享链接
摘要
We investigate a single machine scheduling problem in which the processing time of a job is a linear function of its starting time and a variable maintenance on the machine must be performed prior to a given deadline. The goals are to minimize the makespan and the total completion time. We prove that both problems are NP-hard. Furthermore, we show that there exists a fully polynomial time approximation scheme for the makespan minimization problem. For the total completion time minimization problem we point out that there exists a fully polynomial time approximation scheme for a special case.
