复杂壳体零件制造车间调度方法研究*

付 梅，谢 怀，王荪馨，申高攀

（1.中国航发西安动力控制科技有限公司，西安 710077；2.西安理工大学，西安 710048；3.西北工业大学，西安 710072）

航空发动机生产具有典型的多品种、小批量特征，而不同型号任务之间的频繁切换使得生产组织、生产准备、作业调度、现场协调等都更为复杂和困难。随着航空发动机型号研制任务量的不断攀升，以及中国航发AEOS（Aero-engine corporation of China operation system）生产制造体系在各生产企业的深入推进，构建流水作业生产单元、实现精益化转型、强化生产现场执行和管控机制已成为航空发动机制造企业的普遍共识。

近年来，各生产单位进行了大规模的产线改造和产能提升工程，“专业化、小流水”已成为航发制造企业的主流生产组织方式。在依据精益生产单元、成组技术所形成的流水作业车间内，不同零件沿单元内不同设备流转加工的工艺路线类似，但同一机器上不同工序的加工顺序没有特殊要求。非置换流水车间调度（Nonpermutation flow-shop scheduling，NPFS）是传统置换流水车间调度的一种推广，它允许在不同机器上改变工件的加工顺序[1]。因此，航空发动机精益制造单元生产方式属于典型的非置换流水车间类型。

另外，航空发动机制造企业长期以来沿用“早完工、早入库、保交付”的生产管控模式，这一较为粗放型的生产管控方式与精益生产、成本理念相距甚远；作业调度作为精益单元现场组织生产的指挥棒，直接决定着零部件生产现场的生产准备、资源配置和人员安排等事宜，因此，精益调度、JIT（Just-in-time）调度则成为航发制造企业落地精益生产的重要抓手。考虑到航发制造企业的现实情况，细化到工序级交货期的JIT 调度目前还不具备实施条件，而以零部件交付节点为关注重点的提前/拖期（Earliness/tardiness，E/T）调度则成为现阶段实施精益调度的有效方式。

提前/拖期调度要求零部件在各自既定的交付节点准时完工，而零部件的提前或拖期完工都会产生相应的惩罚成本。零部件早于所要求的交付节点提前完工，势必导致占用有限的制造资源，同时也带来了不必要的在制品积压成本；而零部件的拖期完工则会打乱整个制造链的生产节拍，使得下游生产环节出现整机配套缺件、停工待料、设备闲置等诸多问题。因此，关注零部件的交付节点（交货期），以满足零部件的准时化交付为目的，通过E/T 调度来实现制造单元的精细运作和低成本运营，对于改善目前航空发动机制造企业存在的高投入、低产出、利润率低等问题具有一定的现实意义。

航空发动机燃油控制系统复杂壳体的生产制造过程属于典型的多品种小批量、专业化小流水生产方式，其具有工艺过程复杂、检测项目多、加工周期长等显著特征。在这类壳体零件工艺设计阶段，综合考虑壳体零件的工艺特殊性和加工设备的利用率等因素，零件内的部分工序需充分考虑工序顺序柔性这一特殊要求，即在不影响产品质量和工艺规范要求的前提下，壳体加工过程中部分工序加工顺序可以相互超越。复杂壳体零件在工艺设计阶段引入工序顺序柔性后，为下游的生产调度优化提供了操作空间。

综合上述，精益单元的流水生产方式、零件粒度的E/T 调度和工序顺序柔性约束这3 个特点，形成了本文的研究对象，即带有工序顺序柔性约束的非置换流水车间E/T调度问题。在非置换流水车间调度方面，Liao等[2]以最小化总延迟为调度目标提出一种禁忌搜索算法；肖鹏飞[3]提出一种基于时序差分法的深度强化学习算法用于求解以Makespan 为调度目标的非置换流水车间调度问题。在工序顺序柔性方面，黄学文等[4]在常用的基于工序顺序的编码方法上融入了基于柔性工序顺序的编码方法，以Makespan 为调度目标对带有工序顺序柔性的作业车间调度问题进行了研究；朱文凡等[5]提出了基于柔性工序和机器选择的两段编码方式，并在此基础上改进遗传算法求解带有工序顺序柔性的作业车间调度问题。在E/T 调度方面，杨宏安等[6]提出一种基于两阶段调度策略的改进遗传算法求解作业车间调度问题，可以有效降低提前/拖期调度总成本；Ahmadian等[7]设计了一种变邻域搜索算法用于求解作业车间JIT 调度问题。

