基于动态学习和个体淘汰的鲸鱼算法求解订单接受与调度问题

任丹萍，郑子威，陈湘国

(1.河北工程大学 信息与电气工程学院，河北 邯郸 056038； 2.河北工程大学 河北省安防信息感知与处理重点实验室，河北 邯郸 056038)

对于按订单生产型的企业(Make To Order，MTO)，在收到来自客户的订单时，要根据生产线的实际生产能力考虑订单的完工时间以及订单的最终收益。当订单不能按时完工，不仅需要承担延迟的惩罚还会对企业的信誉有所影响，造成客户的流失。所以企业如果想获得最大的收益，那么有选择性地接受订单和合理地安排订单的生产尤为重要。针对订单的接受与调度问题，已经有很多的学者对此建立了相关的数学模型并提出了多种智能优化算法进行求解。Oguz等人[1]较早地对考虑了订单延迟惩罚的订单接受与调度问题进行了研究，并提出了迭代启发式算法，使用模拟退火算法概念来处理所选订单的排序。Xie等人[2]使用改进的蜂群算法来解决带有延迟惩罚的订单调度问题。Noroozi等人[3]使用粒子群算法与遗传算法相结合的混合算法进行求解订单调度问题并证明了混合算法的优势。宋李俊等人[4]针对多机器下的订单接受与调度问题提出了双层编码的遗传算法，使用将订单顺序和机器顺序分开编码的方式进行求解。Wang等人[5]提出一种基于列表调度的多目标孤雌遗传算法求解多机器生产环境下的订单调度问题。Guhlich等人[6]在按需生产的背景下，对随机的订单生产需求，结合出价价格收入和基于清算功能的订单下达计划来建立决策模型。王雷等人[7]考虑了生产线有限缓冲区的问题，在订单接受与调度模型中加入缓冲区的成本这一要素，并使用和声搜索算法和变邻域搜索的混合方法进行求解。Ou等人[8]限制了订单的拒绝数量，并提出两种启发式算法进行求解，通过实验对算法的时间复杂度进行分析。王思涵等人[9]采用新型的鲸鱼优化算法(Whale Optimization Algorithm，WOA)来求解生产线中车间调度的问题并取得了良好的成效。吕新桥等人[10]使用新型的灰狼优化算法(Gray Wolf Optimization，GWO)应用在车间调度的问题当中并与传统的优化算法作比较，证明了其更有优势。

本文在以上传统的订单接受与调度模型的基础上加入订单拒绝成本这一重要因素，并采用新型的智能优化算法WOA应用在模型当中。针对WOA依然存在像其它寻优算法容易陷入局部最优的缺点，而且不能直接用于求解订单接受与调度这类整数域问题。本文提出改进的鲸鱼优化算法(IWOA)，从编码方式、种群初始化、动态学习、个体淘汰多个方面对WOA进行了改进，使其可以应用于订单接受与调度模型当中，并在一定程度上改善了算法本身过早收敛的缺陷。最后将IWOA和WOA以及文献[10]中改进的灰狼优化算法(HGWO)进行实验对比，证明了IWOA在订单接受与调度问题上的求解效果更好。

1 订单接受与调度问题描述及建模

企业在收到来自客户的订单时，安排合理的生产计划的关键在于结合生产线的实际生产能力和影响订单收益的各种因素建立贴合实际的数学模型。本文研究的订单接受与调度问题描述如下：

(1)在某一时间共有N个订单等待排产，订单可以有选择性的接受。以下公式中Ai为1代表i号订单被接受，0表示i号订单不被接受。

Ai={0,1}

(1)

(2)生产线有M个节点，每个节点只有一台加工机器,每种订单都会经过M个节点处理，若订单在交货期后完成产生延时惩罚。以下公式中SLPi表示订单i产生的延时惩罚，LPi代表i号订单的单位延迟惩罚；FTi,m代表i号订单在m号机器上的完工时间；DTi代表i号订单的交货时间。

SLPi=LPi×max{FTi,m-DTi,0}

(2)

(3)若订单在交货期前完成会积压在库存产生库存成本。以下公式中SSPi表示订单i产生的库存成本。

SSPi=SPi×max{DTi-FTi,m,0}

(3)

(4)订单分为F种类型，若当前订单和上一个加工的订单类型相同时，机器没有准备时间；若当前订单和上一个加工的订单类型不相同时，存在机器切换的准备时间。以下公式中HTj,i-1,i表示j节点上的机器从订单i-1类型切换到订单i的时间，STi,j表示订单i在j节点的开始时间，式(4)为约束条件，表示订单i在j节点的开始时间大于等于订单i在上一个节点的完工时间并且大于等于上个订单在j节点的完工时间加上j节点上的机器从订单i-1类型切换到订单i的时间。

