禁忌搜索1.doc

基于禁忌搜索算法的无等待流水车间问题求解

戚海英，邱占芝
（大连交通大学 软件学院，辽宁 大连 116028）

摘要：本文针对最小完工时间的无等待流水调度问题提出了一种禁忌搜索算法。该算法首先利用调度规则构造较好的初始解，然后用禁忌搜索算法改进当前解。在算法中采用了可达性的变邻域结构，使邻域规模小;而且对未被选中的候选解信息进行记忆，合理平衡了集中与分散搜索。仿真结果证明该算法是有效的。
关键词：禁忌搜索；流水车间；变邻域；集中与分散搜索
中图分类号：TP278
Tabu search algorithms based on the no-wait Flow Shop problems
QI Haiying，Qiu Zhanzhi
(Dept. of Software, Dalian Dalian jiaotong University 116028,China)
Abstract: This paper presents a tabu search algorithm for solving the minimum makespan problem of Flow Shop scheduling. In the algorithm , the scheduling rule is used to create the initial solution and then the tabu search algorithm is applied to improve the last solution. The algorithm uses reachability varying neighborhood ,which is small scale ;but also Information of the unvisited candidate solutions is recollected, intensive search and dispersive search is reasonably balanced .Computer simulation experiments on the actual example show that the algorithm is applicable and effective.
Keywords: tabu search ; Flow Shop ；varying neighborhood ；intensive and dispersive search

4

0 引言
无等待流水车间(no-wait Flow Shop)调度问题，也被称为同序作业调度问题，是许多实际流水线生产调度问题的简化模型，但它仍旧是一个非常复杂和困难的组合优化问题，目前对该问题的研究受到越来越多的关注。
当前求解流水车间调度问题大致可分为构造型和改进型算法两大类，构造型算法如调度规则[1]、RA算法[2]和NEH算法[3]等；改进型算法如禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法等。构造型算法计算量较少，但得到的解往往不能令人满意，而改进型算法通过迭代可获得较好的解。
禁忌搜索算法由Glover提出并进一步确切的设计出来[4 5]的一种迭代方法，算法随着调度问题规模的增长，为获得满意解所需的计算量迅速增加，在一定的邻域结构下，缩小搜索邻域使算法计算量减少是常用的方法。如Nowicki等[6]通过分析调度方案内部的Block结构，引入控制因子使搜索邻域大大缩小，但盲目缩小邻域会使得邻域中某些更好的解丢失，从而使得算法寻优性能下降。Grabowski等[7，8]进一步研究Flow Shop问题的Block性质，由此极大拓展了缩小邻域的思路。Van等[9] 研究了邻域的一种构造形式。孙元凯等[10]提出了变邻域结构。
本文在前面研究的基础上针对以总完工时间最小为目标的无等待流水车间调度问题，提出了一种禁忌搜索算法：采用运算较少的调度规则构造尽可能好的初始解，提高算法的收敛速度，采用可达性的变邻域结构，避免陷入局部最优，在邻域搜索中使用概率选择侯选解，平衡了集中与分散搜索。实际数据仿真表明了算法的有效性。
基金项目：辽宁省教育厅计划项目（20060107）
作者简介：戚海英（1973-），女，山东人，硕士，大连交通大学软件学院讲师，主要从事管理信息系统、车间调度等研究。E-mail：qihaiying@。

