1 引言

调度问题是组合优化领域中一类重要的问题, 在生产管理、通信等方面有着重要作用. 批调度问题是其中的一个重要的分支, 而且与经典调度问题不同的是: 一台机器可以同时处理多个工件; 批的加工时间等于批中工件的最大完成时间; 批的完成时间等于批的开始时间加上批的最大加工时间; 批的完成时间等于批中工件的最大完成时间. 批调度问题考虑了工件的尺寸和机器的容量, 这在实际的活动中经常需要考虑到, 例如半导体芯片的预烧、电路测试、港口货物装卸、金属加工等等. 这些问题中, 工件的尺寸是有差异的, 及其加工需要分批进行, 批的尺寸不能超过机器的容量. 这类问题是经典调度问题在空间上的拓展, 也是生产调度领域中一个新的研究方向.

1.1 问题的描述

针对此类问题, 首先作如下假设^[1]:

(1) 有n个待加工的工件{1, 2,…, n}, 工件的加工时间为p_j, 工件的尺寸为s_j;

(2) 机器的容量为B, 批中工件的总尺寸都小于B, 假设没有工件尺寸大于B的工件;

(3) 假设批一旦开始加工, 在批加工完成之前, 不可以被打断或者添加新的工件, 批k的加工时间为T_k, 等于批中最大加工时间的工件;

(4) 目标是最大加工时间C_max最小, 其中最大加工时间等于批中最后一个离开机器的工件完成时间, NSBM问题的制造跨度为所有批的加工时间总和.

该问题采用三参数表示法可以描述为 $1\left| {B,s_j} \right|{C_{\max }}$ , 数学模型如下:

$Min \;\;{C_{\max }} = \sum\limits_{i = 1}^k {{T_k}} $

(1)

${ \rm s.t.}\;\;\sum\limits_{i = 1}^k {{x_{ij}}} = 1\;\;\;\;i = 1,2,...,n$

(2)

$\sum\limits_{i = 1}^n {{s_i}{x_{ij}} \le B\;\;\;\;} j = 1,2,...,k$

(3)

${p_i}{x_{ij}} \le {T_j}\;\;\;\;i = 1,2...n, \;\; j = 1,2,...,k$

(4)

$0 \le {T_j}$

(5)

${x_{ij}} \in \{ 0,1\} \;\;\;\;i = 1,2,...,n, \;\; j = 1,2,...,k$

(6)

$\sum\limits_{i = 1}^n {\frac{{{s_i}}}{B}} \le k \le n\;\;\;k \in {Z^*}$

(7)

其中, k是分批的批数, x_ij是0–1变量, 式(1)表示优化的目标是制造跨度; 式(2)限定每个工件只能分到一个批次中; 式(3)表示机器容量约束; 式(4)表示批加工时间; 式(5)、式(6)和式(7)是基本约束.

Uzsoy首先提出了该类问题的单机器模型, 即工件尺寸不同的单机批调度问题(single batch-processing machine with non-identical job sizes, NSBM), 证明了当所有工件加工时间相同时, 问题 $1\left| {B,s_j} \right|{C_{\max }}$ 等价于容量为B物品尺寸为s_i的装箱问题. 由于装箱问题是强NP难的, 所以 $1\left| {B,s_j} \right|{C_{\max }}$ 问题也是强NP难的^[2].

针对问题 $1\left| {B,s_j} \right|{C_{\max }}$ , Uzsoy根据装箱问题的first-fit的启发式规则提出了几个启发式算法, 其中 FFLPT 性能最好; Dupont 给出了另外两种启发式算法 BFLPT 和 SKP( successive knapsack problem); Dupont 和 Flipo 提出了问题的分支定界法; Melouk和Damodaran分别利用模拟退火算法(SA)^[3]和遗传算法(GA)^[4]求解了此问题, 但是并没有和性能较好的启发式算法相比较.

2 蚁群算法和鱼群算法

由于在构建差异工件(即工件有尺寸差异)单机批调度问题的解时, 批的加工时间是不确定的, 从而不能类似于经典调度问题的蚁群算法, 把批加工时间的倒数作为蚁群算法中的启发式信息. 针对这一问题, 我们引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息, 提出了JACO (ant colony optimization based a job sequence)和BACO (ant colony optimization based a batch sequence) 两种蚁群优化算法^[5].

2.1 启发式信息

在一组给定的批次下, 当批的总剩余空间越小, 方案越佳. 此外, 批的加工时间等于批中加工时间的最大值, 如果在加工完之前, 有的工件已经加工完毕却没有办法交付使用, 那么这段浪费掉的时间我们称之为冗余时间. 很显然, 对于白白浪费掉的时间, 冗余时间越小的方案往往是最优的方案.

