设备故障下的零空闲多设备工作中心调度

doi:10.3778/j.issn.1002-8331.2304-0246

摘要/Abstract

摘要： 设备故障是车间调度中最为常见的动态事件，易对原生产调度计划造成影响。为保证加工生产在遇到设备故障后能够快速地对原调度方案做出调整，降低设备故障所带来的负面影响，对设备故障下的零空闲多设备工作中心调度问题进行研究。建立了设备故障下考虑调整时间和搬运时间的零空闲多设备工作中心调度模型，优化目标为最小化最大完工时间、搬运次数和系统稳定性；设计NSGA-Ⅱ-V算法用于原调度和重调度的求解；基于NSGA-Ⅱ-V获得的静态调度结果与部分重调度策略的思想，进行设备故障算例测试。测试结果表明，所提模型和算法可较好地处理动态事件为设备故障的零空闲多设备工作中心调度问题。

关键词: 零空闲多设备工作中心调度, 遗传算法, 设备故障, 调整时间, 搬运时间

Abstract: Device failure is the most common dynamic event in shop floor scheduling, which easily affects the original production scheduling plan. In order to ensure that processing production can quickly make adjustments to the original scheduling plan after encountering device failure and reduce the negative impact caused by device failure, the scheduling problem of no-idle multi-device work center under device failure is studied. Firstly, a no-idle hybrid flow shop scheduling model considering setup time and handling time under device failure is established, and the optimization objectives are completion time, handling times and system stability. Secondly, the NSGA-II-V algorithm is designed for solving the original scheduling and rescheduling. Finally, based on the static scheduling results obtained by NSGA-II-V with the idea of partial rescheduling strategy, the device failure cases are tested, and the test results show that the proposed model and algorithm can better handle the zero-idle hybrid flow shop scheduling problem where the dynamic event is completion time failure.

Key words: no-idle multi-device work center scheduling, genetic algorithm, device failure, setup time, handling time

孔继利, 冯英杰. 设备故障下的零空闲多设备工作中心调度[J]. 计算机工程与应用, 2024, 60(14): 306-318.

KONG Jili, FENG Yingjie. No-Idle Multi-Device Work Center Scheduling Under Device Failure[J]. Computer Engineering and Applications, 2024, 60(14): 306-318.

参考文献

