Approximation schemes for scheduling a maintenance and linear deteriorating jobs

In this paper, we study two problems of scheduling a set of linear deteriorating non-resumable jobs on a single machine with a mandatory main-tenance. 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.