批的利用率为批的加工尺寸所占机器容量的比例, 公式为:

${\rm{U}}{{\rm{R}}_k} = \sum\limits_{i \in {B_k}} {{s_i}} $

批的负载率为批中加工时间的变异系数与1的差值, 公式为:

$B{R_k} = 1 - \frac{{{\sigma _k}}}{{{\omega _k}}} = 1 - \frac{{\sqrt {\frac{1}{{|{B_k}|}}\sum\limits_{i \in {B_k}} {{{({p_i} - {\omega _k})}^2}} } }}{{{\omega _k}}}$

W_k为加工时间的平均值, σ_k表示批加工时间的方差, 批的负载率越大, 表示批中加工时间分布越均匀, 加工方案越好^[6].

2.2 算法的描述 2.2.1 JACO蚁群算法

在本文中, 我们采用JACO蚁群算法算法, 直接考虑工件序列, 以方便算法的比较. 具体描述如下^[7]:

(1) 信息素的定义: τ_ij表示工件j排列在工件i之后的信息素浓度, 分批的规则采用BF (Best Fit)规则.

(2) 启发式信息: 利用BF规则进行分批, 实际上就是利用批利用率最大这个启发式信息, 在生成工件序列后, 利用BF规则进行分批, 工件中间隔较小的工件被分在同一批中概率较大. 为方便计算, 定义工件j排列在工件i之后的启发式信息为:

${\eta _{ij}} = \frac{1}{{1 + |{p_i} - {p_j}|}}$

(3) 状态转移概率公式记为allowed_a={j|工件j未被a访问到}, 蚂蚁a当前位置工件i, 那么它的状态转移选择下一个工件概率为^[8]:

$p_{i,j}^a = \left\{ \begin{array}{l}\frac{{\tau _{i,j}^a\eta _{i,j}^\beta }}{{\sum\limits_{ \notin allowe{d_a}} {\tau _{i,j}^a\eta _{i,j}^\beta } }}\;\;\;\;j \in allwoe{d_a}\\0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;j \notin allwoe{d_a}{\rm{ }}\end{array} \right.$

(8)

(4) 信息素的更新:

$\begin{array}{l}{\tau _{i,j}}(t + 1) = (1 - \rho ){\tau _{i,j}}(t) + \Delta {\tau _{i,j}},\\\Delta {\tau _{i,j}} = \sum\limits_1^m {\Delta \tau _{_{i,j}}^a} \end{array}$

(9)

2.2.2 鱼群算法

人工鱼个体的状态可定义为向量 $X = \left( {{x_1},{x_2}, \ldots ,{x_n}} \right)$ , 其中 ${x_i}\left( {i = 1, \ldots ,n} \right)$ 为寻优的变量;人工鱼当前所在的位置的食物浓度定义为Y=f(x), 其中Y是目标函数值; 人工鱼的个体之间的距离定义为 ${d_{i,j}} = \left| {\left| {{X_i} - {X_j}} \right|} \right|$ ; 人工鱼的视野定义为Viusal, 表示人工鱼可以感知的范围;人工鱼的移动步长定义为Step, 表示人工鱼在视野范围内, 找到一个更优点, 每向该方向移动一次单位距离, Step增加1; 拥挤度因子定义为δ, 表示在一定范围内的能够容纳人工鱼数量的限制, 防止食物充足的地方聚集过多的人工鱼^[9,10].

(1) 觅食行为(prey)

觅食行为的行为选择为:

$\left\{ {\begin{aligned}& {{X_i} \to {X_j} \;\; {Y_i} < {Y_j},{d_{i,j}} < visual}\\& {{X_i} \to random\;\;\;\;\;{\rm else}}\end{aligned}} \right.$

(2) 聚群行为(swarm)

聚群行为的行为选择为:

$\left\{ {\begin{aligned}&{{X_i} \to {X_c} \;\; {Y_i} < {Y_c},{d_{i,c}} < visual,\frac{{{n_f}}}{N} < \sigma }\\&{{X_i} \to prey\;\;\;\;\;\;\;{\rm else}}\end{aligned}} \right.$

X_c表示领域内伙伴的中心位置.

(3) 追尾行为(follow)

追尾行为的行为选择:

$\left\{ {\begin{aligned}&{{X_i} \to {X_j} \;\; {Y_j} = \max \{ {Y_n}\} ,{d_{i,j}} < visual,\frac{{{n_f}}}{N} < \sigma }\\& {{X_i} \to prey\;\;\;\;\;\;\;\;{\rm else}}\end{aligned}} \right.$

3 混合算法 3.1 蚁群算法和鱼群算法的优化机理

蚁群算法和鱼群算法虽然都属于群体优化算法, 但是算法中的个体并没有表现出智能性, 个体的行为简单, 只具有基础的判断能力, 无法智能的遵循相应行为规则, 但是当它们形成一个群体的时候, 整个群体会表现出一定的智能性. 这两种算法的个体规律有一定的相似性, 人工鱼群算法初期, 人工鱼的觅食行为是随机的, 这和蚁群算法是相似的; 人工鱼群算法后期, 人工鱼的聚集是由伙伴中心的最优状态决定的, 这与蚁群算法中信息素浓度和启发式信息大小有着相同的作用. 而人工鱼的数量越多, 就越容易寻找局部最优值, 这将有更多的人工鱼游到该位置, 这相当于蚁群算法信息素浓度增加, 类似于蚂蚁群算法中信息素正反馈的过程.

和蚁群算法不同的是, 人工鱼前进的方向是由当前状态最优的情况决定的, 并且在某些条件下会受到拥挤度的限制. 如果该地区人工与数量过多, 超过拥挤度的约束, 即使该地区有很高的价值, 人工鱼也不会聚集. 而在蚁群算法中, 信息素关联着蚁群个体之间的联系, 并且和启发式信息一起共同指导个体行为, 最终所有的蚂蚁都会聚集到同一条最佳路径上来^[11].

两种算法搜索的方式不同, 从而个体的运动方式也各不相同, 这种差异也是由个体运动的目的不同造成的. 启发式信息在两种算法的优化中起到了作用, 因为个体的目的都是尽快寻找食物. 但是拥挤程度并完全不适用于蚁群算法, 因为蚁群寻找到食物后会搬回巢穴, 而鱼群在寻找到食物后会直接吃掉, 并不会存储, 而过多的人工鱼会导致其它人工鱼到这里之前, 食物已经被吃光, 所以拥挤度对算法的全局性起着关键的作用. 蚂蚁在寻找到食物并且搬回的过程中, 如果发现了更高效的路径, 则会转移到其他路径上去, 在选择最短路径上, 蚂蚁的数量并不受到拥挤度的限制, 选择的蚂蚁越多, 对结果越好, 但是如果这条路径并非最优选择, 算法可能会被局限在局部最优解中.

因此, 两种算法之间的核心区别是拥挤程度在优化过程中起着指导作用. 换句话说, 鱼群算法类似于于在蚁群算法中引入拥挤度的概念, 并且算法优化过程中的拥挤程度总是有着重要作用. 拥挤程度的引入可以避免蚁群算法早期, 蚂蚁过早地聚集到信息素高的路径上来, 避免算法的早熟, 提高算法的全局优化能力. 算法后期, 拥挤度的作用便会从正作用慢慢转向副作用, 对算法的收敛速度产生影响. 换句话说, 在早期优化中的拥挤程度可以提高算法的优越性能, 但是在后期优化中对性能会有一定的负面影响. 如何正确使用拥挤度这个因素, 是保证算法高效, 准确的关键^[12].

3.2 先鱼群再蚁群的混合算法

为了保证较优的可行解, 产生初始信息素分布, 防止解过早集中到信息素较高的路径上来, 首先使用鱼群算法保证求解的宽度, 并设置更新迭代率, 当算法的更新率少于设定值时, 转入蚁群算法; 转入蚁群算法后, 更新信息素, 迭代寻找较优解, 当结果不再变化时, 再次转入鱼群算法, 并且调整更新率^[13]. 算法步骤如下:

Step 1. 初始化模型和子空间.

Step 2. 设置AFSA的最大最小迭代次数I_max, I_min, 更新率R_ratio和拥挤度. 生成m条人工鱼, 视野长度V_d, 拥挤度δ和移动步长D_step, 产生初始人工鱼群F(0).

Step 3. 每条人工鱼进行一次迭代, 迭代过程中分别执行觅食, 聚群, 追尾三种行为, 迭代结束后, 将结果与公告板相比较, 更新最优值.

Step 4. 在迭代次数的范围内, 将此次的迭代结果和上一次结果相比较, 计算更新率R. 如果R<R_ratio, 说明优化效果降低, 转入Step 5, 如果R>R_ratio, 说明鱼群算法依然优化效果良好, 转入Step 3.

Step 5. 根据鱼群算法的迭代结果, 生成m只蚂蚁, 初始化信息素τ_{i, j}(0).

${\tau _{i,j}}(0) = \frac{{{M_n}}}{{\sum {{C^{mn}}} }}$

其中, M代表算法中蚂蚁的总数量, n是工件数目, ∑C^mn表示总完工时间.

Step 6. m只蚂蚁随机放入工件上, 根据每条路径上的信息素浓度, 计算状态转移概率 $P_{i,j}^k\left( t \right)$ 并且由位置i转移到位置j, 多次迭代后, 得到最优结果.

Step 7. 判断算法是否达到最大迭代次数后者满足输出条件, 若满足, 输出结果; 若不满足, 以蚁群算法的结果为新的人工鱼群F(1), 并且调整拥挤度阈值和更新率R_ratio, 转入Step 3.

3.3 直接嵌入拥挤度的蚁群算法

将拥挤度直接嵌入蚁群算法的迭代过程中, 在蚂蚁选择每条路径时, 首先判断路径上的拥挤度, 如果拥度小于阈值, 则继续选择该路径, 如果拥挤度大于阈值, 则随机选择可行的其它路径. 蚁群算法路径上的拥挤度为:

${q_{i,j}} = \frac{{2{\tau _{i,j}}(t)}}{{\sum\limits_{i \ne j} {{\tau _{i,j}}(t)} }}$

(10)

算法步骤如下:

Step 1. 初始化时刻t、信息素、拥挤度阈值δ_t和迭代次数限制I_r.

Step 2. m只蚂蚁随机放入工件上, 每只蚂蚁根据信息素选择路径, 状态转移概率 $P_{i,j}^k\left( t \right)$ 表示t时刻蚂蚁由位置i转移到位置j的概率, 如公式(8).

Step 3. 每当蚂蚁选择一条路径, 通过公式(10)计算路径的拥挤度 ${q_{i,j}}$ , 如果 ${q_{i,j}} > {\delta _t}$ , 表示路径过于拥挤, 蚂蚁从可行领域内随机选择其它路径; 如果 ${q_{i,j}} < {\delta _t}$ , 表示路径不太拥挤, 蚂蚁从i转移到j.

Step 4. 利用BF分批规则对工件序列分批, 计算目标函数值; 更新信息素τ_ij, 如公式(9), 和拥挤度阈值δ_t:

$\delta (t) = 1 - {e^{ - ct}}$

(11)

其中, c为阈值变化系数.

Step 5. 重复Step 2、3和4, 直到所有蚂蚁都选择一条路径或者达到最大迭代次数.

两种算法的流程图如图1所示.

4 仿真实验与分析 4.1 实验设计

为了验证本文提出的算法有效性, 本文的实验需要兼顾三个方面要素: 工件尺寸的变化, 工件数的变化, 工件加工时间的变化. 如表1所示, 工件尺寸的大小和加工时间我们采用离散型随机分布的方式, 随机决定工件尺寸的大小; 工件数量方面, 我们通过数量递增的对比结果来对比算法的有效性; 算法的有效性我们考虑算法的加工时间和批利用率、负载率的均值.

各个参数的设置为: 蚂蚁数量m为20、Q=100、τ_{i, j}=1/n、ρ=0.5、α=1、β=1.

4.2 实验结果与分析

加工时间和工件数都是离散的, 为了保证实验的有效性, 我们根据工件的数量分为三类, 分别对结果加以对比, 分别如表2和表3所示.

在表2, 表3中可以看出, 在算法寻优的过程中, 蚁群算法的性能要优于鱼群算法, 但是蚁群算法本身的早熟性, 导致寻优结果局部最优, 但是将蚁群算法和鱼群算法相结合, 利用鱼群算法中拥挤度因子, 并与蚁群算法相结合, 可以有效地避免早熟, 并且对于寻找最优解, 减少寻优时间有着一定的帮助. 通过混合算法3.1和3.2的比较, 混合算法3.2对于工件数量较小, 迭代次数较少的问题有较高效率. 而混合算法3.1对于工件数量较多, 迭代次数较多的算法有较高的性能.

5 总结

本文针对差异工件批调度问题, 并考虑到蚁群算法的早熟性问题, 将鱼群算法与之相结合, 利用鱼群算法中鱼群防止过度聚集, 拥挤度限制的方法, 避开蚁群算法在寻优前期早熟死循环. 对于算法结果, 本文通过负载率和利用率均值的相比较来判断算法结果的优劣, 迭代次数的比较来对比算法效率. 通过对比的结果发现, 混合算法前期可以有效避免早熟, 而且在算法后期又可以加快收敛, 从而使寻优个体能够加快寻找到满意解.

但是对于混合算法中, 混合算法3.1的更新率、拥挤的阈值, 以及混合算法3.2中迭代次数限制, 都需要人为确定, 但是针对不同情况下, 不同的值对结果有着不同的影响, 那么工件数量、工件尺寸的分布、工件的加工时间和机器的尺寸和这些值的关系还需要进一步的探究.