max{FTi,j-1,FTi-1,j+HTj,i-1,i}≤STi,j

(4)

(5)订单在当前节点加工完成则马上进入下一个节点进行加工，无需等待；如果下一个节点机器正在加工其他订单，则当前订单需要等待。以下公式中WTi,j代表i号订单在j号机器的等待时间，式(5)为约束条件，表示订单i在j节点的等待时间等于上个订单在j节点的完工时间加上j节点上的机器从订单i-1类型切换到订单i的时间减去订单i在上个节点的完工时间。

WTi,j=max{FTi-1,j+HTj,i-1,i-FTi,j-1,0}

(5)

(6)订单在节点间等待时会进入缓冲区，订单在缓冲区等待时会存在缓冲成本。以下公式中SWPi表示订单i产生的缓冲区成本，WPi代表i号订单的单位缓冲区成本，SPi代表i号订单的单位库存成本。

(6)

(7)如果订单的最终收益赔钱，并且价格在毁约金以上，则撤销该订单并支付毁约金。以下公式中Pi表示订单i的最终收益，BPi表示订单i的违约金，式(7)为约束条件，表示订单i的最终收益要大于订单的毁约金。

Pi=max{Pi,-1×BPi}

(7)

(8)如果拒绝掉客户的订单会产生拒绝成本。以下公式中SRPi表示订单i产生的拒绝成本，RPi代表i号订单的拒绝成本。

SRPi=(1-Ai)×RPi

(8)

(9)以下公式中PTi,j表示订单i在j节点的加工时间，式(9)为约束条件，表示订单i在j节点的开始时间等于订单i在上一个节点的结束时间加上订单i在j节点的等待时间，式(10)为约束条件，表示订单i在j节点的完工时间等于订单i在j节点的开始时间加上订单i在j节点的加工时间。

STi,j=FTi,j-1+WTi,j

(9)

FTi,j=STi,j+PTi,j

(10)

根据以上问题描述建立的最终表示订单实际收益的数学模型如式(11)所示，公式中MPi代表i号订单的市场收益。

(11)

2 标准鲸鱼优化算法

对于像订单调度这类NP-hard问题，是无法求解到最优解的，使用类似先来先服务、短订单优先、最短交货期优先等标准的、确定型的调度算法求解结果并不可靠，而使用不断寻优的智能优化算法求解效率更高。WOA是模仿鲸鱼捕食这一生物特性而提出的新型智能优化算法，具有参数少、寻优能力强的特点，而且收敛速度和精度优于传统智能优化算法[11]。在算法中每一个鲸鱼个体的位置就可以代表求解函数的一个目标解，即代表一种订单调度结果。WOA包含三种更新位置的方式，分别为包围捕食、螺旋更新、搜寻猎物，鲸鱼首先通过搜寻猎物逐渐获取猎物的相关信息，然后通过包围猎物和螺旋靠近的方式不断地靠近猎物，最终找到猎物，即找到问题的最优解[12]。

2.1 包围猎物

鲸鱼在寻找到目标猎物后，便包围捕获猎物，即向猎物位置前进，在寻优问题中目标猎物就是当前的最优个体，种群中的鲸鱼个体在迭代过程中向最优个体位置前进，位置更新公式如式(12)所示，当p<0.5并且|A|<1时采用鲸鱼当前方式进行移动。

x(t+1)=xbest(t)-A×D

(12)

D=|C×xbest(t)-x(t)|

(13)

A=2×a×r1-a

(14)

C=2×r2

(15)

a=2-2×t/tmax

(16)

式中：t为迭代搜寻次数；tmax是最大迭代次数；x(t)为鲸鱼位置；xbest(t)是全局最优位置；A和C为系数矩阵；r1和r2是[0，1]均匀分布随机数；a为收敛因子，从2到0线性递减；p为[0，1]均匀分布随机数。

2.2 旋转搜寻

鲸鱼在靠近猎物过程中，采用螺旋的方式进行移动，搜索路径中可能存在的最优解，位置更新公式如式(17)所示，当p≥0.5时采用鲸鱼当前方式进行移动。

x(t+1)=xbest(t)+D×ebl×cos2πl

(17)

式中b为常数1，可以改变螺旋的形状；l为[-1，1]均匀分布随机数。

