（运筹学与控制论专业论文）一种平行机流水作业问题的解法taboosearch方法.pdf

摘要 孓3 6 2 8 3 本文提出了一种特殊的机器排序问题即异类机的流水作业 问题，它是平行机流水作业问题的推广，这种问题由于与异类机 有关，目前国内外对此类问题的研究文章则很少，即使有的也 只是在一些非专门文章中寥寥数语带过，没有实质性讨论；但 它却是实实在在要经常遇到的问题，不能回避，而且很多实际 问题如汽车路线问题、运输问题等都可以归结为它的特例，因 此对这个问题的研究有很大的实用价值；平行机的流水作业问 题被认为是两类排序问题一一流水作业问题和平行机问题的推 广，本文对目标函数是一种求最小完工时间的平行机的流水作 业问题给出了一种快速有效的t a b o os e a r c h 近似方法，该算法 是基于一种特殊的邻域定义一一应用了图上关键路和工件块概 念，并给出了加快邻域搜索和算法速度的补充方法；根据上机 实验得出的计算结果表明该方法是切实可行的该方法也可以 推广应用到很多其它流水线的排序问题。 关键词：排序；流水作业；平行机：t a b o os e a r c h 算法。 a b s t r a c t t h i sp a p e rd e a l sw i t has c h e d u l i n gp r o b l e mc a l l e dt h ef l o ws h o pw i t hu n r e l a t e d p a r a l l e lm a c h i n e s ( f s p m ) f s p mi s c o n s i d e r e da sa l le x t e n s i o no ft w oc l a s s i c a l p r o b l e m so ft h es c h e d u l i n gt h e o r y , n a m e l yt h ef l o ws h o pa n dp a r a l l e lm a c h i n e s p r o b l e ma n dc a nb eb r i e f l yd e s c r i b e da sf o l l o w s ：t h e r ei sas e to f j o b sa n das e to f p r o c e s s i n gc e n t e r s e a c ho fw h i c hh a sas e to fu n r e l a t e dp a r a l l e lm a c h i n e s ，aj o b c o n s i s t so fas e q u e n c eo fo p e r a t i o n sp r o c e s s e da ts u c c e s s i v ec e n t e r s ，a n da l lj o b sp a s s t h r o t l 曲c e n t e r si nt h es a m eo r d e ra tt h ec e n t e laj o bc a nb ep r o c e s s e do i la n y m a c h i n e w ew a n tt of i n das c h e d u l et h a tm i n i m i z e st h em a k e s p a n ，o n eo ft h e m o s tf r e q u e n t l yu s e d s c h e d u l i n g c r i t e r i at h ep a p e r p r e s e n t s af a s ta n d e a s i l y i m p l e m e n t a b l ea p p r o x i m a t i o na l g o r i t h m f o rt h e p r o b l e m o ff i n d i n gam i n i m u m m a k e s p a ni naf l o ws h o pw i t lu n r e l a t e dp a r a l l e lm a c h i n e s t h ea l g o r i t h mi sb a s e d o nat a b o os e a r c ht e c h n i q u ew i t has p e c i f i cn e i g h b o r h o o dd e f i n i t i o nw h i c he m p l o y s n o t i o n so fac r i t i c a lp a t hi nag r a p ha n dab l o c ko f j o b s a s p e c i a la d v a n c e dm e t h o d o f i m p l e m e n t a t i o ni m p r o v e st h el o c a ls e a r c hs i g n i f i c a n t l ya n di n c r e a s e st h es p e e do f t h ea l g o r i t h m c o m p u t a t i o n a le x p e r i m e n t ss h o wi t s e x c e l l e n tn u m e r i c a lp r o p e a i e s t h e p r o p o s e da p p r o a c hc a nb eu s e df o rm o d e l i n ga n ds o l v i n gab r o a dc l a s so f f l e x i b l e f l o wl i n es c h e d u l i n gp r o b l e m s k e y w o r d s ：s c h e d u l i n g ；f l o w s h o p ；p a r a l l e l ；t a b o os e a r c ha l g o r i t h m 2 l 、引言 机器排序( m a c h i n es c h e d u l i n g ) 理论起源子二十世纪五十年代的工业制造 业。它是运筹学的一个较年轻的分支，同时也是实际中应用最广泛的运筹学分 支之一，不仅在工业管理与制造，而且在农业、自然资源与环境、交通、计算 机控制领域乃至日常生活中都有很强的应用背景；它已受到越来越多的科研人 员的重视。 在阐述本文问题之前，先介绍以下两类排序问题： 1 平行机问题：平行机问题的一般形式是： 有n 个工件和m 台机器，每个工件都只有一道工序，且工件可以在任何一 台机器上加工，目的是在皿台机器上寻找一个这1 7 个工件的分配，使得与这组 工件有关的某一目标最优。 由于机器性能的不同，平行机问题分为三种类型： 同型机：所有机器的性能完全相同同一工件在任一台机器上的加工时 间是相同的。 同类机：除了机器的速度不同外，其余指标均相同同一个工件在各台 机器上的加工时间只与机器的速度有一个比例关系。 异类机：机器的各种性能都可以不同同工件在每一台机器上的加工 时间是相互独立、彼此没有关联的。 2 流水作业问题：这种排序问题的一般形式可以归纳如下： 有力个工件和m 台机器，n 个工件以同样的加工顺序在皿台机器上加工( 即 每个工件通过机器的顺序是一样的) ，目的是寻找这样一种排序，使得所求目标 最优。 本文提出了目标函数是求最大完工时间最小的平行机的流水作业问题，而 且平行机是异类机。对这种问题的专门研究目前还没有在国内外的文章中见到 过；平行机的流水作业问题被认为是以上两类排序问题一流水作业问题和平行 机问题的推广。 异类机的流水作业问题可以描述为：有一批工件集合和一个机器中心集合， 每个中心都有一个平行机( 异类机) 集合，每个工件都要依次在每一个中心被 加工一次，所有的工件通过每一个中心的顺序是相同的，在一个机器中心里， 一个工件可以在任何一台机器上加工，我们的目的是寻找这样一个排序，使得 最大完工时间最小( 排序问题常用的目标标准) 。 由于该问题是强 脚崖的，所以限制了解决该问题的方法。与该问题比较接 近的排序问题是平行机( 同型机) 的流水作业问题“5 】f 1 ，这个问题也是 严难 的。 卿隹问题的常用解法是：1 比较精确的分枝定界和动态规划方法；2 近似 方法。近来比较常用的近似方法可以分成两类：构造型的方法和改进型的方法； 迄今为止较好的与该问题有关的构造型方法是：c a m p b e l l 等 d a n n e n b r j 口一“月dc ka n ds c h m i d t e 3 3 和n a w a z 等“】改进型的方法包括：下降 搜索法1 2 , 5 1 ；模拟退火方法 6 7 】；t a b o os e a r c h 方法1 8 ，9 1 以及遗传算法1 1 0 改进 性方法也被用来解决本文所提出问题的特例；比如只有两个中心，而且机器是 同型机；再比如机器中心集合里只有一个中心是周型机，其它每个中心里都只 有一台机器等等。异类机的流水作业问题还可以推广到很多其它情况，比如机 器之间有停工间隔、工件之间有搬运间隔等等：与异类机流水作业问题比较相近 的同型机的流水作业问题已有文章讨论过解法，但是对异类机的流水作业问题 却没有在国内外的文章中见到，下面提出一种以t a b o os e a r c h 为基础的改进方 法可以解决上面的问题，该方法采用了一种特殊的邻域，在邻域中应用了图上 的关键路和工件块的概念。在给出具体方法之前，先介绍t a b o os e a r c h 算法 和一些概念 t a b o os e a r c h 算法是近年来发展起来的一种求近似最优解的新算法。它已 经被广泛应用到许多 卿隹的组合优化问题的近似算法中，如已被应用到解决旅 行售货员问题r 彤力，车辆路线问题( v r p ) 等。 t a b o os e a r c h 方法的基本思想：它是一种邻域搜索方法，在求解最优解的 过程中，为了防止盲目搜索和重复搜索，同时为了增加搜索效率，不仅需要对 搜索范围的一些局部信息，而且还要对搜索过程中的一些信息有所了解，同时 也是为了给下次搜索提供决策方法，需要将搜索过程的这些信息记录下来。这 就是t a b o os e a r c h 方法的基本思想。 用t a b o os e a r c h 算法求这个问题最优解或近似最优解的过程是：从可行域 5 的所有点里按照一定标准选一个比较好的称为初始解的点，然后从这个点 出发搜索移动到s 中的另一点，点的搜索移动是按一定的规则进行的，这样的搜 索移动一直到满足停止搜索条件为止。这时所得的点希望能够成为最优解，或者 至少是在所搜索到的范围内是近似最优的；因此要规定一些搜索移动所遵循的 基本原则，这些原则是可以根据不同的问题、不同的目标函数和不同的需要来制 定的，下面列举几条搜索过程中经常用到的一些基本原则。 初始序列或初始解。 用构造性方法或其它方法再在可行域中选一点作为迭代起始点。 产生邻域的方法。下面介绍三种常用产生邻域的方法： 先假定原来怕痒列为( a8cdefgi t ) ， 1 相邻交换：如f 彳b 口fff 占t tj 就是一个相邻交换邻域。 2 插入邻域：即把某一工件从原位置移到另外一个位置，如： fa 占口c 口f 口) 和rabc 口f 口占1 1j 是两个插入邻域。 3 交换邻域；即交换两个不一定相邻的工件，如f 爿fc 口f 曰口， 是一个交换邻域。 邻域的选取在t a b o os e a r c h 方法中起着至观重要的作用， ( 固t a b o ol i s t 为了避免算法出现循环，或者陷入局部最优解以及使得搜索方向朝着解空 间中还没有被搜索过的区域进行，运用t a b o ol i s t 记录最近搜索过程的一些 属性，例如记录不能使目标值改进的点等，当点在t a b o ol i s t 里时，称此点 为 t a b o o 点t a b o o 点将受到限制，不能成为下一次搜索迭代点运用这个原则往 往可以限制那些不合理的点作为搜索迭代点t a b o ol i s t 的长度可以固定， 也可以变化，视具体情况而定。 停止搜索原则 搜索过程应有一个结束条件，当满足这个条件时，整个搜索就结束。 下面是几个常用的停止搜索原则： 1 当邻域集合中的元素个数为零时； 2 自最后一次开始，迭代次数大于允许迭代的最大次数时； 3 有证据表明最优解已经找到时。 运用t a b o ol i s t 时，有时会发生好的搜索点被遗漏或者陷入局部极小的现 象，从而影响了最终搜索到的近似最优解的优劣程度。因此在应用t a b o ol i s t 基本原则的同时，还要附加一些有用的补充方法： a s p i r a t i o n 准则： 如果某一个t a b o o 移动满足一些条件( 视问题、目标等定) ，则该移动被认 为是可行的，比如如果一个r a b o o 移动后得到的序列的目标值比目前得到的最好 的值还好的话，则该移动被接受。 集中搜索策略： 当确定最优解就在某个邻域附近时，为了加快搜索速度，应对这一区域进行 集中搜索这是在比较好的区域里搜索时常用的方法，如从以前最好的解或几乎 最好的解开始从新搜索时或者其它需要用此方法时就要用该方法。 分散搜索策略： 有时不能确定最优解的范围，因此在确定最优解的大概范围时就采用分散搜 索方法：这是为了使移动朝着还没有被搜索过的新区域搜索时的方法。 本文的内容结构安排如下： 第二节给出本文提出问题所采用的模型，并对一些概念加以定义。 第三节详细地介绍了本文所用的t a b o os e a r c b 方法。 第四节在综合第三节所用的t a b o os e a r c h 方法的基础上给出具体算法以及一 些补充方法。 第五节给出算法的结果及对算法的评价。 最后在第六节给出了一些结论。 4 2 、问题定义、概念及模型 在t a b o os e a r c h 方法中，每步迭代解的质量与所选择的模型有很大关系。 本文对m 个机器中心，1 7 个工件的异类机的流水作业问题，我们建立如下模型： 流水作业方向 在该模型中： 有0 1 个机器中心，每个中心0 中有m ，( 1 ) 台异类机，中心集合由肛化，彬 表示，中心口中的机器集表示为埘= 儿，啦，。n 个工件的集合表示为 k n ， 月，每个工件都按相同的顺序lz ，i n 通过中心，因此每一个i j , d e n , 都有儡 道工序组成，用p o 。( o ) 表示工件在中心0 的朋。台机器中机器j 上的加工时 间在中心0 ，工件l ，可以在玛台机器的任一台上加工，每一台机器在任何时刻只 能加工一个工件，任一工件在任何时刻至多只能在一台机器上加工一个可能的 排序由集合对“。g ， e 膨表示f 。，辑是中心e 上加工工件j 的机 器；g 害绳工件在中心0 的，机器上的完工时间，称满足上述条件的解为可 行解我们的目的是寻找可行的排序，使得最大完工时间m a x ，e c 。最小。 例1 假设系统有3 个中心，第一个中心和第二个中心各有两台机器，第三个中心有三 台机器，即m 。= m ：= 2 ，m ，= 3 ，有七个工件要在该系统中加工，每个工件在各 台机器上的加工时间如下表所试示： 3 3 4 p l l j 6 0 5 0 6 0 4 0 3 0 4 0 5 0 3 0 4 0 1 0 2 0 4 0 5 0 6 0 5 0 3 0 3 0 4 0 4 0 5 0 6 0 4 0 3 0 5 0 6 0 5 0 4 0 6 0 3 2 2 6 7 p l i j 3 0 2 0 1 0 0 1 1 0 8 0 7 0 6 0 4 0 3 0 5 0 4 0 3 0 2 0 4 0 7 0 8 0 5 0 4 0 l l o 9 0 1 0 0 6 i 1 2 1 2 1 2 3 l 2 1 2 1 2 3 l 2 l 2 l 2 3 1j r 0 i 1 2 1 2 1 2 3 l 2 l 2 1 2 3 l 2 l 2 1 2 3 l 2 l 2 l 2 3 j，l 0 l 2 3 其中一个可行的排序如下图所示： 中心机器 111 23 24 l 567 21 l 4j61 。 夺3 257 316 4 3 2 215 i 37 l 1 1 0 0 i1 5 0 i2 12 4 c |3 1 1 下面介绍两个重要的概念：批和关键路 批：对于每一个中心，将个工件分配到该中心的所有机器上，每台机器 上的工件集就称为一个批：每个中心口就有岛个批，口中心中机器上的批用 记号以，表示，川， 巩，艇批川j 上工件的个数记为1 1 t ，= l 川，l ，f e 堪，0 膨显然有 ：，n 。= n 。这样机器，上的加工顺序可以表示为? 巧，= 伍，f 砂一，碣，瓴j e p 似，其中：巧，阮) 表示批佴，上在排列碣，中第k 个位置上的元素，尸“，是n l ； 的所有可能的排列集合因此，中心0 上的加工顺序可以表示成这样的玛个排列 集：乃= ，乃一，石。，每一排列与一个批相对应，工件的加工顺序由下式表示： r g = ，蜀，r g 。? ，这样整个系统的加工顺序可用下面集合表示： n 2 a = 冗p 。珏j ：狂i = 死h 冗j m ? 1 r i p ( 心i ) 1 e k d ( k f ，i 辑畏a 蒹旨 的一个分割) ，口锄 这样给定一个# e l i , 工件的完工时间可用下面的迭代公式在0 ( r i m ) 时间 内求出： c t j e 。啼1 2 m a x c cr 1 i t c “e ( k i ) + p ! e ，? k i ( 1 ) 其卑i ( o ) = 0 ，i = l ，2 ，r 吼，q 。) = o 。n = i 2 ，m c ，。i = 0 ， j 一，z ，n 与万相关联的加工时间定义为c r 石，c f 牙= 舢厶 为了从给定的加工顺序丌中得出可行的排序，我们将批以，j 崩合堙地分 配到中心0 的机器上，0 扰由于机器是异类机，在不考虑某些特殊情况下是不可 以任意分配的，这在算法中将会有详细说明。这样一个可行的排序：“，q ， j 酬，0 丘l ，可从加工顺序丌用后面算法提供的方法得到。g ，可用迭代公式( 1 ) 得到。这时我们的问题可以表述为寻找这样的丌，肥况使c 一似最小。 为便于研究，对给定工件初始加工顺序爪刀的排序问题，我们采用如下的 模型图： 定义图占秽：f o ，e u ef j ，其中o = 能￥ 衷示顶点集合，f 和f 阮) 表 示有向弧集，3 u ；：。u ：杆，川，r + 1 j j ，e 0 ) = u ：。u ：u 2 。1 ，以巧，f j ， 佃，巧，陆+ s j j j ) 。e 壤示工件穿过中心的路线顺序，f 阮) 表示在同一批上工件 之间的加工顺序，每一个顶点他，o 表示工件j 在第e 步操作，权重为 异，皿l 是完成该操作的机器：每条弧权重为0 ，由公式( 1 ) 所确定的工件完 工时问g ，等于图g 似j 中到顶点珈，) 的最长路的长度( 包括只，i ) ， c 陆j 等于图g r z j 中最长路的长度即关键路的路长。 例2 例1 的初始加工顺序和模型图如下： 其中虚线表示矿中的弧，实线表示e r 石j 中的弧。 中心 乃， 2 3 下面先给出关键路的概念。 关键路：对于这样的一种路线或顺序，从中心开始，它连续地穿过幺， 腰一，中心，最后在中心皿结束：在每个中心口，0 矩都有这样的唯一的一个 批 k ，在这个批“。上的工件中，它连续地穿过在排列z 。中从q 位置到 位置r s 岛王勒。j 上的工件，把这种路线称为关键路：它可以用这样的顶点 序列表示： l 、乱i 、le t ) ) ；l 、。兀i j r e , + 、) ) 一1 、冠l l l ) ) 1 2 7 i 执i e ：) ) 1 2 1 l 2 h ( e 2 + 、) ) 。， 2 ，a 2 h 如) ) 一。( m 冗m 。e m ) ) m r m f e 。+ 、) ) ( m 冗| ，i 1 m ) ) 其中：厅吼r = 以“ 。r 白+ - j ，d 可，皿一1 。显然g l = l ，厶= ”帆， 是 最后完工工件的位置。称工件集序列： b t = ( 覆j ( e t l l i n h j i e t 七、) 1 一i 兀j l t 1 1 蔫日二 鼹 ( 。m j e ! ) ) 。( 。死t k e ! + 、) ) 。 兀i h ? f ! ) ) 为中心0 上的块，用岛表示，在中心d 加工块工件的机器用 表示，县上 的工件数我们用岛表示，即b o - - l 岛i 薯一岛十，9 日蟛岛上的最后一个工件即为 b 。中的第一个工件，0 = j ，一，利用这一性质我们可以将公式c r 石j 改写为： c 似j = m 舰蛳p 埘 例3 在例2 的图中，关键路是用粗线条表示的，它的堵塞集为毋= f t 鼻钐，毋= f 毋 1 2 3 ) 。8 ft 3 2 ) 。b l 每镪i 侮鼹亍n l z ( h l - - 2 ) 8 2 寺镪i 辑强千2 l ( h f l ) 易中的工件属于佤钏，因此我们有e 2 = 1 ，= 舅e 2 = 2 , _ f 2 - - 5 , 岛习，爿。 显然州，和皿，与一个工件的加工顺序丌紧密相关，但这里不作过多的探 讨。再引入一个与工件的加工顺序a 胡有关的操作对集合定义： y ( ) = u u f f f a n f k j j ，f ，a f k ) ) j ：i 玉k j k s 嘎 ，e “l e m - 根据可口j 的定义，显然有e ( a ) c r ( a ) ，i v c a ；l = e 。，。成r 玩一1 ) 2 j ，例的 意义就是一个中心里所有的顺序工件对集合 3 ：t a b o os e a r c h 方法 在本节我们描述解决本文开头提出的：目标值是使最大完工时间最小的异 类机流水作业问题的t a b o os e a r c h 方法，其中包括： ( 1 ) 初始解。 ( 2 ) 邻域构造。 ( 3 ) 邻域的简化。 ( 4 ) t a b o ol i s t 及其大小。 ( 5 ) a s p i r a t i o n 准则。 ( 6 ) 一个集中搜索和分散搜索策略。 ( 7 ) 停止准则。 3 1 初始解 在本文所给的缁算法中，初始解用的是构造性的方法，初始时将工件的加 工时间按非增次序排列，而后将加工时间较长的工件安排在加工这个工件速度 比较快的机器上加工，在每一个中心，般是都是先将加工时间最长的工件放 在加工这个工件速度最快的机器上加工，次长工件放在加工速度最快的机器上 加工，对其余工件按以上方法依次类推；或者在同一个中心里，对不同的工件， 找出：m i n p g ，后，将该工件放在机器，上加工，然后将该工件从工件集合中 去掉，再在其余的工件中按照以上方法重复进行，直到工件集合为空集；然后 再转入下一个中心，依此类推，再按照列表排序方法将其余的工件逐步安排完 3 2 邻域构造 邻域用的是插入邻域，设0 是所选择的中心，a ，b 表示这个中心的两个 批，肖，是在排列巧。和巧。中的位置，定义y = 以马互岛与加工顺序石1 7 有关，它定义了这样的插入：将工件历。( 从批州。伤。的j 岔量j 上移走，插 入在中珥。的，位置上，如下图所示： b = a x y 死o b = a ，x ) y o r 。一一一” ” 一”“： i： ooo 审o o oo 其中鼻傣示在排列中的位置，实线条表示在移动后要进入弛b o ol i s t 的 工件对，虚线箭头所指表示巧。中j 位置处的工件要移动到的新位置。 用文字描述为： 假定某一时刻工件z i ( ，如果a b ，将z p , z , 。上的啦置拿掉后，工件巧。 臼十，死佤各自在排列碣。中向左移动个单位，另一个工件集巧。o 一， 巧。佤则在排列历。中各向右移动一个单位，z 就排在了另一个排列的难置上， 如果a = b ，且z y ，则工件z 从排列z 。的位置被拿掉后放在了位置，后面，这样 z 。扫+ ，“jz 。o p 的位置各自向左移动一个单位，其它元素的位置不变：如 果a = b ，j ，乃则工件蹴从。的神z 黄移至。d 的前面，这样，工件万。咖) ， z 。& 一，j 的位置各自向右移动一个单位，工件z 就被移到了瑚位置上，z 经过 y = 珈，g t ，r ，b ，j 移动后得到的新的加工顺序记为z ，j ，即为玎的插入邻 域。刀的所有这样的插入邻域历巴jy y 阮j ，是j 经过移动： n b y r 丌j = uuuu r 工产生的，其中： 例= ( t ，, 叫a , x ，, b 呲, y ) ：1 l 班 y - n e n “y 2 x - l , x l , 麓 日6 喇，j 气，碣，0 甜，集合k m 白) 包含了所- f i g , 口。中除去月。伍 再将 丌。( x ) 插入到排列z 中所有可能的移动。很显然当a 柚时，jk 。( ；一j = q 广1 ， 当a = 6 时，ik 。纠i 硼a 谢门统纠，再由等式，。= n ，。酬有l vo r ) l 。 o o o o m 珂r 疗一3 + 似+ 1 j ，。即矿白) 中移动数大约为甩2 m 。 例4 例1 中的y r 石j ( 丌指例1 中的加工顺序) 共含有4 德；动方法。 根据以上定义，可以求出其中 吖z 爿= j 4 口a 由于t a b o o 鼬& r 柚方法的计算效果与单邻域的大小以及邻域的计算复杂性有很 大关系，因此下面我们重点研究对邻域的改进。 3 3 邻域的选择一邻域简化 由于在所有工件的移动中，很多情况下的移动并不能改进c o ，也有不少 移动反而使c 一变大，因此，为了节约时间，加快搜索，要把这些移动排除掉，对 于一个移动f 佃，岛z ，髓，假如它满足以下几种情形n 殳z = z 。c 一) 之一， 则是不能使c 一改进的移动，应当除去。 ( 1 ) 工件z 不属于块，即a 鱼或a 但工 q 或肛 ( 2 ) 工件z 属于块岛，但岛只含一个工件，即a 铂，且j = 岛誓 当a - - b 时，又有以下几种情形： ( 3 ) z 属于块尽的内部，但仍然在岛的内部移动，即c x c f 0 岛 y 誓 ( 4 ) z 是岛的第一个工件，把z 向左移动，即并= y 6 ( 5 ) z 是尽的最后一个工件，把z 向右移动，即j ，p 五 ( 6 ) 岛是第一个块，z 是届的第一个工件，将z 在块内部向右移，即e - - 1 , x 2 e 口y e p 由于这些结论都很显然，这里就不作证明了。 我们把r 6 中元素除去以上这七种情形以后的集合记为矽仞j 。 例5 对于例1 中的给定的加工顺序的缈似j ，可以求出旷例l 五z 即它包含船中移 动，例如，由第一种情形可知移动r ，彩萨似j ，由第三种情形 知凹，1 ，3 ，4 j 芒矿r 石j ，由第四种情况知r ? ，3 ，j 萨形r 石j ， 由簿五聃情形瓤( i 2 ，3 ，2 ，4 ) 隹w ( g ) ：由镰六祷情形知( j ，2 ，i ，2 2 ) 萑w f ) 等等。 经过以上讨论，可以得出：只要在w f 丌) cv f 丌j 中考虑万的移动就j 以j 其中： w ( 7 c 1 = uuu w t h p x b l a ) l e m 芦e 斗e m t 。 对每一个0 ，有： w ! h 西冗) y t j x ) t b m ，1 2 e 。，。 其中形h w r 厅，定义如下( 假定a ) ： 。6 0 r j = v = b ( x j ， 如果b 车a e t ! y 。( ) v f t - i 。 2 8 。x a y ) ，如果b = d e t x c 似j ，在证明引理3 时，还要用到下面的命题： 命题： 对于上述甑丌存在p w f 丌) ，使褥p ( 定。? 丌) ( p ( x ，行) ， 证明：定义集合届= ，r 癌，巧m 倒，相，刀- 脚伍，? 岛5 膏 ，同样地，由对称性， 我们再定义最= ，r 佃，巧。向j j ，瞳，刀h 偿川? q 乞例例， 矛盾。本情形不成立。 情形2 “存在e ，a 戗使得磊l j ，( 列驴， 则存在五岛 z 彳，使得： ( q ? 取a ( x ) ) 氇取a i ) ) 圣y 晴) 0 n 和 氇吼，( k ) ) 。也。礼印) ) e y 掰) x k 矗 0 2 1 成立，其中a - - h i ，设f 为，s f m ，是使得z b r r j 0 成立的指标。由( 2 ) 知存在f “，1 f ”，仃“似j k = j + 1 ，f i 对这种情形，再分两种情况： f = ，”f f ” 对于f = r ”，因为工件巧。例，巧。矧属于同一批：，由( 1 ) 得 t 氇。砥a i 印) 氏瓠。i x j ) ) y i 疗) 。 0 3 因此由( 2 ) 得到 ( 甄。( k ) ) 柱瓦a ( x ) j j y c x j x k ( 4 、 因为图岔例中不包含圈，由( 4 ) 和r 6 的定义，又得到： i 氇取。t x ) ) 氇砥。t k ) ) ) 圣y i 费) ? x k f 。 0 黾、 设p = 曲，a ，鼻a j ，显然，若v e g o r ) ，：= ：，j 丘可得： p 1 酝。费) = p l 沅蠢) ， y a ，) i ( 蛳u “ , t e t a x ) ) ，化a n ( k ) ) ) u u 。呱 , z e t a k ) k ( t , x t o x ) ) a 由( 3 ) ，( 4 ) 又有： r ( x v ) l y ( x ) = f 硝u 。咄f ( 他筇。( x ) ) ( ，筇。f k ) ) ) 1 1 y ( 方) 。 再由式( 5 ) ( 1 ) 得： p ：r 万，石j = i r ( x 。j y r 厅i = p ：r 万，石。夕r ：一j ， p ：r 万，厅+ 夕。最后得： p ( 兀。耳) ，时) 和元素棚，死死扛+ 圳 f 当工硼。疗移录入l 如果a = b ，将元素化忍降一，死俐伪螵z 秒j 或者元 素以死( x j ，在+ s ) j 伪z 榘j 妙屎入r 。这样，当d 劫且数组佃，死，巧5 仔，y 矗鼎。 或数组坤，例，死和圳，矗掣，中至少有一个元素属于，时，v = 心口，工6 圳被禁止； 当a = b 且数组坤玩例，死厅圳，z 女习，国z 栗工秒j 或数组化死俐，死_ 纠，y 矗 x r 奶果j 趔j 中至少有一个数组属于，时，v = 他口，工珥将被禁止。在搜索过程 中，为了对总的情况如：搜索步数、时间、可行集合情况等有一个综合了解， 我们引进一个新的动态表格概念，长度记为1 卯，l 的每一个元素包含以下四 个部分： 加工顺序几 在搜索中从研始到现在的加工顺序所经过的的移动总数 纪。 从初始的亿j 中去掉从刀开始所做的所有移动v 后余下的矿r 石j ，由于 移动v 要到下一次迭代才能知道，而记录在前，因此中的记录是通过一个参 数标记s 控制的，在算法的第四步将s 设为t r u e ，表示要记录一次，但记录是 在下一个迭代的第三步执行的；如果连续的最大次数的迭代仍然没有使c 。改 进，那么我们退回到最新的中的元素，研始从新搜索，搜索开始后这个元素将 从l 中去掉，而且在第六步s 设为t r u e ，且这个元素在下一次迭代的步骤三将 再次被记入三。 与7 r 有关的t a b o ol i s tt 。具体见算法。 在算法的第四步，每当整个系统的完工时间有改进时，动态表格l 中就新 增一个元素r 万，r 石j ，v ，r j ，其中丌是改进了的加工顺序，v r 石j 是一个 从刀开始的移动，当l 长度大于i7 时，最早进入的元素被除掉。在后面第四节 给出的硒算法中，凡是标有硌记号的均是指该名称的最好结果。当执行最大 次数迭代或者l 中的元素为空时算法结束。 例6 再来分析例1 中所给的加工顺序的t a b o ol i s t ，假定初始时，为空集，考 虑移动一，2 ，2 ，纠，设锄则有殇，= ，5 ，2 ，矽。局。= 似6 ，矽，对其余的0 ，有玩= 乃， 在佟这个移动时。我日1 将数组! 刀1 0 臻i ) = f j 4 ，5 ) f i z 曩1 3 ) 。) = ( i 5 6 ) 录入t 。假 定的b ，含有工件5 ，则下面从研始所作的移动( i ) r ，2 ，2 ，其中y = 1 ( 因 为在f l l l l 2 ) 。6 l 烈) ，l = y 蠢s n l 寺，意苞一令数组( 1 。簪l t 2 1 毋l 露1 1 = ( 1 l 6 ) e y ) ， ( i i ) ( 1 ，2 , 2 圳，2 - y - 4 ，( 因为在数组一杩。倒弱，俐，1 - k y ，中存在数组 弼j 俐属，砂一，4 , s j e r ) ) o 所以工件j 不能插至蛔2 的任何位置。 3 5 a s p i r a t i o n 准则 一个被禁止从刀韵移动v ( 即v 在t a b o ol i s t 表中) ，如果最后能导出完工时 间小于或等于c 似8 j ( 其中万8 是在搜索过程中到目前为止发现的最好的 排序) ，则被认为是禁止但可以被利用的，可以从t a b o ol i s t 表中将其除去。 36 搜索策略补充 根据计算结果将r 厅j 中的v 分成三种类型：1 不禁止；2 禁止但可以利用： 3 禁止不能利用。如果一个被禁止从丌的移动v 最后能导出完工时间小于或等于 c m 。( x 8j ( 其中尼8 是在搜索过程中到目前为止发现的最好的排序) ，则被认 为是禁止但可以被利用的；否则就被认为是禁止不可被利用的。最后在wo r ) 的第一、二种类型中选择个能产生最小完工时间的移动，如果所有wo r ) 中 的移动都是第三种类型( 这种情况比较少见) ，我们将，中的最老的元素去掉后 加入0 元素；重复进行直至找到属于矿白j 第一种类型的移动。 4 算法t s 及其补充 综合第三节的讨论，在本节中我们给出t a b o os e a r c h 具体算法，并且为了进一 步减少计算时间，增加运算速度，又给出了算法补充。 4 1 算法t s 先将算法中用到的标记说明如下： z 。指初始的加工顺序，t i = t o t l t e r 指从初始解开始总的迭代数，i = i t e r 指没有使 完工时间改进的迭代数。m c 是动态表格三中第二个成分即从最初的口到现在 的加工顺序所经过的移动数，另外刀有一个上限m m c = m a x t o t i t e r ， t e r 也有 一个上限m 1 = m a x l t e r ，它们与【玎、一起都是凭经验选取的。s 是一个控制v 存储的参量，s 为t r u e 时，则在下一次迭代的第三步做一次三的记录，s 为f a l s e 时，则在下一次迭代的第三步对不做记录。 0 令行= 耳o c 弱：= c 慨f 耳) c ：= c r s t i ：= 0 i ：= o ，t ：= 中m c o s ：t r u e 1 令t i = t i + 1 ，= ，+ 1 ，寻找集合w ( e r ) ，如果r 疗j = 西，且此时的堵塞工件 正好在加工速度最快的机器上，则令石”玎c 87 = c ，s t o p ( 由引理2 知此 时的丌”是最优排序) 。 2 寻找移动v r 厅j 、加工顺序石= 万，、完工时间c = c 似，以及 t a b o ol i s t t 。 3 如果s = t r u e ，仞j ，v 非空，且m c 屯，则。o r ) 的所有的移动 均是被禁止的，即没有可行的移动，这时万即为最优解。先引进两个记号：“。 ，其中指在中一i i , o 中含有工件的批的指标。气表示工件在中一i i , 口、批 是上的位置，即有：石饥r 女。，= 。下面给出求y 范围的具体方法。 o 令k 67 = o ，r 啪：= ，b m ，：b t ，孽m 1 对t g h ) t 弧果“g ) ( h ) ) 【圭y ( 亿) ，砒2 ： 2 如果g b f ，则饥。i = m a x l t g 。，k * + 1 1 。 3 如果h b ，n z _ , ： 如果“缸n ，则有r _ m i n r f h 。，k 暗，否则尺眠。= m i n r t h ，k 缸一1 ，。 结束。 第一步的条件等价于( “堙“) 或者( “堙= u e h , k 。 k t g ) 。 l e a 和r e 。的计算复杂性为o ( m a x c o m a x 。刖，。这样，通过先确定y 的范 围，再代入到算法t s 的第二步，就可以将可行移动p 的范围大