《工程(英文)》 >> 2021年 第7卷 第6期 doi: 10.1016/j.eng.2021.04.011
基于网络图拓扑结构的MILP模型求解智能制造系统中的工艺规划问题
State Key Laboratory of Digital Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
下一篇 上一篇
摘要
智能工艺规划是智能制造系统中的重要组成部分。从制造流程角度出发,工艺规划(process planning, PP)连接着产品设计和实际生产,有着承上启下的关键作用。PP属于非确定性多项式时间困难(NP-hard)问题,现有的问题模型都是非线性形式,因此不能够通过求解现有模型来得到问题的精确解。从工艺网络图的拓扑结构出发,本文提出了一个全新的混合整数线性规划(mixedinteger linear programming, MILP)数学模型,并通过三种优先关系矩阵讨论了网络图中工序的优先关系。该模型能够凭借常用的数学模型求解器,如CPLEX、Gurobi等,来搜寻并获得大部分算例的最优解。该模型通过在5组公开的著名数据集上的测试,证明了其通用性和有效性。实验结果有力地说明了所提模型能够有效地解决工艺规划问题,并获得比当前最先进算法更好的解。
参考文献
[ 1 ] Zhou J, Li P, Zhou Y, Wang B, Zang J, Meng L. Toward new-generation intelligent manufacturing. Engineering 2018;4(1):11–20. 链接1
[ 2 ] Zhong RY, Xu X, Klotz E, Newman ST. Intelligent manufacturing in the context of industry 4.0: a review. Engineering 2017;3(5):616–30. 链接1
[ 3 ] Zhou J, Zhou Y, Wang B, Zang J. Human–cyber–physical systems (HCPSs) in the context of new-generation intelligent manufacturing. Engineering 2019;5 (4):624–36. 链接1
[ 4 ] Leo Kumar SP. State of the art-intense review on artificial intelligence systems application in process planning and manufacturing. Eng Appl Artif Intell 2017;65:294–329. 链接1
[ 5 ] Miljkovic´ Z, Petrovic´ M. Application of modified multi-objective particle swarm optimisation algorithm for flexible process planning problem. Int J Comput Integrated Manuf 2017;30(2–3):271–91. 链接1
[ 6 ] Xu X, Wang L, Newman ST. Computer-aided process planning—a critical review of recent developments and future trends. Int J Comput Integrated Manuf 2011;24(1):1–31. 链接1
[ 7 ] Li X, Gao L, Pan Q, Wan L, Chao KM. An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE Trans Syst Man Cybern Syst 2019;49 (10):1933–45. 链接1
[ 8 ] Li X, Gao L, Wen X. Application of an efficient modified particle swarm optimization algorithm for process planning. Int J Adv Manuf Technol 2013;67 (5–8):1355–69. 链接1
[ 9 ] Gan PY, Lee KS, Zhang YF. A branch and bound algorithm based processplanning system for plastic injection mould bases. Int J Adv Manuf Technol 2001;18(9):624–32. 链接1
[10] Wen X, Li X, Gao L, Sang H. Honey bees mating optimization algorithm for process planning problem. J Intell Manuf 2014;25(3):459–72. 链接1
[11] Zhang J, Xiao Mi, Gao L, Pan Q. Queuing search algorithm: a novel metaheuristic algorithm for solving engineering optimization problems. Appl Math Model 2018;63:464–90. 链接1
[12] Liu Q, Li X, Gao L, Li Y. A modified genetic algorithm with new encoding and decoding methods for integrated process planning and scheduling problem. IEEE Trans Cybern. Epub 2020 Oct 15. 链接1
[13] Li WD, Ong SK, Nee AYC. Optimization of process plans using a constraint-based tabu search approach. Int J Prod Res 2004;42(10):1955–85. 链接1
[14] Liu X, Yi H, Ni Z. Application of ant colony optimization algorithm in process planning optimization. J Intell Manuf 2013;24(1):1–13. 链接1
[15] Li XY, Shao XY, Gao L. Optimization of flexible process planning by genetic programming. Int J Adv Manuf Technol 2008;38(1–2):143–53. 链接1
[16] Jin L, Zhang C. Process planning optimization with energy consumption reduction from a novel perspective: mathematical modeling and a dynamic programming-like heuristic algorithm. IEEE Access 2019;7:7381–96. 链接1
[17] Jiang Z, Jiang Ya, Wang Y, Zhang H, Cao H, Tian G. A hybrid approach of rough set and case-based reasoning to remanufacturing process planning. J Intell Manuf 2019;30(1):19–32. 链接1
[18] Jin L, Tang Q, Zhang C, Shao X, Tian G. More MILP models for integrated process planning and scheduling. Int J Prod Res 2016;54(14):4387–402. 链接1
[19] Li WD, Ong SK, Nee AYC. Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts. Int J Prod Res 2002;40(8):1899–922. 链接1
[20] Hua G, Zhou X, Ruan X. GA-based synthesis approach for machining scheme selection and operation sequencing optimization for prismatic parts. Int J Adv Manuf Technol 2007;33(5–6):594–603. 链接1
[21] Shin KS, Park JO, Kim YK. Multi-objective FMS process planning with various flexibilities using a symbiotic evolutionary algorithm. Comput Oper Res 2011;38(3):702–12. 链接1
[22] Wang YF, Zhang YF, Fuh JYH. A hybrid particle swarm based method for process planning optimisation. Int J Prod Res 2012;50(1):277–92. 链接1
[23] Shabaka AI, ElMaraghy HA. A model for generating optimal process plans in RMS. Int J Comput Integrated Manuf 2008;21(2):180–94. 链接1
[24] Floudas CA, Lin X. Mixed integer linear programming in process scheduling: modeling, algorithms, and applications. Ann Oper Res 2005;139(1): 131–62. 链接1
[25] Li X, Gao L, Shao X, Zhang C, Wang C. Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling. Comput Oper Res 2010;37(4):656–67. 链接1
[26] Xia Q, Etienne A, Dantan J, Siadat A. Reconfigurable machining process planning for part variety in new manufacturing paradigms: definitions, models and framework. Comput Ind Eng 2018;115:206–19. 链接1
[27] Lee K, Jung M. Petri net application in flexible process planning. Comput Ind Eng 1994;27(1–4):505–8. 链接1
[28] Sormaz D, Sarkar A. Process sequencing problem in distributed manufacturing process planning. In: Goldengorin B, editor. Optimization problems in graph theory. Berlin: Springer; 2018. p. 293–324. 链接1
[29] Kim YK, Park K, Ko J. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Comput Oper Res 2003;30 (8):1151–71. 链接1
[30] Zhang S, Wong TN. Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning. J Intell Manuf 2018;29(3):585–601. 链接1
[31] Pan CH. A study of integer programming formulations for scheduling problems. Int J Syst Sci 1997;28(1):33–41. 链接1
[32] Fattahi P, Saidi Mehrabad M, Jolai F. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 2007;18 (3):331–42. 链接1
[33] Zhang L, Tang Q, Wu Z, Wang F. Mathematical modeling and evolutionary generation of rule sets for energy-efficient flexible job shops. Energy 2017;138:210–27. 链接1
[34] Özgüven C, Özbakır L, Yavuz Y. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Appl Math Model 2010;34 (6):1539–48. 链接1
[35] Liu Q, Li X, Gao L. Mathematical modeling and a hybrid evolutionary algorithm for process planning. J Intell Manuf 2021;32(3):781–97. 链接1
[36] Zhang Y, Nee A. Application of genetic algorithms and simulated annealing in process planning optimization. In: Pham DT, editor. Computational intelligence in manufacturing handbook. Boca Raton: CRC Press; 2000. p. 243–68. 链接1
[37] Li WD, McMahon CA. A simulated annealing-based optimization approach for integrated process planning and scheduling. Int J Comput Integrated Manuf 2007;20(1):80–95. 链接1