2.3 随机搜寻

鲸鱼向随机的个体方向移动，进行全局搜索，位置更新公式如式(18)所示，当p<0.5并且|A|≥1时采用鲸鱼当前方式进行移动。

x(t+1)=xrand(t)-A×|C×xrand(t)-x(t)|

(18)

式中xrand(t)为一个随机的鲸鱼位置。

3 改进鲸鱼优化算法

虽然WOA在寻优效率和求解精度等方面优于其他传统优化算法，但是依然存在易陷入局部最优、易偏离全局最优方向的问题。针对这些问题本文分别在编码、种群初始化、向历史个体动态学习、淘汰劣质个体4方面进行了改进。

3.1 基于排序和偏离度的编码方式

WOA被提出是用来解决连续问题的，其解空间是实数域[13]。但是订单接受与调度问题是整数域问题，每一个鲸鱼个体必须可以代表一个订单的加工顺序，文献[13]使用按照鲸鱼个体大小排序来确定车间的加工顺序。本文采取文献[13]的思路，按照鲸鱼个体大小升序排序来确定订单的加工顺序，如表1、表2所示。

表1 原鲸鱼个体

表2 排序后鲸鱼个体

订单的加工顺序:1->3->0->2，但是这种编码方式却不能表示含订单接受的问题，针对这一问题本文在此基础上引入基于偏离度的编码策略，计算鲸鱼个体每一维度和平均值的偏离度，拒绝偏离度大的订单，偏离度计算如式(19)所示：

p=|Ex-x|/Ex

(19)

式中p为偏离度；Ex为均值；x为鲸鱼个体每一维度的数值，则订单的接受情况如表3所示。

表3 加入偏离度后鲸鱼个体

若取p为0.7，1号订单的偏离度大于p，则接受后的订单顺序为3->0->2。

3.2 基于二次反向学习和混沌序列的种群初始化策略

初始化的种群质量影响着整个算法的收敛速度和寻优效果，WOA采用随机的种群初始化方式并不能保证种群的多样性与优质性。孟磊等[14]提出二次反向学习应用于分布估计算法并取得了良好的效果。本文将二次反向学习策略应用于WOA并进行改进，在二次反向学习的基础上加入混沌序列, 混沌映射可以用来生成混沌序列，在种群初始化方面混沌映射产生的混沌序列比伪随机数有更好的效果。比较常用的离散混沌映射是Tent 混沌映射和logistic混沌映射，而且Tent 混沌映射比 logistic混沌映射具有更好的均匀遍历特性[15]。本文将Tent混沌序列和二次反向学习相结合应用于WOA保证种群的多样性与优质性。具体公式如下：

Tent 混沌映射:

(20)

式中，参数p和混沌序列zk都在区间(0，1)之间。

初始种群:

(21)

式中ai表示鲸鱼个体的上界；bi表示鲸鱼个体的下界。

反向点:

(22)

二次反向点:

(23)

3.3 动态学习策略

WOA在旋转搜寻和包围猎物的过程中都是向最优的区域靠拢，但是当前的最优位置有可能是局部最优，在这种情况下若只有当前最优个体指导鲸鱼种群的移动方向，即每次迭代过程中种群中的鲸鱼个体都向当前局部最优个体靠拢，很容易使算法出现早熟，针对这个问题，本文受到GWO利用三个领头狼共同指导灰狼个体位置移动策略的启发，在WOA中保留历史最优的个体，让当前最优个体和历史最优个体进行信息交流，共同指导当前迭代个体的移动方向，这样以来即使当前最优个体是局部最优，因为还有历史最优个体对鲸鱼移动位置的指导，在极大程度上可以使鲸鱼种群跳出当前局部最优，原公式(12)和公式(17)变为以下公式:

x(t+1)=xbest(t)-A×D+L(t)×(xhistory(t)-x(t))

(24)

x(t+1)=xbest(t)+D×ebl×cos2πl+

L(t)×(xhistory(t)-x(t))

(25)

式中xhistory(t)代表历史最优个体。

L(t)=cos(t×π)/(tmax×2)为从1到0递减的非线性函数，使算法前期历史个体比重较大，增加搜索范围；算法后期历史个体比重较小，加快向最优个体的收敛速度。

3.4 个体淘汰策略

