蛙跳算法与批量无等待流水线调度问题的优化

蛙跳算法现有文献

第2 7卷第 8期21 0 0年 8月

计算机应用研究 A pi t nR sac f o ues p l ai eerho mp t c o C r

Vo . 7 No 8 12 .Au . 2 1 g 00

蛙跳算法与批量无等待流水线调度问题的优化声谢圣献潘全科潘玉霞。贾保先，,,(. 1聊城大学计算机学院，山东聊城 2 2 5 2海南大学三亚学院，南三亚 5 22 ) 5 0 9; .海 7 0 2

摘要：针对以 m ksa ae n为指标的批量无等待流水线调度问题，出了一种有效的离散蛙跳算法。首先采用 p提基于工序的编码方式使蛙跳算法直接应用于调度问题；次采用基于 N H与改进 N H和随机产生相结合的初其 E E

始化方法，保证了初始解的高质量和分布性；次采用交叉或变异方法产生新解，持了种群的优越性和多样再保性；对全局最优解执行快速局部搜索，效地降低了算法的时间复杂度，最后有平衡算法的全局和局部开发能力。 对随机生成不同规模的实例进行广泛的实验，仿真实验结果的比较，明所得蛙跳算法的有效性和高效性。通过表 关键词：批量无等待流水线调度；蛙跳算法；快速局部搜索中图分类号：T 8 P1文献标志码：A 文章编号：10— 6 5 2 1 ) 8 2 0—4 0 13 9 (0 0 0—9 9 0d i1 .9 9 ji n 10—6 5 2 1 . 8 0 6 oi0 3 6/.s .0 13 9 .0 0 0 .2 s

S u e r g- a ig ag rt m o o-te mig n - i h f d fo -e pn lo i l l h frltsr a n o- t - wa l f ws o c e u ig p o lm o h p s h d l r be nX E Segxa P NQ a-e, A ux JA B o i I hn-i, A unk P N Y—i, I a- a n a xn( . colfC m ue c ne La ceg U i n￣,Laceg S adn 50 9,C ia . colfS na an n U i rt,Sna 1Sho o o p t Si c, i hn n e i r e o v iohn hn og2 25 hn;2 Sho ay,H ia nv sy a y o eiHann5 2 2,C i ) i 7 0 2 hn a a

Abt c:T i ppr rp sda f c v

h fe r— ai l rh ( F A)f ov gt o s em n o hp sr t hs a e pooe ne etesu l f gl pn a oi m S L a f i fd o e g g t o sl n eltt a igf w so r i h r l sh dl gpol i e re o i mz gm x u o peo m ie, k sa )u dr ow ipo utnc— ceui rbe wt t i r no mn in ai mcm lt n ie(.. maepn n e—a r c o a n m h h c ti f i i m i t n t d i ss it, epooe F Arpeet ni id a o o sa o em t i k eo g a S L ut l f e.Fr l t r s S L r ne a dv u r r a bpr uao i maet r i l F A sibeo sy h p d e s d n i l fg j tn o h i n a rs h d l g p o lm.S c n l d sg e n i i ai t n me h d b s d o eNE h u s c h r l, s d ac o s v r p r— c e ui rbe n e o dy, e in d a t l a i t o a e n t H e r t .T i y u e r so e e a n i z o h i i d o t ro tt n o e ao r d c e d vd a .F n l i r e of r e n a c e ag r h o rmu ai p rt r op o u ea n w i ii u 1 i a y, n od r t re h n et lo t m’ x l i t n c p b l o t n l t u h h i S p ot i a a i— e ao i t n f ce c y a d e in y,e e d d a fs lc ls a c l o t m a e n t e i s r o w p n ih o h o n t e p o o e h f e i mb d e t o a e r h ag r h b s d o h n e t r s a eg b r o d i h r p s d s u l d a i f f g l a i g ag r h r—e p n lo t m.T i c n rd c P i . e c mp t t n lr s l n o aio s s o a h rp s d S L s o i hs a e u e C U t me T o u ai a e ut a d c

mp r n h w t t ep o o e F A i h o s s h t ef cie a d e ce t o n o i sa t n f d n etrs l t n rt e p o lm o sd r d f t n f i n rr d m tn si i ig b t o ui sf rb e c n i e e . e v i f a n n e o o h Ke r s o—te mig n— i f W h p s h d l g p o lm;s ufe r g la i g ag r h;fs lc l e r h y wo d:ltsra n o wat o s o c e u i r b e l n h f d f— p n o t m a t o a a c l o e l i s

批量无等待流水线调度问题是一个具有广泛应用背景和重要理论价值的组合优化问题，是许多实际生产调度过程的简

电场电力系统动态优化等方面，取得了良好的效果。基并于蛙跳算法的以上优点，出了一种离散蛙跳算法，提并嵌入快

化模型，广泛存在于炼钢、品加工、食化工和制药等工业领域。 目前，研究此类问题的文献很少。K m等人…于 20 ua r 0 0年用遗传算法解决批量无等待流水线调度问题， m n等人于 E mos 19 9 5年把批量无等待问题模拟成 T P进行解决。由于此类问 S题的复杂性，智能算法成为求解调度问题的主要方法。蛙跳算法 ( F A) 20年由 E sf和 Lne提出的一 S L是 00 uu asy

速局部搜索，有效地提高了蛙跳算法解决批量无等待流水线调度问题的性能。

1问题描述 批量无等待流水线调度问题 ( t t a n o a o so 1 -r mi n - if w hp o se g w t l

shdl polm,N S ) ceue rbe L F P可描述为：工件分成若干个等大的 将批量，每个批量在机床上的加工顺序相同，同一批量的两个工

种受自然生物模仿启示而产生的基于群体的协同搜索算法。 作为一种全新的生物进化算法，它结合了基于基因进化的模因演算法和基于群体行为的粒子群算法两者的优点 J具有概，

序之间没有等待时间，即要求任意批量在每台机床上的完成时间必须等于其在下一台机床上的开始时间。同时约定，每个批量某一时刻只能够在一台机床上加工，每台机床在某一时刻只能够加工一个批量。每个工件 N={,,,} 1 2

… n按某一工序

念简单、参数少、计算速度快、全局寻优能力强、易于实现等特点。最初应用于成品油管网设计、贴片机贴装顺序』含风、

收稿日期： 0 00—7 2 1—2 1;修回日期： 0 00—5 2 1— 3 1育厅资助项目(O L2 J8 J0)

基金项目：国家自然科学基金资助项目( 0 70 5 7 8 16 )数字制造装备与技术国 6 84 7,0 70 5;

家重点实验室开放课题(中科技大学)博士后科学基金资助项目(0 7 4 09 )华； 20 0 17 1;山东省软件科学研究计划资助项目(0 9 K 15;山东省教 20 R B 2 )作者简介：圣献 (9 7 )男，谢 15 -,山东聊城人，教授，主要研究方向为智能计算和信息安全 …… 此处隐藏：13025字，全部文档内容请下载后查看。喜欢就下载吧 ……