单位加工时间有链约束的恒速机排序问题

Scheduling Unit Length Jobs on Uniform Machines Subject to Chain-like Precedence Constraint

Brucker,Hurink,Kubiak(1999)〔1〕关于有链约束的两台恒速机排序问题Q2|chains,pj=1|Cmax提出了一个多项式时间算法.在文章中,我们考虑目标函数为完工时间和的问题即Q2|chains,pj=1|∑Cj,建立了该问题与问题Q2|chains,pj=1|Cmax的一个联系,即证明了若按问题Q2|chains,pj=1|Cmax的最优排序S,且每台机器在结束加工之前无空闲,则S也是问题Q2|chains,pj=1|∑Cj的最优排序.

For the problem of scheduling unit length jobs subject to chain - like precedence constraints on two uniform machines, Brucker, Hurink, Kubiak （1999） showed that the problem of minimizing can be solved in linear time. In this paper, we consider the problem of minimizing and establish a connection between the two objectives. We prove that if both machines have no idle time before their completion times in some optimal schedule S with respect to the objective, then S is also optimal with respect to the objective.