面向智能制造的柔性车间调度算法研究

何 涛

（温州职业技术学院，浙江 温州 325000）

一、引言

2015年中国发布《中国制造2025》，部署推进实施制造强国战略，提出以推进信息化和工业化深度融合为主线，大力发展智能制造。在多品种、小批量的生产模式成为主流市场环境下，如何优化生产调度，实现智能、低耗和准时交货成为管理者追求的目标。智能生产要求在设计、供应、生产和服务各环节实现端到端无缝协作，从而使整个制造过程的感知、思维、推理、路径规划和决策成为一个整体。智能生产是智能制造的主线，而智能车间是智能生产的主要载体。在智能生产车间获得订单加工的任务后，需进一步对该任务以制造系统预先设定的某个或多个性能指标为目标进行优化计算。只有基于内嵌调度算法的局部最优或次优，才能真正实现制造车间调度的柔性、适应性和可靠性[1-5]。

本文面向智能制造的需求对作业车间调度优化管理问题进行研究，根据多品种小批量生产的柔性车间作业实际情况，考虑加工时间、机台负荷率、总的负荷率等因素，建立调度优化的多目标函数，并引入分解思维对多目标优化算法进行改进设计，实现多目标组合优化的柔性车间调度系统。

二、柔性车间作业调度问题概述

柔性车间的作业调度问题可概述为：有n 个工件（J 表示工件作业集）需在m 台设备上加工（M 表示机设备集）[6-7]。每个作业Ji（1≤i≤n）有ni道工序Oij（1≤i≤n，1≤j ≤n）需要加工。每道工序Oij由可加工的机床集Mij中任一台机床加工，其中Mij⊆M。调度管理的目标是在满足各种资源约束和工序前后关系约束的前提下，以优化管理的目标为导向，为工件的加工作业集选择最优的加工设备集，并给每台加工设备规划最佳的作业加工次序和起始加工时间。因此，需要解决问题：（1）路径分配子问题，即确定各工件的加工机器；（2）加工排序子问题，即对确定各个机器上的加工先后顺序。

通常企业生产调度优化管理考虑下列四种目标因素中的一种或多种因素的组合：（1）与生产量相关，如makespan、平均流程时间、最大流程时间等；（2）与作业交货期相关，如延误作业百分比、平均延误、最大延误等；（3）与在制品相关，如作业平均等待时间等；（4）与设备利用率相关，如设备总的使用率，关键设备使用率等。

表1 柔性车间作业调度

为了更加贴近生产时间，本文同时选取最大作业完工时间、最大设备负荷和所有设备总负荷这三个性能指标，建立如下目标函数：

1.最大作业完工时间

式（1）中，Ti是设备Mi的完工时间。

2.最大的设备负荷WM

式（2）中，Wi是设备Mi的工作负荷。

3.所有设备的总负荷

三、基于MOEA/D 的柔性车间调度的多目标算法设计

以上论述已经建立了多目标优化问题的模型，如何求解是重要的一环。本文采用分解思想，采用基于分解的多目标进化算法（MOEA/D）（Qingfu Zhang 等）[8]，利用切比雪夫聚合方法将多目标车间调度的求解转化成为多个单目标问题同时优化，降低了计算难度、提高了优化效率。

其中，λ=（λ1，…，λm）是一组权重向量，为参考点，对于所有的i=1，…，m，有。

具体而言，首先对多目标调度问题的可行解的编码形式进行设计；然后是种群的初始化；接着产生每个子目标的权重向量；再根据向量间的欧几里得距离计算将种群划分成为多个邻域集合，并在选定的邻域空间内完成个体的交叉、变异等遗传进化操作；最后将新生成的个体择优保存下来，进入下一轮迭代，直到达到设定条件时结束。整个算法设计的流程图如图1 所示。

图1 柔性车间作业调度算法流程框架

关键步骤包含如下几个方面：

（一）编码和解码

柔性作业车间调度问题的可行解实质上是作业任务在可加工设备集中进行选择，并完成所有的作业进行排序。因此，解的编码形式可以解决机器分配和作业排序两个决策问题。根据其特点，采用双层编码形式：第一层工序编码染色体，确定工序间的先后加工顺序，解决作业排序的问题；第二层是机器编码染色体，确定所选择的加工机器，解决机器分配的问题。两层融合一起形成一条染色体，即为柔性作业车间调度的一个可行解。

1.编码。结合表1，说明具体的编码过程。表1是包含有3 个工件和5 台机器的车间生产。首先生成基于工序的编码染色体，为了表示工件的加工顺序，生成表1 的工件编码染色体矩阵，矩阵的元素aij表示工件i 的第j 道作业工序，该元素对应的取值表示对应作业工序的排列顺序，工件不存在的工序对应位置的元素置为0。因此对于表1，有矩阵编码O，可以在初始化的时候，随机生成一个对应的实际加工作业工序矩阵。比如生成O1：

