期刊文献+

具有机器适用性约束的相同工件平行机近似调度算法

An approximation algorithm for scheduling identical jobs on parallel machines with machine eligibility constraints
下载PDF
导出
摘要 针对考虑机器适用性的相同工件平行机调度问题,提出1种二阶段近似调度算法。算法建立了问题的半匹配模型G=[J∪M,E,W],将原问题转化为最优半匹配搜索问题,然后通过初始解构造和优化得到问题的近似解。通过分析G=[J∪M,E,W]的拓扑统计信息对机器均载的影响,设计了初始解构造启发式规则。在此基础上,采用贪心原理,提出了基于启发式规则的初始解构造算法。初始解优化算法以初始解为起点,采用基于交错路径的局部优化方法得到近似解。通过交错路径树,搜索最优交错路径是影响初始解优化算法的重要因素。为提高搜索效率,限定交错路径的最大长度为4。最后,从理论上分析了算法的最坏情况界和时间复杂度。 Atwo-phase approximationalgorithm isproposed for scheduling identical jobsonparallelmachineswithmachine eligi-bility constraints. A semi-matching model G = [ J∪ M ,E ,W]is presented to convert this scheduling semi-matching searching problem A two-phase algorithm is used to obtain an approximation solution,which consists of two pha- ses,the initial solution construction phase and the initial solution improvement phase. Topological analysis of the weighted bipar-tite graph G=[ J ∪M ,E ,W]is performed to speed up workload balancing. The initial solution oped to build a feasible solution by performing a simple greedy method,which is based on heuristics using l^he l^opological informa-tion of G. The initial solution is used as a starting point in l^he improvement algorithm. The proposed improvement algorithm is a local imp^ovement method based on alternating path,which improves the mitial solution to the near-optimal solution. The main -dea of the improvement algorithm s to find the optimal alternating path by constructing efficiency,the length of each path in alternating tree is limited to 4 at most At last, the worst-case ratio and time complexity ofthe proposed algorithm are analyzed.
作者 展勇 徐建安 曲东越 ZHANYon g;XUJian'n;QUDongyue(College ofMechanical & Electrical Engineering, Harbin Engineering University, Harbin 150001, China)
出处 《中国科技论文》 北大核心 2017年第22期2575-2580,共6页 China Sciencepaper
基金 高等学校博士学科点专项科研基金资助项目(20132304120021)
关键词 制造工程 平行机 相同工件 机器适用性 半匹配 近似算法 manufacturing engineering parallel machine identical jobs machine eligibility semi-matching approximation algo-rithm
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部