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

来源：计算数学杂志2017年第4期北京时间：

作者：李金权

单位：北京师范大学珠海分校应用数学学院, 珠海 519087

摘要：本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题，利用relocation约束的性质和贪婪算法的思想，设计了一个多项式近似算法，并证明了当链不可中断，每个链具有相同工件数和工件间具有相同加工时间时，2为该算法的紧界.

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

基金资助：<p>国家自然科学基金资助项目（11401030）；广东省高等学校优秀青年教师培养计划项目（2014年度，Yq2014228）；珠海市智能控制重点实验室建设项目.</p>