一种多品种变批量柔性作业车间调度方法*

常建涛，史尊博，符博峰，杨胜康，李欣伟，韩来新，赵虎军，雷娇娇

（1. 西安电子科技大学，陕西西安 710071；2. 陕西柴油机重工有限公司，陕西兴平 713105）

引 言

柔性作业车间调度问题（Flexible Job shop Scheduling Problem, FJSP）是存在于制造企业实际生产过程中的复杂NP-hard组合优化问题。柔性作业车间调度问题突破了生产资源唯一性限制，每个工件的每道工序可由多台加工设备加工，更加贴合实际生产情况。在离散型制造企业中，零件品种多，工艺路线灵活，车间生产计划的制定与车间的管理较为复杂，多数企业的车间管理仍旧依靠人工调度，影响生产资源的调配[1]。随着实际生产模式的改变和制造企业的发展，多品种变批量生产模式成为FJSP重要的扩展方向之一。

近几年，排产问题选取的研究范围多是混合流水车间或离散车间等典型的生产车间。然而，柴油机气门传动机构零件类型繁多、工艺复杂，属于多品种变批量生产模式，在排产时经常存在不能合理利用生产资源的问题。因此，对多品种变批量生产模式车间调度问题的研究意义重大。

文献[2]提出了一种自学习遗传算法，用于解决柔性作业车间调度问题，该算法以遗传算法为基础并结合强化学习对遗传算法的关键参数进行智能调整。文献[3]采用非支配排序遗传算法III（Non-dominated Sorting Genetic Algorithm III,NSGA-III）解决了综合考虑多个目标（完工时间、工作量平衡、提前和拖期平均值、成本、质量以及能耗）的柔性作业车间调度问题。文献[4]提出了一种三阶段方法，用于解决可变批次的流水车间调度问题。文献[5]提出了一种改进的候鸟优化算法，以总流时间最小化为目标，解决混合流水线与批次混合的调度问题。文献[6]提出了一种改进的候鸟优化算法，以完工时间最小化为目标，解决带有批量流的混合流水车间的调度问题。文献[7]提出了一种改进的基于分解的多目标进化算法，用于解决可变批次的混合流水车间的调度问题。文献[8]提出了一种基于精英个体集的自适应蝙蝠算法，用于解决柔性流水车间调度问题。然而上述文献没有解决可变批次的柔性作业车间的调度问题以及紧急插单动态车间的调度问题。文献[9]针对柔性作业车间分批调度问题，提出采用试探法解决批量划分问题，同时采用遗传算法解决批次划分后的工序调度问题。文献[10]采用遗传算法解决柔性作业车间分批调度问题。文献[11]提出了一种多目标差分进化算法，以最长完工时间、机器总负载、最大机器负载、机器总空闲时间、工件总加工成本和工件拖期惩罚为优化目标，解决柔性作业车间批量调度问题。文献[12]提出了一种基于禁忌搜索算法的分批优化算法，用于解决柔性作业车间分批调度问题。然而文献[9-12]没有解决可变批次的柔性作业车间的紧急插单动态调度问题。

针对以上研究的不足，本文首先以最长完工时间、设备总负载和最大设备负载最小化为目标构建了多品种变批量柔性作业车间调度优化模型，并基于遗传算法对模型进行求解。其次，针对实际生产过程中的紧急插单问题，提出一种多品种变批量生产重调度方法。最后，在实际生产中指导调度人员得出合理的零件批次组合，同时帮助调度人员在紧急插单情况下快速制定合理的生产作业调度方案。

1 多品种变批量柔性作业车间调度

多品种变批量柔性作业车间调度问题描述：有m台加工设备和n种待加工零件，每种零件包含多道工序，每种零件需要生产一定的数量，每种零件每道工序有至少一台加工设备，工序的加工时间随加工设备的性能不同而变化，每种零件的加工工序事先确定。每种零件可分为多个批次在不同的设备上加工，各批次作为一个整体进行加工。每种工件的工艺流程不能改变，每个作业必须按照工序的先后顺序进行。本文的调度模型需要满足以下假设：1）生产之前，原材料和相应的工装夹具都已准备齐全；2）设备启动、下料以及工件在各个设备之间移动所需要的时间忽略不计；3）所有工件每道工序的加工设备集已知；4）每道工序进行中不能中断；5）工件的工艺流程不能改变，每个工件的加工工序固定，必须严格按照工艺顺序进行；6）工件在每台设备上的加工时间固定，同一批次工件的加工时间由该批次工件数量和一个工件的加工时间决定；7）同一批次的工件一同加工；8）在零时刻，所有工件都可被加工；9）同种工件不同批次的工序没有先后约束，可在设备集中选择不同的设备进行加工；10）不同工件的工序没有先后约束；11）每台设备在任一时刻只能执行一种工件某一批次的一道工序；12）每种工件某一批次的每道工序在任一时刻只能在一台设备上执行。

