无人计量实验室中的车间调度问题优化与仿真

武子科，潘 警攀，彭 警诚，张洪光

(1.北京东方计量测试研究所，北京 100093；2.北京邮电大学，北京 100876)

1 警引言

车间调度问题是典型的NP-Hard问题之一，具有广阔的工业应用前景[1，2]。车间调度是指在资源有限的情况下对工件加工任务进行排序，使其达到最优的生产调度指标。该类问题的相关研究，在很多领域中有着重要的实用价值。

北京东方计量测试研究所的无人计量实验室是无人值守的计量检测平台，该实验室可以进行多个型号电学仪器的多个种类计量检测任务，每个任务无调度顺序的约束。因此，可以把无人计量实验室定义为开放式车间环境，该开放式车间环境的计量检测任务分配可以被定义为开放式车间调度问题(open shop scheduling problem，OSSP)。

如图1所示，开放式车间调度问题的一般形式为n个工件在m台机器上进行加工，所有工件均需在每一台机器上进行一次加工，且无前后加工顺序约束，求解最小化最大完工时间的加工排序。如果工件在机器上以固定加工顺序进行加工，该问题将演变为流水车间调度问题；如果每个工件按各自加工顺序进行加工，该问题将演变为作业车间调度问题。因此，开放式车间调度问题具有较高的复杂度。

图1 不同车间调度问题示意图

求解开放式车间调度问题的方法主要有精确算法和智能算法。Bruker等人[3]基于析取图提出的分支定界算法是一种被广泛应用的精确算法，首次在标准算例上取得了部分最优解。Gueret等人[4]在该研究基础上加入智能回溯算法，解决了更大规模的问题。由于精确算法的时间复杂度大，不适于求解大规模问题，当前的研究主要采用智能算法提高求解效率。Liaw等人[5]将基于禁忌搜索的局部改进过程引入遗传算法中，在局部最优子空间进行遗传搜索，获得了标准算例中的大部分最优解。Blum等人[6]在蚁群算法中加入集束搜索提出集束蚁群搜索算法，加速了问题求解速度，提高了解的质量。此外，高亮等人[7]针对粒子群优化算法信息共享机制的缺陷提出改进的粒子群优化算法，提高了粒子群优化算法在该问题中的邻域搜索能力。陈祥等人[8]使用文化基因法进行了优化求解，并在标准算例中验证了其算法在搜索空间较大问题中的优势。灰狼优化算法是Mirjalili等人[9]在2014年提出的一种新型优化算法，大量的实验表明[10，11]，该算法及其改进算法在求解精度和稳定性上优于粒子群优化算法、遗传算法等。灰狼优化算法已广泛应用于路径规划问题、无人机协同调配问题和轨迹预测问题等，然而在车间调度问题中的应用刚刚起步。Komaki等人[12]和Jiang等人[13]分别证明了灰狼优化算法在流水车间调度问题和作业车间调度问题及其变种问题的有效性。但是，在开放式车间调度问题中灰狼优化算法的有效性还未得到实验证明。

由于无人计量实验室具有多种的计量检测任务，如何实现不同任务的合理调度，是无人计量实验室研究主要问题之一。本文首先将无人计量实验室的计量检测任务调度问题定义为开放式车间调度问题，并提出基于适应度和距离评估标准的离散灰狼优化算法(discrete grey wolf optimization，DGWO)。此外，根据北京东方计量测试研究所无人计量实验室的日常实际计量检测需求，使用离散灰狼优化算法，来实现最小化最大完成时间的目标。

2 开放式车间调度问题模型

开放式车间调度问题模型的参数定义，如表1所示。由工件集J={J1，J2，…，Jn}和对其进行加工的机器集M={M1，M2，…，Mm}组成，每个工件Ji∈J均在每个机器Mj上执行相应的工序Oi，j。相关的假设如下：①每个工件需在全部m台机器上完成m个操作，无顺序优先性；②工件加工工序严格遵守加工时间，加工过程不能中断；③任意时刻一台机器只能加工一个工件，且任意时刻一个工件只能在一台机器上加工；④0时刻所有机器可用；⑤不考虑机器故障及工件到达延迟等问题。

表1 参数定义

