PDF《用 模拟 退火算 法解决 生 产调度 问题》

第24卷 第 3期

2 0

0 4年 6月 黄冈师范学院学报JournalofHu a n g g a n g No r ma l Un i v e r s i t y Vo

1 .

2 4 No .

3 J u n .

2 0

0 4 用模拟退火算法解决生产调度问题 杨殿生(鄂州大 学 教务 处,湖北 鄂州436000)摘要:介绍了Me t r o p o l i s准则 , 给出了模 拟退 火算法 解决 生产 调度 问题 的基 本方 法和 步骤 , 并对算法 的有效 性进 行 了验 证. 关键词 : 模 拟退 火算 法;

Me t r o p o l i s准则 ;

生产调 度 问题 中图分类 号:02

2 4 文献标 识码 : A 文章编 号:1003―8078(2O04)03―0045―03Sol v i ng s c he du l i ng pr obl e m wi t h Si m ul a t e d Anne a l i ng Al g or i t h m YANG Di a n― s he ng ( Ed u c a t i o n Ad mi n i s t r a t i o n,Ez h o u U n i v e r s i t y,Ez h ou

4 3

6 0

0 0,Hu b e i ,Ch i n a ) Ab s t r a c t :W e p r o p o s e d i n t h i s p a p e r t h e M e t r o p o l i s r u l e a n d g a v e t h e b a s i c wa y s a n d s t e p s t o s o l v e s c h e d u l i n g p r o b l e m wi t h Si mu l a t e d An n e a l i n g Al g o r i t h m.Fu r t h e r mo r e,we v e r i f i e d t h e v a l i d i t y o f t h e a l g o r i t h m. Ke y wo r d s:S i mu l a t e d Ann e a l i n g Al g o r i t h m ;

M e t r o p o l i s r u l e;

s c h e d u l i n g p r o b l e m 模拟退火算 法SAA( S i mu l a t e d An n e a l i n g Al g o r i t h m) 是基 于Me n t e Ca r l o迭 代求解 策 略的一种通 用随机寻优算 法,其出发点是 基于物理 中固体物质 的退火 过程与 一般组 合优化问题之 间的相似性. 模拟 退火 算法在某一初 温下 , 伴随 温度参 数的不断 下降 , 结 合概率 突跳性在解空 间随机 寻找 目标 函数的全局 最优解 , 即局部 优解能概 率性地跳 出并 最终趋 于全 局最优解.

1 问题 的提 出有个相互独立 的任 务(一1 ,

2 , … , ) 要在 台机 床(一1 ,

2 , … , ) 上进行 加工 , 这 台机 床 的功 能相 同,每次 只能进 行 一个 任务 的非抢 占式加 工,每个任务所 需 的加 工时 间分 别为t(一1 ,

2 , … , ) . 要找一个最小调度,即找对个任务的一个调度,使完成所有任务的时 间最 短.2模拟退 火算 法 的描 述2.1物理退火过程固体 退火是先将固体加热至熔化,再徐徐冷却使之凝固成 规整晶体的热力学过程.退火过程是 系统在 每一温度下 达到平衡 的过程 , 可 以用封 闭系统 的等温 过程来 描述. 由Boltzma n n 有 序性原理 , 退火过程 遵循热 平衡封 闭 系统 的热力学定律 ―― 自由能减 少定律 : 对于与周 围环境交换能 量而温度保持不 变 的封 闭系统 , 系统状态 的 自发 变化 总是朝着 自由能减少 的方 向进行 , 当 自由能达到最 小值时,系统达到平衡态.设E为系统的微 观状态的能量,则系统处在状态i的概 率为P=Ae x p( 一)(1)收稿 日期 :

2 0

0 4 ―

0 3 ―

1 0 . 作者 简介:杨殿 生,男.安徽明光 人,工学 硕士,讲师,主要 从事 工 程数 学 和教学 管 理研 究 维普资讯 http://www.cqvip.com ・4 6・ 黄冈师范学院学报第24卷 其中是E无关的常数 . 由尸一1可知:∑exp(一筹):1.令Z一exp(一筹),则得:一1.代入(1)式,得:P一1exp( 一)(2)F其中,k称 为Bohzma n n常数,T为绝对温度,exp

(一)称为Bohz ma n n因子.(2)式称Gi b b s正则分 布. 该 分布 给出温度

7 1 时 固体 处于能 量为 E 的微观 态 i的概率. 显然 , 固体 处于 能量较 低的微观态 概率 大, 在 温度降低 时,那些 能量相对较 低的微 观态最 有可 能 出现. 当温度趋 于零时,固体基本 上只能处于能 量为最小值 的基态.

2 .

2 Me t r o p o l i s准则固体在恒 定温度下达 到平衡 的过程 可以用 Mo n t e C a r l o方 法加 以模 拟,该方法 虽然简单 , 但必 须大 量采 样才能得 到 比较精确 的结果 , 因而计算 量很大.

1 9

5 3年,Me t r o p o l i s等提 出 了重要性 采样法 , 即以概率接 受新状态. 具体而 言:在温度

7 1 , 由当前状态 i 产生新 状态 , 两 者的能量分别为 E 和E, , 若E,