本文模型定义相关参数如下：J为工件集；n为工件种类数量；M为加工设备集；m为加工设备数量；Qi为第i种工件的加工数量；Bi为第i种工件的批次数量；Lih为第i种工件第h批次的加工工件数量；OSi为第i种工件的工序数量；Oij为第i种工件第j道工序；Mij为可以执行工序Oij的设备集；Oihj为第i种工件第h批次第j道工序；Mihj为可以执行工序Oihj的设备集；STihjk为第i种工件第h批次第j道工序在设备Mk上的加工起始时间；Tihjk为第i种工件第h批次第j道工序在设备Mk上的加工时间；CTihjk为第i种工件第h批次第j道工序在设备Mk上的加工结束时间；CTihjk′为第i种工件第h批次第j道工序在设备Mk′上的加工结束时间；CTi′h′j′k为设备Mk上前一批次的加工结束时间；Cih为第i种工件第h批次的完工时间；αihjk=1为第i种工件第h批次第j道工序在设备Mk上加工；αihjk= 0为第i种工件第h批次第j道工序不在设备Mk上加工；tijk为第i种工件第j道工序在设备Mk上的单件加工时间；Wk为设备Mk的负载；W为所有加工设备总负载。

本文构建的调度模型考虑了最长完工时间和设备总负荷两个优化目标，并采用加权平均将两个优化目标转化为一个优化目标进行求解，数学模型如下。

目标函数：

最长完工时间：

设备总负载：

约束条件：

式（1）中的φ和φ为权重系数。式（4）表示设备Mk的负载。式（5）表示某种零件某一批次某道工序在某台设备上的加工时间。式（6）表示零件批次约束，即每种零件的总加工数量等于该零件所有批次下的数量之和。式（7）表示同一时刻某道工序只能在一台设备上加工。式（8）表示某种零件某一批次某道工序在某台设备上的加工起始时间和加工结束时间应该满足的约束。式（9）表示同一批次下的工件各道工序之间需要满足工艺路线约束。式（10）表示在该设备上执行的工序必须在上一道工序完成之后才可以进行。式（11）表示非负约束。

2 方法框架

本文的方法框架如图1所示。首先，构建生产数据集。零件的加工工艺数据主要包括零件的工序与工时数据，零件的需求数据主要包括零件的种类和数量。利用零件种类批次的正交组合，同时结合历史上排产出现过的批次组合，构建多品种变批量生产数据集。然后，按照生产车间调度资源约束，构建调度数学模型，利用遗传算法对模型进行求解，得到最优组合下的生产作业计划。最后，根据是否遇到紧急插单动态扰动事件，判断是否需要进行重调度。当遇到紧急插单事件时，本文采用基于事件驱动的重调度策略，记录插单时刻的车间状态，包括未完成工件的工件号、设备号、加工时间等信息，计算未完成的工件工序数，输入紧急插单的工件基础数据，将未完成工件的数据和新插入的工件信息组合起来，再利用算法模型进行重调度，得到重调度的车间作业计划，以此计划作为最终的执行生产作业计划。

图1 方法框架图

基于遗传算法求解调度模型的算法流程见图2。

图2 算法流程图

（1）编码

采用分段整数编码来表示染色体，其中第一段编码是基于设备的编码，用于确定工件加工选择的设备，第二段编码是基于工序的编码，用于确定工件加工次序。具体操作可参考文献[13]提出的编码方式。

（2）种群初始化

生成由设备编码和工序编码组成的染色体个体。初始种群解的质量对模型求解的影响很大，因此，本文采用的初始化方式考虑了文献[13]提出的全局选择、局部选择和随机选择3种方式。综合考虑后，采用3种方式的混合，按一定比例选择3种方式，其中全局选择方式比例最高，随机选择方式最低。

