基于遗传算法的军工电子柔性车间动态调度研究

肖玉曼 汤旭东

摘  要：文章对军工电子柔性车间的动态调度问题进行了研究，运用改进遗传算法求解军工电子柔性车间的调度问题。结合军工电子产品的特点，建立了基于项目权重的多目标数学模型，运用改进的遗传算法进行模型求解。该改进算法运用了双层染色体的编码方式及POX的交叉方式，并采用基于事件驱动的重新调度策略。最后，运用实例证明了该研究方法的可行性及有效性。

关键词：遗传算法;FJSP;动态调度;军工电子;项目权重评价

中图分类号：TP181       文献标识码：A文章编号：2096-4706（2022）05-0152-05

Research on Dynamic Scheduling of Military Electronic Flexible Job-Shop Based on Genetic Algorithm

XIAO Yuman， TANG Xudong

（The 26th Institute of China Electronics Technology Group Corporation， Chongqing  400060， China）

Abstract： In this paper， the dynamic scheduling problem of military electronics flexible job-shop is studied， and the improved genetic algorithm is used to solve the scheduling problem of military electronics flexible job-shop. Combined with the characteristics of military electronic products， a multi-objective mathematical model based on project weight is established， and the improved genetic algorithm is used to carry out model solving. The improved algorithm uses double-layer chromosome coding mode and POX crossover mode， and adopts rescheduling strategy based on event-driven. Finally， the feasibility and effectiveness of the research method are proved by examples.

Keywords： genetic algorithm; FJSP; dynamic scheduling; military electronics; evaluation of project weight

0  引  言

在当前风云变幻的国际形势下，我国军用电子元器件、组件模块国产化进程明显加快，军工电子领域普遍呈现订货数量激增的态势。面对市场需求激增的情况，军工企业除了需增加投入生产资源、扩大产能，还需通过科学的方法提升生产效率。生产排程优化就是其中一个突破点。

1  军工电子项目生产排产现状

目前军工电子产品已呈现出集成化、模块化的发展趋势，其主要特点是多品種、小批量、柔性作业、不确定性较多，而军工行业很多还是采用的传统的生产计划制定方式，如人工制定甘特图、网络计划图等。传统的生产计划方式很难达到多任务情况下的最佳的排产效果，同时费时费人力，这样就会造成生产效率低下，浪费生产资源，增加生产成本等。如多个项目在计划编制过程中，生产调度运用传统的计划编制模式，对资源兼顾不足，顾此失彼，会给资源调配增加难度，也会造成计划编制的不合理及频繁调整。

2  智能算法在FJSP问题方面的研究

近年来，通过智能算法解决柔性车间调度问题（FJSP问题）已得到广泛研究，可以提高生产效率，提高企业的市场竞争力[1]。FJSP问题在求解时会同时考虑工件排序和机器选择两个子问题，从而使作业车间调度问题更加符合真实车间情况。解决FJSP问题的常用方法有禁忌搜索法（taboo search， TS），遗传算法（genetic algorithm， GA）和粒子群优化（particle swarm optimization， PSO）等[2-4]。其中遗传算法在车间调度问题的研究中应用最广。本文借鉴前辈学者的理论研究经验，结合军工电子行业产品的特点，对项目进行评价确认项目权重，建立多目标FJSP动态调度问题的应用研究。

3  FJSP动态调度问题的数学模型

FJSP问题简单地说可表述为n个工件在m台机器上的加工，各工件工序加工顺序和工序在各机器上的加工时间已知，求解各工件的加工顺序和所使用的机器，使某些期望值达到最优。本文研究的优化目标是项目的总完工时间最小和总拖期时间最小。同时结合了紧急插单的动态事件发生后的重调度策略。

3.1  模型符号

数学模型涉及的符号意义如表1所示。

3.2  目标函数

最小化最大完工时间：

最小化总拖期时间：

3.3  约束条件

FJSP问题要满足的约束条件分为两大类：工件约束和机器约束。具体约束条件为：

（1）工件的当前工序必须在上一道工序结束后才能开始：

Cij≤Si（j+1）

（2）任何一个工件的一道工序在同一时刻只能够被一台可选机器加工：

（3）一台机器只能同时加工一个工件的一道工序：

