随着我国工业4.0和智能制造的快速发展，柔性车间生产已成为国内大部分制造企业采用的主要生产模式。柔性车间包含柔性流水车间和柔性作业车间两大类，其生产环境具有产品种类繁多、结构复杂、机器种类数量大、突发事件多（譬如突发机器故障和紧急插单）等诸多特点，从而导致出现订单最大完工时间长、总拖延时间大以及机器利用率低等一系列问题，严重影响企业生产效率和客户满意度。分析现有研究可知，尽管目前存在较为丰富的柔性车间生产调度研究，然而其无法有效满足企业生产所面临的产品结构拆分、订单任务安排和机器选择繁杂以及突发事件时有发生等现实复杂柔性车间生产调度的要求。因此，开展面向上述复杂环境的柔性车间生产调度建模与优化研究迫在眉睫。

       本文主要针对制造企业的两类柔性制造场景（包含柔性流水车间和柔性作业车间），主要开展如下车间生产调度建模与优化研究:

    （1）基于改进遗传算法的柔性流水车间调度建模及优化研究。本部分首先构建了考虑产品结构拆分的柔性流水车间单目标静态调度优化决策模型；然后，运用了融合启发式规则和时窗比较策略的双层置换编码解码方法，设计了与双层染色体对应的交叉变异操作与精英保留策略，提出了基于双层置换编码的改进遗传算法，获得了考虑产品结构拆分的柔性流水车间的最优调度方案；最后，采用标准算例验证了改进遗传算法优于一般算法，并在较大规模算例中表现优秀，同时通过实际案例验证了该模型及改进遗传算法的可行性和有效性。

     （2）基于改进NSGA-II的柔性作业车间多目标动态调度建模及优化研究。考虑柔性作业车间面临的订单种类多、机器类型复杂以及突发事件频发（譬如机器故障、紧急插单等）等复杂内外部生产环境，本部分首先构建了考虑订单任务拆分的柔性作业车间多目标动态调度数学模型，该模型以订单总组成时差最小、订单总拖延时间最短和机器空闲总时间最小为模型目标；然后，采用周期和事件混合驱动的动态调度驱动机制，设计了改进非支配排序遗传算法II（改进NSGA-II）。该算法采用启发式规则的三层编码和时窗比较策略的解码，并将熵权TOPSIS法用于评价多目标决策最优前沿面的方案，从而高效获得复杂多变动生产环境下的柔性作业车间调度优化方案；最后，将所建模型与算法应用于企业案例。

       本研究一方面进一步丰富和完善了现有柔性车间生产调度优化理论与方法，另一方面研究所构建的柔性车间调度模型与提出的调度算法可以有效解决目前制造企业所面临的订单任务安排和机器分配难题，有效减少订单生产周期、提升机器利用率与客户满意度。

    With the rapid development of China's Industry 4.0 and smart manufacturing, flexible workshop production has become the main production mode adopted by most domestic manufacturing enterprises. The flexible workshop consists of two categories: flexible flow shop and flexible job shop. Its production environment is characterised by a wide range of products, complex structures, a large number of machine types and many unexpected events (such as unexpected machine breakdowns and emergency order insertion), leading to a series of problems such as long maximum order completion time, large total delay time and low machine utilisation, which seriously affect the production efficiency and customer satisfaction of the enterprise. Analysis of existing research shows that although there is a wealth of research on flexible shop floor production scheduling, it is unable to effectively meet the realistic and complex requirements of flexible shop floor production scheduling, such as the splitting of product structures, complicated order task scheduling and machine selection, and the occurrence of unexpected events. Therefore, it is urgent to carry out research on the modelling and optimisation of flexible shop floor production scheduling for these complex environments.

    In this paper, we focus on two types of flexible manufacturing scenarios (including flexible flow shop and flexible job shop) in manufacturing enterprises, and carry out the following workshop production scheduling modelling and optimisation studies:

    (1) Modeling and optimization of flexible flow shop scheduling based on improved genetic algorithm. In this part, a single-objective static scheduling optimization decision model for flexible flow shop considering product structure splitting is firstly constructed; then, a double-layer replacement coding decoding method integrating heuristic rules and time-window comparison strategy is applied, cross-variation operations and elite retention strategies corresponding to double-layer chromosomes are designed, and an improved genetic algorithm based on double-layer replacement coding is proposed to obtain the optimal scheduling solution for flexible flow shop considering product structure splitting. Finally, the improved genetic algorithm is verified to be better than the general algorithm by using standard cases, and performs well in larger cases, and the feasibility and effectiveness of the model and the improved genetic algorithm are verified by practical cases.

    (2) Research on multi-objective dynamic scheduling modelling and optimization of flexible job shop based on improved NSGA-II. Considering the complex internal and external production environment faced by the flexible job shop, such as many types of orders, complex machine types and frequent unexpected events (e.g. machine breakdown, emergency order insertion, etc.), this part firstly constructs a multi-objective dynamic scheduling mathematical model for the flexible job shop considering order task splitting, with the objectives of minimising order composition simultaneity, minimising total order delay time and minimising total machine idle time. Then, an improved non-dominated sequencing genetic algorithm II (Improved NSGA-II) is designed using a dynamic scheduling drive mechanism driven by a mixture of cycles and events. The algorithm employs triple encoding of heuristic rules and decoding of time-window comparison strategies, and the entropy-weighted TOPSIS method is used to evaluate the solution of the optimal frontier surface for multi-objective decision making, so as to efficiently obtain an optimisation solution for flexible job shop scheduling in a complex and variable production environment; finally, the proposed model and algorithm are applied to an enterprise case.

    On the one hand, this study further enriches and improves the existing theories and methods of flexible shop floor production scheduling optimisation, and on the other hand, the flexible shop floor scheduling model and the proposed scheduling algorithm can effectively solve the order task scheduling and machine allocation problems faced by manufacturing enterprises at present, effectively reducing order production cycle time and improving machine utilisation and customer satisfaction.

