基于蚁群算法的资源均衡优化决策及其MATLAB实现

摘要/Abstract

摘要：

资源均衡问题已被证明属于组合优化中的NP-hard问题，随着网络计划的复杂化，传统的数学规划法和启发式算法已很难解决该问题。本文以各种资源标准差的加权之和作为衡量资源均衡的评价指标，建立了资源均衡优化决策的数学模型，其次，自行设计蚁群算法步骤，利用Matlab编程进行实现，将蚂蚁随机分布在可行域中，蚂蚁根据转移概率进行全局搜索或局部搜索，经迭代求解资源平衡的全局最优和对应的各工序的开始工作时间，最后使用单资源均衡和多资源均衡两个算例对算法进行了测试，验证了该算法的有效性。

关键词: 资源均衡, 蚁群算法, 优化决策

Abstract:

The resource leveling problem has been shown to belong to NP-hard problem in combinatorial optimization. As the network becomes complex, it is difficult to solve the problem with traditional mathematical programming and the heuristic algorithms. The sum of standard deviation of resources is used as the measure of resource leveling, and a mathematical model of resource leveling optimization decisions is built. Secondly, using Matlab, design steps of ant colony algorithm are realized, and using ant colony algorithm, the scope of the non-critical process start work time determined, the ants randomly distributed in the feasible region. Then the ants will conduct global search and local search according to the transition probability, to solve the global optimization of resource leveling. Finally, a single resource leveling and multi-resource leveling are taken for examples, to verify the effectiveness of ant colony algorithm. The convergence speed of the algorithm is fast, and it overcomes the defects of traditional algorithm of easily falling into local optimum, and it is suitable for solving the problems of all resources leveling, with good generality. But the optimization model of this paper assumes that any activity must be in continuous construction, and in between all kinds of resources are independent of each other. It is often not consistent with actual situation, and future research can be further optimized, and the ant colony algorithm can be combined with other algorithms to solve the problem.

Key words: resource leveling, ant colony algorithm, optimization decision

何利娟1, 李欣2. 基于蚁群算法的资源均衡优化决策及其MATLAB实现[J]. 工业工程.

He Li-juan, Li Xin. Resource Leveling Based on Ant Colony Algorithm and MATLAB Optimization Decision[J]. Industrial Engineering Journal .

参考文献

［1］Chan W T, Chua D K H, Kannan G. Construction resource scheduling with genetic algorithms［J］.Journal of Construction Engineering and Management, 1996,122(2): 125-131.
［2］Leu S S, Yang C H. GA-based multicriteria optimal model for construction scheduling［J］. Journal of Construction Engineering and Management, 1999,125(6): 420-427.
［3］Tarek Hegazy. Optimization of resource allocation and leveling using genetic algorithms［J］. Journal of Construction Engineering and Management, 1999,125(3): 167-175.
［4］Jose Luis Ponz-Tienda, Víctor Yepes, Eugenio Pellicer, et al. The resource leveling problem with multiple resources using an adaptive genetic algorithm［J］. Automation in Construction,2013,29(1)：161-172.
［5］田军，寇纪凇，李敏强.利用遗传算法优化施工网络计划［J］.系统工程理与实践,1999,19(5)：78-82.
Tian Jun, Kou Ji-song,Li Min-qiang. Using genetic algorithm to optimize the resources in arrow network techniques［J］.Journal of Systems Science and Information, 1999,19(5)：78-82.［6］付宗仁.基于遗传算法的多资源平衡工序排序优化决策［J］.装备制造技术,2012(8):269-271.
Fu Zong-ren. Multiple resources leveling balancing process sequence optimization based on genetic algorithm［J］.Equipment Manufacturing Technology, 2012(8):269-271.
［7］欧阳红祥，刘炳胜，李欣.网络计划多资源均衡优化遗传算法［J］.武汉理工大学学报(信息与管理工程版),2013，35(2):180-182.
Ouyang Hong-xiang, Liu Bing-sheng, Li Xin.Network planning multiple resources leveling optimization based on genetic algorithm［J］. Journal of Wuhan University of Technology(Information & Management Engineering), 2013,35(2):180-182.
［8］Dorigo M. Optimization, learning and natural algorithms［D］. Milan: Department Tidy Electronics，Politecnicodi Milano,1992.
［9］Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents［J］. IEEE Transactions on Systems Man, and Cybernetics, Part B, 1996, 26(1): 29- 61.
［10］马良，朱刚，宁爱兵.蚁群优化算法［M］.北京:科学出版社， 2008.
［11］李丽香，彭海朋，杨义先.混沌蚁群算法及应用［M］. 北京:中国科学技术出版社，2013.
［12］Liao T J, Stützle T, Montes de Oca M A, et al. A unified ant colony optimization algorithm for continuous optimization［J］.European Journal of Operational Research, 2014, 234(3):597-609.
［13］Dréo J, Siarry P. Continuous interacting ant colony algorithm based on dense hierarchy［J］．Future Generation Computer Systems,2004,20(5)：841-856．
［14］Li Y J, Wu T J. An adaptive ant colony system algorithm for continuous space optimization problems［J］.Journal of Zhejiang University(Science),2003,4(1)：40-46.
［15］Leu S S, Yang C, Huang J C. Resource leveling in construction by genetic algorithm-based optimization and its decision support system application［J］. Automation in Construction, 2000,10(1):27-41.

[1]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[2]	刘电霆, 胡浩平, 吴丹玲. 社会化产品开发众包设计任务间加权网络建模与模块划分[J]. 工业工程, 2021, 24(5): 95-100.
[3]	周晓晔, 马小云, 崔瑶, 王思聪. 单线超市车辆配置与路径问题优化研究[J]. 工业工程, 2020, 23(6): 83-88,116.
[4]	初梓豪, 徐哲, 李明, 顾坤. 随机多模式资源均衡问题建模与求解[J]. 工业工程, 2017, 20(3): 95-105.
[5]	周娜, 舒帆, 金佩卿. 基于混合启发式算法的设备混合布局问题[J]. 工业工程, 2017, 20(1): 77-82.
[6]	阮焕1，耿亮1,2，肖人彬1. 基于极值—蚁群算法的电商末端物流弹性配送策略研究[J]. 工业工程, 2016, 19(1): 51-60.
[7]	廖婷婷，徐哲，李明. 软件开发项目多技能人力资源均衡调度模型[J]. 工业工程, 2015, 18(3): 69-74.
[8]	项薇1, 殷姣1, 陈赛峰2 . 考虑实际护士排班约束的手术排程优化[J]. 工业工程, 2013, 16(5): 120-124.
[9]	李英俊，陈志祥. 基于改进蚁群算法的一类运输能力约束的生产-运输批量问题求解[J]. 工业工程, 2012, 15(6): 119-125.
[10]	屈国强1，2，李俊芳1，侯东亮1，3. 蚁群系统结合指派规则求解HFS调度问题[J]. 工业工程, 2012, 15(3): 62-68.
[11]	张毕西，张万里，宋静. 基于蚁群算法的中小手工制造企业人员调度 [J]. 工业工程, 2011, 14(4): 119-123.