基于改进遗传算法的民航客机地勤调度问题

朱传军，刘明英

(1 湖北工业大学 机械工程学院，湖北 武汉 430068；2 鹤壁技师学院，河南 鹤壁 458030)

民航客机的地勤保障可以看作是一个开放车间调度问题，如何安排保障顺序归结为如何得到一个最优的调度方案以减少等待时间并提高保障效率。开放车间调度问题是NP-hard，精确算法仅适用于有限的几类问题。当机器数量小于3台时，T. Gonzalez等[1]设计了多项式时间算法，使其能在多项式时间内得到最优值。其他精确算法中，非多项式时间算法还有分支定界法和数学规划等方法。Brucker等设计了基于析取图的分支定界算法[2]。由于非多项式时间算法的缺点，学者们提出了启发式算法来求解开放车间调度问题。陈亚绒等针对晶粒分类拣选这一并行多机开放车间调度问题，提出了混合整数规划模型，设计了同时考虑质量与求解效率的启发式算法[3]。针对单一机器干扰下的开放车间重调度问题，刘乐等提出了基于右移、受影响工序和全局重调度方法，实现了开放车间高效率、低成本重调度[4]。国外，Brasel等提出了基于构造插入的高效启发式算法[5]。Gueret和Prins提出了基于列表的启发式方法求解开放车间问题[6]。

在求解开放车间调度问题中，真正具有重要意义的是元启发式算法，而遗传算法是最基本的元启发式算法。Liaw和Prins分别使用遗传算法求解了开放车间调度问题[7-8]。Blum结合蚁群算法和束搜索(Beam Search)算法，提出了一种混合算法[9]。王艳鹏将传统粒子群算法离散化，提出的一种适合于求解开放车间调度优化的离散粒子群算法并取得了较优结果[10]。高亮等为克服粒子群算法在信息共享机制上的缺陷，基于群体智能的信息共享机制，引入了问题的领域知识为导向的局部搜索，得到了开放车间调度问题的高质量解[11]。Sha和Hsu也使用改进的离散粒子群算法，并结合束搜索及主动调度方法对开放车间调度问题进行了优化，得到了许多未求解问题的最优解[12]。王军强等人基于多样性增强的自适应遗传算法[13]，设计了多种算子以提高算法的进化效率和质量，并验证了算法的有效性和稳定性。此外，不同学者也在尝试使用新颖的元启发式算法，以期获得更好的优化效果。例如，陈祥等使用了文化基因算法对开放车间标准问题进行了优化[14]。Hosseinabadi等评估了求解开放车间调度问题中交叉、变异等遗传算子的效果，证实遗传算法求解开放车间问题时选择算子作用很大，并提出了更好的EGA_OS算法[15]。本文针对民航地勤调度问题的特点，建立了混合整数规划模型，设计相应的编码与解码方案及相应的算子，使用遗传算法对该问题进行优化。

1 混合整数规划模型

有n个工件J1,J2,…,Jn需要在m台机器M1，M2，…，Mm上加工，每个工件有m个工序Oij，且每个工序均有固定的加工时长tij。所有工件在零时刻均可开始加工，一个工件的各工序之间没有先后关系且各工序经过的机器也没有规定，但任意工序所使用的设备是事先确定的。此外，为研究问题方便，还有下列假设：1)各工序一经在某设备上开始加工就不能中断，直至加工完毕；2)一个工件的任一工序只能由一台机器加工，不能由多台机器同时加工；3)每台机器每次只能加工一个工件。

在满足上述要求下为各台机器合理安排工件及其开工时间，使最大完工时间最小。

混合整数规划模型用于从数学角度描述开放车间调度问题。对于开放车间调度问题，在建立数学模型时，必须考虑两个问题：1)机器上的工序排序；2)同一工件的工序排序。根据这两点合理安排工序即可得到一个正确的模型。在建模前，先建立如下的集合、参数、变量。

下标与集合：i,i′为工件下标；j,j′为工序下标；k,k′为机器下标；Oi为工件i的所有工序集合。

参数：tij为工序Oij的加工时长；Eijk=1，表示工序Oij在机器k上加工，否则Eijk=0；n为工件个数；m为机器台数；A为一个很大的正数。

变量：Cij为工序Oij的完工时间；Cmax为所有工件的最大完工时间，makespan；Xij,j′=1，表示工序Oij直接或间接地在工序Oij′前加工，否则Xij,j′=0；Ykij,i′,j′=1，表示机器k上工序Oij直接或间接地先于工序Oi′j′加工，否则Ykij,i′,j′=0。

目标与约束：对于同一工件的各个工序，若两两之间的加工先后关系得到确定，则各工序间的加工先后也得到确定。约束(1)用于确定各工序间的先后关系。