[1] 王静云, 王雷, 蔡劲草, 等. 多目标混合流水车间调度问题求解算法[J]. 南京航空航天大学学报, 2023, 55(3): 544-552.
WANG J Y, WANG L, CAI J C, et al. Solution algorithm of multi-objective hybrid flow shop scheduling problem[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2023, 55(3): 544-552.
[2] 罗函明, 罗天洪, 吴晓东, 等. 求解混合流水车间调度问题的离散布谷鸟算法[J]. 计算机工程与应用, 2020, 56(22): 264-271.
LUO H M, LUO T H, WU X D, et al. Discrete cuckoo search algorithm for solving hybrid flow shop scheduling problem[J]. Computer Engineering and Applications, 2020, 56(22): 264-271.
[3] 余斌煌. 柔性流水车间调度问题综述[J]. 现代制造工程, 2022(9): 154-162.
YU B H. Review on flexible flow shop scheduling[J]. Modern Manufacturing Engineering, 2022(9): 154-162.
[4] UMAM M S, MUSTAFID M, SURYONO S. A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem[J]. Journal of King Saud University-Computer and Information Sciences, 2022, 34(9): 7459-7467.
[5] CHU H, DONG K, LI R, et al. Integrated modeling and optimization of production planning and scheduling in hybrid flow shop for order production mode[J]. Computers & Industrial Engineering, 2022, 174: 108741.
[6] 李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23): 2798-2813.
LI Y L, LI X Y, GAO L. Review on hybrid flow shop scheduling problems[J]. China Mechanical Engineering, 2020, 31(23): 2798-2813.
[7] CHEN J, WANG L, PENG Z. A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling[J]. Swarm and Evolutionary Computation, 2019, 50: 100557.
[8] 张晓霞, 吕云虹. 一种求解混合零空闲置换流水车间调度禁忌分布估计算法[J]. 计算机应用与软件, 2017, 34(1): 270-274.
ZHANG X X, LV Y H. A tabu estimation of distribution algorithm to solve the mixed no-idle permutation flowshop scheduling problem[J]. Computer Applications and Software, 2017, 34(1): 270-274.
[9] SHAO W, PI D, SHAO Z. Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion[J]. Applied Soft Computing, 2017, 54: 164-182.
[10] 刘翱, 冯骁毅, 邓旭东, 等. 求解零空闲置换流水车间调度问题的离散烟花算法[J]. 系统工程理论与实践, 2018, 38(11): 2874-2884.
LIU A, FENG X Y, DENG X D, et al. A discrete fireworks algorithm for solving no-idle permutation flow shop problem[J]. Systems Engineering Theory & Practice, 2018, 38(11): 2874-2884.
[11] 裴小兵, 李依臻. 应用改进混合进化算法求解零空闲置换流水车间调度问题[J]. 运筹与管理, 2020, 29(11): 204-212.
PEI X B, LI Y Z. Improved hybrid evolutionary algorithm for solving no-idle permutation flow shop scheduling problem[J]. Operations Research and Management Science, 2020, 29(11): 204-212.
[12] ZHAO F, ZHANG L, CAO J, et al. A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem[J]. Computers & Industrial Engineering, 2021, 153: 107082.
[13] 闫红超, 汤伟, 姚斌, 等. 新混合鸟群算法求解零空闲流水车间调度问题[J]. 微电子学与计算机, 2022, 39(9): 98-106.
YAN H C, TANG W, YAO B, et al. New hybrid swarm algorithm for solving no-idle flow-shop scheduling problem[J]. Microelectronics & Computer, 2022, 39(9): 98-106.
[14] 赵芮, 郎峻, 顾幸生. 基于多目标离散正弦优化算法的混合零空闲置换流水车间调度[J]. 华东理工大学学报 (自然科学版), 2022, 48(1): 76-86.
ZHAO R, LANG J, GU X S. Mixed no-idle permutation flow shop scheduling problem based on multi-objective discrete sine optimization algorithm[J]. Journal of East China University of Science and Technology, 2022, 48(1): 76-86.
[15] 轩华, 唐立新. 带多处理器任务的动态混合流水车间调度问题[J]. 计算机集成制造系统, 2007(11): 2254-2260.
XUAN H, TANG L X. Dynamic hybrid flow shop scheduling problem with multiprocessor tasks[J]. Computer Integrated Manufacturing Systems, 2007(11): 2254-2260.
[16] 王芊博, 张文新, 王柏琳, 等. 基于Agent的混合流水车间动态调度系统[J]. 计算机应用, 2017, 37(10): 2991-2998.
WANG Q B, ZHANG W X, WANG B L, et al. Agent-based dynamic scheduling system for hybrid flow shop[J]. Journal of Computer Applications, 2017, 37(10): 2991-2998.
[17] 甘婕, 侯青玉, 汪思宇, 等. 流水车间调度与视情维修的联合决策[J]. 工业工程与管理, 2023, 28(1): 207-214.
GAN J, HOU Q Y, WANG S Y, et al. The joint decision and optimization of flow-shop scheduling and condition based maintenance[J]. Industrial Engineering and Management, 2023, 28(1): 207-214.
[18] YIN J, LI T, CHEN B, et al. Dynamic rescheduling expert system for hybrid flow shop with random disturbance[J]. Procedia Engineering, 2011, 15: 3921-3925.
[19] JOO B J, CHOI Y C, XIROUCHAKIS P. Dispatching rule-based algorithms for a dynamic flexible flow shop scheduling problem with time-dependent process defect rate and quality feedback[J]. Procedia CIRP, 2013, 7: 163-168.
[20] 李丹. 改进群智能优化算法的海上物流配送路径优化方法[J]. 舰船科学技术, 2020, 42(16): 184-186.
LI D. Optimization method of marine logistics distribution path based on improved swarm intelligence optimization algorithm[J]. Ship Science and Technology, 2020, 42(16): 184-186.
[21] 顾清华, 徐青松, 李学现. 基于距离优势关系的高维多目标进化算法[J]. 计算机科学与探索, 2022, 16(11): 2642-2652.
GU Q H, XU Q S, LI X X. Many-objective evolutionary algorithm based on distance dominance relation[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(11): 2642-2652.
[22] 李珺, 段钰蓉, 郝丽艳, 等. 混合优化算法求解同时送取货车辆路径问题[J]. 计算机科学与探索, 2022, 16(7): 1623-1632.
LI J, DUAN Y R, HAO L Y, et al. Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery?pickup[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1623-1632.
[23] 周永强, 王翠雨, 李颖俐, 等. 改进果蝇算法求解混合流水车间调度问题[J]. 控制理论与应用, 2023, 40(4): 597-606.
ZHOU Y Q, WANG C Y, LI Y L, et al. Improved fruit fly optimization algorithm for solving and the hybrid flow shop scheduling Problem[J]. Control Theory & Applications, 2023, 40(4): 597-606.
[24] AMIRTEIMOORI A, MAHDAVI I, SOLIMANPUR M, et al. A parallel hybrid PSO-GA algorithm for the flexible flow-shop scheduling with transportation[J]. Computers & Industrial Engineering, 2022, 173: 108672.
[25] 雷斌, 刘同朝. 基于PSO-GA混合算法的转向架混流装配车间生产调度研究[J]. 现代制造工程, 2020(7): 19-24.
LEI B, LIU T C. Research on production scheduling of bogie mixed flow assembly[J]. Modern Manufacturing Engineering, 2020(7): 19-24.
[26] SRINIVAS N, DEB K. Multi-objective function optimization using nondominated sorting genetic algorithms[J]. Evolutionary Computation, 1995, 2(3): 221-248.
[27] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[28] LEUNG Y, GAO Y, XU Z B. Degree of population diversity-a perspective on premature convergence in genetic algorithms and its Markov chain analysis[J]. IEEE Transactions on Neural Networks, 1997, 8(5): 1165-1176.
[29] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285.
[30] 赵芮, 顾幸生. 求解零空闲流水车间调度问题的离散正弦优化算法[J]. 上海交通大学学报, 2020, 54(12): 1291-1299.
ZHAO R, GU X S. A discrete sine optimization algorithm for no-idle flow-shop scheduling problem[J]. Journal of Shanghai Jiaotong University, 2020, 54(12): 1291-1299.
[31] ZHOU Y, CHEN H, ZHOU G. Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem[J]. Neurocomputing, 2014, 137: 285-292.