Cij×xijh≤Skl×xklh，Sij≤Skl，xijh=1，xklh=1

Ckl×xklh≤Sij×xijh，Sij≥Skl，xijh=1，xklh=1

（4）工件的工序一旦开始就不能被打断：

Cij×xijh=Sij×xijh+Oijh

3.4  项目权重评价

军工电子产品由于其行业背景的特点，在进行项目重要度评价时，评价因素与普通电子产品有所区别。主要会考虑项目的重要程度、风险程度以及成本效益因素。这三类评价影响因素又可以进一步细分，具体如图1所示。

图1  项目权重影响因素

（1）各影响因素的权重计算。各影响因素的权重计算可采用AHP层次分析法[5]，通过专家评分，由各项目所属专业领域的专家及资深主管组成专家组，对各层级的影响因素进行两两比较，对各专家给出的标度取平均值，对影响因素进行权重计算，即可得出各影响因素的权重。

（2）评分标准。项目在进行评价打分时，参照的评分标准如表2所示。

每个评价因素评分从0～10分，由专家评分得出。将各影响因素平均评分与影响因素权重相乘后，即可得出项目的权重值。

4  遗传算法求解FJSP动态调度问题

4.1  染色体编码

运用遗传算法解决问题的关键就是编码和解码。对于FJSP问题，工件要同时选择较优的加工顺序和较优的加工设备或人力资源（本文统一表示为机器），所以本文采用双层编码方式进行编码[6]，一个调度方案由2层染色体组成，具体含义如图2所示。

工序编码：染色体长度等于所有工件的工序总数，直接用工件编号作为编码基因，工件编号出现的次数为该工件的工序数，Pij表示第i个工件的第j道工序。机器编码染色体如图3所示。

机器编码：染色体长度同工序总数，每一个基因用机器编号直接编码，与第一层编码相对应。每个基因位的机器编号应属于第一层对应工件的工序可用机器集合。

本文采用两阶段的方式产生初始种群，首先随机产生工序编码染色体，其次根据各工件各工序可用机器集合随机产生机器编码染色体。

4.2  选择交叉和变异

选择的目的就是遵循适者生存的原则，将高质量的父代遗传给子代[1]。本文是多目标函数，两个目标函数都是求解最小值，故将两个目标函数的加权求和的倒数作为原个体适应度值。选择采用轮盘赌选择法，即由各个适应度的值在总体适应度的比率确定。

由于染色体编码采用包括工序编码和机器编码的双层遗传编码方式，机器编码是对应工序编码生成的，故先针对工序编码采用POX的交叉方式[6]，机器编码对应的位置进行交叉互换，以避免非法解的产生。交叉的操作如图4所示。

图4  POX交叉操作

变异操作先是在工序编码段的基因随机选取两点进行交换，而机器编码段相应位置的基因也跟着一起交换，因工序基因的交换改变了工件的工序信息，故有可能会使得机器编码段产生非法解，针对非法解则根据机器约束条件设置的罚函数使其淘汰。

4.3  动态优化策略

动态车间调度问题普遍的研究方向分为基于事件驱动和周期驱动的重新调度策略[7]，结合柔性车间发生动态事件的常见情况，本文采用基于事件驱动的策略，也就是在动态事件发生的时刻对还未开始的工序进行重调度。根据军工项目的特点，动态事件主要包括项目交货期调整、紧急插单、项目暂停或取消等。

当动态事件发生时，存在以下两种约束：

一是工件的初始时间：

T-Ji=max（Ci（ji-1），NewT）

Ji为工件i需要重新调度的第一道工序的原工序编号;Ci（ji-1）为工件i需重调度工序的上一道工序的完工时间;NewT则为动态事件发生的时间。

二是机器的初始时间：

T-Mh=max（Ch，NewT）

h为当前机器的编号，且1≤h≤m;Ch为机器h当前工序的结束时间;NewT为动态事件发生的时间。

当动态事件发生时，根据约束条件定位到需重调度的工件工序信息。然后初始化需重调度的工件数，初始化各工件剩余工序加工时间集合，初始化各工序可选机器集合，初始化各工件交货期。即Oi1=OiJi，Oi2=Oi（Ji+1），…，Oi（gi-Ji+1）=Oigi，Mi1=MiJi，Mi2=Mi（Ji+1），…，Mi（gi-Ji+1）=Migi;d1=d1-NewT，d2=d2-NewT，…，di=di-NewT。然后對当前所有还未开始的工件工序进行重调度。当出现交货期变更，则只需要调整目标函数中对应的交货期变量。当出现项目暂停或取消时，则将该项目的未开始工序从待排产工序中去除。

