带树层次加工集约束的调度问题  

Scheduling with tree-hierarchical processing set restrictions

作　　者：张玉忠 李曙光[2] ZHANG Yuzhong;LI Shuguang(School of Operations Research,Qufu Normal University,Rizhao 276826,Shandong,China;College of Computer Science and Technology,Shandong Technology and Business University,Yantai 264005,Shandong,China)

机构地区：[1]曲阜师范大学运筹学研究院,山东日照276826 [2]山东工商学院计算机科学与技术学院,山东烟台264005

出　　处：《运筹学学报》2020年第4期107-112,共6页Operations Research Transactions

基　　金：国家自然科学基金(No.11771251);山东省自然科学基金重点项目(Nos.ZR2015GZ009,ZR201911140724);曲阜师范大学科研项目(No.xkj201504)。

摘　　要：研究工件带释放时间、送货时间和树层次加工集约束的调度问题。工件的加工开始时间不能早于它的释放时间,送货开始时间等于它的加工完成时间。所有机器形成一个树层次结构:若某机器能加工某工件,则该机器在树上的所有祖先均能加工该工件,这些机器构成该工件的加工集。目标是极小化最大送货完成时间。对于工件释放时间和送货时间任意的一般情形,给出了一个多项式时间近似方案(PTAS)。The problem of scheduling with release times,delivery times and treehierarchical processing set restrictions is considered.Each job cannot begin processing before its release time,and its delivery begins immediately after processing has been completed.The machines form a tree hierarchical structure:any job requesting a certain machine may be assigned to any of its ancestors in the tree,and the set of these machines is the job’s processing set.The objective is to minimize the maximum delivery completion time,i.e.,the time by which all jobs are delivered.A polynomial time approximation scheme(PTAS)is presented when the jobs have both unequal release times and unequal delivery times.

关 键 词：调度 并行机 树层次加工集约束 送货时间 多项式时间近似方案 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]