基于改进离散人工蜂群算法的同类机调度优化

张架鹏，倪志伟*，倪丽萍，朱旭辉，伍章俊

（1. 合肥工业大学管理学院，合肥230009； 2. 过程优化与智能决策教育部重点实验室（合肥工业大学），合肥230009）

（*通信作者电子邮箱:zhwnelson@163.com）

0 引言

调度问题是一类重要的组合优化问题，根据现实生产的需要，通常包含具体的约束条件［1］。同类机调度问题是调度问题的一个分支，已被证明是NP-hard问题［2］。同类机一般描述为机器具有恒定的速度差异，这类机器产生的原因主要是机器的购置批次差异导致不同批次的机器具有不同的处理速度、完成同类工作的操作人员的操作水平差异等，其主要存在于生产制造车间。除此之外，钢材在多台机器上的热轧过程等也可以抽象成同类机问题。同类机调度问题是一类特殊的车间调度问题，是连接供应链上下游重要的一环，在实际的生产调度中，运用先进的调度算法，制定科学合理的调度方案，可以有效地提高生产效率、节约资源，从而提升整个供应链的效益。目前，没有统一的方法解决同类机调度问题，因此，对此类问题的研究具有重要的实际意义。

目前，启发式搜索算法是解决调度问题的一类重要可行方法，针对同类机调度问题，文献［3］针对含作业到达时间的同类机调度问题，提出了一种改进的启发式算法；文献［4］采用改进的萤火虫算法求解该问题，引入一种切实有效的针对同类机问题的离散编码方式；文献［5］提出一种采用最大调度时间（Largest Processing Time，LPT）算法进行初始化，利用互换性质进行互换操作的启发式算法求解该问题；文献［6］设计了一种启发式分治（Decompose-Compose，DC）算法，用于解决目标解为最小完成时间和的同类机调度问题。上述方法在求解同类机调度问题时存在如下缺陷:改进的启发式算法的性能有待提高，无法适应作业长度差异较大且机器速度差异较小的情形；萤火虫算法参数设置较多，迭代初期易陷入局部最优；DC算法的运行速度慢，通用性不强。

人工蜂群（Artificial Bee Colony，ABC）算法是一种较新的群智能优化算法，由土耳其学者Karaboga［7］于2005年提出，以其实现简单、收敛速度快、求解精度高、鲁棒性强［8］等特点受到学术界的广泛关注，以后又有人提出了一系列改进优化策略［9］。目前，人工蜂群算法已成功应用于人工神经网络训练［10-11］、函数优化［12］、机器人路径规划［13］、电力系统优化［14］等领域，其中大多数的研究解决的是连续型问题。对于现实生活中存在的很多离散问题的研究相对较少，由于人工蜂群算法的参数少、操作简单，近年来很多学者开始将离散化的人工蜂群算法应用到工业生产［15］、数据挖掘［16］等多个领域。

目前，对于离散人工蜂群算法的研究主要集中在解决调度问题上［17］。文献［18］运用离散人工蜂群算法进行云任务调度优化；文献［19］将离散人工蜂群算法应用到炼钢连铸的工业过程中；文献［20］利用离散ABC 算法求解旅行商问题（Travelling Salesman Problem，TSP）；文献［21］提出了一种求解混合流水线问题的离散人工蜂群算法；文献［22］针对最小化完工时间为目标的混合流水车间调度（Hybrid Flow Shop，HFS）问题，提出一种有效的离散人工蜂群算法，该算法利用混合表示以及前向解码和后向解码方法的组合来解决该问题；文献［23］利用改进的人工蜂群算法求解任务指派问题；文献［24］和文献［25］分别提出一种求解阻塞型流水车间调度的离散人工蜂群算法；文献［26］提出一种改进的离散人工蜂群算法求解批量流水线调度问题；文献［27］提出一种用于优化逆向物流网络的混合人工蜂群算法，算法给出8 种性能良好的邻域结构，从而提高算法的开发能力；文献［28］提出了一种改进的离散人工蜂群算法来解决具有铁水系统动态跳跃特征的混合柔性流水车间调度问题。