目前的研究中，缺少针对工序顺序柔性的非置换流水车间E/T 调度问题的研究。因此，本文针对该问题的特点，以最小化提前/拖期惩罚总成本为调度目标，设计了一种“两段式编码”、“三阶段解码”的改进型遗传算法，并通过复杂壳体零件制造车间的实际数据验证了算法的实用性。

1 燃油控制系统复杂壳体及其典型工艺路线图

作为航空发动机燃油控制系统中的核心关键零件，壳体是各类油泵、调节器和分布器产品各类元件的载体，它在燃油系统中主要起支撑各控制元件和高中低压油路的导引作用（图1）[8]。该零件外形及铸造内腔基本由圆弧、平面过渡面组成，凸凹相间，孔系众多，空间细长油路孔多达100 个，特征尺寸达到2000 个左右，较为复杂的壳体零件需要进行150～200 道工序。复杂壳体类零件的工艺过程复杂，工艺、工装及检测协同环节多。主要工艺类型包括铣、镗、钻、车、特种加工等，其加工设备以加工中心、数控车床为主。

图1 航空发动机燃油控制系统壳体零件Fig.1 The shell part of aero-engine fuel control system

工序顺序柔性是指工件的若干加工工序在满足工艺约束和产品质量的前提下仍可以具有不同的加工顺序[9]。按照文献[9]中的分类方式，复杂壳体零件属于工艺顺序非完全确定性工件，即该工件的所有工艺可分为若干个柔性工序组，在同一工序组内，所有工艺之间不具有先后加工的工艺约束，但不同组之间具有先后加工的工艺约束。图2 为某燃油控制器壳体零件的部分工艺流程图，其中包含有4 个柔性工序组，工序组内工序无先后加工顺序的要求，可以相互超越加工。该工艺流程图中的柔性工序组可表示为{25，30，35}，{45，50，55}，{65，70，75，80}和{95，100，105}。

图2 燃油控制器壳体零件的部分工艺流程图Fig.2 Partial process flow chart of a fuel control system shell part

2 带有工序顺序柔性的非置换流水车间E/T调度模型

综合以上分析，航空发动机燃油控制系统复杂壳体制造单元的生产调度为一种带有工序顺序柔性的非置换流水车间E/T 调度问题。该调度问题可以描述为：一批壳体零件生产任务以相似的工艺路线在壳体制造单元内的多台机器上依次流转加工，其中，每道工序有固定的加工机器和加工时间，且加工过程一旦开始则不容许中断；另外，每个壳体零件含有一个或多个柔性工序组，且柔性工序组内的各道工序无固定的加工顺序要求。作业调度的主要任务是合理安排各个零件在机器上的加工序列和起止时间，同时使得该批壳体零件的提前/拖期完工惩罚总成本最小，以此确保各个零件尽可能在各自的交付节点完工，以期从生产管控角度来支撑壳体零件的精益生产和低成本运行。

带有工序顺序柔性的非置换流水车间E/T 调度问题可以描述为：n个工件J={J1，J2，…，Jn}在m台机器M={M1，M2，…，Mm}上依次加工；任一工件Ji包含ni道工序，Ji的工艺路线为{Oi，1，Oi，2，…，{Oi，j，Oi，j+1，Oi，j+2}，…，Oi，ni}，其中，{Oi，j，Oi，j+1，Oi，j+2}为工件Ji加工过程中的柔性工序组，柔性工序组内的各工序之间无加工先后次序约束；对于工件Ji，其交货期为ddi，完工时间为Ci，提前完工的单位时间惩罚系数为ei，拖期完工的单位时间惩罚系数为ti，工件的提前完工惩罚成本为Ei，工件的拖期完工惩罚成本为Ti；对于工件Ji的任一工序Oi，j，其开工时间为si，j，加工时间为pi，j，完工时间为Ci，j，承制机床为M（Oi，j）∈M。调度任务是在满足工件工艺路线和机床能力约束的条件下，使得所有工件的提前/拖期完工惩罚总成本（Schedule cost）最小。

