求解作业车间调度问题的离散海洋捕食者算法

姚 雄，张永平

(1.盐城工学院机械工程学院，江苏 盐城 224051；2.盐城工学院信息工程学院，江苏 盐城 224051)

0 引言

调度是工业，尤其是制造业的基本活动之一。它对于计划工作、流程时间以及如何处理资源非常重要，它规划了任务的完成时间和工作活动之间的关系。作业车间调度问题(job-shop scheduling problem，JSP)是离散制造系统中最经典的调度问题。JSP作为最困难的组合优化问题之一，是一个著名的NP-hard问题，即没有一种算法能在多项式时间内收敛到问题的最优解。许多学者提出了一些启发式和基于优化的调度算法，以提高制造效率和降低其成本为目标来解决JSP[1-3]。

由于作业车间调度问题的规模和约束，当前大多数研究都集中在启发式和元启发式算法的使用上，广为人知的有遗传算法(genetic algorithm，GA)、粒子群算法(particle swarm optimization，PSO)[4]和蚁群算法(ant colony algorithm，ACO)[5]等。遗传算法是一种基于达尔文进化论和孟德尔遗传学说的随机自适应搜索算法。该算法的主要操作包括相似物种在进化过程中的遗传选择、交叉和变异。粒子群算法模仿了简单的社会系统，最初是用于模拟鸟类搜索食物的过程，但后来被发现是一种很好的优化算法。蚁群算法模拟了蚂蚁的觅食行为，已成功地应用于许多离散优化问题。近年来，新提出的鲸鱼优化算法(whale optimization algorithm，WOA)也获得了许多学者的关注和研究[6]。

为了获得更优良的作业车间调度结果，本文提出了一种海洋捕食者算法(marine predators algorithm，MPA)的离散变体，称为离散海洋捕食者算法 (discrete marine predators algorithm，DMPA)，并从对立学习、混沌映射及自适应步长策略等优化方向入手，实现作业车间高效合理的调度。

1 JSP描述及数学模型

1.1 问题描述

JSP一般描述为在给定加工工艺、机床顺序和每个工件的加工时间下，通过合理安排n个工件在m台机器上的加工顺序来优化性能指标。求解作业车间调度问题时的基本约束条件如下：

a.每个工件都有若干要完成的工序。

b.每个工件不能同时在多个机器上加工。

c.每道工序的加工时间在每台机器上是确定的。

d.所有工件都在0时刻可用。

e.每台机器在同一时段内最多可处理1道工序。

f.所有工序必须在1组机器上完成。

1.2 数学模型

本文将JSP用整数规划模型描述为

min max1≤j≤mcij

(1)

1≤i≤n

约束于：

cij-tij+M(1-aihj)≥cih

(2)

ckj-cij+M(1-xikj)≥tkj

(3)

cij≥0

(4)

aihj、xikj=0,1

(5)

i、k=1,2,…,n

(6)

j、h=1,2,…,m

(7)

tij为工件i在机器j上的加工时间；cij为工件i在机器j上的完成时间；aihj为指示系数，aihj= 1表示在加工工件i时机器h早于机器j，aihj= 0表示在加工工件i时机器j早于机器h；xikj为指示变量，xikj= 1表示在机器j上，工件i早于工件k加工，xikj= 0表示在机器k上，工件i早于工件j加工；M为足够大的正数。

式(1)确定了JSP的目标：使最大完工时间最小化。

2 海洋捕食者算法

海洋捕食者算法是Faramarzi等[7]在2020年提出的一种新型元启发式算法，是利用布朗运动和莱维飞行模拟海洋捕食者觅食猎物的物理行为。该算法通过E矩阵和Y矩阵的迭代更新来完成目标(最佳解)的获取。E是顶级捕食者(最佳解)，捕食者根据猎物Y的位置更新自己的位置。与其他基于种群的算法不同，在MPA中捕食者并不总是搜索者，有时猎物也是搜索者。MPA的数学模型表示为

(8)

XI为顶级捕食者；Xi,j为第i个猎物的第j个维度；n为种群数量；d为维度。

根据捕食者和猎物的寿命,MPA的迭代优化过程分为3个阶段。在第1个阶段，猎物是搜索者，捕食者是目标；在第2个阶段，捕食者和猎物可以同时是搜索者和目标；在最后阶段，捕食者是搜索者。这3个阶段的数学模型如下：