5  FJSP动态调度在军工电子项目中的应用

下面以某军工电子模块、组件生产线为例，进行某时间段生产任务的动态调度优化。该生产线为典型的柔性作业方式，部分工序关键靠人工作业（如手工焊、调试等），部分工序则主要依靠设备（如自动贴片、平行封焊、激光封焊等）。且存在多能工情况，故将各工序关键资源设定为人员或设备。初始排产涉及的项目有5项，用编号1～5表示，如遇到项目产品数量较多时，可拆单，将其视为几个单独的项目。项目的工序数和可用资源集合信息如表3所示。项目各工序加工工时和交货期如表4所示。

5.1  项目权重评估

在进行项目排产前，先请项目专业版块的专家、设计师、工艺人员、项目主管、质量主管就图1中的项目权重影响因素进行两两比较，通过AHP法得出各影响因素如表5所示。

然后由专家组对项目按3.4节所述评分标准进行评价打分，得出5个项目的各影响因素评价得分平均值如表6所示。

综上，将各项目影响因素得分与影响因素权重相乘求和，得到各项目权重如表7所示。

5.2  MATLAB仿真运算

针对以上5个项目的情况，运用遗传算法进行MATLAB仿真运算，软件版本为MATLAB R2018a，运行参数为：种群大小nchr=100，最大迭代次数G=500，交叉概率Pc=0.8，变异概率Pm=0.1。目标函数F1的权重为0.3，目标函数F2的权重为0.7。

仿真运算结果得到的最优方案对应的甘特图展示如图5所示，最小总拖期时间值为5 596.67，最小总完工时间为2 015。

当出现插单情况时，触发重调度机制，对截止到当前时间的未完项目工序及新增项目进行重调度。本案例插入订单时间为500 min时，插入订单权重得分为6.360 542 08，订单其他信息如表8所示。

此时，根据前最优调度方案可得出需重调度的工件信息如表9所示。

重调度后得到的最优方案对应的甘特图展示如图6所示，最小总拖期时间值为8 793.92，最小总完工时间为2 395。

6  结  论

本文基于遗传算法解决军工电子柔性车间动态调度问题。该算法采用双层编码方式，并考虑紧急插单、交期变更、项目暂停等情况进行动态优化，使算法模型更贴近实际需求。同时，在项目权重评价时采用AHP法，得到定量的分析结果。基于遗传算法求解柔性车间动态调度问题比传统的生产计划制定方式更高效，也是适应智能制造的发展趋势。

后续的研究主要工作一方面可以进一步优化模型，考虑添加更多不确定性因素，如工艺流程的变更、设备或资源中断情况等，考虑多个不确定性因素并存时对生产调度的影响。另一方面可以研究优化改进算法或其他的智能算法以求解此类问题。

参考文献：

[1] 郭庆，张明路，孙立新，等.基于遗传算法的柔性车间调度优化 [J].科学技术与工程，2020，20（29）：11931-11936.

[2] 肖华军.考虑能效的双资源柔性作业车间调度问题研究 [D].武汉：华中科技大学，2019.

[3] 刘胜，于海强.基于改进遗传算法的多目标FJSP问题研究 [J].控制工程，2016，23（6）：816-822.

[4] 刘敏，张超勇，张国军，等.基于混合粒子群优化算法的置换流水车间调度问題研究 [J].中国机械工程，2011，22（17）：2048-2053.

[5] 孙宏才，田平，王莲芬.网络层次分析法与决策科学 [M].北京：国防工业出版社.2011.

[6] 张超勇，饶运清，李培根，等.求解作业车间调度问题的一种改进遗传算法 [J].计算机集成制造系统，2004（8）：966-970.

[7] 孙丽珍，毕利.多约束条件下的动态柔性作业车间调度研究 [J].控制工程，2020，27（11）：1921-1929.

作者简介：肖玉曼（1989—），女，汉族，重庆人，工程师，硕士研究生，研究方向：项目管理。