流水车间调度问题的一种启发式算法

-152-:[e-mail],weproposeanewheuristicalgorithmbasedontheanalysisandresearch,thenewmethodofintroducinganevaluatemechanismoftherelativepositionofanytwojobsatthecompletiontime,andtheefficiencyandperformancehasbeenimproved.Theresultofsimulationexperimentsshowsthat,ournewheuristicalgorithmhasgoodperformance,andtheaveragequalityandstabilityofschedulingsequencesgeneratedbythenewmethodaresignificantlybetterthanotherheuristicalgorithmwhichhasthesamecomplexity.Keywords:FlowShop;NEH;ProductionScheduling;HeuristicAlgorithm流水车间调度问题的一种启发式算法刘易麟中国石油四川销售分公司科研设计所，四川成都610000摘要：在过去的20多年中，NEH算法一直被认为是解决以最小完工时间为目的的流水车间问题的最好启发式算法，该算法在实际的工件调度中也得到了广泛的应用。近年来，在对流水车间工件调度问题的研究过程中，也有不少的启发式算法被提出，但是，这些算法提出的大多是对NEH算法的继承和改进，算法性能的提升并不明显。在对流水车间调度问题充分分析和研究的基础上，提出了一种全新的启发式算法，该算法引入任意两个工件的相对位置对于完工时间的影响比较机制，有效提高了算法效率和性能。仿真实验表明，新算法的性能和稳定性均优于包括NEH算法在内的经典和常见的构造型启发式算法。关键字：流水车间；NEH；生产调度；启发式算法引言流水车间调度问题是当前很多以流水线方式生产的制造业车间调度的抽象模型，也被证明是一个典型的NP完全问题[1]，具有很高的理论研究价值和实践价值。自从1954年Johnson发表第一篇流水车间调度（FlowshopScheduling）问题的文章以来，流水车间调度问题一直被很多学者所关注。总完工时间（makespan）是流水车间调度问题中的一个非常重要的性能指标，总完工时间最小可使得资源更加有效利用、任务更迅速传递及在制品库存最小。对于以最小makespan为目标的流水车间调度问题我们可以做如下描述：n个工件在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器，这n个工件通过m台机器的顺序相同，它们在每台机器上的加工顺序也相同；定义,ijO为第j个工件在第i台机器上操作，,ijp为,ijO的执行时间而,ijc表示,ijO的完成时间，其中1,2,,;1,2,,imjn；问题的求解目标是确定n个加工任务在每台机器上的最优加工顺序，使所有加工任务全部完工的时间最短。该问题通常需要作如下假设：每个加工任务在机器上的加工顺序为1,2,,m；每台机器同时只能进行1个加工任务；1个加工任务不能同时在不同的机器上进行；各任务在加工完后立即送下一道工序；任务在机器上开始加工，必须一直进行到该工序完工，中途不允许停下来插入其它任务；所有任务在0时刻已准备就绪，机器调整时间包括在加工时间内；允许任-153-务在工序之间等待；允许机器在任务未到达时闲置。而本问题的目标是找到一个所有工件的排列，使得makespan最小。通常，对以最小makespan为目标的流水车间调度问题的分析一般分为两种思路，求的最优解和取得次优解。求最优解一般使用的是动态规划法、分支定界法等方法，此类方法从某种意义上来说都是属于穷举法，只是在穷举的过程中根据一些计算结果排除某些明显不必要的计算。但是由于这些算法的搜索空间会随着工件数的增加呈指数式急剧增长，所以它们在解大规模问题上有着较大的局限性。正是在这种情况下，就产生了以求可行解或次优解为目的的启发式算法。启发式算法是相对于最优算法提出的，可作如下定义：一个基于直观或者经验构造的算法，在可接受的花费（时间、空间等）下，给出待解决组合优化问题的每一个实例的一个可行解，该可行解与最优解的偏离程度不一定可以事先预计。启发式算法以其计算量小、算法简单并且能得到较好的解而吸引了众多的研究者。启发式算法一般可以划分为元启发式算法[2~4]和构造式启发式算法[5~9]。通常情况下，元启发式算法获得的调度是优于构造式启发式算法，但却需要更多的机器时间和空间，在满足制造业生产车间实时性的需求上有一定的困难，因此，本文的研究重点将放在构造式启发式算法。目前经典的构造式启发式算法有Palmer[5]、Gupta[6]、CDS[7]、RA[8]和NEH[9]算法，其中又以NEH算法的性能为最佳。此外，近年来也不断有新的启发式被提出[10~13]，而多数是基于NEH的算法思想或是对其的改进。本文在综合考虑了多种影响流水车间makespan的因素的同时引入越韩定理[14]，提出了一种新的构造式启发式算法，而仿真实验表明在算法复杂度相当的条件下，新算法的性能优于NEH算法。1新的启发式算法本章将提出一种以最小makespan为目标的流水车间调度问题的构造式启发式算法，在对算法进行设计和描述之前，首先给出一些重要的定义和引理。1.1相关基本理论假设有n个工件在m台机器上加工（,1mn），如上一章的描述，使用,ijp表示第j个工件在第i台机器上的加工执行时间（1,2,,;1,2,,imjn），而在流水车间中每一个工件需要在每一个机器上进行加工，因此当加工顺序12{,,,}n确定后，所有的加工执行时间,jip可以由一个矩阵来表示，称作加工时间矩阵，记作矩阵P。1212121,1,1,2,2,2,,,,nnnmmmppppppPppp矩阵P的第i行表示第i台机器而第j列表示第j个工件，而i行j列对应的值为,jip。而对于一个特定的排列，可将加工时间矩阵在形式上简写为：1,11,21,2,12,22,,1,2,nnmmmnppppppPppp下面引入与本文算法相关的一些定义和定理[14]。定义1.将加工时间矩阵P的左上角与右下角用一条只能向右水平或向下垂直延伸的折现连接起来，以这样的方式构成的线称为可行线。例如，1L=(1,1p,1,2p,...,1,np,2,np,...,,mnp)即是一条可行线，而2L=(1,1p,2,1p,...,,1mp,,2mp,...,,mnp)是另一条可行线。而本文使用()L表示加工顺序为时的所有可行线集合。定义2.假设L为一条可行线，则定义,,()ijijpLp为可行线L的可行和。-154-使用()T表示在工件加工顺序为时所有工件的加工总时长，则有如下等式成立：,,()()maxijijLpLTp(1)证明：首先证明m=2的情况，因矩阵P仅有两行，故显然有：,,1,2,11maxmax{}ijsnijjjLsnpLjjsppp(2)当n=1时，总加工时间为1112aa，故等式(2)成立。假设等式(2)对n成立，现要证明等式(2)对n+1成立。显然，工件1nJ在机器2M上经历的过程只有两种：（1）工件1nJ在机器2M上不需要等待，可以立即被加工，此时有11,2,11(1,2,,1)njnjTnpp，2,1(1,2,,1)(1,2,,)nTnTnp此时有12,11,2,11(1,2,,1)max{(1,2,,),}nnjnjTnTnppp(3)（2）工件1nJ在机器2M上加工前需要等待，此时有2,1(1,2,,1)(1,2,,)nTnTnp，11,2,11(1,2,,1)njnjTnpp故也可推出式(3)成立，根据假设即得：111,2,1,2,1111(1,2,,1)max{,}snnjjjnsnjjsjTnpppp(4)故当m为2时，引理得证。再假设式(1)对m成立，工件jJ在机器mM上的加工完毕时刻为jT，而视1jjTT视为工件在mM上的加工时间，且它在机器1mM上的加工时间为1,mjp，则mM和1mM可视为两台机器的情况，此时有1,(1,2,,)max{}nsmjjsTnTp，由归纳假设，有,,maxskiskiLpTp其中的sL为连接1,1p和,msp的一条可行线，将上式代入式(4)，可得,,1,1(1,2,,)max{max}skinkimjsnLpjsTnpp。证毕。引理2.设工件序列(,,'',,,',,'')iiijjj，'为置换工件序列的i和j两列之后得到的新的工件序列'(,,'',,,',,'')iijijj，,,(,)uivjdpp为连接,,,uivjpp所有可行线的最大可行和，则有下述不等式成立：当,,,,(,)(,),1uivjujvidppdppuvm成立，则有()(')TT成立。证明：1,','',','',,1,','',','',,()max{(,)(,),(,)(,)(,),1,1}ikikimikikjiuivimiuivjTdppdppppdppdppdppkmuvm（5）1,','',','',,1,','',','',,(')max{(,)(,),(,)(,)(,),1,1}ikikjmjkikjiuivjmjuivjTdppdppppdppdppdppkmuvm（6）由条件可知,,,,(,)(,),1uivjujvidppdppuvm，比较式(5)和式(6)，定理得证。-155-台机器（,1mn）上加工，任意工件在每台机器上的加工时间矩阵P如上一章中的定义，仍然使用,ijp表示第j个工件在第i台机器上的加工执行时间，而使用jP表示矩阵P的第j列构成的向量（1,2,,;1,2,,imjn）。此外，根据上一节中引理2，定义如下参数：,1,(1,2,,)miijisumpjn,,,,,,,,,1,min(,)min(,)(,)0,min(,)min(,)1,uivjujviuivjujvippppRuvppppotherconditions,1,2,,;1ijnuvm上述参数中，isum表示加工时间矩阵P中的第j列之和，(,)Ruv表明两个工件之间的相对先后关系，若(,)1Ruv则u列在v列之前，而(,)0Ruv则u列在v列之后。将工件最终的排列记作，初始时为空。新的启发式算法描述如下：（1）按照矩阵P中各个工件的位置将所有列顺序放入序列'中。（2）寻找矩阵P中的两列iP和jP（0,ijn），使得这两列满足(,)1ijRPP或者(,)0i