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

doi:10.3901/JME.2023.16.427

Abstract

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

CLC Number:

TP301

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.

References

[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.