1 问题描述
无等待流水车间调度问题一般可描述为n个工件要在m台机器上加工，每个工件需经过m道工序，每道工序要求不同机器，n个工件在m台机器上加工顺序相同。满足如下约束：①每个工件在机器上的加工顺序是给定的；②每台机器同时只能加工一个工件；③一个工件不能同时在不同的机器上加工；④工序不能预定；⑤工序的准备时间与顺序无关，且包含在加工时间中；⑥工件在每台机器上的加工顺序相同，且是确定的；⑦工件加工技术上的约束事先给定。
工件i在机器j上的加工时间设为tij(i= 1…n；j=1…m)。问题的目标是求n个工件在每台机器上最优的加工顺序使总完工时间最小。设c(ji,k)为第ji个工件在机器k上的加工完成时间，{ j1 , j2 ,… jn }
表示工件的调度，那么对于n个工件，m台机器上的流水车间调度问题的完工时间可表示为：
c(j1,1)＝tj11；
c(j1,k)= c(j1,k-1)+ tj1k，k=2,…,m；
c(ji,1)= c(ji-1,1)+ tj11，i=2,…,n；
c(ji,k)=max{ c(ji-1,k)，c(ji,k-1)}+ tj1k，i=2,…,n；k=2,…,m；
总完工时间为：
Cmax= c(jn,m)
调度目标就是确定j1 , j2 ,… jn，使得Cmax最小。
2 算法的关键技术
禁忌搜索开始于一个初始可行解S，然后移动到领域N(S)中最好的解S*，即S*对于目标函数C(S)在邻域N(S)中是最优的。然后，从新的开始点重复此法。为了避免死循环，禁忌搜索把最近进行的L个移动放在一个禁忌表T中，在目前的迭代中这些移动是被禁止的，在一定次数的迭代之后它们又被释放出来。禁忌表被循环地修改，最后定义一个停止准则来终止整个算法。由于禁忌表的使用，使其在搜索中有可能跳出局部极小。禁忌搜索是一种局部搜索能力很强的全局迭代寻优算法，但它对初始解依赖性强，较差的初始解会降低算法的收敛速度。
2.1初始解的生成
目前已总结了100多条调度规则[1]。调度规则的最大优点是计算量小，基于调度规则来解决调度问题的方法简单、易行，可避免求解解析模型的复杂性，被现场广泛采用，不同的调度规则或组合会产生性能差异很大的调度方案。
通过文献[11]可知，在基于完工时间的指标下，SPT（最短加工时间）调度规则性能最好。本文采用SPT调度规则产生初始解。
2.2变邻域的构造
由于禁忌搜索算法的效率主要取决于对每个邻域搜索的效率，解的邻域的确定直接影响所找到的解的邻域解集合的大小和是否会减少找到全局最优解的机会以及算法的效率。本文采用基于关键路径的变邻域结构[10]。
定义图的关键路径为u=（u1,…,uω）ui∈O , 1≤i≤ω，将每一条关键路径分割为连续的块B1 ,…,Br，且满足①Bj ={Uaj , Uaj+1 , …,Ubj}, j=1, …, r 且 1=a1≤b1＜b1+1＝a2≤b2＜b2+1＝a3≤…≤ar≤br＝ω；②Bj中的工序在同一台机器上处理, 即 μ(Bj) j=1,…,r；③两连续块的工序在不同机器上处理，即μ(Bj)≠ μ(Bj+1)。
Nowichi等[6]移动V(s)的定义为：任取一条关键路径，仅交换关键块两端的操作，而且对于第一个关键块，仅交换后面的两个操作，对于最后一个关键块，仅交换前面的两个操作。所生成的邻域记做N1，其邻域规模不大于（2m-2）。
Van Laarhoven等[9]移动的定义为：交换所有关键路径上关键块中相邻的两个操作，由此所生成的邻域记做N2，其邻域规模为O（mn）。该移动的优点在于，所生成邻域中的解都是可行解。但是该移动所定义的邻域相当大。
显然 N1是N2的子集，在大规模问题中，N1将比N2小得多。使用N1的算法比使用N2的算法更快地陷入局部极值点，而且N2具有可达性而N1不具有可达性。结合N2和N1，提出一种变结构邻域N，其移动操作定义为：选定初始解S0，从其N1邻域中选择好的元素进行迭代，直到某个S*（N1邻域中无更好的解）；然后求S*的N2邻域，从N2邻域中随机选择一个元素作为新的初始解，重复计算，直到满足停止条件。在计算过程中所定义的邻域结构是变化的。先使用N1进行计算，陷入极值点后采用N2邻域。该邻域既具有N1规模小的优点，同时又保留了N2可达性的优点。
2.3禁忌表
禁忌表的目的是防止震荡现象的发生，禁忌表加入新元素的方法是：T:=T，其中 =(y , x)被称作移动V=(x , y)的反向移动。当V=(x , y)被执行时，=(y , x)就变成被禁止的并加入T中。每一个新的移动v都被加到禁忌表T的最末位置，随着新解的加入，老解将从表的头部删除，从而实现自动解禁。
2.4 邻域搜索策略
对邻域N(S)搜索的目的是要选出下一次迭代的解，该解的选择有不同的标准，在本算法中选取候选解时，对未被选中的候选解信息进行记忆，即计算各侯选解的目标函数值，并根据其目标函数值与目前最优值的比值赋以一个概率，该概率代表作为候选解被选为新的当前解的可能性，越接近最优值则被选中的可能性越大，但小概率的解也有可能被选中。当搜索到规定的迭代次数解无改进时将利用这些信息进行分散搜索直至解无改进，此时改变邻域的结构，从新的邻域中随机选择一个新的迭代起点。
2.5算法流程
该算法的实现是先确定一个初始解S0，从其邻域N1中选择好的元素进行迭代，直到某个S*（N1邻域中无更好的解）；然后求S*的邻域N2，从邻域N2中随机选择一个元素作为新的初始解，重复计算，直到满足停止条件。算法的停止条件是限定总迭代次数，下面给出算法的基本流程。
step1：采用SPT调度规则产生初始解，置禁忌表为空，将初始解进入队列，作为迭代的起点。
Step2：从队列中弹出一个解，以此解为初始解，重新初始化禁忌表等参数；若队列空，更新初始解；否则，继续以下步骤。
Step3：判断搜索终止条件是否满足，终止条件为得到最优解，或达到规定的迭代步数而解仍无改进。若达到最优解，转Step4；若达到了规定的迭代步数，转Step2；否则继续以下步骤。
Step3.1：用上述邻域构造方法产生当前解的邻域解 。
Step3.2：对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态s’替代s成为新的当前解，即s= s’，更新禁忌表，同时用s’替换“best so far”状态，否则，继续以下步骤。
Step3.3：根据邻域搜索策略判断候选解对应的各对象的禁忌属性，根据一定概率选择候选解集中非禁忌对象对应的最佳状态为新的当前解，更新禁忌表。同时，若被选中的解是候选解集中的最优解，且目前不是分散搜索状态，则将次优解信息进入队列，以备将来分散搜索时使用；若被选中的不是当前的最优解，且当前不是分散搜索状态，则将最优解信息进入队列；若当前处于分散搜索状态，则不进行队列操作。转步骤Step3。
Step4：输出优化结果，退出。
3 算法收敛性
若有限空间对由当前解的邻域解集中的非禁忌或满足藐视准则的候选集是连通的，并且禁忌表充分大，则禁忌搜索一定能够达到全局最优解。在文献[9]中已经证明，如果邻域结构满足以下假设，则算法必然收敛并找到最优解：
（1）邻域结构对称，即"x，x′ÎX，x ÎN（x′）Û x′ÎN（x）
（2）图GN强连通，即对任意x，x′ÎX一定存在一条由x到x′的路径。
本文的禁忌搜索算法的邻域结构是对称的，任意两个状态可以在有限步内互达，能够收敛到全局最优解。
4 实际算例仿真及分析
对某车间的生产实际数据进行计算，加工时间矩阵（j表示任务，M表示机器）是：