式（1）为调度目标函数，即要求所有工件的提前/拖期完工惩罚的总成本最小，以期各工件在各自交货期准时完工。式（2）为工件Ji的提前完工惩罚成本。式（3）为工件Ji的拖期完工惩罚成本。式（4）为工艺路线约束，工件Ji的两工序Oi，j、Oi，j+1需满足工件内的工艺先后顺序约束。式（5）为机床析取（能力）约束，即同一台机床在同一时刻只能加工一个工序任务。式（6）为工序顺序柔性约束，若Oi，j、Oi，j+1在同一柔性工序组内，则二者无先后顺序约束。

3 改进型遗传算法

求解带有工序顺序柔性的非置换流水车间调度问题时，需要在实际生产环境中为含有柔性工序组的工件选择较优的工艺路线，并对所有工件的加工工序进行排序，确定每台机器上工件的加工顺序。与传统的非置换流水车间调度问题相比，工件具有的工序顺序柔性特性扩展了可行解的搜索范围，大大提高了调度求解的难度。

针对工序顺序柔性特性，提出一种两段式编码方法，即在基于工序的编码的基础上增加一段基于柔性工序组的编码用于描述工件的工艺路线，并设计了该段染色体对应的交叉和变异算子。针对工件准时化交付问题，提出一种三阶段解码方式以尽可能降低工件提前/拖期完工惩罚的总成本。

在改进型遗传算法设计中，种群初始化采用基于最早交货期规则的初始种群生成方法[6]；染色体编码采用两段式编码方法；解码操作选择三阶段解码方式；选择操作采用精英保留和锦标赛方法；交叉操作采用分段交叉策略；变异操作采用逆转变异策略。改进型遗传算法的整体框架如图3 所示。

以下重点对改进型遗传算法中染色体的两段式编码与三阶段解码方式、分段交叉算子和逆转变异算子进行阐述。

3.1 两段式编码

本文采用两段式编码方法来描述针对工序顺序柔性的非置换流水车间调度问题的一个可行解，即在基于工序的编码方式的基础上，考虑工序顺序柔性的特殊性，增加了基于柔性工序组编码的染色体段，以描述各工件内的工序加工顺序，形成了两段式编码方法。两段式编码方法及其后续的遗传操作算子是在兼顾工序顺序柔性和车间调度特征基础上进行的针对性设计。

在基于工序的编码的染色体段中，工件号在染色体中出现的次数即为该工件工艺路线上的第几道工序，如图4 所示。以工件J1为例，若其工艺路线为O1，1→O1，2→ O1，3→O1，4→O1，5，数字1 在染色体段中第1 次出现则表示其工艺路线上的第1 道工序O1，1，第2 次出现则表示其工艺路线上的第2 道工序O1，2。

图4 基于工序的编码方法Fig.4 Encoding method based on operation

在基于柔性工序组编码的染色体段中，将染色体分解为与工件数量相同的若干片段。每个片段用于描述其对应工件的加工工艺路线，其长度为工件的工序数量，每个工件对应片段内的数字序列用来描述工件的工艺路线。如图5所示，工件J1的柔性工序组为{O1，2，O1，3，O1，4}，柔性工序组内的工序顺序有多种组合方式。在编码时，从多个组合中随机取出一个作为柔性工序组内工序的工艺路线，得到工件J1对应的染色体片段为{1，3，2，4，5}，即工件J1的加工工艺路线为O1，1→O1，3→O1，2→ O1，4→O1，5。

图5 基于柔性工序组的编码方法Fig.5 Encoding method based on flexible operation group

将两段染色体拼接为一个染色体，即为针对工序顺序柔性的非置换流水车间调度问题的一个可行解，如图6 所示。以工件J1为例，当1 在基于工序的编码中第2次出现，代表该工件工艺路线上的第2 道工序，结合基于柔性工序组编码的染色体段中J1的工艺路线O1，1→ O1，3→O1，2→O1，4→O1，5，可知此处1 代表工序O1，3。

