期刊首页 优先出版 当期阅读 过刊浏览 作者中心 关于期刊 English

《工程(英文)》 >> 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

收稿日期 :2019-10-29 修回日期 :2021-03-21 录用日期 : 2021-04-27 发布日期 :2021-05-05

下一篇 上一篇

摘要

智能工艺规划是智能制造系统中的重要组成部分。从制造流程角度出发,工艺规划(process planning, PP)连接着产品设计和实际生产,有着承上启下的关键作用。PP属于非确定性多项式时间困难(NP-hard)问题,现有的问题模型都是非线性形式,因此不能够通过求解现有模型来得到问题的精确解。从工艺网络图的拓扑结构出发,本文提出了一个全新的混合整数线性规划(mixedinteger linear programming, MILP)数学模型,并通过三种优先关系矩阵讨论了网络图中工序的优先关系。该模型能够凭借常用的数学模型求解器,如CPLEX、Gurobi等,来搜寻并获得大部分算例的最优解。该模型通过在5组公开的著名数据集上的测试,证明了其通用性和有效性。实验结果有力地说明了所提模型能够有效地解决工艺规划问题,并获得比当前最先进算法更好的解。

图片

图1

图2

图3

图4

图5

图6

图7

图8

参考文献

[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

相关研究