An approximation algorithm for parallel machine scheduling with simple linear deterioration
In this paper, a parallel machine scheduling problem was considered, where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.
NETL
NSTL
万方数据