本文使用整数规划模型[6，14]来描述开放式车间调度问题，并以最小化Cmax为优化目标，如式(1)-(8)所示。式(1)为目标函数；式(2)表示每个工件只能在每台机器上加工一次；式(3)表示每台机器加工完一个工件后只能继续加工另一个工件；式(4)表示零工序可以为任意工序的前置工序；式(5)表示任意工件的一个工序不能同时在另一个工序之前和之后；式(6)表示任意时刻一台机器只能加工一个工件；式(7)表示任意时刻一个工件只能在一台机器上进行加工；式(8)表示最大完工时间不小于任意一个工件的完工时间。

minCmax

(1)

(2)

(3)

(4)

(5)

Ck，j-Ci，j≥Pk，j，∀j∈M;∀i，k∈J;i≠k

(6)

Ci，1-Ci，j≥Pi，1，∀j，l∈M;j≠1;∀i，k∈J

(7)

Cmax≥Ci，j，∀i∈J;∀j∈M

(8)

3 求解开放式车间调度问题的灰狼优化算法

3.1 基本灰狼优化算法

灰狼优化算法是受自然界狼群捕猎行为启发而提出的一种群智能优化算法。该算法模拟了自然界中灰狼群体的领导等级和狩猎机制，用四种类型的灰狼(α狼、β狼、δ狼和ω狼)模拟狼群阶层，并模拟了追踪、围猎和攻击过程。灰狼算法将每只狼抽象为问题的一个解，适应度最好的解为头狼，称为α狼，适应度次好的解为β狼，适应度第三的解为δ狼，其它解为ω狼。ω狼在α狼、β狼和δ狼的引领下完成追踪、围猎和攻击行为，最终捕获猎物。灰狼群围猎的数学模型用以下公式进行描述

(9)

(10)

(11)

(12)

(13)

(14)

3.2 基于适应度和距离评估标准的离散灰狼优化算法

提出的离散灰狼优化算法，使用适应度和距离评估标准，选出最好适应度的个体作为α狼，此外，还选出既有较好适应度、又与α狼有一定汉明距离的β狼和δ狼。从而，尽量让α狼、β狼和δ狼平衡地引导狼群，保持种群多样性，避免早熟现象发生。通过反复迭代，不断更新α狼、β狼和δ狼，使得种群逐渐向最优解收敛。

3.2.1 算法框架

离散灰狼优化算法框架如下：

算法1：离散灰狼优化算法

输入：变异概率pm，距离系数b

Step 1：用随机整数序列，生成初始种群；

Step 2：计算种群适应度，按适应度对种群进行排序；

Step 3：根据适应度和距离评估标准，选出α、β、δ个体，并将其余个体标记为ω；

Step 4：对ω中所有的个体执行按照式(15)离散搜索策略；

Step 5：检查是否到达终止条件，如果没有，则返回Step 2；

Step 6：输出得到的最优个体与最高适应度。

3.2.2 编码方法

本文使用工序编码方案，即将编码定义为按工序排列的序列，编码位数值是由从1到n×m的数字组成。以图2为例，考虑3个工件、3个机器，共计9个工序的问题，按照工序顺序进行编码。以个体(2-3-4-7-5-6-1-9-8)为例，表明其执行顺序为(O12-O13-O21-O31-O22-O23-O11-O33-O32)对应的甘特图见图3。

图2 3×3问题序号对应的操作示意图

图3 个体(2-3-4-7-5-6-1-9-8)的甘特图

3.2.3 适应度和距离评估标准

本文对于灰狼群中α狼、β狼、δ狼三个体，采取了基于适应度和距离排名的选择策略[15]，具体步骤如下：

算法2 适应度和距离评估标准

输入：每次迭代的种群POP，距离系数b

Step 1：计算种群POP中每个个体的适应度Fitness，并将Fitness最优个体标记为α狼；

Step 2：将除α狼外的每个个体Fitness排名(从优到劣)记为Fitness Rank；

Step 3：计算种群中每个个体与α狼之间的汉明距离Distance；

Step 4：将种群中每个个体的Distance排名(从大到小)记为Distance Rank；

Step 5：选择Fitness Rank≤10和Distance Rank≤10的个体组成集合MP；

Step 6：计算MP中每个个体的Sum Rank=Fitness Rank+b×Distance Rank；

Step 7：选取Sum Rank最小的两个个体，分别标记为β狼和δ狼。

3.2.4 离散搜索策略

本文使用基于交叉和变异操作的离散搜索策略表示ω狼向α狼、β狼、δ狼的靠拢过程，如下所示

(15)

算法3 个体更新函数

输入：个体A、个体B、变异概率pm