Si=RB⊗(Ei-RB⊗Yi)i=1,2,…,n

(9)

Yi=Yi+(P·R⊗Si)i=1,2,…,n

(10)

S为运动步长；RB为布朗运动，它是一个正态分布的随机矢量；R为[0,1] 中的均匀随机向量；P为常数 0.5；It为当前迭代次数；Mt为最大迭代次数。

(11)

(12)

RLYi是用来模拟猎物的运动；RL为基于莱维运动的随机向量。

(13)

(14)

RB⊗Ei是用来模拟捕食者的运动；CF为步长控制参数，其更新方式为

(15)

Si=RL⊗(RL⊗Ei-Yi)i=1,2,…,n

(16)

Yi=Ei+P·CF⊗Sii=1,2,…,n

(17)

然而，捕食过程中可能会受到涡流形成或鱼类聚集装置(FA)影响而陷入局部最优，因此采用较长的步长跳跃来避免局部收敛。跳跃方式为：

Yi=

(18)

FA= 0.2；r为[0,1]中的随机数；Xmax和Xmin为猎物位置的上下限；U为一个值为0和1的二进制向量；Yr1和Yr2为随机选择的2个猎物位置。

最后，在每次迭代结束时，通过海洋记忆将当前解与前一次迭代的解进行比较，选择适应度更高的解来提高种群质量。

MPA在理论上是成功的，有许多学者研究了它在连续数学函数领域的优化及改进[8-10]；但是其也存在求解精度低和收敛速度慢的不足，无法创造出高质量初始种群，也没有离散化的版本应用于实际问题。

3 离散海洋捕食者算法

3.1 位置向量与调度解之间的转换机制

海洋捕食者算法是为优化各种连续型非线性函数而提出的，而作业车间调度问题属于典型的组合优化问题，是离散型问题。由于MPA中猎物位置向量不是用离散值生成的，所以需要对这些连续的位置值进行编码。离散个体更新方法旨在确保算法能直接在离散域中工作。

本文采用最小位置值法(smallest position value，SPV)[11]对调度解和位置向量进行转换。如图1所示，对于已有的1组调度解(工序)，先产生1组相应的随机数，随机数的索引值依据SPV规则按从小到大排序，此SPV值与工序一一对应；之后按照工序号的编码顺序对SPV值进行重排；最后重排的每个SPV值对应的随机数即为位置向量中元素的值。逆过程如图2所示。

图1 调度解转为位置向量

图2 位置向量转为调度解

3.2 对立学习初始化

在元启发式算法中，优化过程从随机产生的初始种群开始，原海洋捕食者算法也不例外。如果随机生成的初始种群接近最优解，则很可能会更快地得到正确解。但随机生成的部分个体往往会分布在远离最优解的无效区域和边缘区域，故优化过程也可能是从最优解距离最远的位置处开始，在这种情况下搜索将花费更长的时间，甚至可能无法得到最优解，进而降低了种群的搜索效率。

对立学习(opposition-based learning，OBL)是2005年由Tizhoosh[12]作为机器智能的新方案首次引入的，该方法被认为是计算智能中的一个强大的数学概念[13]。策略为

Oi=Xmin+Xmax-Xi

(19)

Xi为当前向量；Oi为Xi的相反位置；Xmin和Xmax分别为问题中变量的下界和上界。

新位置有更多的机会来寻找到最佳解。Oi由目标函数评估，如果Oi比Xi处于更好的位置，Xi将被替换。在目标函数上下界限对称的时候，由式(19)可以看出，所生成的反向解为原来解的完全镜像(取负)，对部分具有偶函数特性的函数，完全镜像解与原解目标值一致，不适合将2个种群做适应度排序，无法有效获得高质量种群。但作业车间调度问题不是偶函数，上下界不对称，因此适用对立学习策略去提高初始种群的质量。

3.3 混沌映射

混沌映射是一种使用具有不可预测性质的混沌变量的方法，而不是随机变量。混沌序列存在于动态和非线性系统中，并且是非周期性的、非收敛的和有界的[14]。因此，混沌映射比基于概率的随机搜索拥有更高的收敛速度，而且执行简单。由于混沌序列的动态行为，在元启发式的算法中使用混沌变量而不是随机变量将有助于更好地探索搜索空间。

