具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。

Single Machine Scheduling with Precedence Constraints and Processing Time Dependent on Starting Time

This paper deals with the total weighted completion time single machine scheduling with constraints of series-parallel digraph and processing time dependent on starting time.We apply Lawler’s algorithm which is used to solve the total weighted completion time single machine with constraints of series-parallel digraph to our problem by proving the following theorem.Under the condition that job processing time being a linear function of the starting time,jobs in the ρ-maximal initial set I of module M should be processed prior to other jobs in module M,and the schedule is the optimal if the jobs in set I aren’t be preempted by the jobs in N/I.