Combined rules based optimization for AGV joint scheduling in job shop
-
摘要: 以具有自动导航小车(automated guided vehicle, AGV)储运系统的智能车间为研究背景，针对作业车间内机床与AGV联合调度优化问题开展研究。首先，分析作业车间AGV联合调度问题特征，以此建立AGV-加工设备联合调度问题的数学模型以便精确算法求解；随后，将联合调度问题解耦成工序排序与AGV选择两个强关联的子决策问题，在此基础上构建了一套组合规则算法生成框架，并嵌入多样化的启发式规则，设计多种组合规则算法；最后，针对差异化场景算例，对比分析商业求解器Gurobi与组合规则算法的求解结果，并深入分析组合规则算法的有效性和场景适应性。Abstract: This paper takes material handling system in intelligent workshop with AGV(automated guided vehicle) as research background, and a joint scheduling optimization of machine and AGV in job shop is abstracted. This research is conducted as follows: Firstly, the mathematical model of AGV-machine joint scheduling is established at a full consideration of problem characteristics, the mathematical model is used in the exact algorithm; Then, the joint scheduling problem is decomposed into two strongly related sub-decisions, which are job sequencing and AGV selection decision, a combined rule generating framework is constructed, various combined rules are generated by embedding diverse heurstic rules into the framework; Finally, the effectiveness and scenario adaptability of combined rules are analyzed by comparing their experimental results with exact solutions of commercial solver Gurobi in differentiated test cases.
-
Key words:
- job shop /
- automated guided vehicle /
- combined rules /
- joint scheduling
-
表 1 作业车间环境下AGV联合调度文献
下载: 导出CSV
表 2 启发式规则汇总分类
类别 规则 原理 工序排序 到达机器时间最早(JAT) 选择缓冲队列中最早抵达加工机器的任务加工 机器释放任务时间最早(MER) 选择缓冲队列中最早被前工序机器释放的任务加工 任务开工时间最早(JEO) 选择开工时间最早的任务优先加工 任务完工时间最早(JFO) 选择缓冲队列中预计完工时间最早的任务优先加工 AGV选择 搬运完成时间最早(EFR) 选择预计完成搬运任务最早的AGV执行 搬运时间最短(EMT) 选择搬运时间最短的AGV执行 搬运释放时间最早(ERR) 选择释放时间最早的AGV执行
下载: 导出CSV
表 3 实验影响因素汇总
影响因子 影响因子水平 影响因子水平值 车间布局(g) 6 布局方案(a/b/c/d/e/f) 任务规模(s) 3 5/6/20 工序排序规则(o) 4 JAT/MER/JEO/JFO AGV选择策略(h) 3 EFR/EMT/ERR 小车行驶速度(v) 2 1 m/s, 2 m/s
下载: 导出CSV
表 4 小规模问题Gurobi精确解结果(v=1 m/s)
算例
编号布局方案a 布局方案b 布局方案c 布局方案d Cmax tcpu Cmax tcpu Cmax tcpu Cmax tcpu #1 112 13 86 4 94 6 138 26 #2 134 917 92 428 87 770 186 1 800 #3 125 562 101 113 107 764 183 1 800 #4 135 1 800 116 905 126 1 800 192 1 800 #5 105 113 78 8 88 47 130 146 #6 158 1 800 143 1 800 165 1 800 222 1 800 #7 182 1 800 154 1 800 181 1 800 234 1 800 #8 177 1 800 181 1 800 187 1 800 219 1 800 #9 142 30 127 39 143 136 187 1 800 #10 176 1 800 154 262 168 839 235 1 800
下载: 导出CSV
表 5 小规模问题Gurobi精确解结果(v=2 m/s)
算例
编号布局方案a 布局方案b 布局方案c 布局方案d Cmax tcpu Cmax tcpu Cmax tcpu Cmax tcpu #1 73 1 68 1 71 1 83 3 #2 80 4 81 3 81 5 84 12 #3 89 6 90 3 91 5 104 16 #4 78 14 72 8 76 20 99 100 #5 63 3 57 1 59 1 74 6 #6 106 14 106 6 98 19 106 119 #7 158 1 800 79 1 163 91 1 800 123 1 800 #8 97 1 800 134 12 132 17 143 51 #9 100 5 99 4 99 5 114 10 #10 132 21 129 17 133 15 142 30
下载: 导出CSV
表 6 小规模问题下组合规则算法运算时间
算例
编号v = 1 m/s 运算时间/s v = 2 m/s 运算时间/s 布局a 布局b 布局c 布局d 布局a 布局b 布局c 布局d #1 0.033 5 0.021 2 0.019 4 0.019 3 0.034 0 0.023 1 0.019 8 0.019 9 #2 0.031 3 0.024 3 0.023 4 0.023 1 0.027 0 0.024 0 0.026 5 0.024 4 #3 0.024 9 0.024 7 0.024 1 0.023 4 0.028 1 0.024 6 0.025 0 0.024 9 #4 0.026 0.023 6 0.023 1 0.023 3 0.031 4 0.026 4 0.025 6 0.025 6 #5 0.024 8 0.020 4 0.022 3 0.018 7 0.019 3 0.021 7 0.021 3 0.020 3 #6 0.031 8 0.026 1 0.027 2 0.026 6 0.027 1 0.028 8 0.029 6 0.027 2 #7 0.032 2 0.034 0.032 1 0.033 0.034 2 0.033 1 0.034 5 0.035 9 #8 0.028 6 0.027 6 0.029 0.027 5 0.030 1 0.029 9 0.030 0 0.028 5 #9 0.023 4 0.022 6 0.022 4 0.023 2 0.026 0 0.022 9 0.022 8 0.023 6 #10 0.030 6 0.029 3 0.030 5 0.029 0.030 6 0.031 0 0.030 9 0.036 1
下载: 导出CSV
表 7 中大规模问题下组合规则算法运算时间
算例
编号v = 1 m/s
运算时间/sv = 2 m/s
运算时间/s#1 0.585 7 0.585 1 #2 0.596 2 0.611 3 #3 0.569 2 0.563 0 #4 0.588 5 0.583 8 #5 0.589 4 0.564 2 #6 0.914 7 0.823 6 #7 0.866 5 0.816 0 #8 0.920 0 0.873 0 #9 0.879 9 0.816 0 #10 0.888 0 0.844 5
下载: 导出CSV
-
[1] Chawla V K, Chanda A K, Angra S. Automatic guided vehicle systems in the flexible manufacturing system-a review[J]. International Journal of Industrial Engineering, 2019, 26(5): 737-765. [2] 薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857. doi: 10.13196/j.cims.2021.07.009 [3] Imran Ali Chaudhry, Abid Ali Khan. A research survey: review of flexible job shop scheduling techniques[J]. International Transactions in Operational Research, 2016, 23(3): 551-591. doi: 10.1111/itor.12199 [4] Lenstra J K, Kan A. Complexity of vehicle routing and scheduling problems[J]. Networks, 2010, 11(2): 221-227. [5] Knust S. Shop-scheduling problems with transportation[D]. Universität Osnabrück, 1999. [6] Mousavi M, Yap H J, Musa S N, et al. Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J]. PLoS One, 2017, 12(3): e0169817. doi: 10.1371/journal.pone.0169817 [7] 陆远, 冯睽睽, 胡莹. 单个AGV小车多个搬运请求的调度算法研究[J]. 组合机床与自动化加工技术, 2019(2): 157-160. doi: 10.13462/j.cnki.mmtamt.2019.02.042 [8] Shiue Y R, Lee K C, Su C T. Real-time scheduling for a smart factory using a reinforcement learning approach[J]. Computers & Industrial Engineering, 2018, 125: 604-614. [9] 陈敏, 黎展滔, 陈庆新, 等. 考虑有限物流运输能力的智能车间AGV调度算法研究[J]. 工业工程, 2019, 22(4): 49-57. doi: 10.3969/j.issn.1007-7375.2019.04.008 [10] 郭沛佩, 付建林, 江海凡, 等. 基于规则的柔性作业车间机床与AGV联合调度优化[J]. 制造技术与机床, 2021(9): 107-113. doi: 10.19287/j.cnki.1005-2402.2021.09.021 [11] Wolpert D H, Macready W G. No free lunch theorems for optimization[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82. doi: 10.1109/4235.585893 [12] Feng X, Xu Z. Integrated production and transportation scheduling on parallel batch-processing machines[J]. IEEE Access, 2019, 7: 148393-148400. doi: 10.1109/ACCESS.2019.2946801 [13] Nabovati H, Haleh H, Vahdani B. Multi-objective invasive weeds optimization algorithm for solving simultaneous scheduling of machines and multi-mode automated guided vehicles[J]. European Journal of Industrial Engineering, 2020, 14(2): 165-188. doi: 10.1504/EJIE.2020.105696 [14] Durasevic M, Jakobovic D. A survey of dispatching rules for the dynamic unrelated machines environment[J]. Expert Systems with Applications, 2018, 113: 555-569. doi: 10.1016/j.eswa.2018.06.053 [15] Ümit Bilge, Gündüz Ulusoy. A time window approach to simultaneous scheduling of machines and material handling system in an FMS[J]. Operations Research, 1995, 43(6): 1058-1070. doi: 10.1287/opre.43.6.1058 [16] Ham A. Transfer-robot task scheduling in job shop[J]. International Journal of Production Research, 2021, 59(3): 1-11. -
下载:
点击查看大图
图(7) / 表(7)
计量
- 文章访问数: 101
- HTML全文浏览量: 14
- PDF下载量: 16
- 被引次数: 0