当WOA随即搜寻时，是向随机的位置靠拢，这种方法虽然能在一定程度上保证种群的多样性，但是容易产生偏离最优方向的劣质解，影响收敛速度。针对此问题，本文采用了遗传算法的交叉选择策略，每次迭代后，将种群按适应度排序并平均分为两部分，一部分为相对优质的个体，另一部分为相对劣质的个体，两部分进行两两算术交叉生成一个新的种群，让优质个体和劣质个体进行交叉可以保证种群的多样性；将原种群和新种群进行合并，按照适应度排序，淘汰合并后种群中的劣质个体，让保留下来的优质个体进入下一次迭代，保证种群的优质性。具体算术交叉公式如下：

(26)

(27)

3.5 算法步骤

经过改进后IWOA算法伪代码如算法1所示：

算法1 IWOA算法伪代码

(a)按照式(23)方法初始化种群。

(b)对种群进行编码。

(c)按照式(11)计算种群适应度并进行排序。

(d)保留当前最优个体。

(e)按照式(16)计算a的值。

(f)按照式(13)、(14)计算D、A的值。

(g)如果p<0.5执行步骤(h)，否则按照式(25)进行旋转搜寻。

(h)如果Math.abs(A)>=1按照式(18)进行随即搜寻，否则按照式(24)进行旋转搜寻。

(i)判断个体维度是否遍历完毕，若遍历完执行下一步，否则跳转步骤(g)。

(j)判断种群是否遍历完毕，若遍历完执行下一步，否则跳转步骤(f)。

(k)按照式(26)、(27)进行交叉选择。

(l)如果当前种群最优解>历史最优解则更新全局最优解和历史最优解。

(m)判断是否到达最大迭代次数，若到达输出当前最优值，否则跳转步骤(d)。

4 实验结果分析

本次实验设置的相关参数为：种群数量20；迭代次数400；生产线节点数4；订单数量10/20/30；开始加工时间0(当前时间)；10订单下数据集如表4所示；除此之外还有单位缓冲区成本、每种订单在每个节点加工时间、机器切换时间等生产线数据参数。

通过迭代曲线图1所示，三条曲线分别代表3个算法的迭代过程，在不同订单规模下，以最终收益结果、初始收益值、收敛时间作为评价指标，比起HGWO和WOA，IWOA收益更高即更易跳出局部最优，收敛速度更快，初始种群也更加优质，而且在订单数量增加的情况下IWOA的优势也更加明显。

此次排程的甘特图如图2所示，订单顺序为9-7-5-1-6-0-3；拒绝订单号为2、4、8，总收益为32 484.5元；开始排产时间为0，即当前时刻；每个订单需要经过4个节点进行加工，由图2可以看出(由于空间问题中间5、1、6号订单没有展开)，每个订单都需要经过4个加工节点加工，每个订单的开始加工时间就是其在第一个节点的开始加工时间，完工时间就是其在最后一个节点的完工时间，因最开始开工的9号订单前面没有正在加工的订单，所以在每个节点都是无缝加工；下一个订单开始由于和之前的订单类型不同，在节点上需要等待机器的切换时间，所以并不是无缝加工；从第一个订单在第一个节点加工开始到最后一个订单在最后一个节点加工完成大约需要54个小时。

对IWOA、WOA、HGWO，3个算法分别在10订单、20订单、30订单环境下进行多次排产，结果如表5所示，从表5中可以看出，IWOA在收敛速度和平均收益以及订单的接受情况上都明显优于其他两种算法。将每次实验中实际收益和平均收益的最大差值与平均收益的比值作为最大偏离度，则在10订单的环境下，IWOA的收益最大偏离度为1.6%，HGWO为3.0%，WOA为4.8%；在20订单的环境下，IWOA的收益最大偏离度为3.8%，HGWO为7.0%，WOA为6.6%；在30订单的环境下，IWOA的收益最大偏离度为3.2%，HGWO为3.3%，WOA为6.2%；IWOA的排产结果偏离度最小，数据都集中在平均值左右，证明IWOA算法的稳定性也优于其他两种算法。

图1 三组订单迭代曲线图Fig.1 Three sets of order iterative graphs

图2 排产甘特图Fig.2 Scheduling Gantt Chart

表5 排产结果统计表

5 结论

本文建立了以最大收益为目标的订单接受与调度一体化模型，在传统模型的基础上考虑了订单的拒绝成本，使模型更加贴合企业的实际利润，并提出了改进的鲸鱼优化算法(IWOA)求解模型，通过实验结果表明，在多组订单环境下IWOA对模型的求解结果、结果的稳定性以及算法本身的收敛速度、初始解的优质程度都优于鲸鱼优化算法(WOA)和改进的灰狼优化算法(HGWO)。