搜索
第46卷第21期2010年11月机械工程学报JOURNALOFMECHANICALENGINEERINGVol.46No.21Nov.2010DOI：10.3901/JME.2010.21.165Job-Shop调度问题的分批和最优化策略陈进王荣(江南大学机械工程学院无锡214122)摘要：缩短Job-Shop生产的工期除了用优化调度方法外，还可以对批量进行适当的分割，进一步优化生产计划。论述一种简化的Job-Shop批量分割的优化调度的方法，解决分批调度的原则、位置和对工期影响等问题，提出分批的步骤和方法。根据工艺路线的约束，用状态变量描述调度过程，在此基础上用一种启发式的算法进行通常的优化调度，在此调度计划中用一种算法找出工期最长的关键路径。分批应遵循3个规则：①分批的步骤是先优化后分批；②分批应该在这样的一个设备上，即该设备—任务完成后其加工路线上的下一个设备应该有空闲时间；③该任务工序及其后续工序至少有一个位于关键线路上。将任务—工序的等待空闲时间和回溯等待时间与当前工序和后续工序的工时等分后的可能节约工期比较，决定此处是否可以分批及其分批的大小。分批和优化达到了目标——最长工期最小。关键词：Job-Shop优化算法调度批量分解关键路径中图分类号：TP278LotSplittingandOptimizationStrategyforJob-ShopSchedulingCHENJinWANGRong(SchoolofMechanicalEngineering,JiangnanUniversity,Wuxi214122)Abstract：ToshortenmakespanofJob-Shopproductioninadditiontotheoptimizationschedulingmethods,lotsplittingmayalsobeutilizedopportunelyforfurtheroptimizingtheproductionplan.AsimplifiedlotsplittingJob-Shopschedulingoptimizationsolutionispresentedandtheprinciple,location,impactontheproject,thestepsandmethodsareexpounded.Accordingtotherestraintoftheprocessroute,statevariablesareusedtodescribetheschedulingprocess,basedonwhich,aheuristicalgorithmisadoptedforoptimalscheduling.Thelongestcriticalpathintheoptimalschedulingisfoundoutwithakindofalgorithm.Threerulesshouldbefollowedinlotsplitting:①Afteroptimizingschedulingfirst,splittinglot.②Splittinglotshouldbechosenatsuchanequipmentthatthenextequipmentonitsprocessrouteshouldhavefreetimeafterfinishingthetaskattheequipment.③Theequipment-taskandatleastoneofitsfollow-upprocessesareonthecriticalpath.Comparingjob-processwaitingtimeandtrackbackwaitingtime,thepossiblesavingmakespanbetweenpresentprocessandthefollow-upprocesses,thelocationandsizeoflotsplittingaredetermined.Thelotsplittingandoptimizationreachthegoalthatthemakespanisminimized.Keywords：Job-ShopOptimalalgorithmsSchedulingLotsplittingCriticalpath0前言*在不增加生产资源的条件下，对生产批量进行分批可以改变生产的进程。早期批量分解是为了满足场地、运送和交货期的局部要求，一般由管理人员凭经验进行简单的分批，其控制功能非常有限而且不可靠。批量调度问题十分复杂，只有实现了生产计划的信息化，才能具备全面的优化分批问题的20091204收到初稿，20100728收到修改稿条件。人们认识到合适的分批可以用极小的代价明显地改善离散型生产的设备利用率和加工周期，因此吸引了不少学者进行认真的研究，取得了一些成果。JEONG等[1]采用启发式方法来研究单一路径的动态批量分解车间调度，把生产分为非切削时间和加工时间，安排每一个任务为一批次，然后分批次和根据规则依次做出调整。潘全科等[2]利用遗传算法，提出了最小的加工批次和分批算法，该算法根据加工优先级优化了生产周期。中国台湾学者LOW机械工程学报第46卷第21期期166等[3]研究了生产车间分批调度的很多优点。他们进行了对等和不对等的分批策略的比较研究，认为很多合理的等量分批调度是可以减少完工时间和成本的。RABBI等[4]提出一种网络系统的方法，考虑零件的相似性、可变的提前期和资源，采用关键路径法和成组技术使物料需求计划更加有效和真实，易于实现启发式算法。张晓东等[5]讨论了一类同时优化并行生产线的批量分解和调度的问题，并构造了基于批量传递模型的启发式方法的遗传变异因子，提出了分批启发式算法。CHEN等[6]使用多种批量规则的组合解决多目标的调度问题，提出了一种启发式算法，通过调整多目标的权重生成统一的优先级。根据调度方法类别，主要的调度建模方法可被归类为分析的、启发式的和人工智能的三类[7-8]。分析方法是基于数学分析的，如线性规划、排队理论、分支定界算法和动态规划等[9]。启发式法通过分析计算过程和评价指数，有意识地寻找最优，在短时间内找到接近最优的方案[10]。人工智能包含三组基本方法：专家系统、人工神经网络和邻域搜索算法[11]。笔者认为启发式算法的效率总体优于其他算法，但是必须寻找到优良的启发式规则，分批问题的规则要素是关键线路和分批效益的寻找和评价。1基本建模机械加工通过多道工序，在不同的设备上完成加工过程，这些任务经过设备所构成的工艺路线可被视为不同的加工链。Job-Shop生产遵照工艺矩阵R进行批次作业。分批规则是把一个任务分为多个同工艺路线的任务。为描述该过程，设定如下参数：i为任务编号，i=1,2,…,n(下同)；j为设备编号，j=1,2,…,m(下同)；tji为i任务在j设备加工的加工时间，(tji)m×n=T；rji为根据加工路线i任务在j设备里加工的加工顺序，(rji)m×n=R；egi为任务i在加工路线的次序为g的加工设备号，g=1,2,…,m，(egi)m×n=E，g表示加工的顺序号；xji为i任务在j设备里加工的开始时间，(xji)m×n=X，X称为状态矩阵；yji为i任务在j设备里加工的完成时间，(yji)m×n=Y，Y称为输出矩阵。定义1：完工时间是在没有任何中断的调度计划中最长的加工链的时间长度。如果i任务被分为k个子任务，那么任务就由n个变为n+k个。(+)()jimnk=r×′′R，(+)()jimnk=x×′′X。任务i就派生为任务i1,i2,…,ik。假设任务i1,i2,…,ik的批量是相等的。定义2：关键路径(Criticalpath，CP)是连续的没有任何中断的调度计划中的最长加工链，其时间长度等同于完工时间。关键路径表示如下11122233,,,,...lHhhHhhHhhHλαηλιλιλβδλελελϕβλχλχλγμ=式中，H表示由多个设备和任务组合组成的一条子链，h表示一个设备和任务组合，λ表示设备的编号，λ的上标表示在该关键路径中其后设备的距离该字母所示设备的位置序数，如λ1表示λ后面的第一个设备；H或h的下标的其他部分表示任务的编号。定义3：提前期表示任务加工从开始到任务完成的时间段。如果把一个单一的任务分为z个子任务，而且这些子任务的加工是不间断地沿着加工路线加工的，令a～c表示该任务的工艺顺序号，ta～tc均为对应的工艺顺序号的加工时间，设tb为该任务的工艺路线中加工时间最长的工序的加工时间，那么该任务的完工时间1cabbbttDtttzzλλλ=+=++∑,acλ∈{}bλ≠abc(1)式(1)可以推导出一个任务分批后最大可能减少的提前期为(11/z−),cbatλλλ≠=∑，如图1所示。图1CP和完工时间设H为计算过程中的关键路径的加工顺序链，已知一个排产计划时，寻找CP链的算法如下，其中“⊕”表示链接hxx和H。(1)算出最长的输出变量max{}fjiyyη=,令f=hHη，Г=xfη，ε=1。(2)令i=1，i≠η,ε=0，循环执行{如果Г=yfi，则fiH=hH⊕，且ε=1，Г=xfi,η=i，退出循环，月2010年11月陈进等：Job-Shop调度问题的分批和最优化策略167调用自身步骤(2)；否则i=i+1}，直到i=n。如果ε=0且Г0，即没有Г=yfi，说明没有任何任务在设备f上被安排在任务η的紧前排产，则ε=2，转步骤(3)。如果ε=0且Г=0，则转步骤(4)。(3)令j=1，j≠f，ε=0，ω=Г,循环执行{如果Г=yji，则jiH=hH⊕，且ε=1，Г=xji,η=i，f=j，退出循环，转步骤(2)；否则j=j+1}直到j=m。如果ε=0且Г=0，则转步骤(4)。(4)CP就等于H，例如，1112hhhλη的完工时间就等于1112tttλη+++。2策略2.1最优化定义4：团子运动表示为由一个任务分解的相同的子任务不分割地在设备间加工或转移的过程。推论：在已经最优化调度计划里，如果一个在CP上的任务经过分批减少的完工时间达到了这种分批方式可能达到的最大值，那么该分批模式比其他的调度计划中的相同的分批模式有更短的完工时间。证明：假设i任务在j设备分为z个子任务，其下一台设备为j+1。原来的两个加工工序的提前期是tji+tj+1i，如果tjitj+1i，新的两个加工工序的提前期由公式(1)得1/jijitzt++，这就减少了(1)/jiztz−时间。因为任何最优化调度计划的完工时间，短于其他调度计划，而这两种调度计划分批后都减少相同数量的完工时间，因此优化后的分批方式有更短的完工时间。证毕。规则1：调度分批的步骤，首先是最优化，然后分批。启发式方法用于优化调度，如果要由调度缩短完工时间有3个因素需要考虑：尽快安排任务进行加工；尽早使任务完工转换至其他设备上；安排有较长剩余的加工时间的任务尽早加工。第一个因素要求安排符合条件的任务进行尽早投工；第二个因素要求及早安排在相同设备上用时更少的任务；第三个因素要求及早的安排较多的剩余加工时间的任务。“*”被定义为一个算子。如果j=egi，j*h=egi*h=eg+hi，h=1−g,2−g,…,1,2,…,m−g，0hm≤≤。三个因素的评价指数设定为(1)1minmgjijijijhihVytt−∗−∗=⎧⎫=+−⎨⎬⎩⎭∑(2)Vji表示在同一台设备j且相同的加工顺序号g下的所有任务，计算和比较其(1)1mgjijijhihytt−∗−∗=⎧⎫+−⎨⎬⎩⎭∑所得到的最小值。调度最优化算法如下。(1)根据矩阵R，算出矩阵E。(2)g=1，设备j=egi。(3)在同一个g内，设备被指定后，其不同任务可根据式(2)进行次序安排。Vji越小，其次序就越在前面。(4)计算状态矩阵和输出矩阵{}#*(1)max,jijijkxyy−=(3)如果加工开始在0时，而且g=1，则xji=0，j=e1i；其中#min{|}jk