Journal of System Simulation ›› 2024, Vol. 36 ›› Issue (4): 941-956.doi: 10.16182/j.issn1004731x.joss.22-1541
• Papers • Previous Articles Next Articles
Received:
2022-12-23
Revised:
2023-04-11
Online:
2024-04-15
Published:
2024-04-18
CLC Number:
Zhao Yanlin, Tian Yunna. Hyper-heuristic Approach with K-means Clustering for Inter-cell Scheduling[J]. Journal of System Simulation, 2024, 36(4): 941-956.
Table 2
Comparison of contour coefficient and cluster number of 5 entity attributes
测试问题 | 最短加工时间 | 交货期 | 最晚完工时间 | 工序数 | 平均最小工序时间 |
---|---|---|---|---|---|
J50M15C5 | 0.59/14 | 0.69/17 | 0.64/12 | 0.96/18 | 0.93/14 |
J60M16C5 | 0.64/16 | 0.65/14 | 0.65/18 | 0.96/19 | 0.89/19 |
J70M20C7 | 0.67/19 | 0.69/17 | 0.64/22 | 0.96/20 | 0.87/13 |
J80M21C7 | 0.64/10 | 0.65/08 | 0.63/06 | 0.98/20 | 0.92/17 |
J90M21C7 | 0.65/13 | 0.66/21 | 0.66/26 | 1/19 | 0.97/18 |
J100M25C9 | 0.60/08 | 0.70/38 | 0.61/06 | 1/20 | 0.99/18 |
Table 3
Performance comparisons between properties
测试问题 | Makespan | ||||
---|---|---|---|---|---|
最短加工时间 | 交货期 | 最晚完工时间 | 工序数 | 平均最小工序时间 | |
平均值 | 4 998.1 | 5 234.7 | 5 122.1 | 5 169.8 | 5 193.5 |
J50M15C5 | 4 612.0 | 4 650.6 | 4 604.4 | 4 650.2 | 4 612.0 |
J60M16C5 | 5 254.2 | 5 286.6 | 5 339.0 | 5 245.8 | 5 302.0 |
J70M20C7 | 4 918.6 | 5 082.0 | 4 915.4 | 5 206.8 | 5 010.4 |
J80M21C7 | 3 945.0 | 4 725.0 | 4 470.6 | 4 316.8 | 4 802.2 |
J90M21C7 | 4 507.0 | 4 844.2 | 4 657.8 | 4 814.0 | 4 758.4 |
J100M25C9 | 6 752.0 | 6 819.6 | 6 745.4 | 6 785.4 | 6 675.8 |
Table 5
Performance comparison between K-DABh and static partition decision block strategy at minimum Makespan target
测试问题 | Makespan | Gone/% | Gall/% | ||
---|---|---|---|---|---|
K-DABH | K-DABH-ONE | K-DABH-ALL | |||
平均值 | 6.9 | 5.8 | |||
J5M6C3 | 3 344.0 | 3 735.0 | 3 352.6 | 11.7 | 0.3 |
J15M8C3 | 4 885.0 | 4 888.0 | 4 888.2 | 0.1 | 0.1 |
J20M11C3 | 1 737.2 | 2 254.0 | 1 754.2 | 29.7 | 1.0 |
J40M13C5 | 4 700.0 | 4 796.0 | 4 820.0 | 2.0 | 2.6 |
J50M15C5 | 4 612.0 | 4 734.2 | 4 724.4 | 2.6 | 2.4 |
J60M16C5 | 5 254.2 | 5 342.2 | 5 379.4 | 1.7 | 2.4 |
J70M20C7 | 4 918.6 | 5 049.0 | 5 259.2 | 2.7 | 6.9 |
J80M21C7 | 4 364.0 | 4 622.6 | 4 707.0 | 5.9 | 7.8 |
J90M21C7 | 4 507.0 | 4 789.4 | 4 746.4 | 6.3 | 5.3 |
J100M25C9 | 6 752.0 | 6 943.2 | 6 973.6 | 2.8 | 3.3 |
J120M30C9 | 5 138.0 | 5 281.0 | 5 383.6 | 2.8 | 4.8 |
J140M35C11 | 4 412.8 | 4 631.0 | 4 748.0 | 5.0 | 7.6 |
J160M40C11 | 7 267.0 | 7 537.5 | 7 565.7 | 3.7 | 4.1 |
J180M45C13 | 6 646.4 | 6 946.8 | 7 023.8 | 4.5 | 5.7 |
J200M50C15 | 6 241.2 | 6 637.6 | 6 510.0 | 6.3 | 4.3 |
J250M65C15 | 6 379.0 | 6 756.0 | 6 853.4 | 5.9 | 7.4 |
J300M75C15 | 6 002.0 | 6 335.2 | 6 467.6 | 5.6 | 7.8 |
J350M90C15 | 7 007.0 | 7 301.6 | 7 489.0 | 4.2 | 6.9 |
J400M100C15 | 9 606.2 | 10 785.4 | 10 809.8 | 12.3 | 12.5 |
J450M120C15 | 9 408.2 | 11 467.4 | 11 511.4 | 21.9 | 22.4 |
Table 6
Comparison between K-DABH and DABH
测试问题 | Makespan | GDABH/% | |
---|---|---|---|
K-DABH | DABH | ||
平均值 | 3.1 | ||
J40M13C5 | 4 700.0 | 4 727.2 | 0.6 |
J50M15C5 | 4 612.0 | 4 690.6 | 1.7 |
J60M16C5 | 5 254.2 | 5 274.4 | 0.4 |
J70M20C7 | 4 918.6 | 5 018.6 | 2.0 |
J80M21C7 | 4 364.0 | 4 454.2 | 2.1 |
J90M21C7 | 4 507.0 | 4 650.4 | 3.2 |
J100M25C9 | 6 752.0 | 6 977.4 | 3.3 |
J120M30C9 | 5 138.0 | 5 316.2 | 3.5 |
J140M35C11 | 4 412.8 | 4 725.4 | 6.6 |
J160M40C11 | 7 267.0 | 7 514.0 | 3.4 |
J180M45C13 | 6 646.4 | 6 894.0 | 3.7 |
J200M50C15 | 6 241.2 | 6 372.4 | 2.1 |
J250M65C15 | 6 379.0 | 6 667.2 | 4.5 |
J300M75C15 | 6 002.0 | 6 184.6 | 3.0 |
J350M90C15 | 7 007.0 | 7 281.6 | 3.9 |
J400M100C15 | 9 606.2 | 10 064.6 | 4.8 |
J450M120C15 | 9 408.2 | 9 769.8 | 3.8 |
1 | Garza O, Smunt T L. Countering the Negative Impact of Intercell Flow in Cellular Manufacturing[J]. Journal of Operations Management, 1991, 10(1): 92-118. |
2 | Halat Kourosh, Bashirzadeh Reza. Concurrent Scheduling of Manufacturing Cells Considering Sequence-dependent Family Setup Times and Intercellular Transportation Times[J]. The International Journal of Advanced Manufacturing Technology, 2015, 77(9): 1907-1915. |
3 | Feng Yanling, Li Guo, Sethi S P. A Three-layer Chromosome Genetic Algorithm for Multi-cell Scheduling with Flexible Routes and Machine Sharing[J]. International Journal of Production Economics, 2018, 196: 269-283. |
4 | Yan Hongsen, Wan Xiaoqin, Xiong Fuli. Integrated Production Planning and Scheduling for a Mixed Batch Job-shop Based on Alternant Iterative Genetic Algorithm[J]. Journal of the Operational Research Society, 2015, 66(8): 1250-1258. |
5 | Solimanpur M, Vrat Prem, Shankar Ravi. A Heuristic to Minimize Makespan of Cell Scheduling Problem[J]. International Journal of Production Economics, 2004, 88(3): 231-241. |
6 | Solimanpur Maghsud, Elmi Atabak. A Tabu Search Approach for Cell Scheduling Problem with Makespan Criterion[J]. International Journal of Production Economics, 2013, 141(2): 639-645. |
7 | Huang Z, Yang J J. A New Model for Optimization of Cell Scheduling Considering Inter-cell Movement[J]. International Journal of Simulation Modelling, 2022, 21(1): 136-147. |
8 | Tang Jiafu, Wang Xiaoqing, Kaku Iko, et al. Optimization of Parts Scheduling in Multiple Cells Considering Intercell Move Using Scatter Search Approach[J]. Journal of Intelligent Manufacturing, 2010, 21(4): 525-537. |
9 | Li Dongni, Meng Xianwen, Li Miao, et al. An ACO-based Intercell Scheduling Approach for Job Shop Cells with Multiple Single Processing Machines and One Batch Processing Machine[J]. Journal of Intelligent Manufacturing, 2016, 27(2): 283-296. |
10 | Li Dongni, Wang Yan, Xiao Guangxue, et al. Dynamic Parts Scheduling in Multiple Job Shop Cells Considering Intercell Moves and Flexible Routes[J]. Computers & Operations Research, 2013, 40(5): 1207-1223. |
11 | 湛荣鑫, 李冬妮, 马涛, 等. 面向快速响应的赛汝生产系统构建模型与方法[J]. 自动化学报, 2022, 48(12): 2922-2930. |
Zhan Rongxin, Li Dongni, Ma Tao, et al. Configuration Model and Approach of a Seru Production System for Quick Response[J]. Acta Automatica Sinica, 2022, 48(12): 2922-2930. | |
12 | 田园, 田云娜, 刘雪. 求解柔性作业车间调度问题算法综述[J]. 延安大学学报(自然科学版), 2021, 40(3): 64-70. |
Tian Yuan, Tian Yunna, Liu Xue. Review on Algorithms for Flexible Job Shop Scheduling Problem[J]. Journal of Yan'an University(Natural Science Edition), 2021, 40(3): 64-70. | |
13 | Cowling P, Kendall G, Soubeiga E. A Parameter-free Hyperheuristic for Scheduling a Sales Summit[C]//Proceedings of the 4th Metaheuristic International Conference. [S.l.]: [s.n.], 2001: 127-131. |
14 | Anna Karen Gárate-Escamilla, Amaya Ivan, Cruz-Duarte Jorge M, et al. Identifying Hyper-heuristic Trends Through a Text Mining Approach on the Current Literature[J]. Applied Sciences, 2022, 12(20): 10576. |
15 | 贾凌云, 李冬妮, 田云娜. 基于混合蛙跳和遗传规划的跨单元调度方法[J]. 自动化学报, 2015, 41(5): 936-948. |
Jia Lingyun, Li Dongni, Tian Yunna. An Intercell Scheduling Approach Using Shuffled Frog Leaping Algorithm and Genetic Programming[J]. Acta Automatica Sinica, 2015, 41(5): 936-948. | |
16 | 李冬妮, 贾晓宇, 陈琳, 等. 基于蚁群算法和遗传规划的跨单元调度方法[J]. 北京理工大学学报, 2017, 37(7): 704-710. |
Li Dongni, Jia Xiaoyu, Chen Lin, et al. Intercell Scheduling Approach Based on Ant Colony Optimization Algorithm and Genetic Programming[J]. Transactions of Beijing Institute of Technology, 2017, 37(7): 704-710. | |
17 | 罗敏. 基于超启发式算法的多模具限制柔性作业车间问题研究[D]. 杭州: 浙江大学, 2021. |
Luo Min. Research on Hyper-heuristic Approach for Molds-constrained Flexible Job-shop Problem[D]. Hangzhou: Zhejiang University, 2021. | |
18 | José Antonio Vázquez-Rodríguez, Petrovic S. A New Dispatching Rule Based Genetic Algorithm for the Multi-objective Job Shop Problem[J]. Journal of Heuristics, 2010, 16(6): 771-793. |
19 | 刘兆赫, 李冬妮, 王乐衡, 等. 考虑运输能力限制的跨单元调度方法[J]. 自动化学报, 2015, 41(5): 885-898. |
Liu Zhaohe, Li Dongni, Wang Leheng, et al. An Inter-cell Scheduling Approach Considering Transportation Capacity Constraints[J]. Acta Automatica Sinica, 2015, 41(5): 885-898. | |
20 | 刘兆赫. 超启发式方法的动态决策块机制及其在调度问题中的应用[D]. 北京: 北京理工大学, 2016. |
Liu Zhaohe. Hyper-heuristic with Dynamic Decision Blocks and Its Application in Scheduling Problems[D]. Beijing: Beijing Institute of Technology, 2016. | |
21 | 田云娜, 李冬妮, 刘兆赫, 等. 一种基于动态决策块的超启发式跨单元调度方法[J]. 自动化学报, 2016, 42(4): 524-534. |
Tian Yunna, Li Dongni, Liu Zhaohe, et al. A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling[J]. Acta Automatica Sinica, 2016, 42(4): 524-534. | |
22 | Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[C]//1991 1st Proceedings of the First European Conference on Artificial Life. [S.l.]: [s.n.], 1991: 134-142. |
23 | Dorigo Marco, Luca Maria Gambardella. Ant Colonies for the Travelling Salesman Problem[J]. Bio Systems, 1997, 43(2): 73-81. |
24 | Jain A K, Murty M N, Flynn P J. Data Clustering: A Review[J]. ACM Computing Surveys, 1999, 31(3): 264-323. |
25 | 杨俊闯, 赵超. K-means聚类算法研究综述[J]. 计算机工程与应用, 2019, 55(23): 7-14, 63. |
Yang Junchuang, Zhao Chao. Survey on K-means Clustering Algorithm[J]. Computer Engineering and Applications, 2019, 55(23): 7-14, 63. | |
26 | Rousseeuw Peter J. Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis[J]. Journal of Computational and Applied Mathematics, 1987, 20: 53-65. |
27 | Ramze Rezaee M, Lelieveldt B P F, Reiber J H C. A New Cluster Validity Index for the Fuzzy C-mean[J]. Pattern Recognition Letters, 1998, 19(3/4): 237-246. |
28 | Huang P Y. A Comparative Study of Priority Dispatching Rules in a Hybrid Assembly/Job Shop[J]. International Journal of Production Research, 1984, 22(3): 375-387. |
29 | Vepsalainen A P J, Morton T E. Priority Rules for Job Shops with Weighted Tardiness Costs[J]. Management Science, 1987, 33(8): 1035-1047. |
[1] | Shao Xuqiang, Cheng Ya, Jin Yizhong. 3D Streamline Visualization Method Based on Clustering Fusion [J]. Journal of System Simulation, 2024, 36(3): 625-635. |
[2] | Chen Jing, Zhang Zhaochong, Wang Linkai, An Mai, Wang Wei. Short-term Bus Passenger Flow Prediction Based on Convolutional Long-short-term Memory Network [J]. Journal of System Simulation, 2024, 36(2): 476-486. |
[3] | Feng Chen, You Xiaoming, Liu Sheng. Heterogeneous Multi-ant Colony Algorithm Combining Competitive Interaction Strategy and Eliminating-reconstructing Mechanism [J]. Journal of System Simulation, 2024, 36(1): 232-248. |
[4] | Fei Ding, Meinan Zhang, Hengheng Zhuang, Hairong Ma, Dengyin Zhang. Target Search Planning and Algorithm for Monitoring of Polar Disaster Areas [J]. Journal of System Simulation, 2023, 35(7): 1526-1538. |
[5] | Tuo Zhao, Hanqiang Deng, Jialong Gao, Jian Huang. Dynamic Target Assignment of Multiple Unmanned Aerial Vehicles Based on Clustering of Network Nodes [J]. Journal of System Simulation, 2023, 35(4): 695-708. |
[6] | Yifan He, Yulin He, Yongda Cai, Zhexue Huang. I-niceMO Enhanced Algorithm Based on Intersection Angel Geometry [J]. Journal of System Simulation, 2023, 35(4): 797-808. |
[7] | Xu Wang, Weidong Ji, Guohui Zhou, Jiahui Yang. Multi-objective Optimization Algorithm Based on Multi-index Elite Individual Game Mechanism [J]. Journal of System Simulation, 2023, 35(3): 494-514. |
[8] | Guodong Yuan, Ming He, Ziyu Ma, Weishi Zhang, Xueda Liu, Wei Li. Multiagent Following Multileader Algorithm Based on K-means Clustering [J]. Journal of System Simulation, 2023, 35(3): 616-622. |
[9] | Houming Fan, Fushan Xian, Huaiqi Wang. Takeout Distribution Routes Optimization Considering Order Clustering under Dynamic Demand [J]. Journal of System Simulation, 2023, 35(2): 396-407. |
[10] | Chen Xue, Hu Rong, Wang Hui, Li Zuocheng, Qian Bin, Li Yixu. Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem [J]. Journal of System Simulation, 2023, 35(11): 2476-2495. |
[11] | Xiangyang Deng, Limin Zhang, Wei Fang, Miao Tang. Robot Path Planning Based on Bidirectional Aggregation Ant Colony Optimization [J]. Journal of System Simulation, 2022, 34(5): 1101-1108. |
[12] | Xinyu Gao, Jing Ni. Optimization of Dynamic Post-disaster Emergency Distribution Network under Perspective of Rescue Efficiency [J]. Journal of System Simulation, 2022, 34(4): 806-816. |
[13] | Zhe Wang, Hongyuan Shao, Zihao Cong, Wenwen Ma. Simulation of Emergency Medical Materials Collaborative Distribution Considering Supplier Clustering [J]. Journal of System Simulation, 2022, 34(10): 2303-2311. |
[14] | Mingmei Li, Chenglin Wen, Shaolin Hu. A K-modes Clustering Method Based on Maximal Information Coefficient Data Preprocessing [J]. Journal of System Simulation, 2022, 34(10): 2204-2212. |
[15] | Li Gang, Zhang Caixia, Hu Shaolin, Wang Xiangdong, Guo Jing. WSN Clustering Routing Protocol for Bridge Structure Health Monitoring [J]. Journal of System Simulation, 2022, 34(1): 62-69. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||