基于改进蚁群算法求解双目标流水车间调度问题

罗艳媚

(桂林航天工业学院 管理学院，广西 桂林 541004)

流水车间调度问题(Flow Shop Scheduling Problem，FSP)，已被证明在3台以上机器的调度为NP-hard 问题[1]，具有很强的工程研究背景，其研究具有重要的理论价值和现实意义。求解流水车间调度方法一般有精确方法、构造型方法、人工智能法等。精确法储存量大，适合用于小规模的调度问题。构造型方法通过一定的规则来构造问题的解，这类方法能够快速求得解，但通常质量较差，其中 NEH 是最常用的方法。智能优化算法，如遗传算法、模拟退火算法、粒子群算法、人工蜂群算法、蚁群算法等，成为近年来求解车间调度常用的方法。赵芮等[2]提出一种贪婪引力的搜索算法求解了混合领空闲置换流水车间调度。秦旋等[3]将共生生物搜索算法与局部搜索策略相结合的混合算法来求解置换流水车间调度问题，并通过仿真实验验证了所提算法的优越性。针对多目标的车间调度问题，杜士卿等[4]提出基于直觉模糊集相似度的最佳觅食算法，采用双层编码的方式进行编码，利用直觉模糊集来衡量Pareto解与理想解的相似度，通过案例验证了所提算法的有效性；李文韬等[5]以遗传算法为基础，结合了小声境技术来解决双目标的混合流水车间调度问题。现有的流水车间调度优化问题大多数是最小化的完工时间为目标求解，在实际的生产中，还要考虑库存、耗能和发生意外而导致的工期延误等问题。本文拟建立起以最小化的完工时间和总拖期为目标的流水车间调度问题模型，在ACO算法的基础上，结合HEN算法、参数的自适应调整及按一定的概率引入先验知识等策略来求解建立的调度模型，通过仿真实验验证所提改进算法的有效性，为多目标流水车间调度问题的研究提供一种新的方案。

1 流水车间调度问题

流水车间调度问题可简述为：在m台机器上按一定的顺序加工n个工件，每个工件加工时间确定。此类问题有如下特征：

(1)每个工件ji只能在每台机器上加工一次，i=1,2,…,n；

(2)每台机器Mk同一时间只能加工一个工件，k=1,2,…,m；

(3)每个工件在每台机器上的加工时间一定，即tjik；

(4)每个工件都在m台机器上加工，顺序一样，加工时间不同；

(5)每个工件的总加工时间包含准备时间；

(6)初始时刻所有工件都可以加工；

(7)工件ji在机器k上加工的完成时间c(ji,k)；

(8)工件ji的完工时限dji

在实际的车间生产过程中，管理者不仅是要考虑生产的效率问题，同时还要考虑到发生意外而导致工期延误的问题。因此，本文以完工时间和拖期为目标函数，其数学模型如下：

min{f1,f2}

其中f1为最小化的最大完工时间，即加工完所有工件的所有工序的总时间；f2为最小化的总拖期时间，即交货期。

其数学模型为：

C(j1,1)=tj11

(1)

C(j1,k)=C(j1,k-1)+tj1k

(2)

C(ji,1)=C(ji-1,1)+tji1

(3)

C(ji,k)=max{C(ji-1,k),C(ji,k-1)}+tjik

(4)

其中，i=2,3,…,n;k=2,3,…,m

f1=min{C(max)}

(5)

f2=min{T(max)}

(6)

参照文献[6]得交货期的表达式为：

(7)

Ti=max{0,Cji-dji},i=1,2,…,n

(8)

(9)

其中，σ为误工比例常数。本文选紧σ=1.5，为生产的紧工期。

2 蚁群算法

蚁群算法是意大利学者Dorigo M.等受到自然界蚂蚁觅食行为启发而提出的一种仿生算法。最早用于求解TSP(旅行商问题)，其原理是从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。蚁群算法利用蚁群之间的信息传递，通过正反馈寻求问题的最优解。蚂蚁在觅食的过程中，会在其经过的路径上释放信息素，以路径上的信息素浓度为启发来确定下一节点的转移概率。根据概率来选择下一节点，其数学模型为：

(10)

蚂蚁按照轮盘赌规则选择下一转移节点。当蚂蚁完成一次循环后，保存本轮搜索到的最优结果，然后进行信息素的更新，更新规则如下：

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(11)

(12)

(13)

3 改进蚁群算法求解多目标流水车间调度问题

在传统的蚁群算法中，蚂蚁根据节点间的距离来选择路径，通过遍历各节点，和多次的搜索及信息素的更新，最终找到一条最短路径。将蚁群算法用于求解流水车间调度问题时，需要建立起流水车间调度问题与ACO的对应关系，进而求出所需的目标函数值。

3.1 编码与解码

由于ACO不能直接作用于流水车间调度问题，因此本文采用实数编码的方式来表示调度方案，将工件的顺序及每道工序的加工时间分别转换成ACO的路径节点和路径长度，可得到算法直接作用的参数。当蚂蚁遍历一次，就能够得到工件的一个加工序列。例如：在流水车间里4个工件在3台机器上加工，其调度方案为1，4，3，2，表示先加工1号工件，再加工4号工件，最后加工2号工件，则其编码可表示为{1，4，3，2}。

3.2 种群初始化