不同的混沌映射已被用于优化算法，通过改变它们的初始条件，可以很容易地生成不同的序列。本文算法采用圆形混沌映射(circle map)函数来提高MPA的收敛速度，将原算法中的关键随机数替换为混沌函数的变量数。从而广泛地探索空间，以获得更好的结果，使其避免陷入局部最优。过程表示为

(20)

xi+1为当前迭代产生的混沌随机数；xi为上一次迭代产生的混沌随机数；a和b分别为0.5和0.2；x0为0.01；mod为求余函数。图3为圆形混沌映射函数视图。

图3 圆形混沌映射函数

3.4 非线性步长控制策略

在MPA迭代优化中，步长控制参数CF对全局勘探和局部开发的平衡性影响较大。由式(14) ～ 式(18)可知，在迭代过程中，CF从1降低到0，较大的步长控制参数有利于全局探索，较小的步长控制参数有利于开发。因此，为了进一步提高勘探与开发的平衡性，增强全局勘探能力，促进局部开发的快速收敛，本文使用了一种新的非线性步长参数控制策略，定义为

(21)

为了验证所提出的控制参数的有效性，将本文提出的控制参数与原始的MPA非线性控制参数策略(式(15))进行对比。如图4所示，本文采用的非线性控制参数在早期缓慢减小，增加了全局搜索的时间；在后期迅速减小，在算法后期尽快收敛。

图4 步长参数对比

3.5 离散海洋捕食者算法流程

综上所述，离散海洋捕食者算法在原算法的基础上，增加个体位置与调度解间的转换方法，使用对立学习方法优化初始种群，采用圆形混沌映射函数来提高算法的收敛速度，改进自适应步长策略从而更好地平衡勘探和开发。离散海洋捕食者流程如图5所示。

图5 离散海洋捕食者算法流程

4 实验结果与分析

4.1 基准算例仿真

用FT06作为基准算例进行仿真来验证DMPA的算法性能，该算例为6(工件)×6(机器)的典型JSP问题，经过DMPA计算得到最优调度序列，甘特图如图6所示。

图6 FT06调度结果甘特图

在图6中，纵坐标为操作机器号；每个矩形代表1个工序，其左右边界分别为工序的开始时间和结束时间。以3号工件为例，其第1道工序在3号机器加工(301)，第2道工序在4号机器加工(302)，第3道工序在6号机器加工(303)……直至其第6道工序(最后一步)在5号机器完成(306)。从图中可看出该算例最大完工时间(Makespan)为55，这也是FT06问题已知的最优解，证明了该算法的可行性与有效性。

4.2 算法性能评价

将本文所提出的DMPA应用于JSP的7个基准算例，这7个基准算例具有不同的问题规模，比较具有代表性。将其与蚁群算法(ant colony algorithm，ACA)、禁忌搜索算法(tabu search algorithm，TSA)及鲸鱼优化算法(whale optimization algorithm，WOA)得到的结果进行对比，从而测试DMPA求解JSP的性能；ACA和TSA结果数据来源于文献[15]，WOA结果数据来源于文献[16]。DMPA参数按照文献[16]设置，初始种群规模为200，最大迭代次数为100；实验结果如表1所示，较好的结果用粗体标出。

表1 算法结果对比

表1中的“/”表示文献[15]没有进行测试。从表1可以看出，无论是较早的蚁群算法(1992年提出)、禁忌搜索算法(1986年提出)，还是新兴的鲸鱼优化算法(2016年提出)，DMPA都更具有优越性。在求解LA01、LA05这些较小规模问题时，DMPA可取得最优解。在求解LA16、FT10、LA21这些中等规模问题时，这些算法均不能取得最优解，DMPA仅在LA16这个问题上次于ACA，其他问题DMPA结果均更具有优势。而在处理大规模问题LA36、LA26时，DMPA比WOA表现出非常明显的优势，能够得到更好的结果。

5 结束语

MPA作为目前新颖的一种元启发式算法，针对于它的广泛应用还在研究和探索之中。本文将提出的离散海洋捕食者算法(DMPA)用于求解JSP问题，提高了海洋捕食者算法的适用性。DMPA使用对立学习方法增加了初始种群的多样性，采用圆形混沌映射函数提高了算法的收敛速度，改进了原算法的自适应步长策略从而更好地平衡全局勘探和局部开发。通过对7个基准算例的仿真实验，证明了本文算法的有效性和优越性。