基于遗传算法的多目标生产车间调度研究

2016-09-29方霞，曹洁

甘肃科技 2016年17期

关键词：遗传算法工序车间

方　霞，曹　洁

（湖南文理学院，计算机科学与技术学院，湖南，常德　415000）

基于遗传算法的多目标生产车间调度研究

方霞，曹洁

（湖南文理学院，计算机科学与技术学院，湖南，常德415000）

针对生产调度多目标动态复杂性，提出了一种基于AOE图寻找关键路径的改进遗传算法。采用基于工件和机器相结合的编码方法，根据多目标要求，设计了相应的交叉遗传算子。实验结果表明，改进的遗传算法符合车间实际应用情况，对解决多目标动态车间调度问题有实际的应用意义。

遗传算法；多目标；车间调度；关键路径

1　概述

调度功能是车间管理的核心功能之一，它直接关系着车间能否在指定的时间段内合理利用有限的制造资源完成相应的加工任务。调度问题不但冲突多、求解过程相当复杂，而且在不同制造环境下所考虑的约束、达到的目的等均不相同，使得调度问题之间的差别很大［1］，特别是对于多目标问题，求解尤其困难。

组合优化问题通常具有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题，因此，精确求解组合优化问题往往是不可能的。生产调度（JSP）问题是一类典型NP完全问题，随着问题规模的扩大，会发生组合爆炸，算法复杂性呈指数增长［2-3］。各类混合遗传算法是解决实际调度问题最有效的途径和最有前途的调度方法［4］。在充分进行调查研究和比较各类优化搜索方法［5-9］的基础上，提出一种混合遗传算法来有效解决生产调度中的多目标问题。

2　JSP问题描述

JSP（Job-Shop）问题研究n个工件在m台机器上的加工，已知各操作的加工时间和各工件在各机器上的加工次序约束，要求确定与工艺约束条件相容的各机器上所有工件的加工时间或完成时间或加工次序［10］。

使加工性能指标达到最优，具体满足如下条件：

1）同一时刻同一台机器只能加工一个工件；

2）每个工件在某一时刻只能在一台机器上加工，不能中途中断每一个操作；

3）不同工件的工序之间有部分联系；

4）不同工件具有优先级的差别；

5）每个工件相邻工序之间的间隔为零（准备时间可计入机器的加工时间）。

AOE带权有向无环网模型是描述JSP调度问题的一种行之有效的方法，如图1所示。

图1　加工环节示意AOE网

顶点表示事件，弧aij表示工件i的某道工序j，权表示工序加工时间（为了简化模型，准备时间包含于加工时间内视为整体）。

分析AOE网可以得到生产过程中的关键路径，对于解决生产调度中的瓶颈问题有很强的现实意义。通过改善关键活动的工效，可以有效缩短整个工期，提高设备利用率。

车间调度分为静态调度和动态调度两种。静态调度目标为在满足生产任务交货期的前提下，尽可能提高设备资源的利用率，减少调整时间，使生产周期最短。静态调度是车间计划进入执行阶段的基础和依据，遗传算法（GA）在静态调度问题中已经有成功的应用。动态调度指在车间实际的运行过程中，存在着不可预期的被称为动态时间的随机扰动，如机器故障、订单的突然加入或取消等，因此往往需要不断地进行动态重调度［11-13］。具体生产调度加工目标和解决策略如下：

1）企业成本最小化、降低库存；

2）按期交货订单数量最大化。考虑缩短制造周期方面，则调用完工时间最早的工序；考虑不同交货期方面，则计算不同完工提前期，根据事情紧急情况分别对待；

3）资源设备均衡利用。考虑减少机器负荷方面，则调用加工时间最小的工序；考虑设备能力方面，则涉及加班、外协等问题；

4）任务优先数的考虑。在上层决策时，充分关注市场销售、机器生产、库存等方面问题；而装配完成情况与加工次序紧密联系；动态调度事，对于缺件未能按时完工，需要优先加工，将其优先级增大；

