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

Scheduling with tree-hierarchical processing set restrictions

研究工件带释放时间、送货时间和树层次加工集约束的调度问题。工件的加工开始时间不能早于它的释放时间,送货开始时间等于它的加工完成时间。所有机器形成一个树层次结构:若某机器能加工某工件,则该机器在树上的所有祖先均能加工该工件,这些机器构成该工件的加工集。目标是极小化最大送货完成时间。对于工件释放时间和送货时间任意的一般情形,给出了一个多项式时间近似方案(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.