以上方法运用在不同的调度问题上，其算法性能均有一定提升，但是在协调算法的求解精度、收敛速度和稳定性方面性能较差。因此，本文提出了一种改进的离散型人工蜂群（Improved Discrete Artificial Bee Colony，IDABC）算法，并应用于同类机调度问题。引入基于离散人工蜂群算法的同类机调度问题的十进制编码模型，在原始人工蜂群算法的基础上改进初始化策略，并针对实际问题，提出待优参数的生成策略，借鉴差分进化算法、模拟退火算法的思想改进雇佣蜂和跟随蜂的局部搜索策略，充分利用最优解的优质信息改进侦察蜂。通过15个算例，将本文改进的ABC 算法与文献［21］提出的混合离散人工蜂群（Hybrid Discrete Artificial Bee Colony，HDABC）算法、文献［4］提出的解决该类同类机调度问题的改进萤火虫（Improved Glowworm Swarm Optimization，IGSO）算法、原始ABC算法以及遗传算法（Genetic Algorithm，GA）和粒子群优化（Particle Swarm Optimization，PSO）算法等经典智能优化算法进行了比较。

1 同类机调度问题的数学模型

1.1 模型假设

1）有若干台机器同时加工若干件作业，且每件作业只能被其中一台机器加工。

2）每台机器的加工速度是任意的，同一台机器的加工速度恒定。

3）每件作业的长度是任意的。

4）作业到达机器的时间是任意的，且只有机器接收到作业后，才能进行加工。

5）机器在运行过程中不会出现故障，即作业的加工不会被中断。

在实际的生产加工场景中，生产环境较为复杂，规模也较大，一般调度问题难以在多项式时间内进行求解。调度问题可以用甘特图描述，如图1 所示，图1 表示4 台机器加工10 件作业一种情况的甘特图。

图1 4机器10作业加工示意图Fig.1 Processing schematic diagram of 4 machines 10 jobs

1.2 问题描述

同类机调度问题的描述如下:假设有n个作业J={J1，J2，…，Jj，…，Jn}，其中作业Jj(j= 1，2，…，n)的长度为pj。这n个作业需要用m台机器M={M1，M2，…，Mn}进行加工，其中机器Mi(i= 1，2，…，m)加工这n个作业的速度为vi(i=1，2，…，m)。 作 业Ji到 达 机 器Mi的 时 间 为rij(i=1，2，，…，m，j= 1，2，…，n)，每件作业的加工起点为机器接收到该作业。作业Ji在机器Mi的时间为pij(i= 1，2，…，m，j=1，2，…，n)，该作业的完工时间为Cj(j= 1，2，…，n)，且每件作业只能被其中一台机器加工。本文研究的是Qm|rj|Cmax类型的同类机调度问题，考虑到机器的加工效率，其目标函数minZ为最小化所有作业的最大完工时间，即使得最后完工的那台机器的加工时间最小，缩短产品的交付时间。

1.3 数学模型及约束条件

数学模型:

约束条件:

式（1）若由第i台机器加工第j件作业，则aij=1；否则aij=0。

式（2）表示每件作业只能被其中一台机器加工。

式（3）表示机器i加工作业j所用的时间。

式（4）表示作业j的完工时间。

2 改进离散型人工蜂群算法

在ABC 算法中，雇佣蜂和跟随蜂负责邻域搜索寻优，代表算法的开发能力；侦查蜂负责对被遗弃的食物源进行随机初始化，代表算法的探索能力。为提高算法的性能，本文引入了种群初始化方法和搜索机制，既保证算法具有较高的收敛速度和求解精度，又防止算法陷入局部最优。

2.1 基本人工蜂群算法

人工蜂群算法，是受自然界蜜蜂觅食行为的启发而提出的一种群智能优化算法。将蜜蜂采蜜的过程转化为优化问题的寻优过程。蜜蜂群体分为3 类:雇佣蜂、跟随蜂和侦察蜂，雇佣蜂和跟随蜂负责邻域寻优，侦查蜂负责随机初始化被遗弃食物源。

人工蜂群算法需要初始化设置的参数有3 个:蜂群规模2SN，其中雇佣蜂和跟随蜂的规模各为SN；算法的最大迭代次数MaxCycle；食物源经多次迭代而未发生改变的最大保留次数limit。

ABC算法的主要步骤如下:

1）初始化解。根据式（5）随机生成SN个D维初始可行解{X1，X2，…，XSN}。其中，i∈{1，2，…，SN}，j∈{1，2，…，D}，D代表食物源的属性数，uj、lj代表xij取值的最大、最小值，rand［0，1］产生0～1的随机数。式（5）如下:

2）记录最优解。计算SN个可行解的适应度值fiti，根据适应度值确定并记录最优解。

循环开始:

3）雇佣蜂阶段。雇佣蜂根据式（6）对可行解Xi进行邻域搜索，随机选择Xi的一维xij转化为vij，产生新的可行解Vi，计算新可行解的目标函数值和适应度值并比较Xi和Vi的适应度值的大小:若fit(Vi)＞fit(Xi)，则用Vi替换Xi；否则，保持Xi的位置不变。式（6）如下:

5）计算SN个可行解的适应度值fiti，根据适应度值确定并记录最优解。

6）侦察蜂阶段。记录食物源Xi的开采次数trial，若trial＞limit，则放弃该食物源，利用式（5）随机生成新的食物源Xi，加入雇佣蜂和跟随蜂的搜索队列。该过程主要是避免解陷入局部最优。

7）循环。判断循环终止条件是否成立，若成立，结束循环，算法结束；否则跳转到步骤2），进入下一次循环。

2.2 问题的编码设计

同类机调度问题是一类组合优化问题，需要将实数转化为整数，即将人工蜂群算法进行离散化处理。假设在该同类机调度问题中包含U台机器和D件作业，雇佣蜂和侦察蜂的种群规模均为SN，目标函数为最小化最大完工时间。对于该问题，需考虑作业的到达时间，每台机器上的作业按照先到达先加工的原则进行加工即可。

根据该类同类机调度问题的特点，本文给出一种离散化的编码策略。该问题解的具体编码设计如下列矩阵所示，Z是一个SN×D的十进制矩阵，Z={X1，X2，…，XSN}表示SN个加工方案，对应初始的SN个食物源。每一个加工方案用Z的一个行向量Xi=(xi1，xi2，…，xiD)表示，xij的值表示第j件作业对应的加工机器，其中i={1，2，…，SN}，j={1，2，…，D}，xij={1，2，…，U}。食物源的属性与作业对应，属性值与作业的加工机器对应，如编码（2，1，3，2，1，2）表示，作业2、5 在第一台机器上加工，作业1、4、6 在第二台机器上加工，作业3 在第三台机器上加工。

2.3 初始化策略

群智能优化算法的初始化，对解的质量和算法的收敛速度具有直接影响。在ABC 算法中，考虑使初始解均匀分布在可行解空间上（可行域内），可以加强解的质量和算法的全局收敛性。在ABC 算法的初始化过程中，一般采用随机方法初始化蜂群，对于离散人工蜂群算法，食物源各参数的可行域是有限个整数集合，因此，在算法的初始化阶段，需要保证食物源各参数在可行域上均匀取值。

本文给出了一种初始化策略，采用实数向上取整的方式，实现浮点数到整数间的转换。将初始化方程（5）更新为:

其中:ceil()是向上取整函数，经此方法处理，初始化xij的取值范围是[1，2，…，uj]，理论上该uj个整数的取值概率相同，均为1/uj。这里需要说明的是，在该类同类机调度问题中，食物源参数的取值下限lj= 1，与最小的机器编号相对应，所以式（9）不考虑lj的取值情况。

通过这种初始化方法，既实现了离散化，又保证了食物源的各参数在可行域内具有相同的取值概率，提高了算法的性能。算法中的雇佣蜂、跟随蜂、侦察蜂阶段均采用ceil()函数实现离散化。

2.4 局部搜索策略

2.4.1 待优参数的生成策略

在原始的人工蜂群算法中，雇佣蜂和跟随蜂根据式（6）开发更优的食物源，其中参数j表示食物源中待优化的属性，在值域内随机生成。本文根据同类机调度问题的编码方式，以平衡机器的负载为目标，在雇佣蜂阶段，针对待优参数j提出新的生成策略，提升算法的收敛速度。具体步骤如下:

步骤1 寻找目标食物源中出现次数最多的属性值，即加工作业最多的机器，若满足条件的属性值有多个，选择值最小的属性值记为MostValue。