5）减少调整准备时间。充分考虑运输时间的问题，其中涉及到设备地理位置情况、工件准备时间、刀具准备时间等方面。

3　混合遗传算法描述

3.1混合遗传算法

遗传算法（GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法，在许多领域中得到了成功的应用，如函数优化、旅行商问题等。利用遗传算法已经成功解决静态生产调度问题，本文重点针对动态调度中的多目标问题，采用以遗传算法为基础，结合AOE找寻关键路径的混合遗传算法来弥补遗传算法的局部搜索能力的不足，根据适应度的变化采用相应的交叉变异算子，避免“早熟”收敛现象发生，对于生产调度中的动态多目标问题进行有效的解决［11-13］。

3.2编码方案

编码问题是算法设计的首要和关键问题，常见的有二进制编码、格雷码编码、实数编码、符号编码、排列编码、二倍体编码、DNA编码、多参数编码、矩阵编码等［14］。解决经典的工作车间调度问题有基于工序的编码、基于机器编码、基于操作的编码等多种方法。采用基于工序和机器的编码［15］，工序aij用Gi来表示工件i，其出现的次序表示工序加工顺序；机器m用Jm表示某工序加工的机器。如染色体J1G1-J2G2-J1G1-J2G1表示工件1第1道工序在机器1上加工，工件2第1道工序在机器2上加工，工件1第2道工序在机器1上加工，工件1第3道工序在机器2上加工。

3.3种子选择

首先对各工序生成的AOE网进行拓扑排序及逆拓扑排序判断，在该前提下求得关键路径，并对关键活动优先分配机器，保证关键活动的正常如期完成。将关键活动基因置前，后随机生成一定数量的不完全染色体种子，结合工序要求对非关键路径上的工序进行机器分配，形成最终的染色体。采用常用的轮盘赌方法进行选择适应度高的个体，为了防止算法收敛于局部解，种群规模取30个。

为了保证所得到的最优个体不会被交叉、变异等遗传操作所破坏，结合使用最优保存策略，若当前群体中最佳个体的适应度低于总的迄今为止的最好个体的适应度，用迄今为止的最好个体替换掉当前群体中的最差个体。

3.4适应度函数

多目标优化问题是指一个问题存在多个需要优化的性能指标，每个性能指标都有其不同约束条件，多目标优化就是要寻求一个在满足各个约束条件下且能使各个需要优化的目标能得到优化解［11-12］。企业生产调度问题是一个典型的多目标优化问题，生产系统的效率取决于很多因素如生产周期（市场销售）、机器生产的利用率、库存（成本）等，上层管理决策对各目标的考虑权重不同也直接决定着生产调度的结果发生变化。本文算法在交叉变异过程中使用相关参数α、β进行环境适应性调整，以达到多目标综合决策要求。

3.5交叉变异操作

交叉算法直接决定着遗传算法的全局搜索能力，基于关键路径的交叉算子操作如下；首先根据交叉概率和适应度权重的配置选择一对父母个体，仅对后续非关键基因部分进行交叉操作；随机选择非关键活动上的一个工件，其在父母个体中对应的x个操作不变，父母个体剩余其他操作按顺序进行对应变换，分别得到新的两个子代个体。

变异算子决定了遗传算法的局部搜索能力，良好的算子可以有效的维持群体的多样性，防止早熟现象的出现。为了保证关键活动的顺利完成以及种群的多样性，变异操作分为两大步骤进行：首先根据变异概率对关键路径上的工序进行机器配置变异，然后对非关键工序进行局部重新定位［16-18］。

3.6算法流程

1）调度任务数据初始化；

2）建立AOE网，求出关键路径，随机生成初始种群；

3）计算适应度，结合使用最优保存策略采用轮盘赌方法进行选择；

4）基于关键路径进行交叉变异操作；

5）满足终止条件，转步骤6，否则转步骤3；

6）输出最终解集。