3.2 三阶段解码

首先，对基于柔性工序组编码的染色体段进行解码得到各工件的工艺路线，对基于工序编码的染色体进行解码得到各基因位对应的工序序号。然后，采用三阶段解码方式进行解码操作，以降低提前/拖期完工惩罚总成本。采用插入式贪婪解码算法，产生一个包含最优解的活跃调度；在解码过程中，若有工件的完工时间超出拖期宽容度约束，进行染色体修复操作，以尽可能减小工件的拖期完工惩罚；在完成前两个操作后，进行逆向重调度适当延后工件的开工时间，以减小工件提前完工带来的惩罚。

（1）插入式贪婪解码。将染色体看作工序的有序序列，根据工序在该序列上的顺序进行插入式贪婪解码。序列上第1 道工序首先安排加工，然后取序列上第2 道工序，将其插入到对应机器上最早可行的加工时刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的位置。此阶段的目的在于产生一个包含最优解的可行活跃调度。

（2）基于拖期宽容度的染色体修复。在实际的生产环境中，零部件的拖期交付对生产活动的影响更为严重。因此，为尽可能降低工件拖期惩罚成本，在插入式贪婪解码的过程中，若有工序的完工时间超出式（7）设置的拖期宽容度约束，则立即停止解码并进行染色体修复操作。染色体修复操作采用基于关键路径的染色体修复方法[6]。

其中，Ci，j为完工时间；η为拖期宽容度系数。

（3）逆向重调度。通过以上两阶段解码操作可使工件拖期惩罚成本降到最小，在保持拖期成本不变的情况下，适当延迟工件的开工时间有助于降低工件的提前完工惩罚，采用基于逆向重调度的目标值修订方法[6]对染色体进行逆向重调度。

3.3 分段交叉算子

在进行交叉操作时，分别对前、后两段染色体进行交叉操作（图7）。对基于柔性工序组编码的染色体段，随机选中多个柔性工序组进行交叉操作，以产生新的工艺路线。考虑到柔性工序组内的工序数量较少，在各个工件的柔性工序组内随机选中一个交叉点，交换两父代染色体该位置的基因，对于非交换位置的重复基因按照交换位置基因值的映射关系进行交换[10]，从而防止不可行方案的产生。对基于工序的编码方式形成的染色体段，采用POX 交叉算子[11]进行交叉操作，以产生新的调度方案。POX 交叉算子可以很好地继承父代优良特征并且子代总是可行的，相较于其他的交叉算子，POX算子可以得到更好的结果。

3.4 逆转变异算子

在进行变异操作时，分别对前、后两段染色体进行变异操作（图8）。对基于柔性工序组编码的染色体段，随机选中多个柔性工序组，采用逆转变异的方式，将选中的柔性工序组内的基因以逆向顺序排列插入到原位置；对基于工序的编码方式形成的染色体段，随机选中一个基因段，采用逆转变异的方式，将选中的基因段以逆向顺序排列插入到原位置。

4 实例验证

为了验证上述调度模型和方法，以西控公司航空发动机燃油控制系统生产车间的7 种典型壳体零件为验证实例。由于这类复杂壳体零件加工涉及粗加工、半精加工、精加工共计200 多道工序，本研究根据工艺相似性将部分中间工序合并，并保留了14 种典型工序参与算例验证工作。表1 给出了7 种壳体零件在14 台机床上的加工时间。表2 给出了7 种零件各自包含的柔性工序组和柔性工序组数量，以及对应的交货期和提前/拖期完工惩罚系数。其中，柔性工序组内各工序的加工先后顺序不受限制；提前/拖期完工惩罚系数是由车间计调员根据工件交货期紧迫程度、工件拖期完工的影响程度、工件提前完工的在制品积压成本等多种因素人工设定。对于交货期紧迫、拖期完工影响较大的工件赋予较大的拖期完工惩罚系数，适当减小提前完工惩罚系数，通过这种惩罚系数的动态调整，以驱动生产现场开足马力尽早完工从而保证交付任务。而对于交货期较为松弛、车间精益管理水平较高等情况，通过调高工件提前完工惩罚成本，以引导工件按需生产从而减少在制品库存积压成本。实际上，工件提前/拖期完工惩罚成本系数一定程度上定量反映了一个企业的精益管理水平。

