Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints  

作　　者：Yu-Zhong Zhang Shu-Guang Li 

机构地区：[1]Institute of Operations Research,Qufu Normal University,Rizhao 276826,Shandong,China [2]Key Laboratory of Intelligent Information Processing in Universities of Shandong(Shandong Institute of Business and Technology),Yantai 264005,Shandong,China [3]College of Computer Science and Technology,Shandong Institute of Business and Technology,Yantai 264005,Shandong,China

出　　处：《Journal of the Operations Research Society of China》2021年第1期63-77,共15页中国运筹学会会刊（英文）

基　　金：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.

关 键 词：SCHEDULING Nested eligibilityconstraints Release time Deliverytime Polynomial timeapproximationscheme 

分 类 号：O24[理学—计算数学]