基于GEP的装配作业车间调度复合派工法则研究

doi:10.3901/JME.2023.16.427

机械工程学报 ›› 2023, Vol. 59 ›› Issue (16): 427-434.doi: 10.3901/JME.2023.16.427

扫码分享

基于GEP的装配作业车间调度复合派工法则研究

吕海利^1,2,3, 黄志文^1,2,3, 陈建华^1,2, 王正国^1,2, 吴姝^1,2, 韩国震⁴

1. 武汉理工大学交通与物流工程学院武汉 430063;
2. 武汉理工大学物流系统科学与工程研究所武汉 430063;
3. 港口物流技术与装备教育部工程研究中心武汉 430063;
4. 武汉天马微电子有限公司武汉 430000

收稿日期:2022-08-10 修回日期:2022-11-12 出版日期:2023-08-20 发布日期:2023-11-15
通讯作者: 陈建华(通信作者),男,1977年出生,副教授,硕士研究生导师。主要研究方向为运营与供应链管理、物流系统科学等。E-mail:chenjh@whut.edu.cn
作者简介:吕海利,男,1982年出生,副教授、硕士研究生导师。主要研究方向为优化和仿真技术的理论与产业应用等。E-mail:lvhaili@whut.edu.cn;黄志文,男,1997年出生。主要研究方向为车间调度、智能优化算法等。E-mail:293512@whut.edu.cn;王正国,男,1975年出生,副教授,硕士研究生导师。主要研究方向为物流系统决策支持与优化等。E-mail:zgwang@whut.edu.cn;吴姝,女,1986年出生,副教授,硕士研究生导师。主要研究方向为质量可靠性、统计过程监控、智能制造等。E-mail:wushu@whut.edu.cn;韩国震,男,1992年出生。主要研究方向为复杂车间调度优化算法。E-mail:lmy.han@qq.com
基金资助:
国家自然科学基金青年科学基金(11701437);军工项目JGXM(202018HX02);桂林航天工业学院广西航空物流研究中心基金(19KFJJHKWL04)资助项目。

Research on Composite Dispatching Rules of Assembly Job Shop Scheduling Based on Gene Expression Programming

Lü Haili^1,2,3, HUANG Zhiwen^1,2,3, CHEN Jianhua^1,2, WANG Zhengguo^1,2, WU Shu^1,2, HAN Guozhen⁴

1. School of Transportation and Logistics Engineering, Wuhan University of Technology, Wuhan 430063;
2. Institute of Logistics System Science and Engineering, Wuhan University of Technology, Wuhan 430063;
3. Ministry of Education Engineering Research Center for Port Logistics Technology and Equipment, Wuhan 430063;
4. Wuhan Tianma Microelectronics Co., Ltd., Wuhan 430000

Received:2022-08-10 Revised:2022-11-12 Online:2023-08-20 Published:2023-11-15

摘要/Abstract

摘要： 派工法则是求解作业车间调度问题的一种简单有效的方法。针对一种装配作业车间调度问题建立仿真模型，并通过基因表达式编程（Gene expression programming,GEP）算法自动产生并搜索最优的派工法则。仿真模型结果表明，在最小平均流程时间和最小平均绝对偏差两个目标函数下，GEP算法都能够找到比现有常用的派工法则更好的解，在计算时间和求解质量方面也都具有优势，并且有较强的鲁棒性。具体设计上，构造属性筛选机制以减少搜索空间，提升搜索性能，采用动态自适应算法提高GEP的搜索效果，通过仿真试验构建不同的生产环境证明了所提算法的有效性。

关键词: 基因表达式编程, 装配作业车间调度, 派工法则, 属性选择

Abstract: Dispatching rules is a simple and effective approach for job shop scheduling problems. Aiming at an assembly job shop scheduling problem（AJSP）, a simulation model is established and a gene expression programming（GEP） algorithm is proposed to automatically generate and search optimal dispatching rules. Simulation results show that under the two optimization objectives of minimizing mean flow time and mean absolute deviation, the GEP algorithm can find better solutions than existing commonly used dispatching rules and shows advantages in computation time and solving quality, together with a certain level of robustness.Specifically, a feature selection scheme is designed to reduce the search space and improve search performance. A dynamic self-adaptive scheme is also applied to improve the search ability of GEP, and the effectiveness of the proposed algorithm is proved by simulating experiments constructed for different production environments.

Key words: gene expression programming, assembly job shop scheduling, dispatching rules, feature selection

中图分类号:

TP301

吕海利, 黄志文, 陈建华, 王正国, 吴姝, 韩国震. 基于GEP的装配作业车间调度复合派工法则研究[J]. 机械工程学报, 2023, 59(16): 427-434.

Lü Haili, HUANG Zhiwen, CHEN Jianhua, WANG Zhengguo, WU Shu, HAN Guozhen. Research on Composite Dispatching Rules of Assembly Job Shop Scheduling Based on Gene Expression Programming[J]. Journal of Mechanical Engineering, 2023, 59(16): 427-434.

