作业车间调度问题的随机邻域交换算法

1、第25卷第1期2010年2月系统工程学报JOURN AL OF SY STE M S E NGI N EER I N G Vol .25No .1Feb .2010doi:10.3969/j .issn .1000-5781.2010.01.019作业车间调度问题的随机邻域交换算法崔健双,李铁克(北京科技大学经济管理学院,北京100083摘要:针对作业车间调度问题提出了一种随机邻域交换算法RNSA (rando m ne ighborhood s wapp ing algorith m .算法由几个紧密衔接的执行阶段组成,其核心思想是如何设计生成多样性调度以及如何判断新调度的可行性.为此,采用

2、了一种组合随机邻域交换策略并证明了一个调度可行性判定定理.为了验证算法的有效性,对一批Bench m ark 算例进行了测试并与国内外现有研究结果做出了比较.关键词:作业车间调度问题;随机邻域交换;关键路径算法中图分类号:TP273.1文献标识码:A 文章编号:1000-5781(201001-0111-05Rando m nei ghbor hood sw a pp i n g a lgor ith m for job shop scheduli n g pr oble mC U I J i an 2shuang,L I T ie 2ke(School of Econom ics and M

3、anage ment,University of Science &Technol ogy Beijing,Beijing 100083,China Ab stra ct:A r ando m neighborhood s wapping algorith m (RNS A is presented.The algorithm is co m 2posed of several interr e lated phases .Its key ideas a r e how to generate diversified s oluti ons and how t o judge if t

4、he ne w solutions a r e f easible .For doing that,we put f or ward a random neighborhood s wapp ing policy and pr ove a theore m which indicates the calculability of a s olution is the sufficient and necessary conditi on f or its f easibility .F inally,the algorith m was tested with a batch of B enc

5、h 2m ark p r oble m s and compared w ith existing a lgorithm s .Key word s:j ob shop scheduling pr oblem;random ne ighborhood s wapp ing;c ritica l path algorith m0引言作业车间调度问题是关于多类机调度问题的一类重要组合优化问题.文献1系统地总结了这类问题的研究进展.其中,采用遍历搜索的方法由于受时间和资源的限制难以有大的突破,而通过诸如邻域搜索2、混合遗传3-5、转移瓶颈加禁忌搜索6-7等近优求解算法是目前研究热点.本文提出的算法就

6、属于一种近优求解算法.算法的核心思想是如何设计生成多样性调度以及如何判断新调度的可行性,为此,采用了一种组合随机邻域交换策略来生成新的调度并证明了一个可行性判定定理来剔除不可行调度.对于不可行调度立即予以淘汰,以节省计算时间;对于可行调度则再利用关键路径算法做反复地局部优化,逐步逼近最优值.1问题模型设J =J i n i =1、M =M k mk =1分别代表由n 个工件和m 台机器组成的有限集合.工件J i 必须按照预先指定的顺序O i1,O i2,O im (优先顺序约收稿日期;修订日期5基金项目国家自然科学基金资助项目(:2007-10-27:2009-11-1.:70771008.束

7、在各台机器上依序加工.其中,Oik 表示工件Ji在机器M k上一次不可中断加工且加工时间p ik是已知的.同一个工件同时只能被一台机器加工,而同一时间一台机器只能加工一个工件(资源约束.若以C ik代表工件J i在机器M k上加工完成的时间,则最后一个工件在最后一台机器上加工完成的时间称为最大完工时间Cmax,即m akespan.设A代表受优先顺序约束限制的相邻工序对的集合;E k代表在机器k上加工并且受资源约束限制的工序对的集合.要求在满足优先顺序和资源约束条件下,对各个工件加工顺序进行调度排序并确定这些工件在各台机器上的开工时间rt ik0,以使得Cmax最小化,数学模型如下.M inC

8、max =M inm ax(rtik+pik(1s.t.rt jk-rt ikp ik,(i,jA(2rt jk -rtikpik或rtik-rtjkpjk,(i,jEk(3rt ik0(4其中,式(2表示J j必须在J i之后加工(优先顺序约束;式(3要求同一台机器同时只能加工一个工件(资源约束;式(4说明准备时间为0.2初始调度计算开始于一个初始调度.首先对每个工件按照其加工工序从小到大依次编号.在不考虑机器资源冲突的前提下,每个工件的第0道工序开工时间为0,其它后继工序的开工时间等于其前道工序结束时间,得到各道工序的开工时间,即无资源约束的最早开工时间.然后利用下述规则获得一个初始调度.

9、定义1开工顺序优先指派规则把需要在同台机器上加工的工件放在一起进行开工顺序优先指派,规则如下:1无机器约束最早开工时间小的优先;2若1相同,加工工序编号小的优先;3若1、2都相同则工件序号小的优先. 3计算m a ke span并做可行判断Make span的计算原则是:在给定调度下,根据当前机器和工件的空闲状态,选择最早可能被加工的工件立即开始加工在满足问题所有约束条件的前提下,当前机器上当前工件的最早开工及完工时间可按照如下公式计算对m,mM;q,kN,有rt m q=m axet m k,e t mqe t m q=rt m q+p m q(5式中,m、m代表两台不同的机器,q、k代表两

10、个不同的工件.rt mq表示当前工件q在机器m上最早开工时间,e t m q表示最早完工时间,p m q是加工时间.若给定的调度可行,则利用公式(5可以依次计算出每道工序的开、完工时间并最终得到m ake s pan.式(5称为m ake s p an计算公式.定义2对于给定调度,若能够按照公式(5计算得到所有操作的开工、完工时间,则该调度是可计算调度.引理1一个可计算调度是可行调度.证明因给定调度是可计算的,按照定义2,只需遵循公式(5即可得到所有操作的开、完工时间,包括m akespan.当在计算过程中由于e t m k或e t mq未知而影响到不能计算rt mq时,即转向下一台机器的当前

11、工件继续进行计算,直到完成为止.引理2一个可行调度是可计算的.证明使用反证法,假定可行调度不可计算,则意味着或者et m k或者e t mq是未知的,于是对某些操作来说不能获得它们的开工时间,影响到最终不能计算出makespan,而这与调度可行相矛盾.由引理1和引理2有下列结论.定理一个给定调度的可计算性是其可行的充要条件.由此,仅需要判断一个给定调度是否能够计算出所有操作的开工时间,即可知晓该调度是否可行.下面对于有M台机器N个工件的作业车间调度问题,给出具体实现步骤:步骤0在M台机器中选择第m台作为当前机器;步骤1从m中选择当前工件q;步骤2判断et m k和e t mq是否都已知:若已知

12、,令rt m q=m axe t m k,et mq,e t m q=rt m q+p m q,qq+1,转步骤1;否则,转步骤3;步骤3判断m=M?若是,m0,转步骤4;否则,mm+1,转步骤1;步骤4通过对M台机器一轮循环计算后,比较是否每台机器当前工件编号都无变化若是,做调度不可行标记,算法结束;否则,转步骤5;步骤5判断各机器所有工件是否全部计算211系统工程学报第25卷.完成.若是,返回最大完工时间m ake span;否则,转步骤0.4产生新调度并做局部优化搜索随机邻域交换产生新调度的规则如下:1交换可发生在同台机器任意两个相邻操作之间,这样可避免产生过多的不可行调度,减少无效交换

13、;2每台机器每次仅允许发生一次交换;3考虑到多个操作之间存在的隐性耦合关系,以工件号、操作位置和加工步骤等已知参数对交换条件进行限制,满足条件的操作才与其后继操作发生交换.表1Ben chm a rk测试用例TA01TA50测试结果比较Table1Test res u lts and comparis on on Benchmark p roble m s TA01T A50问题规模最优(上界TSS B6RE(%TS AB7RE(%S B2G LS59R E(%HPS O10RE(%R NS A R E(%T A0115×1512311241018112441106123601411

14、2420189 T A0215×1512441244010012440.00125501881245010812440100 T A0315×1512181222013312220.33122501571224014912180100 T A0415×15117511750100119111361180014311750100 T A0515×1512241229014112330174125621611233017412300149 T A0615×15123812450157124701731248018112390108 T A0715&

15、#215;15122712280108124411391229011612280108 T A0815×1512171220012512200125122201411220012512170100 T A0915×1512741291113312820.63129111331283017112800147 T A01015×151241125001731259 1.45126621011264118512440.24 T A11320×15135913710188140231161386119913731103 T A12320×1513671

16、379018813770.731416 3.5813800.9513770.73 T A13320×151342136211491377 2.6113641.6413540.89 T A1420×1513451345010013450.001361 1.1913500.3713450.00 T A15320×151339136011571383 3.2913641.871353 1.05 T A16320×151360137001741418 4.2613771.2513680.59 T A1720×151462148111301519 3.9

17、014801.231480 1.23 T A18320×151396142621151413 1.221433 2.6514252.081412 1.15 T A19320×151335135111201352 1.271376 3.0713531.3513440.67 T A20320×151348136611341362 1.041398 3.7113731.851363 1.11 T A21320×201644165901911692 2.9216792.1316580.85 T A22320×201600162311441638 2.3

18、816251.561618 1.13 T A23320×201557157311031594 2.3815781.3515660.58 T A24320×201646165901791714 4.1316641.0916540.49 T A25320×201595160601691631 2.2616322.3216000.31 T A26320×2016451666112816570.731698 3.2216792.0716570.73 T A27320×201680169711011722 2.5017121.9016910.65 T A

19、28320×201603162211191653 3.1216271.501620 1.06 T A29320×2016251635016216290.2516390.8616451.2316290.25 T A30320×201584161411891621 2.3416131.831601 1.07 T A3130×1517641771014017660.111809 2.5517720.4517660.11 T A32330×151795184021511841 2.561840 2.5118482.951826 1.73 T A3333

20、0×151791183321351832 2.291844 2.9618342.401818 1.51 T A34330×151829184601931898 3.7718792.7318360.38 T A3530×1520072007010020100.1520100.1520070.00 T A3630×151819182501331874 3.0218431.3218230.22 T A3730×151771181321371815 2.481846 4.2318082.091796 1.41 T A3830×15167316

21、9711431700 1.611762 5.3217011.6716890.96 T A3930×1517951815111118110.891822 1.5018100.8418060.61 T A40330×151674172531051720 2.751749 4.4817142.391698 1.43 T A41330×202018204511342106 4.3620712.632053 1.73 T A42330×201949197911542018 3.5419841.801978 1.49 T A43330×2018581898

22、21151946 4.7419283.771893 1.88 T A44330×201983203621672069 4.3420392.822013 1.51 T A45330ࡨ.4520321.602021 1.05 T A46330×202015204711592115 4.9620702.732039 1.19 T A47330×201903193811841973 3.6819582.891932 1.52 T A48330×201949199621412001 2.672080 6.72202

23、23.751979 1.54 T A49330×201967201321342046 4.0220152.441991 1.22 T533×6515335656平均相对误差(R%1111651注带3表明是目标函数值的上界而非最优值;注TSS B、TS B、S B2G L S S,S O为相应文献提出方法的最优值或上界,其相邻列的R为其平均相对误差311第1期崔健双等:作业车间调度问题的随机邻域交换算法A0020192197242009 4.11998.7419 1.A E122114287108212A H P E.根据上述规则,当问题的相关参数满足如下逻辑关系时发生交换:

24、I F (seq_num =r Op rt AND(p r o_o rde r=rStep OR (job_num=sJob THENOr O p rtOr Op rt+1其中,seq_num 是当前机器上加工工序位置;p r o_orde r 是加工工序编号;job_num 是工件编号.后两个参数都是确知值.r Op rt (N -1、rStep (M 和s Job (N 是约定范围的三个随机数.如果说产生新调度是全局范围内的调整变化,局部优化搜索就是小幅调整.本文采用的局部优化搜索策略是对文献8中的关键路径算法(C P A 的改进.改进的C P A 增加了对一个关键块有3个操作的处理方法,

25、即如果一个块中有3个操作,单独做两两交换并选用二者中较好的结果.5算法实现步骤步骤0利用优先指派规则产生初始调度,计算m akespan 作为当前目标函数最优值B estValue;步骤1产生一个新调度;步骤2判断新调度的可行性:若可行,转步骤3;否则,恢复原调度并判断是否达到设定循环次数;若是,停止计算并输出最终结果;若否,转步骤1;步骤3利用改进的C P A 对新调度作局部优化搜索,此时B est Va lue 总是保留最优值,转步骤1.算法中间临时产生的调度都会经过比较后被淘汰,每次仅保留最优调度,因此空间复杂度可忽略不计.算法的计算量,即时间复杂度主要在步骤2、步骤 3.针对此类问题的

26、算法一般采用B enchm ark 问题计算结果的比较来做出评价.6算法效果分析与比较选择了不同规模的80个B enchm ark 算例TA01TA80对算法的效果进行测试.使用C 语言编程、主频1.5G H z 的I B M ThinkPad T40进行计算.因计算结果中T A51T A80(除T A55外都达到了目标函数最优值,表1中仅列出了T A01TA50的计算结果.由T A 系列算例计算结果分析可知:1近44%的算例可获最优值,前50个算例的平均相对误差为0.82%,是参与比较的所有算法中最低的.2为了体现普遍性和公平性,表1数据是在相同环境下对每个算例进行了5遍测试的平均值.3算法

27、也曾对较容易计算的算例做过计算.例如,对于LA01LA15和LA31LA35,在既有环境下,每5个算例一组连续进行计算,每组总计算时间都不超过1s .4对于规模超过2000(N =100,M =20的10个算例T A71TA80,都能够在较短时间内(平均4.3m in得到最优值.5与文献4-6中提出的算法计算结果的比较也表明,RNS A 算法有明显优势.7结束语本文提出了一种组合条件随机邻域交换算法并证明和编程实现了调度可行判定准则,指出可计算性是调度可行的充要条件.可行判定及时淘汰了无效调度,提高了计算效率.算法还成功地引入了改进的CA P,实现了局部邻域优化搜索,对提高算法的搜索深度起到了

28、重要作用.B enchm a rk 测试用例的计算结果证明了算法的有效性和可靠性.参考文献:S,M S D j ,f f O R 2,3(33王磊,黄文奇求解工件车间调度问题的一种新的邻域搜索算法计算机学报,5,(56411系统工程学报第25卷1Ja i n A eeran .ete r m in istic ob shop sch ed u ling:Past p re sent an d u t u re J .E u r op ean Jo u rna l o p e ra ti o na l e search 1999112:90-44.2.J .20028:809-81.Wang L

29、ei,HuangWenqi .A ne w l ocal sea rch a l gorith m for j ob shop scheduling p roblem J .Chine s e Journal of Co mputers,2005,28(5:809-816.(in Chine se 3Jo s éF G,Jorge J M M ,Maor íc i o G C R.A hybrid geneti c algorith m for the j ob sh op s cheduling p roblem sJ .Euro peanJournal of Opera

30、ti on R esearch,2005,167(1:77-95.4B yung J P,Hyung R C,Hyun S K .A hybrid genetic a lg orith m for the j ob shop scheduling problem sJ .Compute rs &In 2dustri a l Enginee ri ng,2003,45(3:597-613.5Federico D C ,Robe rto T,Guiseppe V.A gene tic a lg orith m for the j ob s hop problem J .Co mputers Operati