摘要
针对考虑机器适用性的相同工件平行机调度问题,提出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