柔性作业车间调度分析及其启发式算法.pdf

C o m p u t e r E n g i n e e r i n g a n d A p p l i c a t i o n s 计算机工程与应用2 0 1 2，4 8(1 0)2 3 3柔性作业车间调度分析及其启发式算法苏子林1，苑金梁1，陈炜2，邱景炜1S UZ i l i n l，Y U A NJ i n l i a n 9 1，C H E NW e i 2，Q I UJ i n g w e i l1 鲁东大学交通学院，山东烟台2 6 4 0 2 52 宁夏公路管理局，银川7 5 0 0 0 41 S c h o o lo f T r a f f i c，L u d o n gU n i v e r s i t y,Y a n t a i，S h a n d o n g2 6 4 0 2 5，C h i n a2 H i g h w a yA d m i n i s t r a t i o no f N i n g x i aP r o v i n c e，Y i n c h u a l l7 5 0 0 0 4，C h i n aS UZ i l i n，Y U A NJ i n l i a n g，C H E NW e i，e ta 1 F l e x i b l ej o b s h o ps c h e d u l i n ga n a l y s i sa n di t sh e u r i s t i ca l g o r i t h m C o m p u t e rE n g i n e e r i n ga n d A p p l i c a t i o n s，2 0 1 2，4 8(1 0)：2 3 3 2 3 7 A b s t r a c t：T h em u l t i o b j e c t i v ef l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e mi sa n a l y z e db a s e do nG a n t tg r a p ha n de x p e r i-e n c ef r o mb u i l d i n gb l o c k，ac o m p o s i t ep r i o r i t yr u l ea n dh e u r i s t i ca l g o r i t h mb a s e do nt h i sp r i o r i t yr u l ea r ep r e s e n t e d T h i sc o m p o s i t ep r i o r i t yr u l ei s 南rt h r e es c h e d u l i n gt a r g e t si n c l u d i n gm a k e s p a n c r i t i c a lm a c h i n ew o r k l o a da n dt o t a lw o r k l o a d，c h a n g i n gt h er a t i oo fd a t ai t e m si nt h er u l ec a na d j u s tt h er a t i oo ft h et h r e es c h e d u l i n gt a r g e t s T h i sh e u r i s-t i ca l g o r i t h mr a n d o m l ya d j u s t st h er a t i oo ft h i st h r e es c h e d u l i n gt a r g e t s，a n ds l i g h t l ya d j u s t st h er a t i oc o r r e s p o n d i n gt ot h eb e s ts o l u t i o n，c a nr a n d o m l yg e n e r a t em a n ye x c e l l e n ts c h e d u l i n gs o l u t i o n s T h ea l g o r i t h m Sc o m p a r i s o na n dt e s ts h o wt h a tt h er e s u l to ft h i sa l g o r i t h mi sm o r ee x c e l l e n t T h ea l g o r i t h mr u n sr a p i d l ya n ds t e a d i l y,a n dc a nd i r e c t l yb eu s e di ng e n e r a t i n gi n i t i a ls o l u t i o ni no t h e rs c h e d u l i n ga l g o r i t h m so ru s e di nd y n a m i cs c h e d u l i n g K e yw o r d s：f l e x i b l ej o bs h o ps c h e d u l i n g；p r i o r i t yr u l e；h e u r i s t i ca l g o r i t h m摘要：针对多目标柔性作业车间调度问题，基于甘特图和搭积木经验进行了分析，提出了一种组合优先规则和基于此优先规则的启发式算法。组合优先规则面向完工时间、关键机床负荷和总负荷三个指标，改变规则中各数据项的比例可调整三个指标所占的比例。算法采用随机方式调整三个指标的比例，并微调最优解对应的比例，能随机产生多个高质量调度解。对比测试表明，算法求解质量更高，运行速度快，稳定，可直接用于在其他调度算法中产生初始解，或者用于动态调度。关键词：柔性作业车间调度；优先规则；启发式算法文章编号：1 0 0 2 8 3 3 1(2 0 1 2)1 0 0 2 3 3 0 5文献标识码：A中图分类号：T P 3 0 1作业车间调度问题一直是学术界和工业界研究的热点问题之一，柔性作业车间调度问题(F J S P)因其自身优势得到广泛重视。目前，研究人员已经提出了多种调度算法，其中基于优先规则的启发式算法能够在有限的时间里产生可接受的调度结果，运行时间不随问题规模的增大而迅速增加，易于实施，得到了广泛重视和应用u，尤其在自动化制造系统的动态调度方面口1。目前的研究已经证实组合规则比单一调度规则效果更好o，尤其在多目标F J S P 中。在此基础上，笔者在研究遗传算法的初始种群生成过程中，基于甘特图分析了多目标F J S P，提出了一种基于优先规则的启发式算法，以下简称H A B P 算法，算法实验表明求解质量相对较高，运行速度决，稳定。1 柔性作业车间调度问题的数学模型F J S P 比一般的作业车间调度问题更加复杂，也更加接近调度实际情况，其数学模型描述如下。胛个工件“，Z，Z 在m 个机床 M 1，必，坛 上加工，每个工件Z 包含缃序溉，D f 山，O in 。其中作者简介：苏子林(1 9 7 0 一)，男，副教授，研究方向为计算机集成制造及汽车故障诊断。E-m a i l：s u z i l i n y t y a h o o c o m c a收稿1 3 期：2 0 1 0 1 1 2 2修回日期：2 0 1 1-0 3 2 8C N K I 出版1 3 期：2 0 1 1 0 7 1 4D O I：1 0 3 7 7 8 j i s s n 1 0 0 2 8 3 3 1 2 0 1 2 1 0 0 5 3h t t p：w w w c n k i n e t k c m s d e t a i l 1 1 2 1 2 7 T E 2 0 1 1 0 7 1 4 1 5 4 9 0 2 0 h t m l万方数据C o m p u t e rE n g i n e e r i n ga n d A p p l i c a t i o n s 计算机工程与应用每台机床在某一时刻只能加工一个工序，每个工序加工一旦开始不得中断，直到结束。所有机床和工件在时间0 可以开始加工。每个工件的工序顺序确定，不同工件的工序无先后顺序要求；每个工序D。在一个或多个机床M，上加工，而且在不同机床上的加工时间只。，(只 0)不一定相同。4 个工件5 台机床的柔性作业车间调度问题实例，如表1 所示。调度过程是合理安排工序到适当的机床上，使得一个或多个性能指标最优；已有文献较多考虑完工时间 4-5 本文考虑下列三个调度目标。(1)完工时间(G)最短，即r a i nC-m i n(m a x(G)，O k m(1)(2)关键机床负荷(既)最小，即r a i nW u=m i n(m a x(职)，O k m(2)(3)总负荷(孵)最小，即州m i nW r=m i n(3)表14 x 5 柔性作业车间调度问题实例工件注：表示工件1；0 表示工件1 的工序3；Z。表示工序在各机床的平均加工时间。2 柔性作业车间调度问题分析柔性作业车间调度包括工序选择和机床选择两个方面，最终生成最优或近优的工序排序和机床排序。基于优先规则的启发式算法就是根据某种优先规则，从所有工件的可加工工序中合理选择一个，并安排在合适的机床上加工，最后得到可以接受的调度结果，即从图1 所示的可用工序中，选择一个安排在图2 所示的合适机床上加工，最终生成图3 所示的调度结果。图1 表示表i 实例的各个工件及其工序的平均加工时间，其中填充矩形表示的工序尚未排到图2 中，图2 表示调度排序过程。图l 和图2 都采用矩形表示工序，这样如果把工序看作积木，把机床看作盒子，基于优先规则启发式算法的调度过程很像搭积木旧，即从图1 最上方四块积木中，根据某种优先规则不断取出积木排在图2 中，最后生产图3 的积木排列；同一积木排在不同的盒子里高度不同；排列目标考虑积木的高度最低，盒子里积木总高度最小，以及所有积木的总高度最小。根据搭积木的经验，综合考虑三个目标，图1 中剩余积木高度最大的应该先搭，尽量搭在图2 中最靠左处，并且优先选择在盒子里高度最小的积木。这样，剩余工序总加工时间最长的工件应该优选，尽量排在最早完工的机床上，并且优选在机床上加工时间最短的工序。因此，工序O i，排在机床必上的优先度为：羔办(f，r)=P“一a C，一胪f，(4)k=j式中，P f。表示工件f 的第k 个工序在可加工机床的平均加工时间，G 表示机床必的完工时间，系数反调整机床完工时间在优先度中所占的比例，系数是调整0。在机床必加工时间在优先度中所占的比例。2 52 0厦1 5廿H 1 0目气0J、J 1】3j 工件图1 工件平均加工时间012 3 4 5 6 78加工时间f s图2 调度过程式(4)包括减号分割的三个数据项，第一数据项反映了应优选剩余工序总加工时间最长的工件，第二数据项反映了工序应尽量排在最早完工的机床上，第三数据项反映了优选在机床上加工时间最短的工序，也是优选工序加工时间最短的机床。从调度结果甘特图可知：第一和第二数据项都利于使。最短，第二数据项也利于使机床负荷均匀分布，使W M最小，第三数据项利于使孵最小。因此改变系数仅和的值便可调整三个调度目标的比例，得到不同的调度结果。大量算例数据测试表明，当a 1 0，1 0 o】，卢 1 0，1 0 0 ，脑时，效果较好。在图I 和图2 所示的格局下，可用工序集合是 O，0 2，0 3 小0 4，：)。当a=3、胪2 5 时，各工序的优先度，如表2 所示。其中h(4，2，4)=一3 5 最大，D 4，：应优表2 各工序的优先度(a=3、#-2 5)工序M0 1 31 4D 2，一50 321 40 4：一1 9 5一2 2 51 3 57 5一1 5 5M一2 5 51 41 32 l坛一8一1 2 45 53 5坛一2 8 51 9 52 12 4万方数据苏子林，苑金梁，陈炜，等：柔性作业车间调度分析及其启发式算法先排在机床坛上加工。当a=3、=1 时，h(3，2，4)=2最大，D 3：应优先排在机床坛上加工。从图3 的调度结果甘特图可见，正的三个工序的加工时间都取最小值，而且第一个工序从时间。开始连续加工，没有空闲，第三个工序最后完成加工，因此图3 调度结果的G 达到下限。图3 的所有工序都取最小加工时间，因此图3 调度结果的孵达到下限。所以，图3 调度结果的完工时间最短和总负荷最小，两个调度目标都得到最优。MM l长必霉讹。胍O123 4 56 7891 01 1加工时间f s图3 调度结果甘特图3 基于优先规则的启发式算法基于以上分析，得到H A B P 算法如下：(1)计算所有工序在各机床的平均加工时间；构造调度结果集合三I=硎1 s 琏3 0 0)；构造可加工工序集合謦=Z I1 s f 1 0)，实例集r d a t a 的可用机床数量均值为2，最大为3，实例集v d a t a 的可用机床数量均值为0 5 m，最大为0 8 m。从表5 数据可知，随着可用机床数量所占比例的增加，H A B P 算法更优，运算结果与L B 的相对偏差不随问题规模的增大而增加。另外，H A B P 的运行时间随着问题规模的增大而增加，但趋势平缓。在上述算法测试中，运行时间都不超过1S。由于H A B P 算法主要通过改变6 c 和的值来得到不同的调度结果，不同的随机数序列影响较小，因此多次运行结果稳定。5 结论与展望本文依据搭积木的经验和甘特图，分析了多目标柔性作业车间调度问题，提出了公式(4)和H A B P。公式(4)表达的优先规则可优化巳、W M 和孵三个指标，改变6 c 和的值可调整三个指标在调度结果中所占的比例。H A B P 采用随机方式调整G、W M 和孵在调度结果中所占的比例，并对最优解对应的比例在小范围内微调；随机选择优先度相同的工序和机床，便于得到不同调度结果。H A B P 的运算结果更接近最优解，而且随着可用机床数量所占比例的增加，效果更好；H A B P 属于基于优先规则的启发式算法，运行速度快，稳定可靠。H A B P 不仅由于运算结果更优，速度快，可直接用于动态调度，而且由于能够产生多个调度结果，可用于其他算法产生初始解，如遗传算法、模拟退火算法或离子群等。未来的研究工作集中在以下三个方面：(1)考虑其他调度目标，分万方数据苏子林，苑金梁。陈炜，等：柔性作业车间调度分析及其启发式算法2 0 1 2，4 8(1 0)2 3 7表5H A B P 对不同H U 实例运算结果的比较问题L B。d c M a t a 如。L B 警d 叫L BV 訾如，问题L B。d c M a t a 如，L B。訾d 却L BV 訾如。m 0 65 55 504 74 704 74 701 2 08 5 79 2 06 87 5 67 8 84 17 5 67 5 60m l O8 7 19 3 77 06 7 97 5 81 0 46 5 56 5 501 2 18 9 510 5 91 5 58 0 89 3 11 3 28 0 08 4 55 3m 2 010 8 811 8 58 210 2 210 3 21 O10 2 2l0 2 50 31 2 28 3 29 7 54 97 3 78 4 11 2 47 3 37 5 42 81 0 16 0 96 5 06 35 7 05 9 03 45 7 05 8 42 41 2 39 5 010 1 96 88 1 69 0 59 88 0 98 2 72 21 0 26 5 56 6 61 65 2 95 6 76 75 2 95 3 91 91 2 48 8 19 8 21 0 37 7 58 6 51 0 47 7 37 8 71 81 0 35 5 05 7 95 04 7 74 9 02 74 7 74 8 51-61 2 58 9 4l0 1 61 2 07 5 28 3 71 0 17 5 17 6 92 31 0 45 6 86 2 69 35 0 25 1 52 55 0 25 1 01 61 2 610 8 9l2 6 81 4 1l0 5 611 5 98 810 5 210 5 90 41 0 55 0 35 4 57 74 5 74 8 25 24 5 74 6 31 31 2 711 8 112 7 77 510 8 5l1 4 45 110 8 410 9 10 61 0 68 3 38 4 11 07 9 98 2 l2 77 9 98 0 30 51 2 8l1 1 613 2 51 5 7l0 7 511 3 l4 910 6 910 8 01 O1 0 77 6 28 8 01 3 47 4 97 6 52 17 4 97 6 21 71 2 910 5 8l2 1 21 2 79 9 310 7 37 49 9 3l0 0 41 11 0 88 4 58 8 44 47 6 57 9 03 27 6 57 6 70 31 3 0l1 4 713 5 71 5 410 6 8l1 5 27 210 6 810 8 01 11 0 98 7 88 8 20 58 5 38 6 91 88 5 38 6 21 01 3 1l5 2 317 4 11 2 515 2 015 7 73 615 2 0l5 2 60 41 1 08 6 69 0 34 18 0 48 2 42 48 0 48 0 90 61 3 216 9 8l8 2 87 116 5 717 1 03 116 5 716 6 50 51 1 110 8 711 2 23 110 7 l10 7 80 610 7 ll0 7 70 61 3 315 4 716 4 56 014 9 715 3 12 2l4 9 715 0 60 61 1 29 6 09 7 21 29 3 69 4 40 89 3 69 3 80 21 3 4l5 9 217 0 96 815 3 5l6 5 47 215 3 515 4 50 61 1 310 5 3l1 3 77 4l0 3 810 4 60 810 3 810 4 l0 31 3 517 3 618 0 84 015 4 916 0 l3 215 4 915 5 70 51 1 411 2 3l1 5 72 910 7 0l0 8 21 1l0 7 010 7 20 21 3 610 0 6l3 0 42 2 910 1 610 9 l6 99 4 89 4 801 1 5l1 l l11 8 36 110 8 911 1 42 210 8 910 9 30 41 3 713 5 5l3 5 80 29 8 911 5 01 49 8 69 8 601 1 68 9 29 5 46 57 1 77 8 19 O7 1 77 1 701 3 810 1 912 6 51 9 49 4 310 5 61 0 79 4 39 4 301 1 77 0 77 8 49 86 4 66 6 93 46 4 66 4 601 3 9l1 5 l13 7 81 6 59 6 610 9 11 1 59 2 29 2 201 1 88 4 28 7 94 26 6 67 3 69 56 6 36 6 301 4 010 3 412 5 21 7 49 5 510 5 4-9 49 5 59 5 501 1 97 9 68 5 16 56 4 77 2 91 1 26 1 76 1 70析研究组合规则；(2)基于本文的搭积木经验和甘特图分析，研究其他求解算法；(3)研究H A B P 在其他算法中的应用。参考文献：1 T a iJC，H oNB E v o l v i n gd i s p a t c h i n gr u l e su s i n gg e n e t i cp r o g r a m m i n gf o rs o l v i n gm u l t i-o b j e c t i v ef l e x i b l ej o b s h o pp r o b l e m s J C o m p u t e r s&I n d u s t r i a lE n g i n e e r i n g 2 0 0 8 5 4：4 5 3 4 7 3 2 张根保自动化制造系统 M】2 版北京：机械工业出版社，2 0 0 9：1 6 5 1 6 8 3 Y i a z d a n iM，A m i r iM，Z a n d i e hM F l e x i b l ej o b s h o ps c h e d u l i n gw i t hp a r a l l e lv a r i a b l en e i g h b o r h o o ds e a r c ha l g o r i t h m J E x p e r tS y s t e m sw i t hA p p l i c a t i o n s，2 0 1 0，3 7：6 7 8 6 8 7 4 B a g h e r iA，Z a n d i e hM，M a h d a v i aI，e ta 1 A na r t i f i c i a li m m u n ea l g o r i t h mf o r t h ef l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m J F u t u r eG e n e r a t i o nC o m p u t e rS y s t e m s，2 0 1 0，2 6：5 3 3-5 4 1 5】H m i d aAB，H a o u a r iM，H u g u e tM，e ta 1 D i s c r e p a n c ys e a r c hf o r t h ef l e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m J C o m p u t e r s&O p e r a t i o n sR e s e a r c h，2 0 1 0，3 7：2 1 9 2 2 2 0 1 6 张德富，李新求解作业车间调度问题的陕速启发式算法 计算机集成制造系统，2 0 0 5，2(1 1)：2 3 7 2 4 2 7】K a c e mI，H a m m a d iS，B o r n eE P a r e t o-o p t i m a l 衄a p p r o a c hf o rf l e x i b l ej o b-s h o ps c h e d u l i n gp r o b l e m s：h y b r i d i z a t i o no fe v o l u t i o n a r ya l g o r i t h m sa n df u z z yl o g i c J M a t h e m a t i c sa n dC o m p u t e r si nS i m u l a t i o n，2 0 0 2，6 0：2 4 5 2 7 6 8 X i aWJ，W uZM A ne f f e c t i v eh y b r i do p t i m i z a t i o na p p r o a c hf o rm u l t i o b j e c t i v ef l e x i b l ej o b-s h o ps c h e d u l i n gp r o b l e m J C o m p u t e r&I n d u s t r i a lE n g i n e e r i n g，2 0 0 5，4 8：4 0 9 4 2 5 9 1H u r i n kE，J u r i s c hB，T h o l eM T a b us e a r c hf o rt h ej o bs h o ps c h e d u l i n gp r o b l e mw i t hm u l t i p u r p o s em a c h i n e J O p e r a t i o n sR e s e a r c hS p e k t r u m，19 9 4，15：2 0 5 215 万方数据柔性作业车间调度分析及其启发式算法柔性作业车间调度分析及其启发式算法作者：苏子林，苑金梁，陈炜，邱景炜，SU Zilin，YUAN Jinliang，CHEN Wei，QIU Jingwei作者单位：苏子林,苑金梁,邱景炜,SU Zilin,YUAN Jinliang,QIU Jingwei(鲁东大学交通学院,山东烟台,264025)，陈炜,CHEN Wei(宁夏公路管理局,银川,750004)刊名：计算机工程与应用英文刊名：Computer Engineering and Applications年，卷(期)：2012,48(10)被引用次数：1次 参考文献(9条)参考文献(9条)1.Tai J C;Ho N B Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems 20082.张根保 自动化制造系统 20093.Yiazdani M;Amiri M;Zandieh M Flexible job-shop scheduling with parallel variable neighborhood search algorithm 20104.Bagheri A;Zandieh M;Mahdavia I An artificial immune algorithm for the flexible job-shop scheduling problem外文期刊 2010(4)5.Hmida A B;Haouari M;Huguet M Discrepancy search for the flexible job shop scheduling problem 20106.张德富;李新 求解作业车间调度问题的快速启发式算法 2005(11)7.Kacem I;Hammadi S;Borne P Pareto-optimality approach for flexible job-shop scheduling problems:hybridizationof evolutionary algorithms and fuzzy logic 20028.Xia W J;Wu Z M An effective hybrid optimization approach for multi-objective flexible job-shop schedulingproblem 20059.Hurink E;Jurisch B;Thole M Tabu search for the job shop scheduling problem with multi-purpose machine 1994 引证文献(1条)引证文献(1条)1.薛宏全.魏生民.张鹏.杨琳 基于多种群蚁群算法的柔性作业车间调度研究期刊论文-计算机工程与应用 2013(24)本文链接：http:/