j1
j2
j3
j4
j5
j6
M1
2
6
7
4
2
6
M2
6
4
2
5
3
3
M3
1
5
2
5
7
3
M4
5
4
4
3
2
3
M5
6
2
3
5
7
3
M6
3
5
6
4
3
2
用Visual Basic6.0语言编程，对具有6个任务，6台机器的无等待流水车间进行算法的验证，在算法中禁忌表长度L＝7，最大迭代次数取200，在计算过程中产生的初始序列的目标函数值即总完工时间为60，然后使用禁忌搜索技术进行改进，算法在合理的时间内达到了最优（最优值是55），最优排序对应的甘特图和算法的收敛曲线如下：

图1 最优排序对应的甘特图
图2 算法收敛曲线

仿真结果表示，该算法很好的解决了流水车间最大完工时间最小的问题，该算法在初始值、邻域结构、搜索策略上具有较高的效率。
5 结论
本文针对禁忌搜索算法的缺陷，使用调度规则构造较好的初始解，用基于概率的方式选择候选解，确保始终在优化解空间中寻解。采用集中搜索与分散搜索相结合的策略，对未被选中的候选解信息进行记忆，保证在规定步数内寻不到最优解时，可以跳出此局部极小值，另寻方向继续搜索，以找到优化解；在算法中使用的邻域结构随算法的进程而改变，不仅邻域规模小，而且仍保持了可达性这一重要的属性。通过实例仿真，本算法在合理的时间内达到最优值，验证了本算法的有效性。

参考文献：
[1] Panwalkar S. A survey of scheduling rules [J]. Operation Research，1977，25(1):45-61
[2] Dannenbring D G. An evaluation of flow shop sequencing heuristics[J]. Management Science，1977，23(11)：1174-1182。
[3] Nawaz M, Enscore E E，Jr HamI. A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J]. Omega，1983，11(1)：91-95。
[4] Glover F，McMilan C，Novick B. Tabu search-partⅠ [J]. ORSA J.Computing，1989，1(3)：190-206.
[5] Glover F，McMilan C，Novick B. Tabu search-partⅡ[J]. ORSA J.Computing，1990，2(1)：4-32.
[6] Nowicki, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Problem[J]. Management Science，1996，42(6)：797-813.
[7] Grabowski J，Pempera J.New block properties for the permutation flow shop problem with application intabusearch[J]。J of the Operational Research Society，2001，52(2)：210-220。
[8] Grabowski J，Wodecki M.A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion[J].Computers and Operations Research，2004，31(11）：1891-1909。
[9] Van Laarhoven P.J.M., E.H.L. Aarts，and J.K. Lenstra. Job shop scheduling by simulated annealing[J].operations Research，1992，40(1)：113-125.
[10] 孙元凯，刘 民，吴 澄. 变邻域结构Tabu搜索算法及其在JobShop调度问题上的应用[J].电子学报，2001，29(5)：622-625.
[11] 吴会江，崔国生.用规则调度方法求解无等待流水车间调度问题[J].科学技术与工程，2005，4(8)：501-503.
[12] 邢文训，谢金星. 现代优化计算方法[M]. 北京：清华大学出版社 1999.
[13] 王凌. 智能优化算法及其应用[M]. 北京：清华大学出版社 2001.