[1]王凌.车间调度及其遗传算法[M]. 北京:清华大学出版社, 2003.

[2]Johnson SM. Optimal two-and three-machine production schedules with setup times included [J]. Naval Research Logistics Quarterly, 1954, 1(1): 61-68.

[3]Giffler B, Thompson G L. Algorithms for solving production scheduling problems[J]. Operations Research, 1960, 8(4):487-503.

[4]Panwalker S, Wafik Lskander. A survey of scheduling rules[J]. Operations Research, 1977, 25(1): 45-61.

[5]Simon Y P, Takefuji. Stochastic neural networks for solving job-shop scheduling. I. Problem representation[C]. IEEE International Conference on Neural Networks. IEEE, 1988: 275-282.

[6]Aarts E H L, Van Laarhoven P J M, Lenstra J K, et al. A computational study of local search algorithms for job shop scheduling[J]. 1994, 6(2):118-125.

[7]Laguna M , Barnes J W , Glover F W . Tabu search methods for a single machine scheduling problem[J]. Journal of Intelligent Manufacturing, 1991, 2(2):63-73.

[8]Nakano R, Yamada T. Conventional genetic algorithm for job shop problems[J]. Proceeding of the Fourth International Conference on Genetic Algorithms, 1991, 1:474-479.

[9]Pinedo M. Scheduling: theory, algorithms and system (2nd Edition) [M]. Prentice Hall, Upper Saddle River, New Jersey, 2002.

[10]Brucker P, Schlie R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(3): 369-375.

[11]牟云,阎春平,刘艺繁,孙雷. 考虑能耗和完工时间的柔性流水车间调度方法[J]. 制造业自动化, 2021, 43(10):45-52+74.

[12]刘约翰,韩忠华,林硕,史海波,常大亮,孙亮亮. 可重入工序柔性流水车间有限缓冲区排产研究[J]. 现代制造工程, 2020, 2020(11):21-32+40.

[13]林硕,陈世佳,韩忠华. 改进HNN算法求解柔性流水车间排产优化问题[J]. 控制工程, 2019, 26(09):1667-1674.

[14]韩忠华,朱伯秋,林硕,宫巍. 变工时柔性流水车间排产优化问题研究[J]. 计算机仿真, 2018, 35(07):158-164.

[15]王芳,唐秋华,饶运清,张超勇,张利平. 求解柔性流水车间调度问题的高效分布估算算法[J]. 自动化学报, 2017, 43(02):280-293.

[16]张其亮,陈永生. 基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J]. 系统工程理论与实践, 2014, 34(03):802-809.

[17]杨琴,周国华,林晶晶,赵茜. 基于DBR理论的柔性流水车间动态调度[J]. 控制与决策, 2011, 26(07):1109-1112.

[18]Hasani A, Hosseini S M H, Sana S S. Scheduling in a flexible flow shop with unrelated parallel machines and machine-dependent process stages: Trade-off between Makespan and production costs[J]. Sustainability Analytics and Modeling, 2022, 2(1):2667-2596.

[19]Minghui Z, Yan L, Xin H. Approximation algorithms for two-stage flexible flow shop scheduling[J]. Journal of Combinatorial Optimization, 2020, 39(3):1-14.

[20]Hakeem U R, Wan G, Zhan Y. Multi-level, multi-stage lot-sizing and scheduling in the flexible flow shop with demand information updating[J]. International Transactions in Operational Research, 2019, 28(4):2191-2217.

[21]Watcharapan S, Teeradej W. Hybrid genetic algorithm and tabu search for finite capacity material requirement planning system in flexible flow shop with assembly operations[J]. Computers & Industrial Engineering, 2016, 97(1):157-169.

[22]Li Z, Liu J, Chen Q, Mao N, Wang X. Approximation algorithms for the three-stage flexible flow shop problem with mid group constraint[J]. Expert Systems With Applications, 2015, 42(7):3571-3584.