Xij,j′+Xij′j=1
∀i=1,2,3,…,n,∀j,j′∈Oi,j≠j′

(1)

对于属于同一工件的各工序，其开工时间需要满足一定的先后关系。

Cij≥Cij′+tij-A·Xij,j′∀i=1,2,3,…,n,
∀j,j′∈Oi,j≠j′

(2)

对于同一机器上加工的各个工序，也需要确定其先后顺序，否则会出现一台机器同时加工多个工序的情况。类似上述方法，需要先确定任意两个工序间的先后加工关系：

Ykiji′j′+Yki′j′ij-A·(2-Eijk-Ei′j′k)≤1，
∀k=1,2,3,…,m,∀i,i′=1,2,3,…,n,
∀j∈Oi,∀j′∈Oi′

(3)

Ykiji′j′+Yki′j′ij+A·(2-Eijk-Ei′j′k)≥1，
∀k=1,2,3,…,m,∀i,i′=1,2,3,…,n,
∀j∈Oi,∀j′∈Oi′

(4)

这样，就可以安排同一机器上不同工序开工的先后顺序。如约束(5)所示，后一个工序的完工时间大于等于前一工序完工时间加上本道工序的加工时长。若两个工序不在同一机器上或先后顺序不满足，则该约束不起作用。

Cij≥Ci′j′+tij-A·(3-Eijk-Ei′j′k-Yki′j′ij),
k=1,2,3,…,m,∀i,i′=1,2,3,…,n,
j∈Oi,∀j′∈Oi′

(5)

最后，所有工序的最大完工时间即为makespan：

Cmax≥Cij,∀i=1,2,3,…,n,∀j∈Oi

(6)

数学规划方法只能用于求解小规模开放车间调度问题，其本质是一种非多项式时间算法。当问题规模增加时，数学规划方法的计算复杂度会爆炸式增加，导致计算时间变得很长，因此采用改进遗传算法来进行求解。

2 改进遗传算法及其实现

本文将遗传算法应用于开放车间调度问题中，设计相应的编码方案及算法操作流程。

2.1 编码与解码

开放车间问题是一种特殊的作业车间问题，而针对作业车间问题的遗传算法目前已经有较好的编码方案——基于工序的编码。因此，本文将借鉴已有的编码方案对其进行适当的改进或扩展，以适应开放车间调度优化。用遗传算法求解作业车间调度问题的编码方案有两类：直接编码和间接编码。直接编码对个体解码可直接得到相应的调度方案；例如：基于工序的编码、基于工件的编码等。而间接编码着眼于工件在机器与时间上的分配规则，再由这些规则得到调度方案。上述两种编码方案中，两者各有优劣。目前最常用的是直接编码方案是基于工序的编码。因此，本文采用基于工序的编码方式。假设某开放车间调度问题含有n个工件且每个工件含有m道工序；每个工序只能在一台机器上加工(总共m台机器)，需要确定一个调度方案使总完工时间最短。根据基于工序的编码方案可知，所有工序可以用一个编码串来表示；每个工件号在编码串中总共出现m次，因此编码串(染色体)长度为n×m，其中每个位置代表一个工序。每个工件号必会恰好出现m次。按照从左向右顺序依次读取染色体中各个位置上的数字，若某位置数字i正好第j次出现，表示这是工件i的第j道工序。因此，每个工件的每个位置都能确保被找到。图1给了一个基于工序编码的开放车间调度遗传算法编码例子。假设有3个工件3台机器且每个工件各有3个工序，一个编码方案为[3,2,2,1,3,1,3,1,2]。

每个个体含有一条染色体，每条染色体有n×m个基因，每个基因上有一个基因位，每个基因代表一个工序；整条染色体表示示例中3个工件共含有所有工序。图1中染色体代表工件ID的数字1,2,3均出现3次，即为各个工件均有3个工序。根据基于工序的编码规则，染色体第一个位置是数字3，且该数字3第一次出现，表示第一个要处理的工序为第三个工件的第一个工序。以此类推，在染色体第6个位置是数字1，且该数字第二次出现，表示第6个处理的工序为工件1的第二个工序。最终得到的工序处理顺序在图1第二行给出。显然，任意交换或打乱各个工序的顺序并不会产生错误或非法解。因此，在初始化过程中随机生成的个体均是正确的染色体(合法的编码)。

图1 个体编码方案

从图1知，一个个体中除了工序串外还有2个串，即机器串和时间串，分别表示对应的工序在哪一台机器上加工及相应的加工时间。例如第一个处理的工序为3.1，该工序需要在机器1上加工且对应的加工时长为2。这样通过合理的编码一个个体可以将所有工件信息及调度要素表达出来。

