计 算 机 工 程 第 32 卷 第21期
Vol.32 No.21 Computer Engineering · 博士论文 ·
文章编号：1000—3428(2006)21—0038—03
2006年11月
November 2006
文献标识码：A 中图分类号：TP312
解决Job Shop调度问题的模拟退火算法改进
赵良辉，邓飞其
(华南理工大学系统工程研究所，广州 510640)
摘 要：模拟退火算法是较常用和较理想的解决车间作业调度问题的方法，但由于算法本身的限制和JSP问题的特殊性，其效能难以很好地发挥。该文提出了2种针对JSP问题的改进模拟退火算法：回火退火算法和快速模拟退火算法，前者可以提高最终解质量，后者可以提高算法的运行速度；并以Matlab为工具进行了仿真实验，获得了较好效果。
关键词：模拟退火算法；回火退火算法；快速模拟退火算法；作业车间调度问题；局部搜索算法
Improved Simulated Annealing Algorithm for Job Shop Schedule
ZHAO Lianghui, DENG Feiqi
(Institute of Systems Engineering, South China University of Technology, Guangzhou 510640)
【Abstract】Simulated annealing algorithm is a kind of preferable algorithms on solving job shop schedule problem. However, because of its inbornlimitation and constraints from the job shop environment, its effect is impaired. Two improved SA are proposed: one is temper-SA, which canimprove the quality of the solution; the other is fast-SA, which can shorten the running time of the algorithm. A job shop schedule example isdescribed, which is solved with normal SA, temper-SA and fast-SA respectively.
【Key words】Simulated annealing algorithm (SA); Temper-SA; Fast-SA; Job shop scheduling problem (JSP); Local search algorithm (LSA)
1 概述
作业车间调度问题(Job Shop Scheduling Problem，JSP)是一类满足任务配置和顺序约束要求的组合优化问题，属于NP完全问题，对它的研究已经有几十年的历史。一般的JSP可以描述为有n个加工顺序不同的工件要在m台机器上完成加工[1]。已知：
(1)工件集P= {p1,p2,…,pn}，pi为第i个工件，i=1,2, …,n； (2)机器集M={m1,m2,…,mm}，mj为第j号机器，j=1, 2, …,m； (3)工序集OP={op1,op2, …,opn}，opi={opi1,opi2, …,opim}为工件pi的工序序列。opik为第i个工件的第k道工序使用的机器号，opik=0表示工件pi在第k道工序不加工，k=1,2, …,m；
(4)每个工件使用每台机器的时间矩阵T={tij},tij为第i个工件pi
使用第j台机器的时间。tij=0表示工件pi不使用机器j。
较为理想的最优解，必须选取大参数使运行时间过长。
因此，为了提高模拟退火算法的实际应用价值，就必须对其加以改进。但是最终解的质量和算法运行时间是一对矛盾，在实际应用中只能根据需要侧重于某一方面。
2 有记忆的回火退火算法
定义1 模拟退火算法的接受率X(t)定义为在给定控制参数值t时，搜索过程中接受的变换数与提出的变换数的比值[2]，即：
X(t)=
接受的变换数
t
而且JSP满足下列约束条件：
(1)每个工件使用每台机器不多于1次；
即可以有opi≠opd(i(2)每个工件利用每台机器的顺序可以不同，≠d)；
(3)每个工件的工序必须依次加工，后工序不能先于前工序； (4)任何工件没有抢先加工的优先权，应服从任何生产顺序； 也不临时取消工件的加工。 (5)工件加工过程中没有新工件加入，
根据模X(t)实际上代表的是与t有关的接受新解的概率。
拟算法的机理可知
X(t)=exp(−∆f/t) 式中
∆f
是目标函数值的增量，即新解的函数值减旧解的函中
数值。
本文中初始接受率表示为X0，最终接受率表示为Xf。 定义2 模拟退火算法的冷却进度表为：
(1)初始温度参数t0 ； (2)温度的衰减函数α；
tk+1=α⋅tk；α是小于1的正数；
调度目标：通常是最小化最大完工时间，即minf(S1,
S2, …,Sn)=min{ci}，i=1,2, …,n，其中：ci为工件i的完工时间。
对于以上描述的调度问题，调度算法的任务就是在许可的计算时间内得到最优或是较优的加工顺序。
模拟退火算法( Simulated Annealing Algorithm，SA)作为一种出色的非数值算法，已被广泛应用于解决JSP问题。但模拟退火算法作为一种近似算法在实际应用中也暴露出一些缺点：(1)运行时间较长，尤其是大规模的调度问题，其运行时间经常使得算法无法进行实际应用；(2)算法在运行中容易进入某个局部最优解，尤其是参数选取不恰当时。要想得到 —38—
(3)Markov链的长度L；
(4)停止准则：温度控制参数达到0，或在若干个相继的Markov链中解无任何变化就终止算法。
要提高最终解的质量，就必须避免算法过早地陷入局部
最优。模拟退火算法在运行前期，温度参数t较大，接受率X高，使得程序可以接受劣解从而避免掉入“局部陷阱”；在
作者简介：赵良辉(1973－)，男，博士生，主研方向：信息系统工程；邓飞其，教授
收稿日期：2005-11-18 E-mail：[email protected]
运行后期，t值较小，接受率X低，t趋近于0时程序基本退化为局部搜索算法。为使程序不停留在局部极值，可尝试重新提高t值(加温)，使得算法的接受率再次提高，从而有望跳出局部最优解，接近全局最优解。由于这个过程与金属热处理中的回火过程相似，因此称之为回火退火算法。回火后再进行退火过程，就有可能得到全局最优解。
回火温度可以与退火的初始温度t0相同，这是因为t0对应高的接受率，而回火就是为了得到高接受率，至于回火次数，考虑到回火会导致计算过程的重复，一般不能太多，以不超过10次为宜。第1次回火以上次退火的最终解作为初始解，以后各次回火也都以前次退火的最终解为初始解。
模拟退火由于在搜索过程中可以接受部分恶化解，因此很可能在运算过程中曾经出现过最优解，但在其后的运算中可能被放弃，也就是算法无法保证最终解是整个搜索过程中曾经达到过的最优解。为了避免出现这种情况，给算法增加一个记忆器，记住搜索过程中遇见过的最好结果，但退火过程结束时，将所得最终解与记忆器中的解比较并取较优者作为最后结果，无疑会在许多情况下提高算法所得解的质量。添加了这种记忆功能的算法可称为有记忆的回火退火算法。
记忆转置可以设置为记忆当前最优解和对应函数值的 2个变量，每次搜索都将新函数值与最优解的值比较，储存其中的更优者；算法结束时从最后的当前解和记忆变量中选取较优者为最终解即可。
有记忆的回火退火算法的运算步骤如下：
寻找一个初始解i0；计算k个模拟退火初始温度组成数列T； f*分别为记忆最优解和最优解对应函数值的变量，令i*＝i0，i*，f*＝f0；
for n=1 to k do begin 令t=T(n)；
执行一个Markov链，即运行下述步骤L次： 从当前解i的2变换邻域中随机选取一个新解j；
若 f(j)≤f(i) 则令i=j，同时令i*=i，f*=f;否则，若
exp[((f(i)−f(j))/t]>rand，则依然令i=j(rand是介于0和1之间的随
＝2 700万次。这么大的计算量，使用Matlab在电脑上运行
耗时为5~6小时(数据取自清华同方真爱8380台式机采用Matlab7.0的运行结果；所耗时间主要集中在由编码计算函数值(完工时间)这一步骤中，编码长达4 500，导致运算效率低下)，不大适合实际应用场合。因此为了增强算法的实用性必须提高其速度。
模拟退火算法的近亲：局部搜索算法(Local Search Algorithm，LSA)虽然难以达到最优解，但具有搜索速度快的特点，可以尝试将其与SA算法相结合，形成互补型的混合算法。SA的初始解是随机选择的，由初始解到某个较优解搜索过程浪费了大量的时间，因此可以尝试用LSA代替。在SA的末段，t值衰减到一定值时，接受率X趋于0，这时SA已基本退火为LSA，但其速度却依然缓慢，因此这一部分运算过程也应该用LSA代替。快速模拟退火算法的步骤为：
(1)寻找一个初始解i0；计算模拟退火初始温度t0； (2)由初始解开始执行局部搜索算法得一局部极值点il； (3)从已获得的局部极值点出发，转用模拟退火法，按随机策略进行全局搜索；当t值衰减到某一常数tf时，停止搜索，获得SA终点iSA；
(4)考察局部极值点和SA终点的目标函数值，如果f(iSA)
(5)算法结束，输出iopt。
算法的关键在于合理设置SA部分的参数使整个算法既省时又保持收敛。由于使用SA进行全局搜索时的初值已经是局部极值点，因此在搜索中Markov链必须足够长以保证搜索能跳出“局部陷阱”，因此链长L不能减小(保持原值)，程序的着眼点只能放在终止条件tf上，通过适当的终止条件来限制内循环的次数从而使时间缩短。当SA部分的接受率X趋于0时SA部分可以结束，设此时tf＝t0 /k，则有：
Xf=X(tf)=exp(−∆f/tf) −∆f−∆fk
=exp(=(exp(≈(X0)k
t0/kt0
此处虽然tf对应的
∆f
不同于t0对应的
∆f
，但二者来源
机数)；
若满足终止条件则终止Markov链；否则令t＝αt，回到a ； end
取最终解i和i*中较优者为最优解；
相同，在估算tf的值时可以视为相同。根据X0的取值不同，
不同的k值对应的tf见表1。
表1 不同k值和X0值对应的Xf值
k值：
0.4630.2060.0350.005
0.3580.1220.0120.001
0.0770.0050
X0=0.95 0.599X0=0.9 0.349X0=0.8 0.107X00.028
如此可基本得到全局近似最优解。
3 快速模拟退火算法
定义3 JSP问题的规模定义为其编码长度len；
已知工件数p与机器数m的乘积为p*m，则len≤p*m，因为不是每个工件都需要在全部机器上加工(即不是每个工件都有m个工序)；但是一般二者相差甚少，处于同一数量级，因此p*m也可以反映算法的规模。
当JSP问题的规模增大时，模拟退火算法的速度会变得很慢，原因有2点：一是每次搜索的Markov链必须足够长才能使搜索充分；二是必须进行足够多的搜索(内循环)才能达到终止条件(s个Markov链的最终解相同，或t趋于0)。为了使算法在每个t值上都能恢复(至少是接近)准平衡，Markov链的长度L一般不能太小，常令L=100~300len，那么对于一个150*30调度例子，len约等于4 500，则L约等于150*30*100即450 000；要达到终止条件一般要进行60次以上的内循环，那么实现“从邻域中找到一个新解并与旧解比较”的操作(即第2节所述算法步骤中的c、d步)；就要至少执行45万*60
由表1可见，如果X0=0.95，则k=40时，Xf=0.9540=0.129，可以认为接受率已足够小；如果X0=0.9，则当k=20时，Xf=0.920=0.122可以认为接受率已足够小；对于其它的X0值，都可以得到相应的k值，然后取对应的tf值作为终止条件。
确定合理的值后，内循环的次数有望减少，以X0=0.9为例，如果取t的衰减系数为0.9，则1/20=0.05≈0.928，即只需进行28次内循环t值就已经下降到使接受率足够小的程度，此时立即改用局部搜索算法就能大大节省运算时间。
对于算法中的局部搜索部分，借鉴SA算法采用在当前解的邻域中随机搜索的方式。邻域可以是2变换邻域或3变换邻域，前者的规模为(n-1)*(n-2)，后者的规模为(n-1)*(n-2)*(n-3)，因此后者的搜索空间更大；但从省时角度出发，2变换邻域可以更快地得到邻近解，因此这里更适合采用2变换邻域随机搜索。随机搜索的终止条件以“连续s
—39—
次搜索未得到更优解”为准(s一般取10~20)。
4 实例
仿真工具：Matlab7.0版；
仿真环境：WinXp SP2操作系统，CPU：Pentium-m处理器1.73GHz，512MB DDRII内存。
一个5工件3机器的简单实例，工序矩阵OP和工时矩阵T如表2所示。
表2 一个5*3调度实例
工序矩阵
3 2 1 1 3 2 2 3 0 1 2 3 3 1 2
完工时间
130120
110
1000150140
50
100
150
200
250
Markov链序号
300
350
400
450
500550
600
工时矩阵(min) 27 8 10 6 10 5 14 10 0 25 20 16 5 12 28
图3 各次Markov链最终解函数值
由图3可见，回火退火算法在运行中虽屡次收敛于局部
最优值86，但最后还是跳出局部最优达到全局最优值(83)。 4.3 使用快速模拟退火算法
各初始参数选取与常规模拟退火算法相同，根据X0=0.9和α=0.9按照表1选取k=20，算法中SA部分的终止条件为tf
表4 快速模拟退火算法运行结果
序号
最优解
最优函数值
内循环次数
仿真历时
平均
一个初始解：[1**********]332。
4.1 使用普通模拟退火算法
根据式(1)令初始接受率X0=0.9求得初始温度t0为171.772 5，选取α=0.9，L=100n=1 400，v=10。为求普遍性对本实例连续运行10次，得各次寻优结果如表3所示。
表3 普遍模拟退火算法运行结果
序号 最优解 最优函数值 83 83 86
84.100 0 平均
内循环次数
45 57 48 53.900 0
仿真历时 32.882 7
5 结论
3种算法的性能参数比较如表5所示。
表5 3种算法性能参数比较
算法
普遍模拟退火算法(平均值) 有记忆的回火退火算法 快速模拟退火算法(平均值)
最优函数值 内循环次数 仿真历时 图1为第1次运行时，各次内循环的最终解函数值变化
曲线；图2为第1次运行的结果对应的排产方案(图中数字为工件号)。
160
140
完
工120时间
100
20
号Markov链序
40
60
80
图1 各次Markov链最终解函数值
机号
时间
图2 最优排产方案(4.1)
由表5可知，普遍模拟退火算法在与另两种改进算法的比较中毫无优势，其最优值低于回火退火算法，运算时间高于快速模拟退火算法，因此在实际应用时应尽量使用改进的模拟退火算法。
有记忆的回火退火算法则明显是以时间换精度的算法，一般都能获得较满意的结果，但耗时较大，因此不适于大规模的调度问题。但对于单个工序耗时长而总工序不多的场合(例如大型零件的加工中心)，回火退火算法可以大大减少加工时间，优势明显。快速模拟退火算法的突出优势是需时少，从表中可以看出其耗时是普通模拟退火算法的40%，是有记
忆的回火退火算法的14%，因此非常适合于大规模的调度问题。如果要进一步加快速度，只要稍微降低初始接受率X0和适当加快温度t的衰减速度就可以取得很好的效果。另外它的精度也不低，本例中很接近普通模拟退火算法，因此是很有前途的SA算法的改进方向。
参考文献
1 王万良, 宋 毅, 吴启迪. 求解作业车间调度问题的双倍体遗传算法与软件实现[J]. 计算机集成制造系统—CIMS, 2004,10(1): 65. 2 康立山, 谢 云, 尤矢勇等. 非数值并行算法――模拟退火算法[M]. 北京: 科学出版社, 1994.
3 Collins N E, Egelese R W, Golden B L. Simulated Annealing――An Annotated Bibliography[J]. American Journal of Mathematical and Management Sciences, 1988, 8(3/4): 209.
4.2 使用有记忆的回火退火算法
根据式(1)令初始接受率X0=0.9运算10次求得10个初始温度t0＝[105.0923,161.0118,129.2376,283.5502,146.3037, 174.5926,266.0023,302.2268,231.5180,169.3306]，选取α=0.9，L=30n=420，v=10；运行仿真程序得结果为：
最优解： [1**********]142；完工时间：83min。仿真历时97.375 0s，共进行了545次内循环。图3为各次内循环的最终解函数值变化曲线。 —40—
计 算 机 工 程 第 32 卷 第21期
Vol.32 No.21 Computer Engineering · 博士论文 ·
文章编号：1000—3428(2006)21—0038—03
2006年11月
November 2006
文献标识码：A 中图分类号：TP312
解决Job Shop调度问题的模拟退火算法改进
赵良辉，邓飞其
(华南理工大学系统工程研究所，广州 510640)
摘 要：模拟退火算法是较常用和较理想的解决车间作业调度问题的方法，但由于算法本身的限制和JSP问题的特殊性，其效能难以很好地发挥。该文提出了2种针对JSP问题的改进模拟退火算法：回火退火算法和快速模拟退火算法，前者可以提高最终解质量，后者可以提高算法的运行速度；并以Matlab为工具进行了仿真实验，获得了较好效果。
关键词：模拟退火算法；回火退火算法；快速模拟退火算法；作业车间调度问题；局部搜索算法
Improved Simulated Annealing Algorithm for Job Shop Schedule
ZHAO Lianghui, DENG Feiqi
(Institute of Systems Engineering, South China University of Technology, Guangzhou 510640)
【Abstract】Simulated annealing algorithm is a kind of preferable algorithms on solving job shop schedule problem. However, because of its inbornlimitation and constraints from the job shop environment, its effect is impaired. Two improved SA are proposed: one is temper-SA, which canimprove the quality of the solution; the other is fast-SA, which can shorten the running time of the algorithm. A job shop schedule example isdescribed, which is solved with normal SA, temper-SA and fast-SA respectively.
【Key words】Simulated annealing algorithm (SA); Temper-SA; Fast-SA; Job shop scheduling problem (JSP); Local search algorithm (LSA)
1 概述
作业车间调度问题(Job Shop Scheduling Problem，JSP)是一类满足任务配置和顺序约束要求的组合优化问题，属于NP完全问题，对它的研究已经有几十年的历史。一般的JSP可以描述为有n个加工顺序不同的工件要在m台机器上完成加工[1]。已知：
(1)工件集P= {p1,p2,…,pn}，pi为第i个工件，i=1,2, …,n； (2)机器集M={m1,m2,…,mm}，mj为第j号机器，j=1, 2, …,m； (3)工序集OP={op1,op2, …,opn}，opi={opi1,opi2, …,opim}为工件pi的工序序列。opik为第i个工件的第k道工序使用的机器号，opik=0表示工件pi在第k道工序不加工，k=1,2, …,m；
(4)每个工件使用每台机器的时间矩阵T={tij},tij为第i个工件pi
使用第j台机器的时间。tij=0表示工件pi不使用机器j。
较为理想的最优解，必须选取大参数使运行时间过长。
因此，为了提高模拟退火算法的实际应用价值，就必须对其加以改进。但是最终解的质量和算法运行时间是一对矛盾，在实际应用中只能根据需要侧重于某一方面。
2 有记忆的回火退火算法
定义1 模拟退火算法的接受率X(t)定义为在给定控制参数值t时，搜索过程中接受的变换数与提出的变换数的比值[2]，即：
X(t)=
接受的变换数
t
而且JSP满足下列约束条件：
(1)每个工件使用每台机器不多于1次；
即可以有opi≠opd(i(2)每个工件利用每台机器的顺序可以不同，≠d)；
(3)每个工件的工序必须依次加工，后工序不能先于前工序； (4)任何工件没有抢先加工的优先权，应服从任何生产顺序； 也不临时取消工件的加工。 (5)工件加工过程中没有新工件加入，
根据模X(t)实际上代表的是与t有关的接受新解的概率。
拟算法的机理可知
X(t)=exp(−∆f/t) 式中
∆f
是目标函数值的增量，即新解的函数值减旧解的函中
数值。
本文中初始接受率表示为X0，最终接受率表示为Xf。 定义2 模拟退火算法的冷却进度表为：
(1)初始温度参数t0 ； (2)温度的衰减函数α；
tk+1=α⋅tk；α是小于1的正数；
调度目标：通常是最小化最大完工时间，即minf(S1,
S2, …,Sn)=min{ci}，i=1,2, …,n，其中：ci为工件i的完工时间。
对于以上描述的调度问题，调度算法的任务就是在许可的计算时间内得到最优或是较优的加工顺序。
模拟退火算法( Simulated Annealing Algorithm，SA)作为一种出色的非数值算法，已被广泛应用于解决JSP问题。但模拟退火算法作为一种近似算法在实际应用中也暴露出一些缺点：(1)运行时间较长，尤其是大规模的调度问题，其运行时间经常使得算法无法进行实际应用；(2)算法在运行中容易进入某个局部最优解，尤其是参数选取不恰当时。要想得到 —38—
(3)Markov链的长度L；
(4)停止准则：温度控制参数达到0，或在若干个相继的Markov链中解无任何变化就终止算法。
要提高最终解的质量，就必须避免算法过早地陷入局部
最优。模拟退火算法在运行前期，温度参数t较大，接受率X高，使得程序可以接受劣解从而避免掉入“局部陷阱”；在
作者简介：赵良辉(1973－)，男，博士生，主研方向：信息系统工程；邓飞其，教授
收稿日期：2005-11-18 E-mail：[email protected]
运行后期，t值较小，接受率X低，t趋近于0时程序基本退化为局部搜索算法。为使程序不停留在局部极值，可尝试重新提高t值(加温)，使得算法的接受率再次提高，从而有望跳出局部最优解，接近全局最优解。由于这个过程与金属热处理中的回火过程相似，因此称之为回火退火算法。回火后再进行退火过程，就有可能得到全局最优解。
回火温度可以与退火的初始温度t0相同，这是因为t0对应高的接受率，而回火就是为了得到高接受率，至于回火次数，考虑到回火会导致计算过程的重复，一般不能太多，以不超过10次为宜。第1次回火以上次退火的最终解作为初始解，以后各次回火也都以前次退火的最终解为初始解。
模拟退火由于在搜索过程中可以接受部分恶化解，因此很可能在运算过程中曾经出现过最优解，但在其后的运算中可能被放弃，也就是算法无法保证最终解是整个搜索过程中曾经达到过的最优解。为了避免出现这种情况，给算法增加一个记忆器，记住搜索过程中遇见过的最好结果，但退火过程结束时，将所得最终解与记忆器中的解比较并取较优者作为最后结果，无疑会在许多情况下提高算法所得解的质量。添加了这种记忆功能的算法可称为有记忆的回火退火算法。
记忆转置可以设置为记忆当前最优解和对应函数值的 2个变量，每次搜索都将新函数值与最优解的值比较，储存其中的更优者；算法结束时从最后的当前解和记忆变量中选取较优者为最终解即可。
有记忆的回火退火算法的运算步骤如下：
寻找一个初始解i0；计算k个模拟退火初始温度组成数列T； f*分别为记忆最优解和最优解对应函数值的变量，令i*＝i0，i*，f*＝f0；
for n=1 to k do begin 令t=T(n)；
执行一个Markov链，即运行下述步骤L次： 从当前解i的2变换邻域中随机选取一个新解j；
若 f(j)≤f(i) 则令i=j，同时令i*=i，f*=f;否则，若
exp[((f(i)−f(j))/t]>rand，则依然令i=j(rand是介于0和1之间的随
＝2 700万次。这么大的计算量，使用Matlab在电脑上运行
耗时为5~6小时(数据取自清华同方真爱8380台式机采用Matlab7.0的运行结果；所耗时间主要集中在由编码计算函数值(完工时间)这一步骤中，编码长达4 500，导致运算效率低下)，不大适合实际应用场合。因此为了增强算法的实用性必须提高其速度。
模拟退火算法的近亲：局部搜索算法(Local Search Algorithm，LSA)虽然难以达到最优解，但具有搜索速度快的特点，可以尝试将其与SA算法相结合，形成互补型的混合算法。SA的初始解是随机选择的，由初始解到某个较优解搜索过程浪费了大量的时间，因此可以尝试用LSA代替。在SA的末段，t值衰减到一定值时，接受率X趋于0，这时SA已基本退火为LSA，但其速度却依然缓慢，因此这一部分运算过程也应该用LSA代替。快速模拟退火算法的步骤为：
(1)寻找一个初始解i0；计算模拟退火初始温度t0； (2)由初始解开始执行局部搜索算法得一局部极值点il； (3)从已获得的局部极值点出发，转用模拟退火法，按随机策略进行全局搜索；当t值衰减到某一常数tf时，停止搜索，获得SA终点iSA；
(4)考察局部极值点和SA终点的目标函数值，如果f(iSA)
(5)算法结束，输出iopt。
算法的关键在于合理设置SA部分的参数使整个算法既省时又保持收敛。由于使用SA进行全局搜索时的初值已经是局部极值点，因此在搜索中Markov链必须足够长以保证搜索能跳出“局部陷阱”，因此链长L不能减小(保持原值)，程序的着眼点只能放在终止条件tf上，通过适当的终止条件来限制内循环的次数从而使时间缩短。当SA部分的接受率X趋于0时SA部分可以结束，设此时tf＝t0 /k，则有：
Xf=X(tf)=exp(−∆f/tf) −∆f−∆fk
=exp(=(exp(≈(X0)k
t0/kt0
此处虽然tf对应的
∆f
不同于t0对应的
∆f
，但二者来源
机数)；
若满足终止条件则终止Markov链；否则令t＝αt，回到a ； end
取最终解i和i*中较优者为最优解；
相同，在估算tf的值时可以视为相同。根据X0的取值不同，
不同的k值对应的tf见表1。
表1 不同k值和X0值对应的Xf值
k值：
0.4630.2060.0350.005
0.3580.1220.0120.001
0.0770.0050
X0=0.95 0.599X0=0.9 0.349X0=0.8 0.107X00.028
如此可基本得到全局近似最优解。
3 快速模拟退火算法
定义3 JSP问题的规模定义为其编码长度len；
已知工件数p与机器数m的乘积为p*m，则len≤p*m，因为不是每个工件都需要在全部机器上加工(即不是每个工件都有m个工序)；但是一般二者相差甚少，处于同一数量级，因此p*m也可以反映算法的规模。
当JSP问题的规模增大时，模拟退火算法的速度会变得很慢，原因有2点：一是每次搜索的Markov链必须足够长才能使搜索充分；二是必须进行足够多的搜索(内循环)才能达到终止条件(s个Markov链的最终解相同，或t趋于0)。为了使算法在每个t值上都能恢复(至少是接近)准平衡，Markov链的长度L一般不能太小，常令L=100~300len，那么对于一个150*30调度例子，len约等于4 500，则L约等于150*30*100即450 000；要达到终止条件一般要进行60次以上的内循环，那么实现“从邻域中找到一个新解并与旧解比较”的操作(即第2节所述算法步骤中的c、d步)；就要至少执行45万*60
由表1可见，如果X0=0.95，则k=40时，Xf=0.9540=0.129，可以认为接受率已足够小；如果X0=0.9，则当k=20时，Xf=0.920=0.122可以认为接受率已足够小；对于其它的X0值，都可以得到相应的k值，然后取对应的tf值作为终止条件。
确定合理的值后，内循环的次数有望减少，以X0=0.9为例，如果取t的衰减系数为0.9，则1/20=0.05≈0.928，即只需进行28次内循环t值就已经下降到使接受率足够小的程度，此时立即改用局部搜索算法就能大大节省运算时间。
对于算法中的局部搜索部分，借鉴SA算法采用在当前解的邻域中随机搜索的方式。邻域可以是2变换邻域或3变换邻域，前者的规模为(n-1)*(n-2)，后者的规模为(n-1)*(n-2)*(n-3)，因此后者的搜索空间更大；但从省时角度出发，2变换邻域可以更快地得到邻近解，因此这里更适合采用2变换邻域随机搜索。随机搜索的终止条件以“连续s
—39—
次搜索未得到更优解”为准(s一般取10~20)。
4 实例
仿真工具：Matlab7.0版；
仿真环境：WinXp SP2操作系统，CPU：Pentium-m处理器1.73GHz，512MB DDRII内存。
一个5工件3机器的简单实例，工序矩阵OP和工时矩阵T如表2所示。
表2 一个5*3调度实例
工序矩阵
3 2 1 1 3 2 2 3 0 1 2 3 3 1 2
完工时间
130120
110
1000150140
50
100
150
200
250
Markov链序号
300
350
400
450
500550
600
工时矩阵(min) 27 8 10 6 10 5 14 10 0 25 20 16 5 12 28
图3 各次Markov链最终解函数值
由图3可见，回火退火算法在运行中虽屡次收敛于局部
最优值86，但最后还是跳出局部最优达到全局最优值(83)。 4.3 使用快速模拟退火算法
各初始参数选取与常规模拟退火算法相同，根据X0=0.9和α=0.9按照表1选取k=20，算法中SA部分的终止条件为tf
表4 快速模拟退火算法运行结果
序号
最优解
最优函数值
内循环次数
仿真历时
平均
一个初始解：[1**********]332。
4.1 使用普通模拟退火算法
根据式(1)令初始接受率X0=0.9求得初始温度t0为171.772 5，选取α=0.9，L=100n=1 400，v=10。为求普遍性对本实例连续运行10次，得各次寻优结果如表3所示。
表3 普遍模拟退火算法运行结果
序号 最优解 最优函数值 83 83 86
84.100 0 平均
内循环次数
45 57 48 53.900 0
仿真历时 32.882 7
5 结论
3种算法的性能参数比较如表5所示。
表5 3种算法性能参数比较
算法
普遍模拟退火算法(平均值) 有记忆的回火退火算法 快速模拟退火算法(平均值)
最优函数值 内循环次数 仿真历时 图1为第1次运行时，各次内循环的最终解函数值变化
曲线；图2为第1次运行的结果对应的排产方案(图中数字为工件号)。
160
140
完
工120时间
100
20
号Markov链序
40
60
80
图1 各次Markov链最终解函数值
机号
时间
图2 最优排产方案(4.1)
由表5可知，普遍模拟退火算法在与另两种改进算法的比较中毫无优势，其最优值低于回火退火算法，运算时间高于快速模拟退火算法，因此在实际应用时应尽量使用改进的模拟退火算法。
有记忆的回火退火算法则明显是以时间换精度的算法，一般都能获得较满意的结果，但耗时较大，因此不适于大规模的调度问题。但对于单个工序耗时长而总工序不多的场合(例如大型零件的加工中心)，回火退火算法可以大大减少加工时间，优势明显。快速模拟退火算法的突出优势是需时少，从表中可以看出其耗时是普通模拟退火算法的40%，是有记
忆的回火退火算法的14%，因此非常适合于大规模的调度问题。如果要进一步加快速度，只要稍微降低初始接受率X0和适当加快温度t的衰减速度就可以取得很好的效果。另外它的精度也不低，本例中很接近普通模拟退火算法，因此是很有前途的SA算法的改进方向。
参考文献
1 王万良, 宋 毅, 吴启迪. 求解作业车间调度问题的双倍体遗传算法与软件实现[J]. 计算机集成制造系统—CIMS, 2004,10(1): 65. 2 康立山, 谢 云, 尤矢勇等. 非数值并行算法――模拟退火算法[M]. 北京: 科学出版社, 1994.
3 Collins N E, Egelese R W, Golden B L. Simulated Annealing――An Annotated Bibliography[J]. American Journal of Mathematical and Management Sciences, 1988, 8(3/4): 209.
4.2 使用有记忆的回火退火算法
根据式(1)令初始接受率X0=0.9运算10次求得10个初始温度t0＝[105.0923,161.0118,129.2376,283.5502,146.3037, 174.5926,266.0023,302.2268,231.5180,169.3306]，选取α=0.9，L=30n=420，v=10；运行仿真程序得结果为：
最优解： [1**********]142；完工时间：83min。仿真历时97.375 0s，共进行了545次内循环。图3为各次内循环的最终解函数值变化曲线。 —40—