The problem of scheduling jobs with release and delivery time subject to machine eligibility constraints is considered.The eligible sets of the jobs are nested,and pre-emptions are not allowed.The goal is to minimize ...The problem of scheduling jobs with release and delivery time subject to machine eligibility constraints is considered.The eligible sets of the jobs are nested,and pre-emptions are not allowed.The goal is to minimize the maximum delivery completion time,i.e.,the time by which all jobs are delivered.For the special case of equal release time,a 2-approximation algorithm is presented whose running time depends linearly on the number of jobs.For the general case of unequal release time,a polynomial time approximation scheme is derived.展开更多
基金This work was supported by the National Natural Science Foundation of China(No.11771251)Key project of Shandong Provincial Natural Science Foundation of China(No.ZR2015GZ009)Shandong Provincial Education Reform Project(No.2015M098).
文摘The problem of scheduling jobs with release and delivery time subject to machine eligibility constraints is considered.The eligible sets of the jobs are nested,and pre-emptions are not allowed.The goal is to minimize the maximum delivery completion time,i.e.,the time by which all jobs are delivered.For the special case of equal release time,a 2-approximation algorithm is presented whose running time depends linearly on the number of jobs.For the general case of unequal release time,a polynomial time approximation scheme is derived.