参考文献

[1] BLACKSTONE J H, PHILLIPS D T, HOGG G L. A state-of-the-art survey of dispatching rules for manufacturing job shop operations[J]. International Journal of Production Research, 1982, 20(1):27-45.
[2] ALLAHVERDI A, NG C T, CHENG T, et al. A survey of scheduling problems with setup times or costs[J]. European Journal of Operational Research, 2008, 187(3):985-1032.
[3] XIE C, ALLEN T T. Simulation and experimental design methods for job shop scheduling with material handling:a survey[J]. The International Journal of Advanced Manufacturing Technology, 2015, 80(1-4):233-243.
[4] YOKOYAMA M. Hybrid flow-shop scheduling with assembly operations[J]. International Journal of Production Economics, 2001, 73(1):103-116.
[5] LIN B, CHENG T. Fabrication and assembly scheduling in a two-machine flowshop[J]. IIE Transactions, 2002, 34(11):1015-1020.
[6] SUNG C S, KIM H A. A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times[J]. International Journal of Production Economics, 2008, 113(2):1038-1048.
[7] POTTS C N, WASSENHOVE L V. A branch and bound algorithm for the total weighted tardiness problem[J]. Operations Research, 1985, 33(2):363-377.
[8] KUNDAKCI N, KULAK O. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 96:31-51.
[9] LI N, GAO L, LI P, et al. A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates[J]. Journal of Intelligent Manufacturing, 2013, 24(4):763-774.
[10] OZTURK G, BAHADIR O, TEYMOURIFAR A. Extracting priority rules for dynamic multi-objective flexible job shop scheduling problems using gene expression programming[J]. International Journal of Production Research, 2018, 57(1):1-17.
[11] PHILIPOOM P R, MARKLAND R E, FRY T D. Sequencing rules, progress milestones and product structure in a multistage job shop[J]. Journal of Operations Management, 1989, 8(3):209-229.
[12] REEJA M K, CR F. Dispatching rules for scheduling in assemble job shops-Part 1[J]. International Journal of Production Research, 2000, 38(9):2051-2066.
[13] REEJA M K, CR F. Dispatching rules for scheduling in assemble job shops-Part 2[J]. International Journal of Production Research, 2000, 38(10):2349-2360.
[14] NATARAJAN K, MOHANASUNDARAM K M, BABU B S, et al. Performance evaluation of priority dispatching rules in multi-level assembly job shops with jobs having weights for flowtime and tardiness[J]. The International Journal of Advanced Manufacturing Technology, 2007, 31(7):751-761.
[15] THIAGARAJAN S, RAJENDRAN C. Scheduling in dynamic assembly job-shops with jobs having different holding and tardiness costs[J]. International Journal of Production Research, 2003, 41(18):4453-4486.
[16] 金锋赫,孔繁森,金东园. 基于设备可用时间约束的装配作业车间调度规则[J]. 计算机集成制造系统, 2008, 14(9):1727-1732. JIN Fenghe, KONG Fansen, JIN Dongyuan. Scheduling rules for assembly Job Shop based on machine available time[J]. Computer Integrated Manufacturing Systems, 2008, 14(9):1727-1732.
[17] DIMOPOULOS C, ZALZALA A M S. Investigating the use of genetic programming for a classic one-machine scheduling problem[J]. Advances in Engineering Software, 2001, 32(6):489-498.
[18] 吕海利,朱家涛,王正国. 装配作业车间的JIT调度研究[J]. 机械工程学报, 2021, 57(5):157-165. LÜ Haili, ZHU Jiatao, WANG Zhengguo, et al. Research of just-in-time scheduling for assembly job shop[J]. Journal of Mechanical Engineering, 2021, 57(5):157-165.
[19] 费红霞,潘炼. 基于改进的基因表达式编程算法在作业车间调度问题中的应用[J]. 计算机与数字工程, 2009, 37(6):6-10. FEI Hongxia, PAN Lian. Application of improved gene expression programming for job shop scheduling problem[J]. Computer and Digital Engineering, 2009, 37(6):6-10.
[20] 左劼. 基因表达式编程核心技术研究[D]. 成都:四川大学, 2004. ZUO Jie. Research on core technology of gene expression programming[D]. Chengdu:Sichuan University, 2004.
[21] 王爱法,杨梅梅,福春霞. 二叉树及其遍历算法的应用[J]. 重庆理工大学学报, 2018, 32(11):194-198. WANG Aifa, YANG Meimei, FU Chunxia. Application of binary tree and its traversal algorithm[J]. Journal of Chongqing University of Technology, 2018, 32(11):194-198.
[22] TAY J C, HO N B. Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems[J]. Computers and Industrial Engineering, 2008, 54(3):453-473.

基于GEP的装配作业车间调度复合派工法则研究

Research on Composite Dispatching Rules of Assembly Job Shop Scheduling Based on Gene Expression Programming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价