[23]Raviteja B, Siba S M. Improved teaching–learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems[J]. Journal of Industrial Engineering International, 2018, 14(3):555-570.

[24]巴黎, 李言, 曹源, 杨明顺, 刘永. 考虑批量装配的柔性作业车间调度问题研究[J].中国机械工程, 2015, 26(23):3200-3207.

[25]姜一啸, 吉卫喜, 何鑫, 苏璇. 基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度[J]. 中国机械工程, 2022, 33(21):2564-2577.

[26]王秋莲, 段星皓. 基于高维多目标候鸟优化算法的柔性作业车间调度[J]. 中国机械工程, 2022, 33(21):2601-2612.

[27]李俊青, 杜宇, 田杰, 段培永, 潘全科. 带运输资源约束柔性作业车间调度问题的人工蜂群算法[J]. 电子学报, 2021, 49(02):324-330.

[28]张国辉, 陆熙熙, 胡一凡, 孙靖贺. 基于改进帝国竞争算法的柔性作业车间机器故障重调度[J]. 计算机应用, 2021, 41(08):2242-2248.

[29]栾飞, 吴书强, 李富康, 杨嘉, 蔡宗琰. 一种求解柔性作业车间调度问题的鲸鱼群优化算法[J]. 机械科学与技术, 2020, 39(02):241-246.

[30]张维存, 赵晓巧. 柔性作业车间人员配置及作业排序问题研究[J]. 计算机应用研究, 2018, 35(12):3722-3728.

[31]王万良, 范丽霞, 徐新黎, 赵燕伟, 张静. 多目标差分进化算法求解柔性作业车间批量调度问题[J]. 计算机集成制造系统, 2013, 19(10):2481-2492.

[32]沈益民, 范玉顺. 带有跨工序约束的柔性job shop调度问题[J]. 计算机应用研究, 2008, 2008(07):2023-2026.

[33]Liu R, Piplani R, Toro C. Deep reinforcement learning for dynamic scheduling of a flexible job shop[J]. International Journal of Production Research, 2022, 60(13):4049-4069.

[34]Jiang T, Zhu H, Gu J, Liu L, Song H. A discrete animal migration algorithm for dual-resource constrained energy-saving flexible job shop scheduling problem[J]. Journal of Intelligent & Fuzzy Systems, 2022, 42(4):3431-3444.

[35]Wang C, Li Y, Li X. Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 261-271.

[36]Tamssaouet K, Dauzère P S, Knopp S, Bitar A, Yugma C. Multiobjective optimization for complex flexible job-shop scheduling problems[J]. European Journal of Operational Research, 2022, 296(1):87-100.

[37]Park J, Ng H, Chua T, Ng Y, Kim J. Unified Genetic Algorithm Approach for Solving Flexible Job-Shop Scheduling Problem[J]. Applied Sciences, 2021, 11(14):6454-6454.

[38]Fan J, Shen W, Gao L, Zhang C, Zhang Z. A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths[J]. Journal of Manufacturing Systems, 2021, 60:298-311.

[39]Hemamalini T, Geetha G. Combinatory Least Slack and Kuhn Tucker Optimization for Multiobjective Flexible Job Shop Scheduling[J]. Journal of Physics: Conference Series, 2021, 1947(1):1-14.

[40]Jacques C, Emmanuel N. An Exact Method for Solving the Multi-Processor Flow-Shop[J]. RAIRO - Operations Research, 2000, 34(1):1-25.

[41]Emmanuel N, Philippe B, Jatinder N G. Solving hybrid flow shop problem using energetic reasoning and global operations[J]. Omega, 2001, 29(6):501-511.

[42]Orhan E, Alper D. A new approach to solve hybrid flow shop scheduling problems by artificial immune system[J]. Future Generation Computer Systems, 2004, 20(6):1083-1095.

[43]Kemal A, Orhan E, Alper D. Using ant colony optimization to solve hybrid flow shop scheduling problems[J]. The International Journal of Advanced Manufacturing Technology, 2007, 35(5-6):541-550.

[44]Cengiz K, Orhan E, Ihsan K, Mustafa K Y. An application of effective genetic algorithms for Solving Hybrid Flow Shop Scheduling Problems[J]. International Journal of Computational Intelligence Systems, 2008, 1(2):134-147.

[45]Niu Q, Zhou T, Ma S. A Quantum-Inspired Immune Algorithm for Hybrid Flow Shop with Makespan Criterion[J]. J. UCS, 2009, 15(4):765-785.

[46]Liao C, Evi T, Chung T. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem[J]. Applied Soft Computing, 2012, 12(6):1755-1764.

[47] CUI Z, GU Xingsheng, An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problem[J]. Neurocomputing, 2015, 148(1):248-259.

[48]Santos D, Hunsucker J, Deal D. Global lower bounds for flow shops with multiple processors[J]. European Journal of Operational Research, 1995, 80(1):112-120.