（运筹学与控制论专业论文）（半）在线排序中若干问题的研究.pdf

摘要 摘要 本文研究了两类排序问题，一类是同型机上可中断半在线排序问题，一类是 同类机上的在线排序问题并且对这两类问题都给出了最优的( 半) 在线算法全 文共分为三章 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识 第二章主要研究了m 台同型机上已知总和的可中断半在线排序问题目 标是极小化最大的机器完工时间( a x ) 和极大化最小的机器完工时间( 瓯；。) 对于。目标，给出了一个最优的半在线算法，其竞争比为1 对于i 。目标， 当m 2 时，证明了任何半在线算法的竞争比至少为；黑等，并且对于m = 2 ，3 的情 形分别给出了最优的半在线算法 第三章主要研究了两台同类机上的在线排序问题，目标函数为极小化最大 工件开工时间首先证明了问题的下界为1 + s ，然后证明了贪婪( g r e e d y ) 算法 的上界为1 + s ，从而是最优的在线算法这里s 是两台机器的速度比 关键词：半在线，可中断排序，竞争比，同类机排序 a b s t r a c t a b s t r a c t t h i sp a p e rm a i n l ys t u d yt w o s c h e d u l i n gp r o b l e m s o n e i sp r e e m p t i v es e m i o n l i n e s c h e d u l i n go ni d e n t i c a lp a r a l l e lm a c h i n e s ，t h eo t h e ri so n l i n es c h e d u l i n go nu n i f o r m m a c h i n e s w ep r e s e n to p t i m a la l g o r i t h m sf o rt h e s et w op r o b l e m s t h ep a p e rc o n s i s t s o f t h r e ec h a p t e r s t h ef i r s tc h a p t e rg i v es o m ei n t r o d u c t i o n sa n dp r e l i m i l a r i e sf o rs c h e d u l i n gp r o b - l e m s t h es e c o n dc h a p t e ri n v e s t i g a t e st h ep r e e m p t i v es e m i o n l i n es c h e d u l i n gp r o b l e m o nmi d e n t i c a lp a r a l l e lm a c h i n e s ，w h e r et h et o t a ls i z eo fa l lj o b si sk n o w ni na d v a n c e t h eg o a li st om i n i m i z et h em a x i m u mm a c h i n ec o m p l e t i o nt i m ea n dt om a x i m i z et h e m i n i m u mm a c h i n ec o m p l e t i o nt i m e f o rt h ef i r s to b j e c t i v e ，w ep r e s e n ta no p t i m a l s e m i - o n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i o1 f o rt h es e c o n do b j e c t i v e ，w es h o wt h a t t h ec o m p e t i t i v er a t i oo fa n ys e m i - o n l i n ea l g o r i t h mi sa tl e a s t 鬻f o ra n ym 2a n d p r e s e n to p t i m a ls e m i o n l i n ea l g o r i t h m sf o rm = 2 3 t h et h i r dc h a p t e rc o n s i d e r so n l i n es c h e d u l i n go nt w ou n i f o r mm a c h i n e sw i t ht h e o b j e c t i v eo fm i n i m i z i n gt h em a x i m u mj o bs t a r t i n gt i m e w ep r e s e n ta no p t i m a la l g o r i t h mf o ra n ys 1 ，w h e r esi st h em a c h i n es p e e dr a t i o k e yw o r d s ： s e m i o n l i n e ，p r e e m p t i v es c h e d u l i n g , c o m p e t i t i v ea n a l y s i s ，u n i f o r m m a c h i n e s c h e d u l i n g i i 第一章绪论 1 1 排序问题 第一章绪论 一般的平行机排序问题可以描述为：给定一个工件序列o - = 如1 ，p 2 ，p 。) ，需要把它们分配到m 台机器尬，上去加工机 器尬的速度为s 。1 不失一般性，此时可以假定1 = s 1 8 2 冬茎s 。 如果将工件功分配给机器旭加工，那么p ，的加工时间为譬排序者的任务就是 寻找一个可行排序，使给定的目标函数达到最小( 极小化目标) 或最大( 极大化目 标1 我们一般用三参数表示法n 蚓7 来表示一个具体的排序问题，三个参数0 f ， 卢和，y 分别刻画了机器状况，工件特征和目标函数下面我们分别对每个参数所代 表的含义作具体介绍 a 主要描述了机器的数量和速度如果每台机器舰的速度岛= 1 ，则称 为同型( i d e n t i c a lm a c h i n e s ) 机，否则称为同类机( u n i f o r mm a c h i n e s ) 在。域中分别 用p 和q 表示本文主要考虑了这两种机器类型，当然还有其它的一些机器类型， 如不同种类机( u n r e l a t e dm a c h i n e s ) ，流水作业( n o ws h o p ) ，有序作业( j o bs h o p ) ，自由 作业( o p e ns h o p ) 等等 口主要描述了工件的特征，如工件是在线的还是离线的，加工是否可以中断， 工件是否需要准备时间，工件之间是否存在加工顺序约束等等我们会在下一小 结给出具体描述 吖主要描述了目标函数类似于所有的组合优化问题，任何一个给定的排序问 题都有有限个可行解，目标函数给出了这个含有限个解的解空间的一个度量，并 在这个度量意义下定义了最优解对于某个给定的排序问题，定义某台机器的完 工时间为安排好所有的工件后，最终分配到这台机器上的最后一个工件的完工时 间排序问题中最经典的目标函数是c _ 。( m a k e s p a n ) ，即极小化最大的机器完工 时间也就是对于每个可行排序，c - 。代表了最迟完工的机器的完工时间，现在 我们要在这有限个可行排序中找到一个c k a x 最小的最优排序与c _ 。目标对应的 第一章绪论 是c k i 。目标，与g 一目标不同，c k t 。是一个极大化目标，即极大化最小的机器完工 时间c k a x 和c k ；。从不同的角度刻画了负载均衡的思想，前者着重于控制负载最 大的机器，而后者着重于提高负载最小的机器的负载本文第二章主要讨论了这 两个目标函数，第三章讨论了极小化最大开工时间s 。a x 这一目标函数当然还有 很多其它的目标函数，如总完工时间，最大误工时间等等，请参考一些排序方面的 专著【2 7 排序问题有着广泛的应用背景，如计算机科学中的并行计算问题，管理科学 中的生产调度问题等等近几十年来，运筹学界对排序问题进行了深入的研究，其 思想与方法已经逐步渗透到了计算机科学，管理科学等学科领域中， 2 第一章绪论 1 2 在线，半在线，可中断，竞争比 经过几十年的研究，经典的排序模型有了很多的变体，并且这些改变都是与 实际模型相关的而本文所主要考虑的改变主要是集中在工件的性质方面 根据我们在排序时掌握工件信息的多少把排序问题分为离线( o m i n e ) 和在 线( o n l i n e ) 两类在离线问题中，全部工件的所有信息在排序时均已知，我们可以 充分利用这些信息对工件进行安排而对在线问题，我们只知道当前到达的工件 及之前的工件的信息，而对接下来的工件信息一无所知，其基本假设有以下两条： ( 1 ) 工件的信息是逐个释放的即工件“+ 1 的信息只有在排序者对工 件p 一，p ，作出安排后才会被排序者所知 ( 2 ) 工件加工不可改变即一旦排序者将工件安排给某台机器加工，在其后的 任何阶段不能以任何方式予以改变 半在线( s e m i o n l i n e ) 排序问题是介于离线问题和在线问题之间的排序问题， 也就是说我们除了知道当前到达的工件及之前的工件的信息，同时还知道一些 其它方面的信息常见的信息有预先知道所有工件的总长度( s u r n ) 2 4 】，最大工件 的加工时间( m a x ) 2 0 ，工件从大n d , 来( d e c r e a s i n g ) j 1 l ；2 】，工件的加工时间在一 个区间i ；k ( g r o u p ) 2 0 ，以及预先知道离线最优值( o p o 1 等等 半在线排序问题的研究主要体现在如何有效的利用这些已知的部分信息 来设计出更好的算法，即要求该算法的性能要比已知的最好可能的在线算法 的性能要好半在线方面的研究主要集中在排序问题尸m | | a x 和q m l a x 方 面f 4 ；6 ；1 3 它们研究了已知信息的多少与该排序问题的可近似程度之间的关系， 以及在设计近似算法时不同类型的信息的用处在半在线排序的研究出现之前， 几乎没人知道这些信息对于设计近似算法的有用程度，也几乎没人知道如何利用 这些信息来设计更好性能的近似算法因此，与经典的平行机排序问题一样，半在 线排序问题也是同样有趣和有意义的 可中断( p r e e m p t i v e ) 排序与不可中断( n o n p r e e m p t i v e ) 排序的主要区别在于： 对于不可中断情形，工件一旦分配给了某台机器，就必须一直在该机器上加工直 到结束；而对于可中断情形，工件可以在不同的机器上加工，只要保证在每台机器 第一章绪论 上加工的时间段没有重叠在很多实际系统中，例如许多操作系统的调度器，就是 利用可中断来平衡每个任务的等待时间，从而提高系统的响应时间因此，可中 断的调度策略具有重要的实际意义在另一方面，若在可中断的前提下，还允许并 行，即同一个工件的不同部分可以并行的分配给不同的机器处理，则会导致平凡 解( 每台机器的负载一样大) 所以，我们主要考虑不可并行的情形，即同一个工件 的不同部分必须是不可重叠的分配到机器上加工的。参照三参数表示法，记本文 研究的可中断问题为p i p m p t l c m a x $ 口p 1 w n p t l c k 。 一个在线或半在线算法的性能是通过它的竞争l l ( 最坏情况界) 来衡量的 对一个工件序列盯和算法a ，记a ( o ) 代表算法a 的目标值，o p t ( a ) 代表其离 线问题的最优值对于c 0 。目标，算法a 的竞争比定义为助= s u p a - - 型z l - ， ，对 于c k 。目标，算法4 的竞争比定义为r = s u p 号掣) 我们称一个在线( 半在 线) 问题的下界为p ，如果没有任何在线( 半在线) 算法的竞争比小于p 当问题的 某个在线( 半在线) 算法的竞争比等于问题的下界时，我们就称这个算法是最优 的 现在我们可以用排序的三参数法来描述下面两章中所讨论的问题第二 章主要讨论了p m l p m p t ，s u m c 。年 1 p m l p m p t ，s u m l c m i 。( m = 2 ，3 ) ，第三章讨论 了q 2 1 0 n l i n e l s 。a x 4 第一章已知总和的l - j _ 巾断半往线排序问题 第二章已知总和的可中断半在线排序问题 本章主要研究了m 台同型机上己知总和的可中断半在线排序问题该 问题可以描述为：给定一个工件序列o - = 研，p 2 ，m ) ，需要把它们分配 到m 台同型机晒，尬，上去加工不妨假定p ，( 1sj 礼) 代表每个 工件的加工时间工件和机器在零时刻都处于就绪状态，且工件的加工可 以中断问题的目标是使最大机器完工时间。最小或最小机器完工时 间c 二i 。最大我们主要考虑了该问题的半在线算法的设计，即预先知道所有 工件的加工时间之和( s u m ) 的情形利用排序的三参数表示法，该问题可以记 为p m p m p t ，b u t t 2 , i c k “或p m l p m p t ，s u m c k i n 本章共分为三节21 节首先总结了目前已知的一些在线，半在线算法的结 果2 2 节给p r n i p r n p t ，s u m l c m 。的最优半在线算法，其竞争比为1 2 3 节给出 t p m l p r a p t ，s u m l g k i 。( m = 2 ，3 ) 的最优半在线算法，其竞争比分别为l ( m = 2 ) 和；( m = 3 ) 5 第_ 章已知总和的町叶 断半疗三线排序问题 2 1 可中断半在线排序方面已知的一些结果 本节主要叙述在可中断半在线排序方面已有的和最新的研究结果由于可中 断半在线排序的研究主要集中在问题0 i 删i c k 。和问题q i p m i c f m ；。方面，所以 我们下面的讨论从这相应的两个方面出发 问题 最优算法的竞争比作者 p m p m p t ，o n l i n e i g n “ 丽薪一南 c h e ne ta l - 3 】， s g a l l 2 8 】 p m l p r n p t ，d e c r l c m h 。墨瓣r n 22 i n k 一孚 s e i d e ne ta 1 【2 9 】 p m l p m p t ，m a x i “ l i l a x 。m 22 i n k ；一孚 s e i d e ne ta 1 2 9 p 2 l p m p t ，g r o u p a x 4 + 2 r r ，1 r 2 h e ，j i a n g 1 4 】 i 4 ，r 2 p 3 p m p t ，g r o v e l c m “ 3 3 t 2 r1 r ； h e ，j i a n g 1 4 2 2 4 7 + + * 6 r ，i 3 r ： 2 _ 7r ： q 2 1 w n p t ，o n t i n e l c m “ f 曼! ) ! s + s + 1 w e n ，d u 【3 2 ， e p s t e i ne ta 1 【5 q 2 1 p m p t ，o p t c k “ l e p s t e i n 6 】 q 2 t p m p t ，d e c r l “m a x 蕊3 s + 3 ，簧措 e p s t e i n ，f a v r h o l d t 【7 】 国2 1 矽唧，g r o u p g m a x 糟，器攀啬) ，1 曼r 1 ，并且功1 ，将功的1 一二；一l 部分分给机器 疋，剩余部分分 给机器尬+ 1 ，s = s + 1 ，转4 3 若聊+ l ；一1 1 ，并且功 1 ，将工件功分给机器m ，t = t 一1 ，转4 4 若没有新工件到达，停机，否则令j = j + 1 ，返回1 引理2 2 ，2 ：算法a 1 的定义是合理的，即分给每个工件加工的时间段不重叠 证明：显然，按算法a 1 的第l 步和第3 步分配的工件的加工时间段没有重叠下 面我们考虑按4 1 的第2 步分配的工件根据第2 步的规则，我们有岛1 ，那 么功一( 1 一q 一。) sq 。这说明工件珊在机器m s + ( 此时骂i = o ) 上的完工时间 不超过它在机器 以上的开工时间，所以分配给聊的加工时间段没有重叠 定理2 2 3 ：算法a 1 的竞争比为1 ，因此是最优的半在线算法 证明：下面分两种情形讨论， 情形1 p m a x 1 根据 1 的定义，每个工件功，j = 1 ，2 ，一，n 都是由第1 步或 第2 步分配的，所以有 l ：= 琏= - = l 嚣= 1 ， 一r 一 第_ 辛已知总和的叫巾断半仵线排序问题 而根据引理2 2 1 ，就可以得至1 a l ( a ) = o p t ( a ) = 1 情形2 p m “ 1 设 y = p ： 弘1 ，i = 1 ，2 - ，n ) y = p j i p j 1 ，j = 1 ，2 一，n ) 并且= 眦爿仇 由于 t ( 1 ，礼) = p i + p j = m ， p i e x鲫e y 我们有osm i y | 根据 1 的定义，步1 和步2 将所有的工件p i x 分配给前 面的口台机器，因此珑= 1 ，h = 1 ，o t 一1 ，并且臻1 而步3 将所有的工 件四y 分配给最后的i y l 台机器，并且是每台机器分配一个工件这样我们就有 进一步若o t 2 时，问题p m l p m p t ，s u m g 。i 。的任何在线算法的竞争比至少 为鬻 证明：通过标准化，可以假定t ( 1 ，他) = m 首先m 一1 个工件p 。= p 2 = = p m t = ；占到达当在线算法4 将这些工件分配给所有的m 台机器后，假定各台 机器的当前负载为f 1 f 2 f 。下面分两种情形讨论 情形1 - f 。i m 鬲- j i 则最后m 一1 个工件p 。= p m + 1 - = p 2 2 1 到达我 们有a ( 盯) 丽m - - 1 ，根据引理2 - 3 1 1 ，o p t ( 口) = 1 z f f p a r a 2 而m 二- 3 情形2 k 丽m - i 由于 ( m 一2 ) f 2 + f 。sb + f 2 + + f m t ( 1 ，m 一1 ) = 1 我们有f 2 i ；忑1 此时最后一个工件p m = m 一1 到达我们有a ( 盯) i 鬲1 j ，而根 据引理2 3 1 1 ，o p t ( a ) = 志，所以r 桨 在本节的其余部分，我们引进髟代表半在线算法j 4 运行时在j 时刻( 第，个工 件被分配完时) 机器尬的负载并且约定l ：= 0 第：二章已知总和的川中断半存线排序问题 2 3 2 算法 本小节我们给出问题p 3 lp m _ 讲，s u m i c 。i 。的晟优半在线算法4 2 的定义同理， 通过标准化，可以假定t ( 1 ，礼) = 3 ，f f r 以o p t ( a ) 茎1 为了描述算法a 2 ，我们首先 定义两个子过程b ( 脶，) 和g ( 脶，舰) ，其中s ；，将功分给机器舰，剩余的所有工 件p ，+ 1 ，m 都分给机器 矗，停机 3 若功+ q 一， ；并如+ 骂一lsi 2 ，将功的；一q 一，部分分给机器旭，剩余 部分分给机器尬，其余的所有工件秘+ h ，强都分给机器慨，停机 下面我们给出p 3 i p m 融s u m i c k i 。的最优半在线算法 算法a 2 0 设j = l _ 一1 2 第一章已知总和的可巾断半在线排序阔题 1 ；g p j i 2 丌“1 一l j 2 ，调用子过程b ( m 1 ，a 如) 分配工件p j ，j = j - - 1 ，返回1 2 若功 ；并且l ；一l ；，调用子过程g ( 如， 矗) 分配工件鳓，p j “，m ，停 机 3 若；功 1 ，将工t c p j 分给机器慨，i n n c ( m i ，尬) 分配工件功+ b 一， 停机 4 若p j 1 ，将工件p j 分给机器尬，调用b ( 几n ，m 2 ) 分配p 什一，p n 中的每一 个工件 第章已知总和的“】中断半任线排序问题 2 3 3 算法分析 本小节将证明a 2 是解问题p 3 1 p m p t ，s u 蚓c k j 。的最优半在线算法 引理2 3 3 1 ：子过程b ( 炳，尬) 和a ( m ：，) 的定义是合理的，即分配给每个工件 的加工时间段没有重叠 证明：显然，m b ( m 1 ，尬) 的步l 和步3 分配的工件的加工时间段没有重叠下面我 们考虑由步2 分配的工件容易知道功在机器 如上的完工时间为 骘：譬一，+ ( 圭玉三学一骂一。) = 圭圣土学 由于功+ 曰一1 2 三；一1 ，故 生掣q 一。 3 一j 一 所以功在机器 如上的完工时间不超过它在机器m ，上的开工时间l ；一因此分配 给机器的加工时间段没有重叠 同理，我们只需考虑由g ( 尬，舰) 的步3 分配的工件假定功是由步3 分配的第 一个工件由于功+ 玛一1 ；，故 l ；= l 2 i - i + 功一( ；一巧一。) q 一， 这说明功在机器胍上的完工时间不超过它在机器地上的开工时间，所以分配给 工件胁的加工时间段没有重叠而分配给工件功+ 1 ) ，的加工时间段没有重叠 是显然的 引理2 3 3 2 ：如果工件功是由子过程b ( 尬， 毛) 分配的，那么我们有上。2 曰 一 第一辛已知总和的a j 叶一断半在线排序问题 证明：如果协是由步1 分配的，那么我们有 l y = l ；- i + p ys 等i 1 ：譬 如果胁是由步2 分配的，那么 并且 骘：堕等也 目：l j _ i ：- + p y ( 生挚一l 2 ) ：目=( 生卫竽一) = 因此l ；= 2 l ；如果p j 是由步3 分配的，那么 2 ( l j 一1 + 日一1 + 功) 广一 工；= l ；一。十聊一( 殇。一留一t ) = 骘一t + 功 由以上引理2 3 3 2 可知，子过程胃( m 1 ，) 尽可能的保证机器坛和蝎上的负 载比例为2 ：1 而接下来的一个引理将说明子过程g ( 舰，尬) 将尽可能保证机 器 以的负载不少于；，而机器尥的负载等于；，除非来了一个大工件，并且这个大 工件将被放到机器尬上去 引理2 3 3 3 ：如果工件功，胁+ 1 ，m 是由子过程e ( m 。，m t ) 分配的，并且q 一1 i 2 进步若蟛 j 2 ，那么一定存在一个大工件鲰( j ) ，使得仇被单独分配给机器，而工 牛p k + 1 ，m 均分给机器m 。，并有瑶= q 一1 + t ( j ，) 一m o 珐 1 l q 譬 一 啡呀 + o 日 磅此 = 因 譬 巾 弓 2 翳 + 一 弓 为 且 因 卓k 又 第二章已知总和的u j 叶 断半存线排序问题 证明：分两种情形考虑： 情形1 娣= ；假定碍s ；那么我们有瑗+ l ：s ；既然c ( 舰，尬) 将工 件功，p j 仙，分给机器 缸和 矾，而根据假设，我们知道 蟛+ 工：= t ( j ，礼) + l ；一，+ 巧一， ；， 这与塌+ 砖；矛盾所以或 ； 情形2 瑶；注意若所有的工件协，p 。都是由e ( 燧，m t ) 步1 分配的，则 并且瑗= 上；一1 ； 矛盾那么存在一个工件m ( a j ) 是由g ( a 以，舰) 的步2 或步3 分配的如果m 是 由g ( m 。，舰) 的步3 分配的，那么我们有 瑶= 磙一，+ ( ；一珥一。) = ； 矛盾因此徘是c a t ( m , ，地) 的步2 分配的，那么g ( 眠，必) 将孤分给机器地， p k + 1 ，m 分给机器 以所以 并且 l ：一巧一1 + t ( j ，n ) 一p l ：= p 。+ l ：一， ； 注记2 3 ，3 ha 2 不可能按步1 分配完所有的工件，实际上，若假定每个工件p j 0 = 一1 6 第一章已知总和的u 】巾断半钨：线排序问题 i ，n ) 都是由b ( m i ，m 2 ) 分配的，那么根据引理2 3 3 2 ，我们有 r 2 ，e 一1 l n 一1 i 一 既然p n 也是由步1 分配的，那么 ；并且碟一。 j 2 那么 p 。+ 厶：一，+ l ：一， ；， 而这与t ( 1 ，礼1 = 3 矛盾 注记2 3 3 - 2 ：显然，一旦菜个工件功是由a 2 的2 4 步中的某一步分配的，那么算法 将在该步终止 注记2 3 3 3 ：若a 2 调用b ( 矗，m 2 ) 分配当前到达的工件功，那么一定是下列两种 情形之一： ( 1 ) a 2 在步1 调用b ( m 1 ，m 2 ) 分配所有的工件 p 1 ，p 2 ，所) ( 2 ) a 2 在步4 将 p 1 ，p 2 ，一，功) 中第一个不小于1 的工件分配给机器m 3 ，而在 步1 和步4 调用b ( 五，) 分配所有如1 ，p 2 ，功 中剩余的工件 下面介绍算法a 2 的主要思想：既然离线最优值至多为1 ，我们要尽量保证每 台机器的负载至少为2 3 ( 通过算法a 2 的步1 3 ) ，这使得算法的竞争比不太于- 3 2 如果存在一个大工件p j 1 ，那么最优值由剩余的工件总长度t ( 1 ，n ) 一p ，决定，至 多为匹l 号l 丑1 我们将它单独分给机器且如，在a 2 的步l 和步4 调用丑( 尬，a 如) 将 剩余的工件分配给机器m i 和 如，并保证两台机器的负载之比为2 ( 例如，m 2 的负 载为三【；l ；) 二韭) 这也保证了算法的竞争比至多为墅埤二班塑掣二丑= 3 2 引理2 3 3 4 ：算法a 2 的定义是合理的，即它总能产生一个可行排序 证明：根据引理2 3 3 1 ，由算法j 4 2 分配的工件的加工时段没有重叠下面我们将 要证明4 2 调用b ( 尬， 如) 和g ( 蟊， 4 ) 分配当前到达的工件m 的过程是合理的 1 7 第二章已知总和的u j 中断半在线排序问题 考虑b ( 舰，尬) 的定义觏是由步1 分配的，必须满足条件岛+ 上孑一。警 所以l ；一1 2 曰_ 1 若功是由步2 分配的，则有 l j l + 鼍一1 + 巩 i 所以l ；一1 + p ，2 三；一1 因此l ；一。22 上；一1 是4 2 调用b ( 舰，尬) 时需满足的充 分条件，若功是由步3 分配的，那么l ；一】一三；一1 o 必须满足综上所述，当调 用b ( ，且如) 分配工件功时，只须满足条件e 一】2l ；一】 在另一方面，既然碥= l 3 = 0 ，满足l 52 玮这样我们可以调 用日( 矗，m 2 ) 分配工件p 1 根据引理2 3 3 2 ，我们有l 2 髓，这样我们又可 以调用_ b ( 尬，尬) 分配下一个工件那么我们可以调用b ( ，) 分配系列的 工件，根据注记2 3 3 3 ，这正是a 2 调用口( 蝇，) 的方式 根据g ( 地， 引的定义，当调用g ( 以， 分配工件时不需要满足额外的条 件 引理2 3 ，3 5 ：设功是由算法a 2 的步2 分配的第一个工件，那么l 一1 j 证明：根据注记2 3 3 2 ，前面的j 一1 4 工件( 当然包括肼一1 ) 是由a 2 在步1 调 n b ( m ，尬) 分配的根据a 2 的规则，那么我们有功一1 ；并且目一。 ；不 管b ( m ， 如) 如何分配工件印一都有功1 目一2 + 胁- h 因此l ；一l 2 日那么存在一个工 件柳( f j ) ，使得a l ；一! 专兰，其中茁0 i 鲫f l ：根据注记2 3 3 3 ，可知切1 ，协一1 ) 中已经分配给机器 磊和的工件也 是由b ( m 1 ，) 分配的定义 日= 川m 被分给机器 以和( 或) 舰，h j ) ，c = i h 根据引理2 3 3 2 ，对于每个 h ，有珠2 l 2 假定口中的工件为b ，a 。，鼽。， 并且i 1 i 2 - 2 q ，那么根据引理2 3 3 2 的证明，功是由b ( m l ，尬) 的步1 或步3 分 配的下面分两种情形考虑：( 1 ) 若功是由步3 分配的，记f = j ，z = o ( 2 ) 若功是由 步1 分配的，那么我们断言一定存在一个工件a 。( q 2 l 6 ，根据b ( 舰，) 的定义， 纯。是由步3 分配的，矛盾不妨假定是日中最后一个由步3 分配的工件，那么显 然鼽。+ ，胁。是由步1 分配的记f = i q ，z = 鼽。 0 q b c 根据以上所讨论的工件研和工件砘+ 1 ，功( 如果f j ) 的分配，我们有 日= l l 。+ p f 一( l j 。一l 1 ) 曰= l i ，+ ( l _ 1 一上 ，) + 茁 那么可以得到l t = 骂一p l ，l l ，= 工；一z 结合l - i 2 l l l ，我们可以得 至i j l 2 一z 2 ( q 一肌) ，即鼽日一生竽 一 定理2 3 3 7 ：算法a 2 的竞争比不大于2 ，因此是最优的 证明：设功是由a 2 的步2 ，3 或4 分配的第一个工件显然，p 1 ，一，功l 是由 2 的 步1 调用b ( 脑，m 2 ) 分配的根据引理2 3 3 2 ，我们有目一l 2 骘- 1 下面我们根据 工件功的分配分三种情形讨论 情形1 p j 是由步2 分配的此时骘一t = 0 那么骂一。；，工 件协，功+ 1 ) ，是由g ( 必，鸠) 分配的因此l j = 日一t ；下面我们来估 1 9 第_ 章已知总和的可中断半订：线排序问题 、。l n 。2 “。3 根据引理2 3 3 5 ，可得l ；一1 ； i 2 结合骘一1 = 0sj 2 ，根据引理2 3 3 3 ，我们有l ：2 ； a 2 ( a ) = m i n ( l j ，l ：，l ：) 所以喾并；因此我们假定碍 ；根据引理2 3 3 3 ，存在一个工件m ( 七j ) ， 使得玩= 曰一，+ t ( j ，n ) 一p k 因此 a 2 ( a ) = m i n l ：，l ：，l i ) = l ：= 霹一，+ t ( j ，n ) 一p 既然l 。2 骘- l ，下面分两种子情形考虑 子情形1 1 日一1 = 2 骘一既然t ( 1 ，n ) = 目一。+ l 知。+ t ( j ，几) ，根据引理 2 3 1 1 ，我们有 o p t ( o ) s 既然q ，= 2 写一。，可得 三( ! ! 兰2 二堡! 堡= ! 垡二! ! 鱼! ! ! 二翌1 2 2 o p t ( a ) ，l ；一1 + 日一l + t 0 ，佗) 一p a 2 ( a ) 22 ( l ；一1 + t ( j ，他) 一p ) 器糕 2 ；寸根据引理2 3 3 6 ，存在一个工件鼽( f5 一1 ) 使 得印2 目一1 一生，其中g 0 结合引理2 3 1 1 ，可得 o p t ( a ) t ( 1 ，礼) 一仇。一砘。一。sl ；一1 + l ；一1 + t ( j ，礼) 一p k p z 一2 0 一 生。幺 一那 1 2 3 骘 且瑶 并若 第二章已知总和的叫巾断半神i 线排序闯题 因此 ! 堡二! 二兰! 竖堕! l 堡! 一 2 o p t ( a ) 3 l ；一t 一。+ 2 ( t ，豫) 一p ) 3 a 2 ( c r ) 。2 ( l ；一1 + r d ，礼) 一p k ) 。2 情形2 聊是由步3 分配的此时，我们有目一l ： u 根据引理2 3 3 3 ，我们有瑗j 2 若碍；，我们有 a 2 ( 小：m i n l ：，l i ； 那么! 箬磊导sj 3 因此我们假定碥 j 2 根据引理2 3 3 3 ，我们有 a 2 ( 盯) = m i n 工：，l ：，噬 = l ：= l ；+ t ( j + l ，礼) 一p k ，2j + 1 根据引理2 , 3 1 1 ，我们有 o p t ( a ) 曼t ( 1 ，佗) 一p i 。一n 。一，s t ( 1 ，n ) 一p j p = l ；+ q 十t ( j + 1 ，) 一p 女 结合l ；22 巧，可得 o p t ( a ) ，日+ 骘+ t ( j + 1 ，n ) 一p k ，! a 2 ( 口) 2l ；+ t ( j + 1 ，札) 一p 一2 第= 章已知总和的u ，中断半融线排序问题 情形3 功是由步4 分配的