步骤2 记录该属性值的出现次数n以及在食物源中的位置locations。

步骤3 在locations中随机选取一个作为待优化参数j。

其 中，mostValue={1，2，…，uj}，locations为1×n的 行向量。

2.4.2 基于差分算法的局部搜索策略

差分进化（Differential Evolution，DE）算法是一种基于群体差异的启发式并行搜索方法，其本质上是一种函数优化算法。DE算法具有良好的寻优能力，已成功应用于很多优化问题中。DE 算法的思想上其他进化算法类似，其核心是变异、交叉和选择操作，不同在于，DE 算法通过种群中多个个体的差分信息实现进化。DE 算法有多种变异策略，其中DE/rand/1 策略用来维持种群的多样性，避免陷入局部最优，DE/best/1策略可以加快算法的收敛速度，二者的公式如下:

其中:i={1，2，…，SN}，p1、p2、p3是{1，2，…，SN}中随机选取的不与i相等的参数，xbest为当前全局最优解，F∈[0.5，1]。

受差分进化算法的变异策略的启发，结合人工蜂群算法的特点，本文提出了新的局部搜索策略。通过对差分进化算法的DE/rand/1变异策略和DE/best/1变异策略的变动，将雇佣蜂和侦查蜂的局部搜索式（6）更新为以下3 种，并用ceil()函数进行离散化处理。

其中:i={1，2，…，SN}，k是{1，2，…，SN}中随机选取的参数，且k≠i，J={1，2，…，D}，由上文的生成策略生成。best 表示当前全局最优解，即最佳食物源，φij∈[0，1]，随机取值。

2.5 雇佣蜂阶段

雇佣蜂的任务是在初始的食物源的邻域内搜索更优的解，该过程需要综合考虑种群的多样性和收敛速度。本文借鉴差分进化算法的进化策略，进化初期在较大范围内搜索最优解，保持种群的多样性，进化后期，种群以收敛到较小的范围内，缩小搜索范围以增加搜索精度。本文以可行解的平均适应度值为标准，区分食物源的优劣，并针对较优和较劣的食物源分别给出不同的搜索策略，雇佣蜂搜索过程如下:

步骤1 为当前解集中每个可行解对应的食物源分配一只雇佣蜂。

步骤3 计算指定解Xi的适应度值fit(Xi)。

步骤6 计算新解适应度值fit(Vi)并与原解适应度值fit(Xi)比较:若fit(Vi)＞fit(Xi)则更新食物源；否则保留原食物源。

2.6 跟随蜂阶段

雇佣蜂寻优过程结束，跟随蜂开始工作，在原始的人工蜂群算法中，跟随蜂采用轮盘赌的方式选择目标食物源，并进行进一步搜索，从而加快算法的收敛速度。在跟随蜂寻优的过程中，为了防止陷入局部最优，本文通过借鉴模拟退火算法中“以一定的概率接受较差解”的思想，给出了一种新的食物源更新策略，从而更新了跟随蜂的搜索过程。定义如下概率因子:

在模拟退火算法中，接受较差解的概率会随着时间的推移温度的降低而不断减少。在本文中，将接受较差解的概率与解的质量相关联，如果较差解与原解的适应度值差距越小，则接受该较差解的概率越大；反之概率越小，概率因子pi的取值范围是(0，e-1)。

跟随蜂搜索策略如下:

步骤1 跟随蜂以轮盘赌的方式随机选择食物源Xi。

步骤2 选择式（14）进行局部搜索，得到新食物源Vi。

步 骤3 计 算Xi、Vi的 适 应 度 值fit(Vi)、fit(Xi)，如 果fit(Vi)＞fit(Xi)，更新食物源；否则执行步骤4。

步骤4 根据式（15）计算跟随蜂选择较差解Vi的概率pi，如果pi＞rand，更新食物源；否则保留原食物源进入下一次迭代。

2.7 侦查蜂阶段

在原始人工蜂群算法中，食物源经limit次迭代未更新就会被舍弃，侦查蜂随机初始化生成一个新的食物源，但此食物源的质量一般不高，且理论上拥有更少的迭代更新的次数，因此对全局最优解的贡献有限。为提高侦查蜂初始化食物源Xi的质量，本文充分利用最佳食物源Xs携带优质信息，让Xs的参数从第二位起间隔插入Xi中并取代Xi中原有参数，生成新的食物源Xj。比较食物源Xi与食物源Xj的适应度值，取适应度值较优的作为新的食物源。过程如下:

