（运筹学与控制论专业论文）若干机器排序问题及其tabusearch算法.pdf

摘要 y 3 6 2 i 8 机器排序理论自二十世纪五十年代产生以来，已在各个领域得到了广泛的应 用。本文讨论了两个最新的机器排序问题并提出了相应的算法。在工件准备时间、 机器准备时间、先后顺序制约、批处理和交货期等条件的约束下，把平行机和工件 作业( j o bs h o p ) 问题结合起来，并追求带权总延误最小，是本文探讨的第一个问 题。：v i c e n t ev a l l a s 等人于1 9 9 8 年研究过类似的问题，但他们没有考虑工件带权重 的情形，同时他们的目标函数只是使总的加工时长最短。我们根据t a b us e a r c h 算 、 一 ) 法的基本原则，为本问题具体地设计了邻域结构、搜索策略、t a b u 表和搜索停止条 件。本文讨论的第二个问题是一个带延迟下界的单台机器多链时间约束问题，目前 尚未发现有关于如何把t a b us e a r c h 用来求解类似问题的研究。本文在此方面做了 些尝试和探索，给出了具体的算法。 计算试验结果表明，我们给出的算法能够在一定的时间内求出性质较好的解。 关键词：排序、t a b us e a r c h 、平行机、工件作业、k - 链 分类号：0 2 2 s o m em a c h i n e s c h e d u l i n g p r o b l e m sa n d t h e i rt a b us e a r c h a l g o r i t h m s a b s t r a c t ：t h e t h e o r yo fm a c h i n es c h e d u l i n g ，w h i c hs t u d i e sh o wt oo p t i m a l l y a l l o c a t er e s o u r c e st oas e to ft a s k s ，h a sb e e n l a r g e l ya p p l i e dt om a n yf i e l d s i nt h i sp a p e rw e c o n s i d e rt w o c o m p l e xm a c h i n es c h e d u l i n gp r o b l e m s ，o n ev i e w e da sag e n e r a l i z a t i o no ft h e j o bs h o pp r o b l e mw i t hp a r a l l e lm a c h i n e ，j o bb a t c h e s ，s e t u pt i m ea n dr e l e a s ea n dd u ed a t e s ， t h eo t h e rc a l l e do n e m a c h i n e s c h e d u l i n gp r o b l e m 、撕t 1 1m u l t i c h a i n s a n dl o w e rb o u n d d e l a y s t h ed i f f e r e n c e sb e t w e e nt h ef o r m e rp r o b l e ma n dt h eo n ev i c e n t ev a l l a sp r e s e n t e di n 19 9 8l i ei nt w oa s p e c t s f i r s t , t h ej o b sa r ec o n s t r a i n e db yas e r i e so fw e i g h t s ，w h i c hr e f l e c t s o m en o t i o no f p r i o r i t ya m o n gt h e m ；s e c o n d l y , t h eg o a lc o n s i d e r e dh e r ei st om i n i m i z et h e t o t a l w e i g h t e dt a r d i n e s sr a t h e rt h a nj u s tm i n i m i z et h em a k e s p a n i nr e s p e c tt o t h el a t t e r p r o b l e m ，t h ea p p l i c a t i o no f t a b u s e a r c hp r o c e d u r et oi th a sn e v e ra p p e a r e ds of a r a c c o r d i n gt ot h eb a s i cr u l e so f t a b us e a r c h ，w es m o o t h l yd e s i g nf o rt h et w op r o b l e m s t h e i r n e i g h b o r h o o ds t r u c t u r e s ，s e a r c hs t r a t e g i e s ，t a b u l i s t sa n d s t o p c r i t e r i a 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 w t h a to u rp r o c e d u r e sc a nf i n dh i g hq u a l i t ys c h e d u l e si ns h o r t r u n n i n g t i m e s k e yw o r d s ：s c h e d u l i n g ，t a b us e a r c h ，p a r a l l e lm a c h i n e ，j o bs h o p ，k - c h a i n s 2 若干机器排序问题及其t a b us e a r c h 算法 第一节引言 机器排序( m a c h i n es c h e d u l i n g ) 理论起源于二十世纪五十年代的工业制造业。有t l l 台 机器，1 1 个待加工工件，每个工件都需要在每台机器上加工一次，并且在每一个时刻， 一台机器只能加工个工件，一个工件也只能占用台机器，如何安排这些加工任务使 总的加工时问最短便是一个典型的机器排序问题。排序理论就是研究如何对有限的资源 ( 如机器) 做一个有效的安排，以便能够完成一些任务( 如工件的加工) 。它是运筹学的一 个较年轻的分支，同时也是实际中应用最广泛的运筹学分支之一，不仅在制造业，而且 在农业、医院、交通、计算机控制领域乃至日常生活中都有很强的应用背景。研究它， 对于在现有资源条件下提高工作效率和经济效益有着重要作用，已受到越来越多的科研 人员的重视，大量的研究成果也已经以著作或论文的形式发表。 1 i 机器排序问题的常用符号和分类 虽然早期研究的模型来源于制造业，但为了和惯用的名词术语保持一致，本文仍 使用“机器”、“工件”、“加工时间”等术语来描述各种各样的排序问题，只是它们已不 再局限于本来的含义。在现实问题中，“机器”和“工件”可以有任何合理的解释，比 如说，“机器”可以是轮船将要停泊的港口，或是计算机的中央处理机，“工件”可以是 将要停泊港口的轮船，或是等待处理的程序。 设有m 台机器，1 1 个待加工工件。如果工件j 有多道工序，我们分别用v ；代表第 i 道工序；对只有一道工序的工件就直接用它的工件编号表示该工件。每道工序都有一 个加工时间( p r o c e s s i n gt i m e ) ，记为p i 或p i ，都有一个交货期( d u ed a t e ) ，记为d j 。 对于一个排定的加工计划，可以计算出每个工件的完工时间，用c ；( 或c ，；) 表示工 件j ( 工序v j i ) 的完工时间( c o m p l e t i o nt i m e ) 。有时，我们也用s 、( 或s 9 表示工件j ( 工 序v ，i ) 的开工时间。当然有： c j i = s j 。+ p j l 在与工件交货期有关的排序问题中，往往需要计算工件的延迟时间( l a t e n e s s t i m e ) ，记为l j = c j - d j ：延误时间( t a r d i n e s st i m e ) ，记为t j = m a x ( o ，l j ) 所谓一个可行的排序，是指满足约束条件的工件加工顺序编排。它的目标可以是 最小加工全长、最小总延误等等。 在实际生产和日常生活中，排序问题千变万化，如何清楚描述各种情形，我们采 用了文 2 中所使用的三参数表示法：0 b y 。它可以表示大多数的排序问题。 ( 1 1 参数a 表示机器情况。 当a = 1 时，即表示单台机器上的排序问题。按工件是否具有先后约束关系分为 两种： 工件独立( i n d e p e n d e n tj o b s ) ，即工件没有先后约束关系( f r e eo f p r e c e d e n c er e s t r i c t i o n s ) ： 工件有先后约束关系( d e p e n d e n tj o b s ) 此时，又可分为三类： ( i ) 森林( f o r e s t ) ：每个工件的出度( o u t - d e g r e e ) 或入度( i n d e g r e e ) 都 不小于1 ( 在其有向图中) ； ( i i ) 树( t r e e ) ：如果森林是连通的； ( i i i ) 多链( c h a i n s ) ：具有先后约束关系的工件分成n 个子集，每个子集中 的工件，其出度和入度都不超过1 。本文第四节详细讨论该类的一个问 题。 当q 1 时，又分为两类： 平行机排序。即有若干台机器，每个工件只有一道工序，可以在其中的任 台机器上加工。根据机器性能的不同，分别用p ，q ，r 表示。p 表示同型机 ( i d e n t i c a lm a c h i n e ) ，即所有机器的性能完全相同，工件j 的加工时间与机 器无关，为p ，：q 表示同类机( u n i f o r mm a c h i n e ) ，这类模型中所有的机器在 速度上有一致性的差别，工件j 在机器i 上加工时间为p s 。( s i 为机器i 的 加工速度) ：如果机器速度上的差别没有一致性，则称这类模型为非同类机 ( u n r e l a t e dm a c h i n e ) ，记为r 。此时，工件j 在机器i 上的加工时间为p i 。 串联机排序。即有若干台机器，每个工件有多道工序，分别需要在相应的机 器上完成加工。如果n 个工件的多道工序加工路线是一致的，被称为流水作 业( f l o ws h o p ) ，用f 表示；如果n 个工件的工序加工路线都是待定的、不完 全相同的，被称为工件作业( j o bs h o p ) ，用j 表示；另外对于每个工件的工 序加工路线是可以随意确定的模型，被称为自由作业( o p e ns h o p ) ，用o 表示。 有时，我们也在机器类型后加一个整数m ，表示只考虑有m 台机器的排序问题。 比如用j 2 表示两台机器的工件作业问题。 ( 2 ) 参数b 表示工件情况及有关约束条件。比如用p r e c 表示工件在加工次序上存在先后 顺序的限制。 ( 3 ) 参数y 表示目标函数。如c m a x = i n a x c i j e j 就是加工全长，e j w 3 t 。即所谓的带权总 延误等等。 综合三个参数的含义，f 2 c m a x 表示两台机器的流水作业问题，并使加工全长 最小；j m p r e c e w i t ；表示m 台机器工件作业的带权总延误问题。 1 2 机器排序问题已有的算法及本文的结构 已经证明，绝大部分机器排序问题都是n p - 困难的。为了求得精确解，人们通常 使用分枝定界法( b b ) 或动态规划( d p ) 方法来解决一些小规模的问题。而一旦问题规模 增大，这些算法便不能有效求解。于是，人们转而寻求近似最优解。已有的近似算法包 括【4 = 启发式算法( h e u r i s t i c s ) ： 遗传算法( g e n e t i c sa l g o r i t h m ) ； 模拟退火算法( s i m u l a t e da n n e a l i n g ) ： 神经网络算法( n e u r a ln e t w o r k s ) ： t a b us e a r c h 算法： 邻域搜索算法( l o c a ls e a r c h ) 以及其它的算法。 其中t a b o os e a r c h 算法已被应用到许多的n p 一困难的组合优化问题的近似求解 中，实验证明有令人满意的结果。 本文也试图将t a b o os e a r c h 算法应用到两个复杂的排序问题中： 将平行机( p a r a l l e lm a c h i n e s ) 问题与j o bs h o p 问题结合起来，在批处理( j o b b a t c h e s ) ，机器准备时间( s e t u pt i m e s ) ，工件准备时间( r e l e a s et i m e s ) 和工件交 货期( d u ed a t e ) 的约束下，追求带权总延误，w ，t ，最小： 带延迟下界的k 一( n ，n 。，n 。) 一链约束的单机器排序问题，追求c m a x 最小 这两个问题都是n p - 困难的。其中，作者v i c e n t ev a l l s n ，m a n g e l e sp e r e z ，和 m s a c r a m e n t oo u i n t a n i l l a 在1 9 9 8 年研究过类似的问题，他们的问题与这里的问题 有两个不同之处，一是他们没有考虑工件带权重的情形；二是他们的目标函数为 m i n c m a x 。而问题，目前尚未发现有将t a b o os e a r c h 算法应用到该类问题上的研究。 本文试图在将t a b o os e a r c h 算法应用到以上两个问题中做一些探索和尝试。我们的计 算结果表明，该算法获得了良好的效果。 文章结构是这样安排的。引言之后是第二节，详细地数学描述第一个问题；第三节 深入介绍本文为求解问题而提出的t a b us e a r c h 算法，从t a b us e a r c h 算法的基本原 则出发，将分别阐述邻域结构( n e i g h b o r es t r u c t u r e ) 、t a b u 表( l i s t ) 、搜索策略 ( s e a r c h i n gs t r a t e g y ) 、搜索停止条件( s t o p p i n gc r i t e r a ) 等：第四节给出问题的 t a b us e a r c h 算法：计算实验结果在第五节给出：第六节是全文的总结。 4 第二节问题的数学描述及模型 机器排序方面的大多数研究工作都是从简化了的模型出发，为生产管理人员设计 生产计划。这种简化了的模型往往与现实生产情况不符，导致管理人员对研究人员提供 的生产计划产生怀疑。本文结合工业生产的实际情况，提出了一个崭新的机器排序问题， 它综合考虑了多种因素，如批处理( j o bb a t c h e s ) ，机器准备时间( s e t u pt i m e s ) ，工 件准备时间( r e l e a s et i m e s ) 、工件权重和工件交货期( d u ed a t e ) 等，并把平行机问题 与j o bs h o p s 问题结合起来：m 个机器组，每组有一台或多台可利用的机器；一系列待 加工工件，每个工件有一道或多道具有先后顺序关系的工序，并规定每道工序只能在哪 一组机器上加工( 在组中，它可由任一台机器加工) ，在满足上述约束条件的情况下， 追求带权总延误w ，t ，最小。 下面详细描述该问题。 ( 1 ) 工件、工序及权重： 一个工件集合j 包含n 个工件j ，任一个工件j 含有n ( j ) 道工序 ( o p e r a t i o n ) ，即j _ - - ”j 1 ，7 j ，2 ，v j , n ( j ) ) 每个工件j 都有一个权重w j ( 该权重反 映各工件在工件组中的重要程度，例如，每个违反交货期的工件，其单位罚款额 不一样) ，则每道工序v j ，的权重w j ，；= w j ，i = 1 ，2 ，n ( j ) 。我们设v 是所有工件的 工序的集合。 ( 2 ) 机器： 一个机器集合朋包含m 组机器，h p m = m 。，m 2 ，m m ) 任何一组机器m k 有r 。 台相同的机器，r k 1 ，k = l ，2 ，m 对任何一道工序v ，我们用m ( v ) 表示加工 该工序的机器 ( 3 ) 机器准备时间，工件加工时间，交货期以及先后约束关系： 任意一道工序v j ，的处理时间d u r ( v 。) 有两部分组成，一是机器准备时间 s e t u p ( v j ，i ) ，二是工序加工时间p ( v j ，j ) ，即d u r ( ”j ，i ) = s e t u p ( v j ，i ) + p ( ”j ，i ) 当然， 同一工件的连续两道工序的处理时间可以有重叠时段： m i n ( d u r ( ”j i - 1 ) ，s e t u p ( 7 j ，i ) ) 如下图所示( 转下一页) d u r ( v j ，) 沥 ，f s = - s e t u p ( 飞；) 珍形钐钐形黝 ( 图2 1 ) 由此可以看出，在机器准备的过程中，工件可以未做好准备。我们用 f s ( ”j ，。j ，i ) 2 一s e t u p ( 7 j ，i ) 来表示两道连续工序的时间间隔，即我们认为，同一个工件的连续两道工序恰好 是前后首尾相连的，除了一个时间间隔f s ( ”。”j 。) 一s e t u p ( ”j i ) 以外这样处 理的好处是把工序的先后关系蕴涵其中。 ( 4 ) 工件准备时间与交货期： 每个工件j 了都有一个准备时间( r e l e a s et i m e s ) r j o 和一个交货期 d j 0 为了方便算法的实施，我们把r ，和d ，分解到工件j 的每道工序上去。 这可以用以下的递归公式实现： ，2 , 1 ，”) ( 5 ) 批处理： 部分工件由于性质相同可以结合在起同时进行加工，这样可以减少机 器的准备时间假设有n ( l ) 个相同工件j = v 。，v 。，。v l ， ，即n ( l ) 个工件有相同的机器准备时间、工序个数，每道工序的加工时间也相同。则 我们设批处理l 有n ( j ) 个批v 。，i = 1 ，n ( j ) ，那么批v l 。的机器启动时间为 s e t u p ( v t ；) ，加工时间为n ( l ) 幸p ( v i ；) 与单个工序处理方式一样，我们也认为， 连续两个批v 。，和v i ，恰好是前后首尾相连的，除了一个时间间隔 6 32 i j v 牡，v妒 甜s一 、t， 一 l 三， r幽+ 、i， 一 l v r 、三v x，a 0 m 1 l = 、l，、l， ， l v 三 r r ，、，l l u 胛 = v 、np 一 ， 件力k f 【，口 一序e n d d ，、l f s 2 一s e t u p ( 。j ，i ) 一( n ( l ) 一1 ) m i n ( p ( 7 j i _ 1 ) ，p ( 7 j i ) ) 以外。不失一般性，我们把每个批v 。与每个工件看成是一样的。 下面举一例子说明。 例1 ：有四个工件，每个工件三道工序的排序问题如下： n ( l ) = 4 。n ( j ) = 3 ： s e t u p ( 7 j ，1 ) 2 5 ，s e t u p ( 7 j ，2 ) = 5 ，s e t u p ( ”13 ) 2 4 ，v j 2 1 ，2 ，3 ，4 ： p ( v ) 2 2 ，p ( v j 2 ) 2 6 ，p ( 7 j 。3 ) = 4 ，v j 2 1 ，2 ，3 ，4 则批处理如下图所示； ( 图2 2 ) ( 6 ) 目标函数： 我们考虑m i n e j e vw i t j 如果它为零，则达到了最优：否则，尽量求一较好的近 似解。 经过上述处理后，我们把“问题不可行”分为两种情况：在某一时刻正在加工的 工件数比现有的机器数大：某些工件的完工期超过其交货期。 另外，我们还将用到以下一些符号和计算公式： s ，：工序v 的开工时间； v 。：在第k 组机器上加工的工序的集合； c v = s ，+ d u r ( v ) ：工序v 的完工时间； j ( v ) ：工序v 所属的工件； p r e d ( v ) ： 工件j ( v ) 中在工序v 之前加工的工序的集合； p r e d - i n ( v ) ： 工件j ( v ) 中工序v 的紧前加工的工序： s u c ( v ) ： 工件j ( v ) 中在工序v 之后加工的工序的集合： s u c i n ( v ) ：工件j ( v ) 中工序v 的紧后加工的工序； 设初始解为s = s ，iv e v ，工序v 在第k 组机器上加工，即m 。= m ( v ) 则我们定义集 合mp r e d ( v ) 如下： 7 m p r e d ( v ) = 如果= 妒； 球咻r 甄划脚女l b t 4 郇r k r ； 这里，w = w e v k i s s 。) ， w 1 ，w 2 ，w j ) 是w 中的工序的集合，它们有s w ，s w 2 s w 这样的大小关系。所以，m _ p r e d ( v ) 表示在第k 组机器中工序v 的所有紧前加工的工序 的集合。 如果只从加工工序v 的机器的角度考虑，则我们定义m _ e s ( v ) 为工序v 的可能的 最早开工时间，虬l f ( v ) 为工序v 的可能的最晚完工时间。 显然： f s ，如果在时间p ，一1 , s ，l 至少有心道工序在机器组m 。上加工； 址哪卜卜强川热耋溢磊舞嚣。 i c ， m l f ( v ) 2 f ， 如果在时间乜， 这里f = m i n + 1 l 至少有r 道工序在机器组m 。上加工； i r 【c ，d ，l 并且在【c ，f 如任一时刻，1 降机器组m 。上加工的工序个数 d ( v ) ) 设p 表示违反机器的工序的集合，且设mv i o l ( s ，m k ) 表示s 中在m l 【机器组里违反机器 的所有工序的集合。则mv i o l ( s ，) 可按如下算法计算出来： 算法3 3 2 s t e p i ：j = l ，m _ v i o l ( s ，帆) - - o s t e p 2 ：把v 。中的工序按开工时间递增的顺序排列： t 。，t 。，t 。) ， h jv 。1 s t e p 3 ：j h ? 是：p = ( v v kls v t 1 r 。? 是：m _ v i o l ( s ，帆) - - mv i o l ( s ，魄) u p ) ： j = j + 1 转s t e p 3 否：j = j + l ，转s t e p 3 否：停止 因此，解s 中所有违反机器的工序的集合为： m _ v i o l ( s ) = u m 。x _ v l o l ( s ，) 解s 中所有违反约束条件的情况的集合为： v i o l ( s ) = d d j i o l ( s ) um _ v i o l ( s ) 这里，m _ v i o l ( s ) 和v i o l ( s ) 都是子集族。 下面举例说明： 例3 ：针对例2 ，我们令r ：= 1 ，其余的不变。 由于d ( 5 ) = 2 0 ，所以d ( 4 ) = 1 6 ，d ( 3 ) = 1 3 ，d ( 2 ) = 7 ，d ( 1 ) = 6 所以，d d _ v i o l = “5 ) ， 4 ) ，( 3 ) ， 2 ) ) 另外，由于r ：= 1 ，所以x _ v l o l = “7 ，1 5 ，1 8 ) ， 3 ，7 ，1 2 ，1 5 ，1 8 ) ， 3 ，9 ) ， 9 ，1 7 ， 5 ，h ) ) 因此 v i o l = 2 ， 3 ， 4 ) ， 5 ) ， 7 ，1 5 ，1 8 ， 3 ，7 ，1 2 ，1 5 ，1 8 ， 3 ，9 ) ， 9 ，1 7 ， 5 ，1 1 如果解s 中经过一个搜索方向迭代到s 时，导致工序v 被延误，则很有可能一部 分甚至全部s u c ( v ) 中的工序也被延误。因此，为了尽量减少这种“连锁反应”，我们用 下面的方法来定义迭代方向： ( 一) 如果p e d d _ v i o n ( s ) ，这里p = v ) ，则 ( i ) 如果j _ e s ( v ) s 。，则 当虻e s ( v ) s 。时：令s ，i m a x j e s ( v ) ，虬e s ( v ) ) ； 当忆e s ( v ) = s 。时：则每道工序w m _ p r e d ( v ) 定义了一个方向如下： s 。= f l l a x j e s ( v ) ，s ) ： s 。= s ，4 + d u r ( v ) 例4 ： 在例3 中，因为 2 ) d d _ v i o l ，s 2 = 8 ，j e s ( 2 ) = 4 且m _ e s ( 2 ) = 6 ，显然4 6 所以，如果我们期望移动工序f 2 的话，则 s 2 。= l l l a x ( 4 ，6 ) _ 6 如下图所示： ( 图3 1 ) 又因为 4 ) d d j i o l ，s 2 = 8 ，m _ e s ( 4 ) = s 4 = 1 9 且mp r e d ( 4 ) = 1 0 所以，如果我们期望移动工序 4 ) 的话，则 s - - m a x s l o ，1 6 ) - - m a x 1 8 ，1 6 ) = 1 8 ， s 1 0 1 = s 4 4 + d u r ( 4 ) = 18 + 3 = 2 1 如下图所示： 1 01 31 5 1 61 82 12 2 ( 图3 2 ) ( 2 ) 如果3e s ( v ) = s 。 在此种情况下，我们不能直接把v 往前移，因为j _ e s ( v ) ：s 。但是，只要该问题 有可行解，则一定存在一道工序q p r e d ( v ) 使得工序s u c i n ( q ) 满足 j _ e s ( s u c _ i n ( q ) ) s 。一；。( 。) 。因此，经过一系列上述( 1 ) 的方法后，工序v 就可以往前移。 例5 ： 在例3 中，显然 3 ) d d _ v i o l ，但是j _ e s ( 3 ) = s 。= 1 0 ，因此工序 3 ) 不能往左移 1 4 然而工序 2 d d v i o 且j e s ( 2 ) ：4 s 。= 8 所以先移动 2 直到j s ( 3 ) s 。，然后就可以 移动工序 3 ) 了 ( 二) 如果p mv i o l 首先，我们定义 s l a c k _ p r e d ( p ) = i v e pim _ e s ( v ) c ，) 这里，s l a c k p r 印( p ) 表示p 中可以向左移的工序的集合，s l a c k s u c ( p ) 表示p 中 可以向右移的工序的集合。 ( 1 ) 如果s l a c kp r e d ( p ) d 则每道工序vs l a c k _ p r e d ( p ) 都定义了一个迭代方向： s 。= m a x f l e s ( v ) ，n e s ( v ) ) ： ( 2 ) 如果s l a c k p r e d ( p ) = 口且s l a c k s u c ( p ) 西 则每道工序v s l a c k _ s u c ( p ) 都定义了一个迭代方向： s 。- l n i n ( j l f ( v ) ，m _ l f ( v ) ) 一d u r ( v ) ： ( 3 ) s l a c k _ p r e d ( p ) = 西且s l a c k _ s u c ( p ) = d 这时，由于p 中工序数超过了机器数，为了减少一个工序，必须把某一 个工序前移或后移一段时间。 如果把某个工序v e p 后移 首先确定后移到哪一个时刻。我们将v 的开工时间定为： t ( v ) = m i n c wlw p 一 v ) - s u e ( v ) ) 这样对当前解s 的扰动影响最小。 再确定移动p 中的哪一道工序。我们选择满足下面条件的 工序v + 作为后移工序： “1 e ( v ) + 威( v ) 一d ( v ) ) = m i n 。_ p ( v ) o ( v ) + 威矿0 ) 一d ( v ) ) 这样，p 中的所有工序后移之后产生最小延迟( l a t e n e s s ) 的工序是v + 如果把某个工序w e p 前移 为了尽量减少对当前解的扰动影响，w 的完工时间应满足 t ( w ) - = l a x ( s 。lv e p 一 w ) 一p r e d ( ) ) 且t ( w ) r ( w ) + d u r ( w ) 如果t ( w ) r ( w ) + d u r ( w ) ，则不考虑w 前移，因为由t ( w ) r 如) + d u r ( w ) 可 得：s ( w ) + d u r ( w ) - o ，( ) 表示一个虚拟工件，其加工时间为p ( ，木) = o 。 我们设每个工件( i ，j ) 的加工时间为p ( i ，j ) o ，并不妨假设n l n 。2 n 。， r ( n ，j ) = o ，j = l ，2 ，k 显然，对任一个给定的链j ，当所有的r ( i ，j ) = o ，v i 时，则 该问题为普通意义下的有先后约束关系的单机器多链时间约束问题；当n ，= n 。= = m 时， 则我们可以简称k 一( n ) 一链。在满足延迟下界和先后约束的条件下，我们求加工全长最 短，即 m i n c 。( s ) = m i n ( m a x 扎i c ( i ，j ) ) = m i nc 一( ， ) 对于上述问题，我们作如下三点假设与说明： 不允许中断： 延迟下界约束只存在于同一链中的任两个相邻工件。同一链中的任两个不相 邻工件以及任两个属于不同链的工件之间不存在延迟下界： 所有变量均为非负整数。 在文献 5 中，已证明该问题是强n p c o m p l e t e 的。所以，它不可能有多项 式算法。 4 2 带延迟下界的k - ( n 1 ，n 2 ，n o 一链问题的t a b us e a r c h 算法 这里，我们试图将t a b us e a r c h 算法运用到该问题中以期求出比较好的近似最优 解。该类排序问题提出较晚，到目前为止，还没有一篇文献研究过如何把t a b us e a r c h 算 法运用到类似问题的求解中，因此，我们期望这里所做的尝试和探索能在一定程度上 弥补该方面的缺陷。对该问题，与第三节一样，我们仍然按照t a b us e a r c h 算法的基 本原则，对其具体的邻域结构、t a b u 表，鼓励原则以及停止条件分别进行讨论。 设初始解为 s 2 s ( 1 ，1 ) ，s ( 2 ，1 ) s ( n l ，1 ) ，s ( 2 ，2 ) s ( n 2 ，2 ) s ( n k ，k ) ，s ( ， ) 我们引入“块”的概念，即把解s 划分成若干块，每个块既可以是整条链，也可以是 一条链的一部分( 子链) ，但每个块内部的工件仍然保持与原来链中的顺序一致。相邻两 个块一定属于不同的链，否则可以合并成一个块。例如上述初始解用块可表示成 s = b 1 ，b 2 ，b i ，b 。，( ， ) ) 。 ( 一) 邻域 我们采用了插入邻域 设解s 2 b 1 ，b 2 ，b 。b 。，b b 。b b ，b 。b ( ， ) ) 且设 b 。2 f ( j 。，f ) ，( j 。十1 ，f ) ，( 1 。，f ) ) ，b b = “j b ，驴，( j 。+ 】，g ) ，( 1b ，g ) ) ， 1 - f ，g 业现考虑单工件的插入邻域，即把某个工件向左或向右移动到另一个位置，得 到s 的邻域中的一个点。 ( 1 ) 左移。 2 4 定理1 ：( i ) 在同一个块的工件内部，右边的任一工件不能向左插入： ( i i ) 我们考虑把块b b 中的第一个工件( j 。，g ) 左移到块b 。的第一个工件( j 。f ) 之前。 如果至少存在块b ；，a + l _ i b - i ，该块中的工件属于链g ，则工件( j ”g ) 肯 定不能前移到工件( j 。，f ) 之前； 如果块氏。，艮，中的工件都不属于链g ，则当 n a x f s ( j 。一】，g ) + p ( j b - 1 ，g ) + r ( j b - ，g ) ，s ( j 。，f ) + m a x s ( 1 h ) + p ( 1 h ) 一s ( j 。，f ) ，r ( j b g ) s ( j ”g ) + r ( jb ，g ) 时，工件( j 。，g ) 肯定不能前移到工件( j 。，f ) 之前这里，h 为块b - 1 中的工件 所属的链且h g 证明： ( i ) 结论显然成立； ( i i ) 结论显然成立； 如果把工件( j 。g ) 插入到工件( j 。，f ) 之前，则可能的开工时间应满足 s ( j 。，g ) = m a x f s ( j b - i ，g ) + p ( j b - - 1 ，g ) + r ( j b - i ，g ) ，s ( j 。，f ) ) 工件( j 。，g ) 的可能的新开工时间与工件( j 。，f ) 的旧开工时间的差额 a ：m a x s ( j c l ，g ) + p ( j ，l ，g ) 十r ( j b l ，g ) 一s ( j 。，f ) ，0 ) 所以，工件( j h + 1 ，曲的可能的新的开工时间 s ( j b + 1 ，g ) ：m a x s ( 1 b mh ) 十p ( 1 b _ 1 ，h ) + p ( j b ，g ) + ， s ( j 。，f ) + 时p ( jb g ) 十r ( j ”g ) ) = 十p ( j b ，g ) + n l a x s ( 1 h ) + p ( 1 h ) ， s ( j 。，f ) + r ( jb ig ) 显然，如果s ( j u + l ，g ) s c m a x ，此时，工件( j b g ) 肯定不能前移到工件( j 。，f ) 之前。因此， 由 s 。( j b + 1 ，g ) = a + m a x s ( 1 1 ，h ) + p ( 1b _ 1 ，h ) ，s ( j 。，f ) + r ( j b ，g ) 】 s ( j b + 1 ，g ) = s ( j