表示生产的工件工序的加工先后顺序为：O21-O11-O31-O12-O22-O13，即为形成了一个编码染色体的第一层。

接着生产编码染色体的第二层：根据工序的加工顺序，选择加工设备。对照表1 中，按照第一层编码的基因顺序，形成每个作业基因的可加工设备集。比如有，k 个作业工序，形成k 个可选设备的子集{S1，S2，…，Sk}，其中Si表示第i 个作业工序的可加工设备集合。编码过程如图2 所示。

图2 编码形式

2.解码。解码时先对双层编码的第一层的作业工序编码基因串进行解码，按照从左往右的顺序依次获取编码的基因，从而确定所有作业工序的加工顺序，即形成一个有序的作业工序列表；然后依据第二层机器编码基因串确定每个作业的对应的加工机器，即形成设备加工的时间顺序表格；最后按照设备加工顺序表以最早允许加工时间为开始时间，进行加工作业安排，即可形成可行解。

（二）种群初始化和选择方法

种群初始化选择现有的方法较多，各有利弊。常见的方法有：比例选择（轮盘赌选择）、稳态繁殖、反向学习选择、排序选择法等。为了合适的种群初始化选择，本文采用随机的轮盘赌选择法和精英个体解选择的两阶段初始化方法。

1.种群初始化

首先，随机初始化工序编码链。对应前面的工序矩阵编码O，随机生成其对应的每个元素的值。生成元素的值的范围应该是在[1，2，…，k]，其中，k 为总的工序数，不存在的工序，其对应的元素值为0。比如上文中O1即为随机长生的工序个体，对应的加工工序染色体为：O21-O11-O31-O12-O22-O13。

其次，随机初始化工序编码链。对应双层编码的第一层的每个工序基因随机初始化选择可加工的机器，从而生成机器编码链。比如对照O1工序链对应生成机器链M5-M1-M3-M2-M5-M1。

2.选择方法

首先，使用随机的轮盘赌选择法。假设最初产生的n 个可行解，个体i 的适应度值为fi，那么该个体被种群选择保留的概率表示为

其次，保留初始化种群中的精英个体。对所有的个体按照适应度进行排序，挑选群体中最优的几个个体进行保留。

（三）权重向量的产生

（四）个体交叉操作

首先，确定上层的交叉方式，然后根据上层交叉形式来实现两层编码的同时交叉操作，一方面保证在工序交叉过程中同一工件的不同工序间一定的先后顺序不能错位，另一方保证下层的机器交叉对应工序交叉，从而使得整个二层编码依然是调度方案的可行解。具体过程如下：

步骤1：利用交叉概率Pc，选出需要交叉的父代个体。

步骤2：随机产生一个整数r，1≤r≤k；将所有的工件作业工序按照r 分成两个部分：Ji，1 ≤i≤r 和r＜j≤k。

步骤3：选择一个父代1，在其第一层工序编码层中将Jr工件包含的基因位和第二层对应的基因保持不变，并复制到子代染色体对应基因位上去；将另外一个父代2 中的除Jr工件外的其余工件对应的两层基因依次复制到子代染色体剩余的基因位中去；第二层设备编码层依然对应第一层的位置进行交叉操作，从而简单有效地满足机器约束。假设随机产生数r=2，则加工工件结合分为两个部分{J1，J2}和{J3}，整个操作过程如图3所示。

图3 交叉过程

（五）变异操作

选择适当的变异方法局部得到更优的解。根据双层编码的特点，变异操作采用两种方式：第一层部分基因交叉变异，第二层对应基因自变异的形式。具体过程如下：

步骤1：产生变异概率Pb，选出需要变异的父代个体。

步骤2：随机产生一个整数r，1≤r≤k；将染色体编码层的第一层的工件作业工序基因Jk与其邻域基因Jk+1，进行交叉变异操作；将染色体编码层的第二层对应的基因位在可加工设备集进行随机自变异操作，具体过程如图4 所示。

图4 变异过程

四、仿真及分析

为对上述方法正确性进行验证，选取Kacem基准测试中的一个实例进行仿真，该测试集具体详细信息如表2 所示。设定种群大小为100，进化迭代数为100，交叉概率为0.5，变异概率为0.01，连续仿真10 次后，可得部分最优解如表3 所示。

表2 仿真实例

表3 仿真支配解

根据上述求得的最佳非支配解，从最大作业完工时间、最大的机器负荷、所有机器总负荷等三个方面因素来综合衡量，以解1 最优，可以得到甘特图（见图5）。

图5 甘特图

五、总结

根据智能制造对作业车间调度优化管理的新要求，研究多品种小批量生产的柔性作业车间调度，综合考虑最大作业完工时间、最大的机器负荷、所有机器总负荷等因素，建立多目标函数；引入分解的思想，基于分解的多目标进化算法进行改进设计，对编码形式、遗传操作等进行设计；最后引入标准的数据集进行验证，证明算法的正确性和有效性。