Step 1：随机生成个体上的两个位置c1和c2；

Step 2：在B中将A中c1与c2之间的序号赋值为0，生成B1；

Step 3：从B1中c2后一位开始，将非零元素顺序排列成C；

Step 4：将全零个体D从c2后一位开始用C赋值；

Step 5：将D中的空位用A中c1与c2之间的元素填充；

Step 6：根据变异概率，对个体D执行插入变异操作。

在离散搜索策略中，种群中的每个个体都作为一个亲本，随机与α狼、β狼、δ狼之一执行个体更新函数，得到子代个体。图4显示了一次个体更新中交叉过程的实例。为保证种群的多样性，对交叉生成的个体执行一定概率的插入变异操作。其具体过程为：在个体上随机选择两个位置，将后一个位置上的序号放置于前一个序号之前。此外，图5显示了一次个体更新中的插入变异过程。

图4 个体交叉过程示意图

图5 个体变异过程示意图

4 实验与讨论

4.1 实验设计

为证明离散灰狼优化算法求解开放式车间调度问题的性能，在经典数据集和北京东方计量测试研究所无人计量实验室实际问题中进行了实验。Taillard等人提出了经典数据集[16]，是开放式车间调度问题的常用数据集，本文选取由7个机器和7个工件组成的10个测试实例，以T7-1～T7-10作为测试问题编号。北京东方计量测试研究所的无人计量实验室由六个机械臂自动检测环节O1O2O3O4O5O6组成，6个待检测件均需进行无顺序要求的六个环节的计量检测。图6显示了实验室的布局情况，和其中两个执行不同计量检测任务的自动检测环节实物图。本文选取该实验室实际计量数据中的10组数据作为10个实例，并使用编号F1～F10进行区分(https:∥github.com/ZikeW/OSSP.git)。

图6 无人计量实验室的调度问题示意图

本文将选取Hosseinabadi等人提出的扩展遗传算法(EGA_OS)[17]、Senthilkumar等人提出的启发式算法(Hu1)[18]、基本灰狼优化算法(GWO)作为对比算法[9]。其中，EGA_OS算法和Hu1算法的交叉概率为0.8；DGWO的距离系数b从1线性递减到0。所有算法的种群规模为50，变异概率为0.2，终止条件为种群进化600代。

针对每个问题，每种算法都运行50次，通过比较50次Cmax的平均值，来测试算法的有效性。此外，使用误差棒来表示50次Cmax的标准差，来比较算法的稳定性[19]。

4.2 实验结果与分析

如图7所示，对于经典数据集T7-1～T7-10测试问题，提出的DGWO算法在绝大多数问题中取得了最好Cmax的平均值结果。此外，EGA_OS算法虽然也得到了较好的平均值，但是有着较大的标准差，说明了其稳定性有待提高，Hu1算法和GWO算法取得的平均值和标准差都相对较大。上述实验结果说明，提出的DGWO算法在开放式车间调度问题的经典数据集测试中具有较好的有效性和良好的稳定性。

如图8所示，与其它对比算法相比，提出的DGWO算法在北京东方计量测试研究所无人计量实验室数据集的绝大多数问题中均取得了最好的Cmax平均值和标准差。这些实验结果，说明了提出的DGWO算法在无人计量实验室调度问题中具有有效性和稳定性，能够应用于实验室中实际计量检测任务的调度，提高计量检测效率。

综上，两种实验结果说明了不同算法在不同规模问题中的有效性和稳定性，也说明了提出的DGWO算法能够适用于7×7规模的经典数据集和6×6规模的实验室数据集，可以较好地适应不同规模的测试问题。

5 结束语

灰狼优化算法作为一种新兴的智能优化算法，已经在很多领域得到了应用，但是在开放式车间调度问题中的相关研究才刚刚起步。本文提出了一种离散灰狼优化算法，验证了离散灰狼优化算法在开放式车间调度问题的可行性。在经典数据集和北京东方计量测试研究所无人计量实验室实际问题上进行的测试，证明了提出算法的有效性和稳定性，为未来无人计量实验室的计量检测任务调度研究打下了基础。

图7 Taillard经典数据集T7-1～T7-10仿真结果

图8 无人计量实验室数据集F1～F10仿真结果

在未来无人计量实验室调度问题的研究中，工件的运输延迟、机器故障等事件会影响实验室计量检测任务的统筹调度，如何解决这些不确定性调度问题是无人计量实验室的未来研究方向之一。