一种基于禁忌搜索技术的作业车间调度算法
收稿日期!"##$%#&%$#基金项目!国家’九七三(重点基础研究规划项目)*++&#$#,##-资助.作者简介!黄志/男/*+0,年生/
博士研究生/主要研究方向为12难度问题)特别是作业车间调度问题-3黄文奇/男/*+0,年生/
教授/博士生导师/主要研究方向为计算复杂性理论及应用/12
难度问题.一种基于禁忌搜索技术的作业车间调度算法
黄
志*/黄文奇*
/"*)华中科技大学计算机系/湖北武汉4$##04-
")
中国科学院
软件所/北京*###&0-
5%6789!:;<7=>+?",$.=@A 3;<7=>:;8+?A B 6.C B 6
摘
要!描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法.该算法基于禁忌搜索技术.算法中利用了新的
禁忌搜索方法.从对一组问题基准实例的实验计算结果看/该算法在合理的计算时间内/对多个实例得到比当前没有用转换瓶颈技术的禁忌搜索中最好的算法之一的D E F G 算法更好的结果.
关键词!作业车间调度312%难3启发式3禁忌搜索中图分类号!D 2
$#*文献标识码!F
文章编号!*###%*""#)"##H -#"%#"""%#4
I J K L M N O P Q R S T U VL WX S Y L LZ U S M [P\L M ]L YZ P L ^Z [P U V _J N W K
‘a F 1b c ;8
*
/‘a F 1b d@=%e 8*/"
*)f g h i j k l g m k n op n l h q k g j r s t g m s g i m uv g s w m n x n y z /{q i |w n m y}m t ~g j !t k zn or s t g m s g i m uv g s w m n x n y z /"q w i m 4$##04/p w t m i -"
)#m !k t k q k g n or n o k $i j g /p w t m g !g %s i u g l zn or s t g m s g !/&g t ’t m y *###&0/p w t m i
-I Y T O M S [O !F =@((@C A 8)@;@<*8+A 8C 79>B *8A ;6(B *+B 9)8=>A ;@68=86<667,@+-7=-*B .9@6B (/B .+;B -+C ;@0<98=>8+-*@+@=A @08=A ;8+-7-@*.D ;@79>B *8A ;68+.7+@0B =A 7.B B +@7*C ;A @C ;=8e <@.F =@10@)@9B -@0A 7.B B +@7*C ;6@A ;B 08+<+@08=A ;@79>B *8A ;6.2B 6%-A 86@/48@90+.@A A @**@+<9A +A ;7=D E F G /1;8C ;8+B =@B (.@+A A 7.B B +@7*C ;79>B *8A ;6B (A ;B +@=B A <+8=>+;8(A 8=>.B A A 9@=@C ,A @C ;=8e <@
.5U 67L M V T !/B .+;B -+C ;@0<98=>312%;7*03;@<*8+A 8C 3A 7.B B +@7*C ;
8引
言
作业车间调度问题)9E E 2-是12%难问题:*;
/也是最难的组合优化问题之一.简单来说作业车间调度问题可以描述如
下.有一些工件和一些机器/每个工件由一组工序组成)这些工序必须按给定顺序加工-.每个工序在给定的机器上加工/加工过程中不能被打断.另外/每台机器同一时刻至多能处理一个工序.问题的目标是找到使所有工件完工时间
)67,@+-7=-最短的调度.对9E E 2问题人们设计了很多启发式算法/
包括有基于优先指派的算法/转换瓶颈算法:";
/
局域搜索算法/神经网络算法/基因算法/E G
等.其中E G
和D E E G :4;
/都利用了转换瓶颈技术和局域搜索技术/
并且是当前最好的启发式算法中的两个.禁忌搜索是局域搜
索中最有效的算法之一.本文就是给出了一种有效的基于禁忌搜索的启发式算法/该算法中设计了新的禁忌搜索方法.而且该算法没有利用转换瓶颈技术/我们将该算法和D E F G 算法:H ;)
不用转换瓶颈的禁忌搜索算法中效率最高的算法之一-做了比较/发现该算法计算结果好于D E F G 算法好的实例要
多于不好的.
>作业车间调度问题
本节的大部分内容可以在文献:H ;中找到.令?@A
*/B /m C 表示工件集/D @A */B /l C 表示机器集/E @A */B /n C 表示工序集.工件’由n ’个工序序列组成!)x ’<*F */x
’<*F "/B /x ’<*F n ’-/这里x ’<*@G ’<*
t @*n t 是前’%*个工件中的工序的总数)’@*/B /m /x #@#且G m
t @*n
t @n -.工序t 必须在机器H t I D 加工一段不能被打断的时间u t J #/t I E .可以将工序集E 分成一些子集D K @A t I E !H t @K C /每个子集对应于要在机器K 上加工的工序/且令l K @L D K L .在机器K 上加工的序列是M K )M K )*-/B /M K )l K --/K I D /M K )t -/表示子集D K 的在M K 中处在t 位置的元素.满足上述限制的一组工序开工时间r t N #/t
I E 是一个可行解/
一个可行解也称作是一个调度.该问题就是要找使67,@+-7=即673t IE )r
t F u t -最小的调度.令O K 表示在机器K 上加工的工序所有的执行序列的集
第",卷第"期"##H 年"月小型微型计算机系统
PQ 1Q U B 9 V ",1B ."W @. ."##H 万方数据