[1]柳冬,宋豫川,杨云帆,等.机器故障的柔性加工与装配作业车间分批联合调度算法[J].智能系统学报,2022,17(3):556-567.[doi:10.11992/tis.202101038]
LIU Dong,SONG Yuchuan,YANG Yunfan,et al.Batch scheduling algorithm for flexible machining and assemblyjob shop when the machine breaks down[J].CAAI Transactions on Intelligent Systems,2022,17(3):556-567.[doi:10.11992/tis.202101038]
点击复制
LIU Dong,SONG Yuchuan,YANG Yunfan,et al.Batch scheduling algorithm for flexible machining and assemblyjob shop when the machine breaks down[J].CAAI Transactions on Intelligent Systems,2022,17(3):556-567.[doi:10.11992/tis.202101038]
机器故障的柔性加工与装配作业车间分批联合调度算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
17
期数:
2022年第3期
页码:
556-567
栏目:
学术论文—智能系统
出版日期:
2022-05-05
- Title:
- Batch scheduling algorithm for flexible machining and assemblyjob shop when the machine breaks down
- Keywords:
- flexible assembly job shop scheduling; sublots and batches; machine breakdown; dynamic scheduling; local search; genetic algorithm; completion time; hybrid greed decoding
- 分类号:
- TP278
- 摘要:
- 针对传统的加工与装配分阶段独立调度中资源利用率不高的问题，将加工与装配联合同时进行调度。在考虑工件批量和批次的前提下提出一种改进遗传算法求解该问题，以最小化最大完工时间为优化目标建立数学模型，根据问题特性提出一种工件末工序前移的邻域结构，提升了算法的局部搜索能力进而改善整体求解质量。设计了一种基于装配设备负载均衡的混合贪婪解码方法，完成了装配设备选择。考虑到实际车间中机器故障的特点，提出了相应的响应策略和染色体更改规则，解决了动态调度问题。最后通过算例分析验证了所提算法和策略求解该问题的可行性和有效性。
- Abstract:
- To solve the problem of low resource utilization in traditional independent scheduling of machining and assembly by stages, the machining and assembly are simultaneously scheduled. An improved genetic algorithm is designed to solve the problem by considering the batch and sublots of the workpiece. First, a mathematical model is established to minimize the maximum completion time. According to the problem characteristics, a neighborhood structure with the workpiece’s last process is proposed, which enhances the local searching ability of the algorithm and improves the overall solution quality. Furthermore, a hybrid greed decoding method based on the load balancing of assembly equipment is designed to complete its selection. Considering the characteristics of machine breakdown in a real workshop, a corresponding response strategy and chromosome changing rule are introduced to solve the dynamic scheduling problem. Finally, the feasibility and effectiveness of the proposed algorithm and strategy for solving the problem are verified by example analysis.
- 参考文献/References:
-
[1] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of operations research, 1976, 1(2): 117–129.
[2] HO N B, TAY J C, LAI E M K. An effective architecture for learning and evolving flexible job-shop schedules[J]. European journal of operational research, 2007, 179(2): 316–333.
[3] 张超勇, 饶运清, 李培根, 等. 柔性作业车间调度问题的两级遗传算法[J]. 机械工程学报, 2007, 43(4): 119–124
ZHANG Chaoyong, RAO Yunqing, LI Peigen, et al. Bilevel genetic algorithm for the flexible job-shop scheduling problem[J]. Chinese journal of mechanical engineering, 2007, 43(4): 119–124
[4] 姜天华. 混合灰狼优化算法求解柔性作业车间调度问题[J]. 控制与决策, 2018, 33(3): 503–508
JIANG Tianhua. Flexible job shop scheduling problem with hybrid grey wolf optimization algorithm[J]. Control and decision, 2018, 33(3): 503–508
[5] ZHANG Sicheng, LI Xiang, ZHANG Bowen, et al. Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system[J]. European journal of operational research, 2020, 283(2): 441–460.
[6] 石小秋, 李炎炎, 邓丁山, 等. 基于自适应变级遗传杂草算法的FJSP研究[J]. 机械工程学报, 2019, 55(6): 223–232
SHI Xiaoqiu, LI Yanyan, DENG Dingshan, et al. Self-adaptive multistage GA-IWO for solving flexible job shop scheduling problem[J]. Journal of mechanical engineering, 2019, 55(6): 223–232
[7] 李明, 雷德明. 考虑准备时间和关键目标的柔性作业车间低碳调度研究[J]. 机械工程学报, 2019, 55(21): 139–149
LI Ming, LEI Deming. Research on flexible job shop low carbon scheduling with setup times and key objectives[J]. Journal of mechanical engineering, 2019, 55(21): 139–149
[8] 徐本柱, 吉靖, 费晓璐. 柔性作业车间中基于工序分批的调度问题与求解[J]. 中国机械工程, 2016, 27(23): 3221–3229
XU Benzhu, JI Jing, FEI Xiaolu. Problems and solutions of flexible job-shop scheduling with operation lot-splitting[J]. China mechanical engineering, 2016, 27(23): 3221–3229
[9] 李聪波, 沈欢, 李玲玲, 等. 面向能耗的多工艺路线柔性作业车间分批优化调度模型[J]. 机械工程学报, 2017, 53(5): 12–23
LI Congbo, SHEN Huan, LI Lingling, et al. A batch splitting flexible job shop scheduling model for energy saving under alternative process plans[J]. Journal of mechanical engineering, 2017, 53(5): 12–23
[10] NOURALI S, IMANIPOUR N, SHAHRIARI M R. A mathematical model for integrated process planning and scheduling in flexible assembly job shop environment with sequence dependent setup times[J]. International journal of mathematical analysis, 2012, 6(41): 2117–2132.
[11] NOURALI S, IMANIPOUR N. A particle swarm optimization-based algorithm for flexible assemblyjob shop scheduling problem with sequence dependent setup times[J]. Scientia Iranica, 2014, 21(3): 1021–1033.
[12] ZHANG Sicheng, WONG T N. Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach[J]. International journal of production research, 2017, 55(11): 3173–3196.
[13] 刘爱军, 杨育, 邢青松, 等. 柔性作业车间多目标动态调度[J]. 计算机集成制造系统, 2011, 17(12): 2629–2637
LIU Aijun, YANG Yu, XING Qingsong, et al. Dynamic scheduling on multi-objective flexible job shop[J]. Computer integrated manufacturing systems, 2011, 17(12): 2629–2637
[14] BAYKASO?LU A, MADENO?LU F S, HAMZADAY? A. Greedy randomized adaptive search for dynamic flexible job-shop scheduling[J]. Journal of manufacturing systems, 2020, 56: 425–451.
[15] 杨小佳, 刘建军, 陈庆新, 等. 变扰动强度下柔性装配作业车间调度性能分析[J]. 计算机集成制造系统, 2021, 27(3): 800–814
YANG Xiaojia, LIU Jianjun, CHEN Qingxin, et al. Performance analysis of flexible assembly job shop scheduling under variable disturbance intensity[J]. Computer integrated manufacturing systems, 2021, 27(3): 800–814
[16] 朱传军, 邱文, 张超勇, 等. 多目标柔性作业车间稳健性动态调度研究[J]. 中国机械工程, 2017, 28(2): 173–182
ZHU Chuanjun, QIU Wen, ZHANG Chaoyong, et al. Multi-objective flexible job shop dynamic scheduling strategy aiming at scheduling stability and robustness[J]. China mechanical engineering, 2017, 28(2): 173–182
[17] 张彪. 基于候鸟迁徙算法的批量流混合流水车间调度方法研究[D]. 武汉: 华中科技大学, 2019.
ZHANG Biao. Research on lot streaming hybrid flowshop scheduling method based on migrating birds optimization algorithm[D]. Wuhan: Huazhong University of Science and Technology, 2019.
[18] 王凌, 郑大钟. 基于遗传算法的Job Shop调度研究进展[J]. 控制与决策, 2001, 16(S1): 641–646
WANG Ling, ZHENG Dazhong. Advances in job shop scheduling based on genetic algorithm[J]. Control and decision, 2001, 16(S1): 641–646
[19] 张国辉. 柔性作业车间调度方法研究[D]. 武汉: 华中科技大学, 2009.
ZHANG Guohui. Research on methods for flexible job shop scheduling problems[D]. Wuhan: Huazhong University of Science and Technology, 2009.
[20] 张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145–151
ZHANG Guohui, GAO Liang, LI Peigen, et al. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of mechanical engineering, 2009, 45(7): 145–151
[21] 张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004, 15(23): 2149–2153
ZHANG Chaoyong, RAO Yunqing, LIU Xiangjun, et al. An improved genetic algorithm for the job shop scheduling problem[J]. China mechanical engineering, 2004, 15(23): 2149–2153
[22] 张超勇, 饶运清, 李培根, 等. 求解作业车间调度问题的一种改进遗传算法[J]. 计算机集成制造系统, 2004, 10(8): 966–970
ZHANG Chaoyong, RAO Yunqing, LI Peigen, et al. An improved genetic algorithm for Job-Shop scheduling[J]. Computer integrated manufacturing systems, 2004, 10(8): 966–970
[23] PONGCHAIRERKS P. An enhanced two-level metaheuristic algorithm with adaptive hybrid neighborhood structures for the job-shop scheduling problem[J]. Complexity, 2020, 2020: 3489209.
[24] 张超勇, 管在林, 刘琼, 等. 一种新调度类型及其在作业车间调度中的应用[J]. 机械工程学报, 2008, 44(10): 24–31
ZHANG Chaoyong, GUAN Zailin, LIU Qiong, et al. New scheduling type applied to solving job-shop scheduling problem[J]. Chinese journal of mechanical engineering, 2008, 44(10): 24–31
[25] 巴黎, 李言, 曹源, 等. 考虑批量装配的柔性作业车间调度问题研究[J]. 中国机械工程, 2015, 26(23): 3200–3207
BA Li, LI Yan, CAO Yuan, et al. Research on flexible job-shop scheduling problem with consideration of batch splitting and assembly[J]. China mechanical engineering, 2015, 26(23): 3200–3207
备注/Memo
收稿日期:2021-01-31。
基金项目:重庆市技术创新与应用示范项目(cstc2018jszx-cyzdX0150);重庆市技术创新与应用示范专项项目(cstc2018jszx-cyzdX0187)
作者简介:柳冬，硕士研究生，主要研究方向为智能优化算法、生产调度;宋豫川，教授，博士生导师，博士，主要研究方向为制造系统工程、智能制造及装备。发表学术论文50余篇;杨云帆，硕士研究生，主要研究方向为智能优化算法、生产调度
通讯作者:宋豫川.E-mail：syc@cqu.edu.cn
更新日期/Last Update:
1900-01-01