为了保证能够得到质量较高的解，在种群初始化中，采用HEN算法[7]求得的结果作为ACO的初始解。HEN是一种有效解决调度问题的启发式算法，将多台机器的流水车间调度问题转化为模拟两台机器的车间调度问题，其优化步骤如下：

(1)计算每个待加工工件的总加工时间；

(2)以不递增的顺序对工件进行排列，得到初始序列；

(3)选择序列中的前两个工件，分别计算这两个工件加工过顺序不同的时间，选取时间小的排序；

(4)将初始序列中的第3个工件插入到步骤(3)得到的序列中，计算所有的可能排序(插入后有3种可能排序)，选时间最短的排序为最佳排序；

(5)重复步骤(4)，直到所有的工件都完成该操作。

通过以上步骤，得到改进算法的初始解。

3.3 参数自适应调整

α和β是ACO的重要参数，其值为固定值，对算法的收敛性及搜索速度有较大的影响。因此，对α和β进行了改进，将其调整为根据迭代次数G的变化而变化的量。α、β与迭代关系如下：

(14)

(15)

式(14)(15)中G1=1/2Gmax。

在搜索前期，以各节点间距为主要因素进行搜索，α取较小值，β取较大值。随着搜索的进行，各路径上的信息素有一定的积累，此时，以信息素为主要的搜索据，α取较大值，β取较小值，保证算法遍历的完整性。

3.4 状态转移策略

在ACO中，蚂蚁以最大概率进行转移，容易陷入局部最优导致算法过早收敛。因此，本文将先验知识选择和概率选择相结合的策略进行状态转移，使得算法在“利用过去的信息”和“探索新路径”间建立较好的平衡。使得概率较大的工件容易被选择，概率不大的工件也有机会被选择。其表达式为：

(16)

其中，q0∈(0,1)，本文取q0=0.5，为利用先验知识的程度。q为(0,1)上服从均匀分布的随机数。

3.5 信息素更新策略

信息素是蚂蚁进行搜索的重要依据，影响算法的收敛速度和可行解的质量。在ACO算法的基础上，本文采用局部和全局信息素更新相结合的策略对信息素进行更新。

蚂蚁搜索时，从节点i转移到j后，更新局部信息素。当所有蚂蚁搜索完后，根据搜索结果对信息素进行更新，即加强较优路径上的信息素，以ρ来挥发较差路径上的信息素。其表达式为：

(17)

(18)

3.6 最大—最小蚂蚁系统

在算法进行信息素的更新后，引用了最大—最小蚂蚁系统来限制信息素浓度，防止信息素过大而导致算法陷入局部最优，或者信息素过小而导致部分可行解无法被搜索。本文将初始信息浓度τ0设置为1，信息素的最大限制值τmax为1.5τ0，最小限制值τmin为0.3τ0；当所有蚂蚁都遍历完后，对信息素进行判断，并将其限制在[τmin,τmax]范围内。

3.7 改进ACO算法的框架流程图

图1 算法流程图

4 实验与结果

4.1 评价指标

为验证所提算法求解多目标流水车间调度问题的可行性，采用以下指标对算法进行评价：

(1)两个极值解间的距离D[8]

D越大表明算法的解散布范围越广。

(2)可行解的数量N

N越大说明算法的寻优能力越强。

4.2 结果分析

本文选用典型的流水调度问题Car类和Rec类来验证所提算法的性能。将基本算法和改进算法各独立运行20次，将得到的所有可行解合并，剔除重复可行解后再进行Pareto排序，得到的可行解集为各算例的最终解集。表1为测试集及实验结果。

表1 问题测试集及实验结果

由表1数据可知，对于可行解的个数，除了Rec07和Rec17外，本文算法求得的解的个数大于或等于基本ACO算法。对于极值D，除了Car05、Rec09及Rec13外，本文算法所求得的结果优于基本ACO算法。

图2 Car01的Pareto解

图3 Car04的Pareto解

图4 Rec01的Pareto解

图5 Rec09的Pareto解

图2～图5为所求测试集中的4个典型算例的Pareto解集,横坐标表示最小化的最大完工时间，纵坐标表示最小化的总拖期时间。在相同条件下，本文算法获得Pareto解的个数大于基本ACO算法，在解的均匀性上也优于基本算法。

综上，在求解多目标流水车间调度问题中，本文所提的改进ACO算法，利用HEN求得较好的初始解，利用参数α和β的自适应调整及在状态转移策略中结合了先验知识，保证算法遍历的完整性，扩大了其搜索空间，找到更多的可行解；信息素更新策略的调整和最大—最小蚂蚁系统的应用，加快算法的收敛速度，同时又限制其因信息素积累过高而陷入局部最优，具有更强的搜索能力。

5 结束语

本文以最小化的最大完工时间和总拖期时间作为调度目标，建立了双目标的流水车间调度问题模型。在基本ACO算法基础上，结合HEN算法，将其求得的值作为所提算法的初始解；在信息素更新中采取局部与全局更新相结合的策略，并引入最大—最小蚂蚁系统，利用Pareto对可行解进行评价。通过典型算例的仿真实验，与基本ACO算法相比，本文所提的改进算法在求解多目标流水车间调度问题具有更好的性能。本文目前只考虑了车间调度问题的完工时间和交货期，在实际的生产调度中，还需要考虑能耗等问题，在后续的研究中可进一步建立更贴近实际调度的模型，为调度问题提供更科学有效的求解方法。