（3）解码

在计算适应度函数之前还原染色体所表示的加工顺序。本文采用了文献[14]提出的左移插入式解码。

（4）适应度计算

采用适应度值根据模型中的目标函数对种群个体进行评价。本文的优化目标是最长完工时间和设备总负载，这两个量的单位都是时间，因此不用考虑量纲不一致的问题，只需将二者加权平均将其转化为一个目标值Fi。个体适应度值Ffit(i)=。

（5）选择操作

根据每个个体的适应度判断个体优劣，选择较优个体保留在种群的子代中。本文结合截断选择和锦标赛选择两种方式进行选择操作。

截断选择的策略是根据适应度值对种群中的个体按照从优到劣的顺序进行排序，选择前1%的个体直接进入下一代。

在锦标赛选择中，每次从种群中随机采样两个个体即二元锦标赛选择，然后选择较优个体进入交叉池中，只有个体的适应度值优于其他竞争者时才能赢得锦标赛。锦标赛选择循环迭代，直到两种选择方式的个体之和达到原来的种群规模。

（6）交叉操作

从种群中随机选取n个个体，根据适应度值利用轮盘赌的方式从n个个体中选择两个，对这两个个体进行交叉操作。设备编码部分采用均匀交叉方式，具体过程为：首先根据设备编码长度随机产生一个整数N，再随机生成N个不同的整数，根据这N个整数将染色体P1和P2对应位置的基因位复制到子代染色体C1和C2相应位置，再将P1剩下的基因复制到C2中，将P2剩下的基因复制到C1中。工序编码部分采用改进的优先操作交叉（Improved Precedence Operation Crossover, IPOX）方式[15]。

（7）变异操作

变异的主要作用在于使算法能够跳出局部最优解，因此不同的变异方式对算法能否求得全局最优解有很大的影响。设备编码部分采用的变异方式是从一个染色体的设备编码部分随机选取一个位置，寻找对应的加工工序，从该工序可选择的加工设备集中随机选取一台设备代替原先的设备编码。工序编码部分采用位置变异方式，即从一个染色体的工序编码段中随机产生两个位置并交换这两个位置的值，同时修改染色体对应的机器编码段相应基因位置，产生新的个体。

3 试验与分析

本文采用模拟的数据进行仿真试验。首先针对零件未分批次进行调度，再针对零件分批次按照本文方法进行调度，通过两种调度方案的对比验证本文方法的可行性。零件种类、工序、工时等模拟数据见表1。

表1 零件仿真数据

零件未分批次的调度方案见图3。3种零件的可选批次均为3、4、5，由此构建3种零件的批次组合，再利用算法模型进行求解，最终可得零件分批次的调度方案（图4），同时可以得到零件的批次。对比两种方案的最长完工时间可知，本文的方法可行、有效。

图3 零件未分批次的调度方案

图4 零件分批次的调度方案

以图4的调度方案作为原始调度方案，当遇到紧急插单的动态扰动事件时，进行重调度。设置紧急插单时间为40 min，则可得到紧急插单后的调度方案（图5）。紧急插单的零件种类、工序、工时等信息见表2。

图5 紧急插单后的调度方案

表2 紧急插单时的零件和时间信息

为了方便看出效果，将紧急插单前的原始调度方案（图4）和插单后的调度方案（图5）合并为图6。

图6 紧急插单前和插单后的调度方案

4 结束语

本文研究了多品种可变批次下的柔性作业车间调度问题。采用零件批次组合的方法，构建多品种变批量生产数据集，建立了多品种变批量生产调度优化模型。基于遗传算法对模型进行求解，并考虑紧急插单动态扰动事件，采用基于事件驱动的完全重调度策略设计了一种重调度方法。最终指导调度人员在实际排产时得出合理的零件批次组合，从而为实际生产的车间排产方案提供参考。但是面临大规模调度问题，零件的批次组合会很多，即使结合历史上的批次组合，仍然会有求解速度慢、时间长的问题。为了获得更佳的调度效果，如何在调度之前指引零件分批（例如采用强化学习构建零件分批决策模型，形成较好的分批策略），进而提高算法的求解能力是后续的研究方向。