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

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

作　　者：王吉波[1] 

机构地区：[1]沈阳航空工业学院理学系,沈阳110034

出　　处：《中国管理科学》2005年第2期51-55,共5页Chinese Journal of Management Science

基　　金：教育部博士点基金资金资助项目(20020141013)

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

关 键 词：排序 单机 线性加工时间 串并有向图 加权总完工时间 

分 类 号：O223[理学—运筹学与控制论] C931[理学—数学]