图6 两段式编码方法Fig.6 Two-segment encoding method

图7 分段交叉算子Fig.7 Segmented crossover operator

图8 逆转变异算子Fig.8 Inversion mutation operator

表1 壳体工件各工序加工时间Table 1 Processing time of each operation of shell parts min

表2 工件的柔性工序组分布及提前/拖期完工惩罚系数Table 2 Distribution of flexible operation group and coefficient of earliness/tardiness penalty

表3 为改进型遗传算法的参数设置表，计算机硬件参数为CPU 3.6GHz，内存16G，采用MATLAB R2018b实现本文设计的改进型遗传算法。图9、图10 分别为改进型遗传算法运行20 次得到的最优调度方案甘特图和改进型遗传算法收敛曲线，表4 为最优调度方案对应的7 个壳体零件的最终加工工艺路线。在图9 的甘特图中，7 个零件的加工工序用7 种颜色表示，7 条竖线表示7 个零件所要求的交货期，7 个壳体零件依次经过14台机床的流转加工，并在各自的交货期节点附近完工。该试验结果表明，本文提出的调度模型和方法适用于专业化小流水制造车间的优化调度，同时在精益化排产、准时化生产组织方面也有良好效果。

表3 改进型遗传算法参数设置表Table 3 Improved genetic algorithm parameter settings

图9 壳体实例调度甘特图Fig.9 Gantt chart of the shell parts scheduling

图10 改进型遗传算法收敛曲线图Fig.10 Convergence curve of the improved genetic algorithm

表4 7 个壳体优化加工序列Table 4 Process route of 7 shell parts after optimizing

另外，为了验证工序顺序柔性这一特殊工况对于车间调度方案的影响情况，分别采用两种试验方法：一种是不考虑工序顺序柔性约束，直接在柔性工序组内依次按顺序加工；另一种是按照本文在柔性工序组内进行优化选择。两种试验方法共仿真20 次，分别得到的最优调度方案结果见表5。可知，最优方案的提前/拖期完工惩罚总成本为328.06 元，相较于不考虑工序顺序柔性的最优方案的提前/拖期完工惩罚总成本374.37 元，惩罚总成本降低了46.31 元，采用改进型遗传算法后总成本下降12.37%。试验结果表明，在工艺设计阶段引入工序顺序柔性，为后续的作业调度提供了优化空间，本文设计的改进型遗传算法对于求解考虑工序顺序柔性的非置换流水车间调度问题具有显著优势。

表5 柔性工序组内的顺序加工和排序优化两类试验结果Table 5 Experiment results of process in sequence and operation sequence optimization in flexible operation group

5 结论

（1）针对航空发动机燃油控制系统壳体零件专业化小流水、精益生产、工艺过程复杂、制造周期长等显著特征，将流水线生产、精益单元、JIT 调度等引入该类壳体零件的生产现场组织中，所形成的调度优化模型和改进型遗传算法对于航空制造企业实现精益化转型、强化生产现场执行与管控等具有一定的促进作用，同时也在汽车发动机壳体、减速器壳体、各类泵壳体等车间的精益生产与现场组织方面具有一定的适用性。

（2）在调度优化模型中，以零件交货期为控制节点，采用零件完工时间的提前/拖期惩罚成本的调节机制，通过车间决策者人工调整提前和拖期惩罚因子取值，以满足企业不同发展阶段、不同管理水平的差异化管控需求。

（3）在调度算法设计中，采用两段式染色体编码方式，满足了壳体零件工艺顺序柔性这一特殊要求；采用三阶段解码方式，在确保调度解可行的前提下依次降低零件的拖期成本和成品提前库存成本，从而最终实现零件准时完工的精益调度目的。

（4）本文所提出的E/T 精益调度模型，都是在确定性环境下的理想调度模型。然而航空复杂产品属于典型的多品种小批量生产方式，零部件生产现场动态随机因素众多。为此，下一步将机器故障、急件插入等常见例外工况引入精益调度模型中，并设计与该不确定条件下的精益调度模型相适应的智能优化算法。