2.8 改进离散型人工蜂群算法的步骤

步骤1 初始化参数。最大迭代次数MaxCycle和食物源多次迭代未更新的保留次数limit，根据式（9）初始化雇佣蜂种群Xi（i={1，2，…，SN}）。

步骤2 计算种群中各食物源的适应度值fit(Xi)。

步骤3 根据3.4 节给出的待优参数选择策略确定优化参数j（j={1，2，…，D}）。

步骤4 记录当前全局最优解best，赋值cycle= 1，开始

因此，理论上，在求解Qm|rj|Cmax类型的同类机调度问题上，IDABC算法的较原始人工蜂群算法更优。

3 实验及结果分析

3.1 实验环境及参数设置

本文所有程序代码均采用Matlab R2016a 软件编写，使用的PC 配置如下，操作系统:64 位Windows 10，处理器:Intel Core i7-7700 CPU 3.60 GHz 3.60 GHz，内存:8 GB。

本文ABC 算法的参数设置如下，雇佣蜂规模SN= 90，最大迭代次数MaxCycle= 700，食物源经多次迭代未更新的最大保留次数limit= 50。为保证对比的公平性，将对比算法的参数设置如下:原始离散人工蜂群算法参数设置同上；文献［21］改进的离散人工蜂群算法的种群规模和最大迭代次数设置同上；文献［4］改进离散萤火虫算法的最大迭代次数设为700，种群规模设为90，其余参数保持原有的设置不变；遗传算法（GA）种群规模为90，交叉概率为1，变异概率为0.01，迭代次数为700；粒子群优化算法（PSO）的种群规模为90，迭代次数为700，学习因子为1.494 45，惯性权重为0.729。

3.2 结果分析

3.2.1 实验结果分析

针对Qm|rj|Cmax型同类机调度问题，本文设计的算例为JiMj，其中Ji表示作业数量，i={50，80，100，150，200}，Mj表示加工机器数量，j={6，8，10}，如J50M6表示50 件作业在6 台机器上进行加工。每件作业长度取1～100 的随机数，每台机器的运行速度取1～10的随机数，作业按照先到达先加工的顺序在各台机器上加工。

本文考虑了该类同类机调度问题的15 种不同规模的应用场景，给出15 个算例，对于每一种应用场景，用IDABC、HDABC、IGSO、原始人工蜂群（ABC）算法、遗传算法（GA）和粒子群优化（PSO）算法进行求解。为防止偶然性干扰，每组实验运行100 次求平均值，并用平均值（ave）、最优值（min）、最劣值（max）和方差（var）等4个指标衡量各种算法的优劣。

表1 给出了算法IDABC、HDABC、IGSO、ABC、GA 和PSO分别求解上述15 个算例的结果，图2（a）～（d）为IDABC 与ABC、HDABC、IGSO 等算法针对不同算例的求解曲线，其中，每个算法的迭代次数均取为700。4 个子图选取的算例分别为J50M8、J80M6、J100M10和J200M8，代表了从小到大的不同规模的应用场景。通过比较分析表1结果和图2（a）～（d）可以得出以下结论。

首先，在收敛速度方面，由图2（a）～（d）的4种算例的求解曲线可以看出，IDABC 算法的收敛速度要明显快于其他3 种算法；其次，在求解精度方面，由表1 实验数据可知，对于所有15 个算例的求解结果，IDABC 算法求解的平均值、最优值和最劣值均优于其他5 种算法，与5 种算法中表现最好的HDABC 算法相比，求解精度平均提高了4.1%，且实验规模越大，IDABC 算法的优越性越明显，表明IDABC 算法在求解精度上是6种算法中最好的；最后，在算法的稳定性方面，由表1实验数据可知，除了算例J80M10和J200M6，IDABC 对其求解的方差略差于HDABC 的求解结果外，对其余13 个算例的求解结果，IDABC算法求解的方差均为最优，与HDABC算法相比，稳定性平均提高了26.9%，且对于大规模的问题IDABC 算法也能保证平均误差很小，表明IDABC 算法在求解的稳定性方面总体上优于其他5种算法。综上所述，在以上6种算法解决Qm|rj|Cmax型同类机调度问题中，本文改进的离散人工蜂群算法在算法的求解质量方面和求解的稳定性方面均为最优，且明显优于IGSO、GA 和PSO 算法，在收敛速度方面优于HDABC、IGSO和ABC等算法。