解码过程与编码相反，解码是利用一个个体内各个串的信息通过合理的方法与步骤或通过某种映射关系将其转化为相应的调度的过程。目前对于车间调度问题存在多种解码方法，且解码过程并不是编码的逆推，但编码方法的优劣会影响解码的效率与质量。一般来说，解码过程要比编码过程更加复杂。即使对同一个体使用不同的解码方法，得到的调度方案可能会完全不同。

在车间调度问题中，常用的解码方法即为三类：半主动调度、主动调度及无延迟调度。三种解码方法的共同目的是在工序加工顺序、使用的机器、对应的加工时间给定的前提下为每台机器上的工序确定一个合理的开工顺序，在满足同一工件各工序加工顺序合理的约束下使得总完工时间最小(或其他技术指标最优)。在一般情况下使用主动调度解码方法可以得到更好的调度方案，同时也可提高机器利用率。本文给出的算法使用主动调度的解码方法。

2.2 工序先后顺序处理方法

在传统作业车间调度优化中，各个工序的先后关系是事先给定的且任何时刻不能改变。对于开放车间调度问题，各工序间没有先后关系。因此，本文所有算法中对于初始个体其工序的排列均为随机生成。对于上一节提出的编码方案，可以采用随机打乱工序编码串上的各个基因(连同的机器上加工时间也要调整)的方法实现。例如，对于图1所示的例子，另一个允许的个体可以是如图2所示的随机生成个体。

图2 一个随机生成的个体

2.3 选择操作

在遗传算法中，新的个体组成了下一代群体；新个体的产生常常通过算法中任选两个父代个体经由选择操作、交叉操作和变异操作得到。其中，选择操作是其中的第一步，其目的是以较大的概率将父代具有优势的个体保留下来，父代个体对环境的适应能力越强、优势越大其被保留的概率也越大。选择操作主要有两种：赌轮盘选择法和锦标赛选择法。

赌轮盘选择法模拟博彩游戏中的轮盘赌。假设群体P(i)中有N个个体；一个轮盘也被划分为N个扇形，每个扇形代表一个个体且个体越好、优势越大(通常适应度值越大)扇形的面积越大。这样，转动轮盘，指针所指的扇形区域所代表的个体就会被选中。因为扇形面积与个体适应度的大小呈正比，因此适应度越好的个体越有可能被选中。

锦标赛选择操作每次从群体P(i)中选取若干个体(一般是两个)，每个个体被选中的概率相同。比较选出的各个个体的适应度，选取适应度较好的个体进入下一代。重复上述过程直到N个个体全部选出。相对赌轮盘选择，锦标赛选择方法操作比较简单，无需复杂的转换亦能保持下一代个体中解的多样性。因此，本文采用锦标赛选择法。

2.4 交叉操作

