（运筹学与控制论专业论文）lp范数下两台同型机排序问题研究.pdf

摘要 摘要 本文研究了两台同型机的在线和半在线排序问题该问题可以描述为： 给定一个相互独立的工件序列j = p t ，p 。，) ，每个工件的加工时间( 长 度) 是鼽，i = 1 ，n ，且需要把它们分配到两台同型机尬， 如上进行不可中 断地加工工件和机器在零时刻都处于就绪状态机器的负载是指所有在 这台机器上加工的工件的总长度在算法s 下机器舰的负载记为z 。( z s ) ( 在不 会引起歧义的情况下，可筒记为地i = 1 ，2 ，目标是极小化机器负载的z ，范数， 即k ( j ，s ) 三 l ( g ，s ) 9 + 1 2 ( 一s ) 9 】；，这里p 1 全文共分为三章 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识 第二章主要研究了k 范数下两台同型机上己知工件按照加工时问从大到小 的顺序到达的半在线排序问题我们证明了l s 算法是求解该问题的最优半在线 算法，竞争比为思瑟( 坠老拶) 9 ，同时还证明了该问题及其所对应的在线 问题的随机下界 第三章主要研究了f 。范数下两台同型机的另两个半在线排序问题对于已知 工件的最大加工时间和总加工时间的两个问题，证明了最优半在线算法的竞争比 均为( 生等业) ； 关键词：排序，半在线，随机下界，竞争比，岛范数 a b s 仃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 i e so n l i n ea n ds e m i - o n h n es c h e d u l i n gp r o b l e m so nt w o i d e n t i c a lm a c h i n e s g i v e nas e q u e n c ej = p 1 ，p 2 ，m ) o f i n d e p e n d e n t j o b s ，e a c h w i t h a p o s i t i v e p r o c e s s i n g t i m e ( s i z e ) p i ，i = l ，n ，w h i c h m u s t b e n o n p r e e m p t i v e l y s c h e d u l e do no n eo f t h et w oi d e n t i c a lm a c h i n e s 脑，尬t h el o a do f am a c h i n ei st l l e t o t a ls i z eo ft h ej o b sa s s i g n e dt oi t t h el o a do fi - t hm a c h i n er e l a t e dt oa na l g o r i t h m si sd e n o t e db yk ( z s ) ( f i ) ，i = 1 ，2 ，r e s p e c t i v e l y t h eo b j e c t i v ei st om i n i m i z et h e s u mo f t h e f pn o n n o f m a c h i n e s l o a d ，i e ，岛( | ，s ) 三【“( z s ) ”+ t 2 ( j , s ) 9 】；，w h e r e p 1 ( n o r e t h a tf o rp = 1 ，t h e p r o b l e mi st r i v i a la n da n ya l g o r i t h my i e l d sa no p t i m a l s o l u t i o n ) t h ep a p e rc o n s i s t so f t h r e ec h a p t e r s c h a p t e rlg i v e ss o m ei n t r o d u c t i o na n dp r e l i m i n a r i e sf o rs c h e d u l i n gp r o b l e m s c h a p t e r2i n v e s t i g a t e st h es e m i - o n l i n es c h e d u l i n gp r o b l e mu n d e rt h el pd 0 1 t u o nt w oi d e n t i c a lm a c h i n e s ，w h e r ej o b sc o m ei nn o n - i n c r e a s i n go r d e ro ft h e i rs i z e s w ep r o v et h a ta l g o r i t h ml si so p t i m a lf o ra n y 知n 0 1 t l lw i t l lc o m p e t i t i v er a t i o l m 1 ，极 d 刊c t 。范数也有其应用背景 2 比如一个工件的加工时间对应于机器磁盘存取的 频率，那么每个工件有一个与对应机器的负载成正比的延迟因此，工件的最大 延迟与机器的最大负载成正比( 即机器负载的k 范数) ，平均延迟则与各机器负载 的平方和成正比( 即机器负载的f 2 范数) 3 f ，范数下的排序除了有其实际应用，对 这类问题的理论研究也同样重要事实上，最优化问题特别是排序问题的一个主 要缺陷是对于目标函数每个不同的度量都有不同的最优解通常，不同算法用于 不同度量，也都给出了自己的解因此，人们自然会问：对于给定的一个排序问 题，到底哪个是真正”正确”的解，是否有一个算法，它在不同的度量下均是有 效的? 本文针对某些问题给出了肯定的回答当然另外还有很多其它的目标函 数，如总完工时间，最大误工时间等等，请参考一些排序方面的专著【l 】 2 第一章绪论 1 2 半在线问题和竞争比分析 根据我们在排序对掌握工件信息的多少把排序问题分为离线( o f f ：l i n e ) 和在 线( o n l i n e ) 两j 类在离线问题中，全部工件的所有信息在排序时都是已知的，我 们可以充分利用这些信息对工件进行安排而对在线问题，是指工件的信息逐 个释放，即工件p 件1 的信息只有在对工件p 一，a 进行安排后才会被释放，并且 工件一个个到达，一旦到达，就必须安排它在某台机器上加工，且在以后不可改 变半在线( s e m i o n l i n e ) 排序问题是介于离线问题和在线问题之间的排序问题， 也就是说我们除了知道当前到达的工件及之前的工件的信息，同时还预先知 道工件的部分信息，但仍不允许对任何已安排的工件进行重排【4 ；5 常见的信 息有预先知道所有工件的总长度( s u l h ) f 6 】，最大工件的加工时间( m a x ) j 7 ，工件 从大到小来( d e c r ) 8 ；9 】，工件的加工时间在一个区间i 内( g r o u p ) 7 ，工件的相对大 、( o r d i n a l ) 1 0 ，以及预先知道离线最优值( o p t ) 1 l 】等等半在线排序问题的研究 主要体现在如何有效的利用这些己知的部分信息来设计出更好的算法，即要求该 算法的性能要比已知的最好可能的在线算法的性能要好在半在线排序的研究出 现之前，几乎没人知道这些信息对于设计近似算法的有用程度，也几乎没人知道 如何利用这些信息来设计更好性能的近似算法因此，与经典的平行机排序问题 一样，半在线排序问题也是同样有趣和有意义的 对离线问题，我们将求解离线问题的算法称为离线算法离线算法的性 能用最坏情况界( w o r s t - c a s er a t i o ) 来衡量对一个工件序列j 和算法s ，记s ( j ) 代表算法s 的目标值，o p t ( j ) 代表最优值对于极小化目标，算法s 的最坏情 况界定义为c ( s ) = 8 u p 帮s 争j 击) 对于极大化目标，算法s 的最坏情况界定义 j 、。 为e ( s ) = s u p 帮) 对于一个( 半) 在线问题，求解该问题的算法就称为( 半) 在线算法( 半) 在线算 法的性能是可以通过它的竞争比( c o m p e t i t i v er a f t o ) 来衡量的其定义与离线算法 的最坏情况界类似，其o o p t ( j ) 为相应离线问题的最优目标值我们希望设计 出竞争比尽可能小的算法，如果没有任何( 半) 在线算法的竞争比小于岛则称这 个( 半) 在线问题的下界为p 当这个问题的某个( 半) 在线算法的竞争比等于问题 的下界时，我们就称这个算法是最优的对k 范数来说，如果有一个算法对所有 的p 1 都是最优算法，那么可以称为全范数最优算法【2 例如p 2 l 琵m ( 1 2 】， p 2 l o r d i n a l 1 。 1 3 】问题都有了全范数最优的算法 3 第一章绪论 所谓随机性算法是指算法在执行过程中可以作出随机选择的一类算法这种 选择不完全依赖于算法的输入，但决定着算法以后的执行情况和算法输出换句 话说，对同一输入多次运行算法，由于所作的随机选择不同，算法的实际进程可能 会有所不同，最后得到未必相同的输出，这是它与确定性算法的最大区别对随机 算法s 和工件序列j ，s ( j ) 是算法在执行过程中产生的那些随机变量的函数，因 此我们不再用某一次执行算法得到的结果，而用其期望值( e x p e c t a t i o n ) e ( s ( l ，) ) 来 定义随机算法s 解工件序列t ，所得的目标函数值，这里期望取遍随机变量所有 可能的取值对随机算法也可引入竞争比的概念，但比确定性算法更为复杂一 些可以用e ( s ( j ) ) 代替上式中的s ( t ，) ，即对于极小化目标，算法s 的竞争比定义 为c ( s ) = s u p 万e 寺s 瓣j ) 对于排序问题的随机下界可利用y a o 定理得至l j 1 4 1 4 一一苎二垩堕笙 1 3 论文概述 本文所讨论的几个排序问题分别可以用三参数表示法记 为p 2 1 0 n l i n e l l p 、p 2 1 d e e r l l p 、p 2 m 口。f 岛和尸2 扣“m f k 第二章主要讨论p 2j d e c r j k 和p 2j 帆f i n e i f p 问题首先对p 2 | d e c r 忆问题，我们 证明了l s 是竞争比为，登( 坠镑警) 的最优半在线算法，并且给出了 上述两个问题的随机下界，分别为1 当a 雯万轰a2 和n a ，笋j 9 貉，这 l ，a l o n 等 2 3 】提出了一个问题的多项式近似方案最近，a z a r a g l t a u b 2 4 给出 了p m l o f f l i n e l l p f 司题的一个近似算法，对任意的p 1 ，最坏情况界不超过1 3 8 7 5 平行机排序问题随机算法研究是排序中的难点对于p 2 1 0 n l i n e l g 一， b a r t a l 等 2 5 1 提出了竞争比为；的最优随机算法对于问题p 2 l d e c r c k 。，s e i d e n 等 2 0 给出了一个竞争比为；的最优随机算法最近，a l b e r s 2 6 提出 了问题p m l o n l i n e i 。的随机算法，当m 趋向于无穷时，该算法的竞争比 为1 9 1 6 对p m l o n l i n e l e k 溉j i a n g 等【2 7 】证明了问题的下界至少为墨1 1 i 然而，很少有文献研究l 范数下的随机算法在本章的第三小节将给出 t p 2 l o n l i n e l l 。和p 2 l d e c r l l p 问题的随机下界 7 堕三童生蔓堑工堕鱼旦型垫堕窒型塑堕盟堑壁囹星 2 2 p 2 l d e c r l l p 最优算法 本节我们讨论1 u n p 2 t d e c d g ，证明了对于任意的p 1 ，l s 是最优的半在线 算法，竞争比为，罂杰( 坠薏；嘉￥；掣) ；因此，对于这个半在线问题l s 是全范数最 优半在线算法 2 该结果也推广t s e i d e n 等【2 0 】的结果 在本节接下来的部分，我们均假定工件以饥，p 2 ，m 的顺序到达，且工件是 按照它们的加工时间从大n 4 , 的顺序到达，即拂p l + 1 ，i = 1 ，n 一1 我们首 先给出一些引理 引理2 2 1 ：定义h ( r ) er p + ( c r ) 9 ，0 r c ，其中c 是一个常数，则( 1 ) 当r 时，日( r ) 是单调递增的；( 2 ) j 岛h ( r ) c p ；( 3 ) 日( r ) 是关于i c 一2 t i 能j 单调递 增函数 证明：显然日7r ) = 矿9 一p ( c r ) ，方程日协) = o 有唯一解r = ，r h ( r ) o 当且仅当r 睦，c 由此n n n r 禹cc 】时，日( r ) 单调递增；当r 1 0 ，) 时日( r ) 单 调递减因此 蔷= 日( ；) = 逡氅日( r ) 日( r ) 。m ：，a ：x 。h ( r ) = 日( c ) = c p 因为当r 唔c 】时，i c 一2 r 单调递增，当r 【0 ，i ) 时单调递减，由此可 得日( r ) 关于l c 一2 r l 是单调递增的 引理2 2 2 ：对于问题尸2 i d e 盯l ，对任意满足川4 的工件序列j ，l s 算法总产生 最优解 证明：l j i 3 6 9 情况是平凡的因此我们只需考虑i j i = 4 为了方便起见，我 们假设所有工件总长度是1 用b 表示将任意两个工件放在一台机器上，剩余工 件放在另外一台机器上的算法用e 表示将任意三个工件放在一台机器上，剩 下的一个工件放在另外一台机器上的算法n o p r 必然是b 和a 中的一种因 此只要i 正n l ，( zl s ) l p ( zb ) 和l ，( zl s ) l p ( za ) 就可以得到所要的结果 令i ，j ，七 2 ，3 ，4 ) ，i j 注意到，如果一个算法a j j n t 完工件后某台机器的 负载为r ，则目标值为l p ( z a ) = ( g , p + ( 1 一r 翔；由于p l p 2 p s p 4 且总长 为1 ，u m a x r ，1 一r ) 2i 1 由引理2 2 1 ( 1 ) 可知，( o ( j i a ) ) ，关于m a x r ，1 一r ) 是单 调递增的 箜三至生翌塑! 堕鱼堕型塑塑重型塑堕垫塑! 堡塑嬖 若p l2p 2 + p 3 ，则_ l p ( z l s ) 一( 硝+ ( p 2 + p 3 + p 4 ) ) ；由亍：m a x p l + p i ，p j + p k ) = p l + 鼽m a x p i ，p 2 + p 3 + p 4 ，则k ( j ，l s ) sl p ( j ，b ) 同理可 得岛( zl s ) l p ( 五g ) 若p l p 2 + p 3 ，则三p ( z l s ) = ( ( p l + m ) 9 + ( p 2 + p 3 ) 9 ) ；， 上，( 工b ) = ( ( p l + p i ) n + ( 功+ p k ) ) ；因为，j ，b 2 ，3 ，4 ) ，i j k ，j 目- p 1 p 2 p 3 p 4 ，所d a m a x m + p i ，协+ m p l + p 4 ，n l a x p l + 仇，p j + p k p 2 + p 3 由 此推出五，( 正l s ) l p ( zb ) 同理可得岛( z 三s ) sl p ( zg ) 因此l s 对含有4 个 工件的序列总产生最优解 引理2 2 3 ：q ( 三s ) 可以由工件序列矗= 妇，y ，z ，z ，z ) 达到，其中 f 1 ( z 上s ) 的情况类似) 则肌必然安排 在第二台机器上加工事实上，若不然，我们记s 为p n 分配在第一台机器上的开 工时间由于考虑最小数目工件的序列，则有f l ( z l s ) = 8 + 肌由l s 规则可 得s i 2 ( z l s ) 因此 l ( z l s ) 一f 2 ( z l s ) s ，矛盾 令j = 如1 ，0 2 ，p 。一1 ) ，贝u l t ( j ，l s ) = f l ( 工l s ) ，f 2 ( j 7 ，l s ) = f 2 ( 正l s ) 一 不失一般性，设o p t 将p 。放在第二台机器上加工设算法p 安排工件序列，的 方法与最优算法0 p t 安排t ，的一样令“= f 2 ( 以l s ) ，v = f 2 ( 正o p t ) ，则有 即 嚣器制l p 器o p t ， 亿- ， 岛( ，d p r ) 一( z ) 。 ( 1 一u ) p + ( “一p 。) 9 、( 1 一“尸+ u p 一面( j 7 ，o p t ) ) p。( 1 一v ) p + p 由于l ，( l ，o p t ) l v ( j ，p ) = ( ( 1 一口) ，+ 扣一) ，) ；则 ( 1 一 ) 9 + ( “一p 。p 、( 1 一u ) + ( “一p 。尸 ( l ，( j ，o p t ) ) p 二( 1 一u ) p + 如一p 。) p 9 第二章f ，范数下两台同型机确定型和随机排序问题 设e ( z ) = ( 1 1 1 ) 9 + ( u z 户，( b ( z ) = ( 1 一”) 9 + ( v x ) p ，叫( z ) = g ) q ( 。) ， 因此 喇= 型业嘉掣型盥， 南于 之u 。，c 1 ( x ) q ( 茁) ，则7x ) 0 ，因此 ( ? k ) ( 0 ) 由此推出 ( 1 一“) 94 - ( u p 。户、( 1 一u ) 9 + 舻 ( 1 一 ) 9 + 一p n ) p 。( 1 一u ) p + 伊 因此( 2 1 ) 成立由于序列，中的工件的总长度小于l ，我们可以将工件长度乘以某 一个数使得总长度为l ( 进一步标准化) 因此对任意不满足( j ) 的，我们可以不 断去掉j 中的最后一个工件直到它满足( i ) 为止( 注意到对单个工件的序列，( i ) 自然 成立) 下面证明( 蛾考虑序n j = 1 4 ，1 4 ，1 6 ，1 6 ，1 6 注意到对任意的算 法a ，两台机器负载的差为h ( a ) 三 l l ( j , a ) 一1 2 ( j , 脚! = 1 1 2t 2 ( j , a ) i 则 有h ( l s ) = ：6 且_ h ( o p t ) = 0 由引理2 1 ( 3 ) 可知对任意含有5 个工件的序列j ， k ( z l s ) 是九( 二s ) 的单调递增函数如果序列j = 1 4 ，1 4 ，1 6 ，1 6 ，1 6 已经 使之黼达到最大，那么这个就是我们要找的工件序列若不是，为了增 加芒揣的值，必须选择序列维得 ( 上s ) 1 6 由条件( i ) 可得陬 1 6 然而 由于工件总长为l ，且p l p 2 肌可得p n ：n ，从而推出ns5 结合引 理2 ，2 2 ，可知可知i j l = 5 因此( i i ) 成立 现在回到引理的证明给定一个非增序列j = p 1 ，p 2 ，船 ，p 5 1 6 ，由 于l p 。一p 5 3 p 5 ，贝i j p l 1 3 显然任意三个工件的总长大于1 2 也就是说任 意三个工件的总长大于剩余工件的总长最优算法o p t , 必须将p 1 和p 2 分在一台机 器，p 3 ，p 4 ，p 5 分在另一台机器由于p l ：2 我们通过以下三步来得到我们所要的序列： ( a ) 设= 虹地与j 2 i 型，用硝= p l 一和匝= p 2 + 分别替代p l ，i a 2 ，显 然 ( l s ) 增大而h ( o p t ) 保持不变因此意黼变大且有计+ p 4 = 吐+ p 3 ( b ) 设一= 红手，用硝= 拼一e 7 ，硝= 照+ ，砖= p 3 一7 和哎= 挑+ 7 分别 替代科，癌，p 8 和m ，于是有肼n = 硝，砖= 或，且危( l s ) 和 ( o p t ) 均不变 ( c ) 设= 血3 塑，碟= 砖一，硝= 珐一，晓= p s + 2 9 ，则碟= 砖，j l h ( l s ) 的 l o 塑三兰生蔓塑! 堕鱼旦型塑堕宣型塑堕! ! 塑! 堡囹里 增加不影响 ( o p t ) 因此导出一个更大的考矗笨现在我们得到了一个序 列= p ! ，碟，碟，硝，炖) ，它满足硝= 硝，碟= 蹦= 感，且硝2 碟s 硝 情况2 p 1 + p 4sp 2 + p 3 n p l ，p 4 和p 5 被安排在同一机器上设= 地血盟= i 2 捌，玩= p a e ，硝= p 4 + 贝l j h ( l s ) 变大 7 9 h ( o p t ) 不变，因 此专为 器变大，j t 导o a p ，+ p ：= p 2 + 砖这与情况l ( a ) 相似因此可以通过 类似于情况1 ( b ) 和( c ) 的讨论得到结果 由此可见8 u p 专盎笛岛由工件序列而= g ，g ，z ，2 ，z ，2 1 ，q ( l s ) 1 鼍客毛，p ( ) - 证髓：由引理2 2 3 可得g ( l 固s u p 毒揣，由于k ( 如，l s ) = ( 白+ 2 2 户+ 白+ z ) 9 ) i 1 和l ，( j o ，o p t ) = ( ( 2 可) 9 + ( 3 2 ) ) ；，则 肼 幽s u p ：y z z ( 豁i ) ； ：f ，。、o o ， 令a = y z ，月, l j ls a 1 ，x = 2 不是上面方程的解n n a 4 2 由此得证 第二章k 范数下两台同型机确定型和随机排序问题 引理2 2 5 ：对任意的p 1 ，任何求解p 2 l d e r c 的确定型算法的竞争比至少 为1 ，) “ - ：n t z 若算法a 将这两个工件分给不同的机器，则最后来三个长度都为】的工件 设j = + ，a + ，1 ，1 ，1 ) 则有 丽l p ( j 丽, a ) ( 堕菡2 a 筹3 p 业) ；= 盟，p ( )岛( z o p t ) 2 、 (+ ) ，+送z 急坤、一7 因此我们可得任何半在线算法的竞争比至少为，恐奠厶( ) _ 根据引理2 2 4 和2 2 5 ，我们得到本节的主要结论： 定理2 2 6 ：对排序问题p 2 l d e c r l f p ，p 1 ，l s 是最优的确定型半在线算法，竞争比 。m 。a 。x 。f p ( a ) 由于l p t ：是将工件按从大到小排列以后，进行三5 r 方式加工因此，可以得到 定理2 2 7 ：由l 尸t 求解p 2 1 d n f n e 问题，p 1 ，最坏情况界为1 罂亳，p ( ) - 1 2 苎三塞生翌塾工塑鱼塑型盟塑星型塑堕塑堡壁塑墼 2 3p 2 1 0 n l i n e l l p ，p 2 1 d e c r l p 随机下界 在上一节我们证明t l s 是p 2 d e c r l t 。问题最优的半在线算法，从本节开始， 我们来研究p 2 i m 托n e l f p ，p 2 i d e c r i 知随机下界 2 3 1 p 2 l o n l i n e l l 。随机下界 定义 野( ) 兰( 史岩) ；，g p ( ) = i 弓支端- 前面我们知道对问题p 2 l 帆f n e i ，l s 是竞争比为s u p ( ) 的最优确定型算 法，并且8 u p 纬( ) 在关于。的下述方程的零点处取到：x p 。( ( 1 + z ) 。+ 1 ) = 2 9 类似于引理2 2 4 的证明，可知对每个给定p 1 ，s u p 卯( ) 在点“1 上取到， 即s u p g p ( a ) = 雩野昴( ) ，并且可以证明黔g p ( ) 也是在点”上取到 0 凸j 凸1 定理2 3 1 ：对任一给定的p 1 ，任何求解排序问题p 2 o n l i n e 1 ，的随机算法的竞 争比至少为2 野g p ( ) 证明：设q l2 五i i 2 i - - 2 7 i 五巧显然osq ls1 - 首先，前两个长度均为1 的工件 到达如果某一算法a 以概率口 2 - ( 2 1 - - 2 j 一) q ： 2 i = g p ( ”) ， 笙三里生蔓塑! 塑宣旦型! ! 堕壅型塑堕! ! 塑! 壁塑璧 结果显然成立 若随机算法a v a 概率g q 1 将前两个工件放在不同机器上的，则来最后一个 长度为”的工件最优解是把前两个工件给同一台机器，最后的那个给另一台机 器，目标值为( ”一+ 2 ，) ；而 e ( 如( 1 ，1 ，a ” ，a ) ) = g ( ( ”+ 1 ) 9 - t - 1 ) ；- t - ( 1 一g ) ( “+ 2 p ) ； 生! 生! ! ! ! ! ! 垒：! ：墨卫：! ( f 垒：! ! ：1 2 1 ! ! 二= 虫! 垒：= = ! ：2 1 l p ( 1 ，1 ，” ，0 p t )f + + 印1 ； f 垒：竺! ! i ! ! 垒：! ! ! 擘! = ! 垒：! ! ! ! ! ! ! ( + ”+ 2 2 ) ； = g ( ”) 因此 黥嗡筹搿独i i i a x l a o p t，领) 如( 1 ，”) ，) 一11 7 1 4 笙= 蔓生堕壑! 塑鱼旦型! ! 堕室型塑堕! ! 型! 壁塑望 2 3 2 p 2 1 d e c r l l 。随机下界 定义 驰，2 纛犏， 则2 野( ) 在岔 1 ，2 ) 上取到，岔如前面所定义 定理2 3 2 ：对任一给定的p 1 ，任何求解排序问题p 2 d e c r l l p h 9 随机算法的竞争 比至少为怒f p ( ) ， 证明：令q 22j 五言赫显然o 啦1 首先，前两个长度均为甜的工件 到达如果某一算法a 以概率q 丝塑垒二= 2 1 ! ! ；叟2 ( ! 垒：2 f 2 1 ； = 昂( + ) 如果任意算法a 以概率q q 2 将前两个工件分给不同机器，则来最后三个长 度都为1 的工件记了= ，岔，l ，1 ，1 ) 最优解是把前两个工件给同一台机器，最 后三个工件给另一台机器，目标值为( ( 2 + p + 妒) ；而 则 e ( 岛( 正a ) ) = 口( ( + + 2 ) ，+ ( + 1 ) ，) ；+ ( 1 一g ) ( ( 2 + ) ，+ 扩) ； 里! 生! 墨垒) ) ：! ! ! 垒：! 竺! 垒：! 竺2 1 ! ! = ! ! ! ! ! 垒：! ：翌! ! k ( z0 p 丁) f ( 2 a + 1 p + 3 p ) ； 蔓三里生蔓塑! 堕鱼堕型型! 堕窒型塑堕垫壁壁回壁 0 ( + ) 因此 瓦e ( l 而a j 丽, a ) ) o p t 辫昂( ) 岛( 正) 一砭r ”一7 1 6 篁三童生堕塑工堕鱼堕型垫亟塞型塑堕塑垫壁塑垦 2 4 小结 对于一些已知的结果我们傲了一些数值上的分析，当p 取不同值时，2 2 节 和2 3 节中的所研究的界得到了不同的值我们可以通过表格知道，这些函 数关于p 是单调递增的，并且当p 趋向于无穷时，函数值也趋向于我们已知 的_ p 2 ii c k 。的相关结果 在线 半在线 l s 算法竞争比随机下界 l s 算法竞争比 随机下界 p 辫昂( )辫q ( ) 1 m 。n a ( x 。f v ( a ) 1 m s 。a x 。f p ( a ) 1 51 0 8 1 7i 0 6 2 2 1 0 0 7 11 0 0 7 0 2 1 1 “l1 1 0 6 91 0 1 4 21 0 1 3 7 31 2 3 l l 1 1 6 5 91 0 2 7 71 0 2 6 5 51 3 2 4 8 1 2 2 5 81 0 5 1 91 0 4 8 5 1 0 1 4 0 8 31 2 7 7 51 0 9 3 31 0 8 4 2 2 01 4 5 3 21 3 0 4 9 1 1 2 7 61 1 1 2 2 1 0 0 1 4 9 0 51 3 2 7 6】1 5 8 71 1 3 6 7 o 。1 5 0 0 0 1 3 3 3 31 1 6 6 71 1 4 2 9 表2 1 结果比较 1 7 篁三至生鎏塑工堕鱼旦型塑兰垄堡闽墼盟量垡簦鲨 第三章 f p 范数下两台同型机半在线问题的最优算法 3 1 引言 本节主要讨论半在线问题p 2 1 m a x l l v 和p 2 1 s u r n l l , 在这两个问题中，我们分 别已知的半在线信息是工件的最大加工时间和所有工件的总加工时间 对于已知所有工件的最大加工时间的半在线排序问题，h e 和z h a n g 【7 】7 对p 2 l m a x g 一问题提出竞争比为4 3 的半在线算法对于问题p 3 l m a x l g 。，蔡 圣义不仅给出了一个竞争比为( 1 + 厕) 6 1 5 9 0 7 的半在线算法，并且证明了 该问题的下界至少为、，厄h e 2 8 】证明t p 2 1 m a x l c m l 。的最优算法竞争比为3 2 在 文献 2 9 】中，t a n 和w u 证明了当m 3 时，问题p 刊m o z i c 。的最优半在线算法竞 争比为m 一1 针对已知所有工件的总加工时问的半在线排序问题，k e l l e r e r 3 0 等 研究y p 2 s u m g 一问题，并且提出了竞争比为4 俗的最优半在线算法a n g e l e l l i 等【3 1 】证明t p 3 l s u m l c , - , , 。f q 题的下界为1 3 9 2 9 ，并且提出了竞争比 为2 7 1 9 的算法当机器数为m 时，c h e n g 等 3 2 提出了竞争比为1 6 的算法，并且 给出当m 6 时，问题的下界为3 2 对于问题p 忙札叫c 。，a n g e l e l l i 等 3 3 提 出了当m 0 0 时，问题的下界为1 5 6 5 ，对于极大化目标，h e 2 8 1 证明了 问题p 2 l s u m l c 讯的最优半在线算法的竞争比为3 ，2 在文献【2 9 中，证明了 当m 3 时，问题p m l s u m c , 。i 。的最优半在线算法竞争比为m 1 对于同时已知这两个部分信息的半在线问题，在文献 3 4 1 中有一定的 研究，t a n 和h e 对p 2 1 8 u m & m a x g 问题提出了竞争比为6 5 的最优半在线算 法t a n 和w u 2 9 研究t p m s u r n g z m a x c m m 问题，对m = 2 情况提出了竞争比 为5 4 的算法，对m = 3 情况提出了竞争比为3 2 的算法，并且当m 4 时，提出了竞 争比为m 一2 的最优半在线算法 对于一般的2 2 范数，蔡圣义( 3 5 对p 2 l m a x l l 2 ，p 2 1 s u m l l 2 两个问题，分别提出了 最优算法，竞争比均为、，丽3 1 8 笙三童生蔓墼! 堕宣旦型塑兰鱼垡塑墨盐墨垡蔓鲨 3 2 p 2 1 m a x l l p 最优算法 本节假设已知工件的最大加工时间，记为三= m a x p ；：tsi n 算法a ： ( 1 ) 将当前到达的工件放在m 上加工当有下列情况之一发生时，则转第2 步，同时 将此工件放在 如上加工； a ) 如果该工件放在a n 上，该工件的完工时间至少2 l ； b ) 该工件的加工时间为 ( 2 ) 将以后到达的工件按l s 规则进行加工 定理3 2 h 对任意的p 1 ，g ( a ) ( 竺兰g ；业) ； 证明：设她和尬的最终负载分别为1 l 和f 2 ，最优解中对应负载为e 和且= m a x l l ，z 2 ) ， = r a i n 1 ，f 2 ) 令d = 钍一 ，由算法a 可戋l ：l ds l 下面分情况讨论： ( 1 ) 蝇上第一个工件的加工时间为厶且f l l 则由算法a 可知，上只加工这么一个工件，且算法a 产生最优排序； ( 2 ) 肘j 上第一个工件的加工时间为厶且f l 二 此时有v l ，且l p ( j ，a ) = ( 2 p + 瑶) ；= ( 舻+ t j p ) ；= ( 伊+ 扣+ d ) ，) ；， k ( 工d p 丁) = 【( 啦p + ( 呓) ， ；【2 ( ! 笋) p ；因此有 c ；( a ) = 丽l a 4 a ) ( 鬻) ；= ( 竺二1 1 酽) ； 记，( 茁) = 鼍募蔫笋，对，扛) 求导，得到 ，( 垆塑业筹 当p 1 时，( 。) 0 ，可知，( z ) 单调递减，考虑到 d 1 因此 q ( a ) ( 掣) ； 事实上，令 f ( x ) = 护+ ( 1 一z ) 9 ， 由f ，扛) = p 护一( 1 一z ) ”一1 】知，当。 1 2 1 对，f ( 。) 单调递增因此( 丧) p + ( 西3 ) ， ( 丧) + ( 丧) ，即妒+ 妒 酽+ 4 p ，因此 即捣( 学) ； 型 竺：鲨! ! 驷+ 2 p 一3 p 由定理3 2 1 和定理3 2 2 可以得到 定理3 2 3 ：对于问题p 2 l m a x l l v ，算法a 是最优的半在线算法 2 0 笙三童生堕墼工堕鱼囹型塑兰垄丝塑壁塑墨垡簦鲨 3 3 p 2 1 s u m l l p 最优算法 本节假设已知所有工件的总加工时间，记为m = 鲁lp ； 算法a ： ( 1 ) 假如把当前到达的工件放在尬上加工，此工件完工时间不超过2 m 3 ，则此工 件在尬上加工，否则转入( 2 ) ； ( 2 ) 将当前到达的工件放在 如上加工； ( 3 ) 将这以后到达的工件按l s 规则进行加工 定理3 3 1 ：对任意的p 1 ，c p ( a ) ( 2 ：”- _ 刍i2 r p - b l ，! 一 证明：设慨和尬的最终负载分别为1 1 和1 2 ，显然a 7 ( j ) = ( 理+ 喀) ；，o p t ( j ) 2 ( 警) 一阵 下面分情况讨论： ( 1 ) 存在长度大于2 m 3 的工件，称此工件为大工件 由算法a 知道，在大工件到达前，m 2 上不加工任何工件，且尬上加工工件的 总时间不大于m 3 当大工件在m 2 上加工后，后来到达的工件都在m 上加工因 此算法爿产生最优排序； ( 2 ) 所有工件长度都不大j = 2 m 3 通过对算法a ，的分析，可知当上第一个工件加工完那一刻，至少有一台机 器负载不小于m 3 ，且每台机器负载都不大于2 m 3 当完成算法a 7 的第3 步以后， 机器的最终负载都不会超过2