3.2.2 参数分析

群智能算法初始化参数的选取对算法的性能有一定的影响，同一算法在解决不同领域的问题时，其参数的设置存在差异。原始的ABC 算法采用的是针对连续型问题的编码方式，本文利用改进的离散型人工蜂群算法求解Qm|rj|Cmax类型的同类机调度问题，采用的编码方式是离散的，为达到最佳实验效果，需要对ABC 算法的参数进行分析。本文实验讨论的参数有3个:初始食物源数量（雇佣蜂规模）SN、算法最大迭代次数MaxCycle和食物源经多次迭代未更新的最大保留次数

limit。

以下3 组实验分别分析SN、MaxCycle和limit对算法性能的影响，采用的同类机调度问题的算例均J100M10，每组实验算法运行100 次，取平均值作为最终结果，并以目标函数的平均值作为评价函数值评价算法的性能。

图2 四种算例的算法求解曲线Fig.2 Algorithmic solution of curves for four examples

图3（a）显示的是雇佣蜂规模SN对本文算法性能的影响（MaxCycle=1 000，limit=80），如图3（a）所示，算法的评价函数值与雇佣蜂规模整体上呈现负相关，且在一定范围内，算法的评价函数值随雇佣蜂规模的增加而快速减小，当雇佣蜂规模超过一定值后，算法性能逐渐趋于稳定。由图3（a）可知，算法的最佳雇佣蜂规模为90。

图3（b）分析的是最大迭代次数MaxCycle对本文算法性能的影响（SN=90，limit=80），迭代次数对群智能算法的影响巨大，本文取（100，300，500，600，700，800，900，1 000，1 100，1 200）10 组最大迭代次数进行分析。由图3（b）可以看出，在MaxCycle∈[0，700]范围内，评价函数值随最大迭代次数的增加越来越优，当MaxCycle＞700，最大迭代次数的改变对评价函数值的影响相对平缓，即不能较大程度上影响算法性能。因此，针对该类同类机调度问题的人工蜂群算法的最大迭代次数取为700。

图3（c）描述的是食物源经多次迭代未更新的最大保留次数limit对本文算法性能的影响（SN=90，MaxCycle=700），本文limit的值取（10，20，30，40，50，60，70，80，90，100）10 组，通过实验分析其优劣。理论上，如果limit的值太小，则食物源更新的速度过快，无法达到最优解，如果limit的值太大，则会降低种群的多样性，算法易陷入局部最优，因此这两种情况都会降低算法的性能。如图3（c）所示，在limit∈[0，50]范围内，算法的评价函数值随limit值的递增而减小，此时算法性能逐渐提升，当limit= 50 时，算法的性能在实验组中达到最优，当limit＞50时，评价函数值整体上随limit值的递增而增大，算法性能逐渐下降。因此，针对该类同类机调度问题的参数limit的最佳取值为50。

图3 参数SN、MaxCycle和limit对本文算法性能的影响Fig.3 Effect of parameters SN、MaxCycle and limit on performance of the proposed algorithm

4 结语

针对同类机调度领域存在的问题和不足，本文提出了一种改进的离散型人工蜂群（IDABC）算法求解同类机调度问题。首先，引入了同类机调度问题的数学模型；其次，引入了种群初始化策略，获得均匀分布的种群，通过改进雇佣蜂和跟随蜂的局部搜索策略，提高了算法的种群多样性和防止算法陷入局部最优，通过提出带优参数的生成策略和改进侦察蜂的全局搜索过程，提高了算法的收敛速度；最后，分析了本文改进算法的整体性能，并利用15 个算例的仿真对比实验，证明了本文算法具有良好的收敛速度、求解精度以及求解稳定性，可以有效地求解同类机调度问题。

本研究只考虑了最小化最大加工时间一种类型的同类机调度问题，在后续的研究工作中，应考虑更多应用场景，同时，进一步优化人工蜂群算法，提升算法的寻优性能。