[1]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]
Copy

Batch scheduling algorithm for flexible machining and assemblyjob shop when the machine breaks down

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 17 Number of periods: 2022 3 Page number: 556-567 Column: 学术论文—智能系统 Public date: 2022-05-05
Title:
Batch scheduling algorithm for flexible machining and assemblyjob shop when the machine breaks down
Author(s):
LIU Dong;  SONG Yuchuan;  YANG Yunfan;  LEI Qi
State Key Laboratory of Mechanical Transmission, Chongqing University, Chongqing 400044, China
Keywords:
flexible assembly job shop scheduling; sublots and batches; machine breakdown; dynamic scheduling; local search; genetic algorithm; completion time; hybrid greed decoding
CLC:
TP278
DOI:
10.11992/tis.202101038
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
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems