一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究  

MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME FOR THE RELOCATION SCHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS

作　　者：李金权 

机构地区：[1]北京师范大学珠海分校应用数学学院,珠海519087

出　　处：《计算数学》2017年第4期421-430,共10页Mathematica Numerica Sinica

基　　金：国家自然科学基金资助项目(11401030);广东省高等学校优秀青年教师培养计划项目(2014年度;Yq2014228);珠海市智能控制重点实验室建设项目

摘　　要：本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.In this paper, the relocation scheduling problem with precedence constraints is investi- gated, where objective function is total weighted completion time. A polynomial algorithm is proposed for this kind of NP-hard scheduling problems based on the properties of relocation constraints and greedy rule. Also, it is proved that the performance ratio of the algorithm is 2 when each of chains is not nonpreemptive, and has the same jobs with the same processing times.

关 键 词：Relocation资源约束 优先加工约束 调度 加权总完工时间 

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