基于提出的编码方式，设计了一种交叉操作。如图3所示，任意选取经选择操作后的两个优秀父代个体；随机在工件[1,2,3,…,N]中确定s个工件(1≤s

图3 交叉操作示意

图3是两个父代个体交叉操作的例子，共有3个工件且工件2被选中。P1中属于工件2的工序在2,3,9三个位置，P2中属于工件2的工序在4,8,9三个位置。将这些位置表示工序、机器、加工时间的基因各复制一份，分别填充到子代个体O1、O2的相应位置上。图中工件2有3个工序复制后分别放入O1、O2对应的位置(虚线框所示)。此时，O1、O2各有6个位置没有填满，同时P1、P2中工件1和3的6个工序也未处理。个体P2中剩余6个工序连同机器与相应的加工时间按照原来的顺序331113复制一份后填入到个体O1的空余基因位中.这样，子代O1中除虚线框中的工序外，其余工序的顺序也是331113。同理可得个体O2。

本文提出的交叉操作通过对选定若干个工件的工序进行保留，并使用另一父代个体的工序对子代个体中空余基因位进行填充，确保了两个父代个体的基因的深度融合，从而产生更优秀的个体。

2.5 变异操作

变异操作是遗传算法中独有的操作，用于模拟个体基因突变这一过程。在交叉操作中，新生成的子代群体由于继承了父代的优秀基因，其总体性能优于父代群体。与交叉操作不同，变异操作没有方向性，即一个个体经过变异后，与之前相比，可能变得更好但也可能变得更差。因此，为了充分发掘个体的潜力，获得某些变异后表现更优的个体，算法中引入了变异操作。此外，相对交叉操作而言，变异操作发生的概率较低，这是变异操作的又一个特点。

如图4所示，变异操作中首先随机选择两个不同的基因位(第3、第6位)，将两个位置代表的工序、机器及加工时间同时进行交换，交换后得到新的个体。如前所述，对于提出的编码方案，任意交换两个位置代表的工序、机器及加工时间不会影响解码过程。

图4 变异操作

2.6 算法的改进

传统遗传算法在每一代个体更新过程中没有新的个体引入，这会导致在算法迭代后期各个个体内部基因高度相似，由此降低了交叉操作的效果，使得最优解停滞于当前值，而没有新的最优解产生。这是由于群体多样性受到了制约，无法通过遗传操作得到更优秀的基因片段，产生更优的解。为克服这一不利因素，本文对传统遗传算法进行适当创新，改进了已有的选择方法，即在每次迭代中留出少量的个体数，并用新生成的个体覆盖老的个体。这样，每次迭代中个体的多样性得到了保证。

2.7 算法流程

本文算法流程总体的步骤与常规遗传算法一致，都是通过选择、交叉、变异从而完成一次迭代。

步骤1 确定算法的相关参数(个体数、交叉概率、变异概率等)并对个体进行初始化，即随机生成个体。

步骤2 选择操作：从当前群体P(i)中随机选择两个个体，比较两个个体的适应度值，选择适应度较好的个体作为下一代个体的父代。

步骤3 交叉操作：随机选取两个父代个体，随机生成区间[0, 1]内的有理数R，若R不大于给定的交叉概率，则进行交叉操作；否则放弃交叉操作。

步骤4 变异操作：随机选取一个交叉后的个体，随机生成区间[0, 1]内的有理数r，若r不大于给定的变异概率，则进行变异操作；否则放弃变异操作。

步骤5 对所有新一代个体计算适应度，并更新全局最优解。

步骤6 判断是否达到算法停止条件，若不满足转到步骤2进行下一轮迭代；若满足则输出结果。

3 实验结果与分析

3.1 民航客机保障与维护调度问题

计算实例来自民航客机的保障优化问题。根据保障类型及飞机种类的不同，表1～3给出了3组调度实例及相应的保障时间。实例1中有6架飞机需要维护，代表了中等规模的开放车间调度实例；实例2中有8架飞机规模较大；实例3中只有4架飞机，是一个小规模实例。对于维护时长，实例1和实例2的时长相差不大；实例3的维护时长较长。本文采用改进遗传算法求解上述三个实例。

表1 第一个实例的数据 min

表2 第二个实例的数据 min

3.2 参数设置

遗传算法采用C++语言编程并在Visual Studio 2010软件上运行。为避免单次计算中算法所得结果的不确定性及偶然性，每个实例计算5次。此外，在预先多次测试的基础上，选择以下参数：群体中个体数400，迭代次数为400次，交叉概率0.7，变异概率0.05，每轮迭代后有10%的个体为新生成的个体。

3.3 遗传算法计算结果与分析

实例1～3的计算结果列于表4中。第一个实例的最优解为266 min，且5次计算中均得到了最大工期为266 min。第二个实例工件个数较多，相应的最大工期较大为369 min。实例3虽然维护时间较长，但由于仅有4个工件，维护压力较小且总完工时间较短。由表4可知，前两个实例每次计算都能得到同一最大完工时间；而第三个实实例每次计算得到的结果略有差异，其最大完工时间均值为207 min，这是由于第三个实例各工序平均时长较长，最优调度方案稍有偏差即引起总完工时间较大的偏差。

表4 遗传算法计算结果 min

图5是求解实例1的收敛曲线。可以看到，开始时最大工期下降较快，这是由于初始时群体多样性较好，即含有不同基因的个体较多，每个个体容易获得优良基因。随着迭代不断进行，最优个体被保留，各个体中优秀的基因趋于一致，交叉后得到的个体中优秀基因与其父代相似度较高，此时算法对个体的改进有限，个体的改进幅度不断变小，最大工期最终收敛于266 min。

图5 遗传算法求解实例1的收敛曲线

图6是实例3最优解对应的甘特图，最优最大工期为305 min。机器1处理的第一个工序为4.2，是第四个工件的第2个工序，其加工时长为63 min。对照表3.3可知，该工序为飞机4维护的第1个工序。由于开放车间中同一工件的各个工序先后处理顺序没有要求，本例工序4.2实质为工件4的第1个工序，这是允许的。图6的甘特图中所有工序对应的实际工序号、对应加工机器与加工时间列于表5中。不难发现，各个工序的实际加工时间均符合表3中相应数据，说明该调度方案是合理的。

表3 第三个实例的数据 min

图6 实例3的最优甘特图

表5 图6机器上各工序详细信息

4 结论

本文针对民航客机地勤保障调度问题的特性，建立了求解此类调度问题的混合整数规划模型，兼顾求解效率与质量，设计了一种改进遗传算法。根据生产实际设计了实验算例，使用该算法成功求解了飞机保障调度这一典型的开放车间问题并对计算结果进行了分析。未来研究方向将侧重于考虑更加实际的工程问题，如一个工序的加工时间并不是固定的，而是在一定范围内波动或按照特定的概率分布的。此外，带有工件辅助时间的开放车间调度问题的优化方法也可作为未来研究的方向。