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...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.展开更多
We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of a...We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of all jobs and the total load on all machines.We show that the problems are polynomially solvable when the increasing rates are identical for all jobs;we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function,where the objective function is to minimize the total load on all machines.We also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time.The objective is to find a schedule which minimizes the time by which all jobs are delivered,and we propose a fully polynomial-time approximation scheme to solve this problem.展开更多
基金supported by the National Natural Science Foundation of China （Grant No.10101010）
文摘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.
基金This work was supported by the National Natural Science Foundation of China(Nos.11071142,11201259)the Natural Science Foundation of Shan Dong Province(No.ZR2010AM034)+1 种基金the Doctoral Fund of the Ministry of Education(No.20123705120001)We thank the two anonymous reviewers for their helpful and detailed comments on an earlier version of our paper.
文摘We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of all jobs and the total load on all machines.We show that the problems are polynomially solvable when the increasing rates are identical for all jobs;we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function,where the objective function is to minimize the total load on all machines.We also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time.The objective is to find a schedule which minimizes the time by which all jobs are delivered,and we propose a fully polynomial-time approximation scheme to solve this problem.
