（运筹学与控制论专业论文）两台同类机极大化机器最小负载问题研究.pdf

摘要 摘要 本论文研究两台同类机极大化机器最小负载的排序问题。模型要求在两台 速度之比为q 的机器上加工工件，并已知工件加工时不可中断，目标是使负载 最小的机器其加工时间最大化。本文分析了用己尸t 算法解离线模型的最坏情况 界，给出了证明最坏情况界是紧的实例。其次，针对已知工件从大到小到达的 半在线模型，本文根据l 竹算法在口的某些区间段达不到问题下界的情况，设 计了最优算法，并证明了算法的竞争比。其中最坏情况界和竞争比都表示为参 数q 的分段函数。最后，针对处于不同区间段上的g ，分别给出以q 为函数的实 例来说明半在线问题的下界，从竞争比的角度证明了算法的最优性。全文共 分为三章，第一章介绍了论文用到的排序知识和相关研究结果；第二章介绍 了l 刀算法最坏情况界的证明思路和具体证明过程；第三章介绍了最优算法的 证明过程和问题的下界。 关键词：同类机，加工时间，三p t 算法，最坏情况界，竞争比，下界 a b s t r a c t a b s t r a c t t h i st h e s i ss t u d yt h en o n p r e e m p t i v em a x i m i z a t i o np r o b l e mo nt w ou n i f o n i lm a c h i n e s ，w h e r eo n em a c h i n ei sqt i m e sa se f f i c i e n to ne a c ht a s ka si st h eo t h e r , w i t ht h e g o a lo fm a x i m i z i n gt h em a k e s p a n w ea n a l y z et h ew o r s e - c a s er a t i oo fa l g o r i t h ml p t 。 a n dg i v ei n s t a n c et op r o v et h et i g h t n e s so ft h er a t i o s e c o n d l y , w es t u d yt h es e m i o n l i n e v e r s i o n ：j o b sa r r i v eo n eb yo n ei nt h eo r d e ro fn o n i n c r e a s i n gs i z e s w ed e s i g no p t i m a l a l g o r i t h m si nt h ei n t e r v a l sw h e r ea l g o r i t h ml p ti sn o tt h eo p t i m a lo n e ，a n dp r o v e t h ec o m p e t i t i v er a t i oo ft h ea l g o r i t h m s t h ew o r s e - c a s er a t i oa n dt h ec o m p e t i t i v er a t i o a l eg i v e na sp i e c e w i s ef u n c t i o n so fq a tl a s t ，i n s t a n c e sw h i c h e x p r e s sa sf u n c t i o n so f qa l eg i v e nt op r o v et h el o w e rb o u n d so ft h ep r o b l e m t h i sp a p e ri n c l u d e st h r e es e c - t i o n s s e c t i o nii n t r o d u c e sb a s i ck n o w l e d g eo fs c h e d u l i n ga n do u rr e s u l t s s e c t i o n2 p r o v e st h ew o r s e c a s er a t i oo fa l g o f i t h ml p t s e c t i o n3p r o v e st h ec o m p e t i t i v er a t i o o fo p t i m a la l g o r i t h m sa n dg i v e st h el o w e rb o u n d s k e yw o r d s ： u n i f o r mm a c h i n e ，m a k e s p a n ，a l g o r i t h ml p lw o r s e c a s er a t i o ， c o m p e t i t i v er a t i o ，l o w e rb o u n d n 一 第一章绪论 1 1 排序和算法 第一章绪论 排序( s c h e d u l i n g ) 1 6 j 题研究的背景主要是机器制造，后来逐渐推广到计算机 科学、运输调度、生产管理等领域，它的研究已经成为运筹学方向的一个非常 活跃的分支。排序的实质是利用机器( m a c h i n e ) 或者资源( r e s o u r c e ) ，最优地完成 一批给定的任务( t a s k ) 或者工件( j o b ) 。根据实际背景的不同，在执行任务或者加 工工件过程中，可能需要满足某些限制条件，比如任务的到达时间、截止时 间、加工顺序、资源对加工时间的影响等。其中目标函数也可以根据实际需求 的不同而改变，而所谓的最优地完成指的是使指定的目标函数值达到最小或最 大。 一个排序问题主要由机器的数量和种类，任务或工件的限定条件、资源的 种类和性能等情况综合决定，目前通常沿用g r a h a m 等人1 1 4 提出的q 例7 三参数 表示法( t h r e e f i e l dr e p r e s e n t a t i o n ) 来描述一个具体的排序问题，其中q ，p 和1 分别 表示机器、任务、目标函数三个域的性质以及满足的条件。 排序问题可分为三类，离线( o f f l i n e ) ，在线( o n l i n e ) ，半在线( s e m i o n l i n e ) 。 离线问题是指调用算法前，工件的所有信息已知。这类排序问题中有一些是存 在多项式时间最优算法的p 问题，但更多的是目前不存在多项式时间最优算法 的p 一难问题，一般只能通过改进穷举过程，设计分支定界法或者动态规划法 等方法来求得最优解。目前对于大多数p 一难问题，常用的做法是设计多项式 时间的启发式算法得到问题的近似解，而不是直接寻找最优解。这里就存在如 何衡量一个启发式算法好坏的问题，现在的主要标准是把算法解和最优解进行 比较，看两者之间的差别有多大，一般用最坏情况界( w o r s tc a s er a t i o ) 来表示， 并把能够估计这种误差的启发式算法称为近似算法( a p p m x i m a t i o na l g o r i t h m ) 。下 面给出求解极大化( 极小化) 问题的近似算法最坏情况界的定义：给定一个工件 序列j ，设c ( ，) ( 或简记为c a ) 和c ( j ) ( 或简记为c + ) 分别为算法a 和最优排序的 目标函数值。则算法a 的最坏情况界定义为一，满足： 一= i n f c l c + ( ，) c c a ( n v i ( 一= i n f c l c ( j ) c c 。( n v ，) ) ( 1 1 ) 另一种常见的是在线排序问题，指的是工件一个个地到达，工件信息随着 第一章绪论 加工过程逐个依次释放，并且一旦被安排就不能改变。介于离线和在线问题之 间，知道部分未到达工件信息的排序问题称为半在线排序问题。针对在线( 半 在线) 问题设计的算法称为在线( 半在线) 算法( o n l i n e ( s e m i o n l i n e ) a l g o r i t h m ) 。其 算法好坏也存在衡量的标准，一般用算法竞争l ：g ( c o m p e t i t i v er a t i o ) 来度量， 具体定义的形式和( 1 1 ) 一致，其中c ( j ) 表示在线( 半在线) 算法的目标函数 值，伊( j ) 表示相应离线问题的最优目标函数值。算法的竞争比往往和问题的 下界( 1 0 w e rb o u n d ) 相结合。下界指的是所有求解该问题的在线( 半在线) 算法至多 可能达到的竞争比，即7 = i n f r a l 。如果一个在线( 半在线) 算法的竞争比恰好 等于问题的下界，则该算法已经在某种意义上达到了最优，也就是通常所称 的最优算法。对一个给定的算法，它的竞争比有时候不是很明显就能估计出 来的，但是竞争比的一个上界却相对容易得到，称之为算法的一个上界( u p p e r b o u n d ) 。从而如果估计到一个算法的上界，并且找到问题的一个实例使得调用 该算法时，恰好可以达到这个上界，则称此时算法的界( 竞争比) 是紧的( t i g h t ) 一2 一 第一章绪论 1 2 问题描述 考虑下面的两台同类机极大化排序问题。两台具有恒定速度的同类机，从 零时刻开始加工工件，并且工件在加工的任一时刻都不可中断，目标是求负载 最小的机器其加工时间的最大值泓本文研究该问题的离线形式和已知工件加 工时间递减的半在线问题，用三参数法分别表示为q 2 i i n 和q 2 1 d e c r l 衙 本文用尬表示具有恒定速度q ，i = 1 ，2 的机器。记每个工件的大, j , # j p j ，j = 1 ，2 ，这里的大小( s i z e ) 是指工件在单位速度的机器上加工的时间。对任意 一个工件序列，i = 切1 ，沈，) ，第歹个工件，j = l ，2 ，在某台机器上( 不一定 是单位速度的机器) 的加工时间称为该工件在这台机器上的负载( 1 0 a d ) ，其值 为孕，i = 1 ，2 。一台机器的负载就是所有由它加工的工件的负载之和。不失一般 性，假设1 = q 1 口2 = ：，即尬是速度为l 的快机器，它与的速度之比为口 该问题的研究源于以下研究背景：工厂有两条生产线加工工件，其加工能 力恒定但大小不同。每一个到达的工件不可切割且必须经过其中任一条生产线 的加工。由于技术上的限制，若其中一条生产线完成了加工任务而另一条生产 线仍在加工，则整个作业系统将处于不稳定状态，影响机器性能。为尽可能使 系统保持稳定状态，要设计一个加工方案，使系统稳定工作的时间尽可能地 长。 另一个熟悉的例子是圣诞老人问题( t h es a n t ac l a u sp r o b l e m ) ( 参见【2 】) ，n 份 独立的礼物要分派给仇个小朋友，目标是使感到最不满意的小朋友尽可能 地满意。第i 个小朋友看待n 份礼物的价值用非负向量r i = ( 吒1 ，砰，叩) ，i = 1 ，2 ，m 表示。设五 1 ，2 ，n ) 表示分派给第i 个小朋友的礼物子集，满 足五n 五，= 0 ，i i i ，则第i 个小朋友的满意度可表示为e = 碍，目标函数值是 j 求m i n 只的最大值。当特殊到只有两个小朋友的情形，并且他们对同一份礼物 的满意度之比为一个常数时，就是本文研究的排序问题。 由于p 2 1 1 i n 是经典的p 一难问题( 参见【1 1 】) ，而它是q 2 1 1 饥问题特殊 到机器速度之比等于l 的子问题，所p a q 2 1 1 c m l n 也是p 一难问题，从而研究 近似算法就具有重要意义。求解平行机排序问题的一个重要算法是l s ( l i s t s c h e d u l i n g ) 算法，最初i 扫g r a h a m 1 2 提出，对极小化问题，它把到达的工件安 排到能使其最早完工的机器上。另一个重要的算法是三p 孔l o n g e s tp r o c e s s i n g t i m e ) 算法，i 妇g r a h a m 1 3 提出，用于解决离线的极小化问题。它首先把工件 一3 一 第一章绪论 从大到小排列，然后按此顺序把每一个工件安排到使其最早完工的机器上。 如果直接用原来定义的l s 、l p 丁算法解本文的极大化问题，则算法结果可以 是任意坏的。例如，当两台机器的速度之比口 2 时，若工件集i = 1 ，1 ) ， 则算法都把两个工件指派到快机器上，算法解为m i n 1 + 1 ，o ) = 0 ，而最优解 为m i n 1 ，口) = 1 基于l s 和l p t 算法中的“贪婪”思想，可以类似地定义用于解极大化问 题q 2 11 c m 饥的l s 算法和l 尸丁算法： l s 算法把到达的工件安排到当前负载最小的机器上。 l p t 算法把工件从大到小排列，然后按此顺序把每一个工件安排到当前负载 最小的机器上，若两台机器的当前负载相同，则把工件安排到快机器上。 注意，下文提到的l s 算法和l p 丁算法都是指用于求解极大化问题的算法。 显然，用l p t 算法求解半在线问题q 2 d e c r 和用l 刀算法求解离 线q 2 1 1 c ，饥模型的结果一致。当一个工件到达时，l p t 算法总是希望增加当前 负载小的机器上的负载，我们称之为“l 刀规则。由l p t 规则，给定一个单 调非增的工件序列，l p t 算法总会物1 指派到尬上，把仇指派到上。 一4 一 第一章绪论 1 3 相关研究结果 关于m 台同型机、同类机极大化排序问题的研究始于1 9 8 2 年d e u e r m e y e r 等 人【6 】做的工作，他们证明- j l p t 算法解胁l l g r o i n 问题的最坏情况界不超过 常数；，接着c s i r i k 等人【5 】得到了最坏情况界，为。4 。r 。n 一- 2 】对于在线的p m i l n 问 题，w o e g i n g e r 2 0 证明了l s 算法是最优算法，竞争比为m 对于在线 的q m l l c m i 。问题，a z a r 和e p s t e i n 1 指出即使m = 2 ，问题的下界也不是有界 的( 用于说明下界的实例使界达到两台机速度之比口，当口一o o 时，下界也趋 于无穷) 。陈思霞【4 】证明了l s 算法是解该问题的最优算法，竞争比为劬， j = 。l 其中劬，歹= 1 ，2 ，m 表示第j 台机器的速度。对于q m l i n 的半在线问 题，【l 】考虑了工件从大到小到达或最优解已知的半在线模型，证明了最优 算法竞争比为m ，若两个条件同时成立，则竞争比可降至常数2 。注意，当特殊 到两台机即m = 2 时，这两个界都是q 1 时的最大值，对口的所有取值未必是紧 的。 s e i d e n 等人【1 8 】最早提出了工件递减的半在线排序模型。对 于e m l d e c r l t n 问题，h e 和t a n 1 5 指出l s 算法是m = 2 ，3 时的最优算法。 考虑两台同类机的排序问题，m i r e a u l t 等人【1 7 】研究了l p t 算法 解q 2 1 1 g 一的最坏情况界，把它表示为机器速度之比口的分段有理函数。随 后e p s t e i n 等人【9 】指出在线q 2 1 1 g 问题的最优竞争比为m i n 1 + 石1 ，1 + 寿) e p s t e i n 7 研究了半在线问题q 2 1 d e c r l ，找到问题下界并设计了最优算法。 对于q 2 1 1 c k n 问题，e p s t e i n 8 研究了它的在线模型，指出l s 算法是竞争比 为q - i - 1 的最优算法。本文研究了l 刀算法解q 2 1 1 竹离线模型的最坏情况界， 并找到了半在线问题q 2 l d e c r 竹的最优算法，把l p t 算法的最坏情况界以及 最优算法的竞争比表示为参数口的函数，所做的结果和【1 7 ；7 】中极小化问题的结 果相对应。 近年来，还有很多关于两台同类机极大化问题半在线模型的研究，如 8 】研 究了已知最优解值的半在线模型；t a n 和c a o 1 9 研究了已知工件总大小的半在 线模型并找到了最优算法；l u o 等人【1 6 】研究了已知最大工件大小的半在线模 型，给出了竞争比不超过碧的算法，c a o 和t a n 3 改进了问题的下界并设计了 在口的大部分取值区间上达到最优的算法；e p s t e i n 和y e 1 0 研究了已知最后一个 工件最大，且知道当前到达工件是否最后一件的半在线模型。 一5 一 1 4 本文研究结果 定理1 4 1 ：刀算法求解q 2j i n 问题的最坏情况界为 产( g ) = 巡 2 q + 3 q f 1 ，1 v g 5 ) q f 饥丐，向 q 【以，鲻2 、 q 【学，学) 口 蝴2 ，学) q 【学，q o ) 口【q o ，1 + 锈) g 【1 + , 5 ，1 + 锯) 口【1 + 怕，o o ) ， 其中口o 2 4 8 5 6 是方程9 3 2 q 2 3 ：0 的最大实根。 定理1 4 2 ：求解排序问题q 2 l d e c r i c m t n 的最优算法的竞争比为 r ( q ) 呈型旦 q + 2 3 口 墨咝 2 口+ 3 兰2 - 口+ 2 q 【1 ，q 1 ) q 【q l ，华) q 【牛，以) q 【以学) q 学，学) q 【学，学) q 【学，学) q 【学，1 - 4 - 侗 q 【1 + 锯，o o ) ， 其中9 1 1 0 3 8 2 是方程4 口4 + 8 q a + 1 5 q 2 - 4 - 6 口一3 6 = o 的最大实根。 对比以上两个定理的结论( 参见图1 1 ) 可知，用l 刀算法求解半在线问 题q 2 1 d e c r j c n 时，在区间f 两，q o 1 + 锈，o o ) 上是最优算法，并且仅在区间 总长度约为o 4 7 l 的两段范围内达不到最优。注意到一( q ) 和r ( q ) 都在口一o 。时达 一6 一 帕一一心 血“柏一舶l乞 g呈g继研址的g血n业研丑m 一 上娜晰一 g 呈g 詈| 神 第一章绪论 到它们的最大值2 。所以一( g ) 和r ( 口) 的整体非参数界都是2 ，在q 一时达到。 由上述定理知，对q 1 ，有 产( 口) r ( 口) 币2 q 图1 1l p t 算法和最优算法的竞争比 一7 一 ( 1 2 ) 3 2 1 1 l 1 l 1 l 第二章l p t 算法的最坏情况界 第二章l p t 算法的最坏情况界 2 1 证明思路及预备知识 在详细证明之前，本节先介绍证明的整体思路及预备知识。 本文采取反证法来证明算法的最坏情况界( 竞争比) ，假设c 月 赤矿， 对一个工件序列，记互为调用算法a 时，在机器尬上加工的工件的大小之和， i = 1 ，2 不失一般性，假设c = 1 ，则五+ t 2 1 + 三记弓为包含前j 个工件的工 件集。在证明时，根据哪台机器上的负载决定了算法的目标函数值，可以分为 以下两种情况： 情形a c = m i n t 1 ，q 死) = 乃 i 而1 因为五 ；1 记鼽为调用算法a 时，在 机器m 2 上加工的最后一个工件。设l t 为以按算法指派后并且下一个工件未到达 时，机器尬上加工的工件之集，i = 1 ，2 从而有b = l 1ul 2 和f = i l l i + l l 2 i 设却为工件轨之后的所有工件的大小之和，即鼢= 乃+ t 2 一易 j = l 若研是按l p t 规则被算法4 指派到机器尬上加工的，也就是说安排到当前 负载较小的机器上的，则关系式乃 口( 乃一肌) 成立，从而有 勿 易一争( 1 + 百1 一而1 ) 一而1 ( 1 + 扣一南) 亿- ， 由( 2 1 ) ，可以得到l 二1 i 和i l 2 i 的上界。事实上，因为 所以 驯( 1 + 秒1 一而1 ) i 引见正 q ( 阮| - 1 ) ( 1 + 扣一而1 ) ， 一8 一 第二章l p t 算法的最坏情况界 所以 i l 2 1 而丽确+ 1 q 3 情形b c a = r a i n t 1 ，a t e = 口正 而1i 因为而 1 记仇为调用算法a 时，在 机器尬上加工的最后一个工件。设以为按算法指派后并且下一个工件未到达 时，机器尬上加工的工件之集，i = 1 ，2 从而有r = 仉u 巩和钍= l 仉l + i 巩i 设z u 为工件m 之后的所有工件的大小之和，即= 正+ t 2 一殇 j = l 类似于上一种情形，若m 是按l 刀规则被算法a 指派到机器尬上加工的， 则关系式q t 2 乃一成立，从而有 m 丑一口正 ( 1 + 石1 一而1 ) 一再1 面= ( 1 + 言) ( 1 一刁1 面) ( 2 4 ) 类似地，f 1 3 ( 2 4 ) u - f 以得到l 巩l 和1 l 的上界，因为 ( 1 u l l 一1 ) ( 1 + 昙) ( 1 一再1 而) ( 1 u l l 一1 ) m = l 巩帆一m 噩一仇g 正 习茜 所以 i 巩i 而砜而“ ( 2 5 又由 吲( 1 + 扣一而1 ) i u ，1 p _ t 2 而1 ， 得到 吲 研硕而 ( 2 。6 对给定的一( 口) ，当p l ( m ) 是按l p t 规则进行指派时，可以得到有关工件之 间大小关系的式子，并且在证明中可以通过( 2 2 ) ，( 2 3 ) ( ( 2 5 ) ，( 2 6 ) ) 计算i l l l 和l l 2 i ( | 明i 和i 巩i ) 的上界，再根据l l ，i 和i l 2 i ( i 仉l 和i i ) 的值分情况讨论。对给定 的i l l a 和l l 2 i ( i u , i 和f 巩1 ) 的值和根据算法的特点，确定l 1 和l 2 ( 巩和巩) 集合里 面包含哪些工件。最后结合最优排序对这些工件的安排，导出矿 1 ，从而与 假设矛盾，完成证明。 一9 一 第二章l p t 算法的最坏情况界 2 2 最坏情况界的证明 本节主要证明l 尸t 算法解q 2 1 1 c m 饥问题的最坏情况界，在此根据g 的不同取 值区间把证明分为几个引理，并在每个引理证明的最后给出工件序列说明最坏 情况界的紧性。 注意到，当调用l p t 算法时，若i l 2 i = 1 ，则a = 仇且l 1 = 轨 ，l 2 = 忱) 若在最优排序中研和p 2 没有同时指派给尬加工，则伊p 1 + 轨= 正 1 否则 c + q x l = g ( 五一p 1 ) q ( t 1 一耽) = 口( 丑一乃) q ( t 1 + t 2 一p i ) 显然，此时l p t 算法就是最优排序。所以 在下面的证明中，不妨设i l 2 i22 ，i 矾i 2 且l 巩i 1 引理2 2 1 ：当口 1 ，钜) 时，三刀算法的最坏情况界恰为 沪m a x3 q + 3 ，g ) _ 爹三主 撩卜 证明：注意到，当q 以时，有 南= m ，n 2 q + 3 ，1 一 1 7 c 2 刀 而2 叫n ，一一7 啪) 情形a s r l ( 口) 的定义和( 2 2 ) ，( 2 3 ) ，计算可得i l l l 3 ，i l 2 i 4 下面根 据i l l l 和l 三2 i 的不同取值分情况讨论。 子情形1 i l l i = 1 且i l 2 i = 2 s l p t 算法的特点，显然有l i = p 1 ) 且l 2 = 仇，船) 因为在最优排序中必 存在一台机器加工b 中至少两个工件，所以另一台机器最多加工岛中的一个工 件，从而有c + q ( p 1 + 动) = 祝 南1 ，其中最后的不等式由( 2 7 ) 得到。 子情形2 i l l i = 1 且i l 2 i = 3 一1 0 一 第二章l p t 算法的最坏情况界 显然，l 1 = 研) 且l 2 = p 2 ，p 3 ，m ) 考虑最优排序对工件集局的所有可能指 派。若存在一台机器加工局中3 个以上的工件，则由( 2 7 ) ，有c q ( p l + x 1 ) = 口五 1 否则两台机器各加工局中的两个工件，注意到，因为胁在算法中被指 派到尥上加工，所以有关系式q 慨+ 船) p l ，从而 c 口溉+ 船+ 2 7 1 ) p l + g 勋g 慨十幻) = a t l 1 + i 1 一i 丽1 1 ，矛盾。 子情形4 1 l 1 l = 2 且l l 2 l = 3 注意到，当 厂孺q 以时，f l j ( 2 3 ) 得1 l 2 1 丽莉1 + 1 ，所以有 q ( p 1 - 4 - 仡+ z 1 ) q ( q + 1 ) p a + q x t ( q + 1 ) ( p l + p a q p 4 ) + q x t = ( g + 1 ) ( 丑一锄一q p 4 ) + q x t ( q + 1 ) t 1 一口( 口+ 1 ) 肌 ( 丽2 q + 3 一掣 ，所以 q ( p l + p 2 + 黝) 卯1 + ( p l + 肌一q p 3 ) + q x t5 ( g + 1 ) p 1 + m + 幻) 一2 q p 4 = ( 口+ 1 ) 乃一2 咖 ( g + l ，3 2 口q + + 3 3 一百2 q = 1 ( 2 9 ) 因为在最优排序中，必存在一台机器加工忍中至少3 个工件，所以屁中至多两个 工件被指派到另一台机器上。由( 2 8 ) 和( 2 9 ) ，有c + sq 伽1 + p 2 + 勋) 1 情形b 由产( 口) 的定义和( 2 5 ) ，( 2 6 ) ，计算得l 巩l 4 且l 巩i 3 下面按 照i 仉l 和l 巩l 的取值分情况讨论。 子情形1 i 巩i = 2 且i 巩i = 1 第二章l p t 算法的最坏情况界 显然，仉= 切1 ，船) ，巩= 耽) ，所以p 1 q p 2 因为在最优排序中必存在 一台机器加工岛中至少两个工件，即另一台机器加工b 中至多1 个工件，所以 有c + g 1 + 孔) q ( q p 2 + z u ) q 2 仞2 + z 。) = 口2 t 2 1 ，其中最后一个不等式 由( 2 7 ) 得到。 子情形2 1 巩l = 2 3 1 l 巩i = 2 显然，巩= 切1 ，p 4 - 且v 2 = 【化，船) 因为p 4 被指派到m 上加工，所以有p l 口渤+ p 3 ) 若在最优排序中存在一台机器力n 1 2 4 $ 至少3 个工件，则由( 2 7 ) ， c + q ( p l + z u ) q ( q ( p 2 + 船) + z u ) q 2 0 2 + p 3 + z 口) = 口2 t 2 1 否则两台机 器分别加工只中的两个工件，此时有c g ( p 2 + 船+ ) = a t 2 1 子情形3 i 仉l = 3 且l i = 1 显然，u i = n ，p 3 ，p 4 ，巩= 仇) ，所以p 1 + p 3 q p 2 又由( 2 7 ) ，有 且 q 6 0 1 + z u ) g 慨+ 船+ x u ) q ( q i d 2 + z u ) q 2 溉4 - ) = 9 2 t 2 1( 2 1 0 ) g 溉+ 船+ z u ) g 1 + 船+ z 让) q ( q p 2 + z u ) q 2 慷+ z ) = q 2 t 2 1 ( 2 1 1 ) 类似子情形2 对最优排序的分析，由( 2 1 0 ) 和( 2 1 1 ) 可得c 1 子情形4 i 仉i = 3 且i 巩i = 2 注意到，当、两口 以时，f l t ( 2 3 ) 知1 u 2 1 丽可1 i 而 互1 ，所以 q ( p 1 + p 2 + z u ) q ( q p 2 + p 2 + z u ) q ( q + 1 ) + z 缸) = q ( q + 1 ) ( t 2 一p 4 ) ，所以 口1 + p 2 + ) q ( q ( p 2 + p a ) 一肌+ 渤+ z u ) ) q ( q t 2 一m + ( 正p 3 ) ) 一1 2 第二章l p t 算法的最坏情况界 g ( ( ) 正一轨) 口( ) 揣一警= l ( 2 1 3 ) 因为在最优排序中，必存在一台机器加工岛中至少3 个工件，所以 f l t ( 2 1 2 ) 和( 2 1 3 ) ，c + 口1 + 耽+ z u ) 1 紧例当口 析丽时，令工件序列为 毒，黠舞，j 1 ，吾1 ，；) 显然，l p t 算法 ，p 4 ，p 5 指派到尬上加工，把p 2 ，p 3 指派到上加上，所以算法解c 工= 鬻 在最优排序中，p 3 ，m ，p 5 被指派到尬上加工，p 1 ，p 2 被指派到尬上加工，所以最 优解口= 1 ，从而最坏情况界r l ( q ) = 品= 鬻 当 孺q 钜时，令工件序列为 ：，1 ，1 一击) 显然，p t 算法把p 1 ，阳指 派到尬上加工，鼢指派到上加工，所以算法解c l = = 1 在最优排序中，耽， 船被指派到尬上加工，p 1 被指派到尥上加工，所以最优解c = 1 ，从而最坏情 况界产( 口) = 品= q 引理2 2 2 ：当口【以，1 + 怕) 时，l p 丁算法的最坏情况界恰为 r l ( 口) = q 【以，业2 、j q 学，学) q 【学，学) q 【学，q o 2 4 8 5 6 ) q 【q o ，1 + 锈) q 【1 + 锯，1 + 锯) 证明：当g 【以，1 + 佰) 时，通过直接计算可得 和 口q 茎f 鬻1 侗 亿 【学，+ 锯) 、。 托胁a x 蜃鬻藉，筹) 亿嘲 情形a 由( 2 2 ) ，( 2 3 ) ，通过计算得到i l li 4 ，l l 2 i 3 子情形1 1 l 1 i = 1 且l l 2 l = 2 显然，l 1 = 妇1 ) ，岛= 如，船) ，所以纰 a 考虑最优排序对工件集b 的 帕一“一他 虹“帕一怕呈口玺幻玺哥墨g铲堑幻 鬻器猎籍 皇 宅吾 m m ，_、【 = g l 第二章l p t 算法的最坏情况界 一_ = 二二。1 。一 所有可能指派。若p 1 是尼中唯一一个被指派到尬上加工的工件，显然有c + 饥+ 卸：五 1 都1 是b 中唯一一个被指派到上加工的工件，则由( 2 1 5 ) ，有 矿仡+ 船- i - x t ( p l 怕) c + 仡+ 船 1m a x 1 歹 + 现) = m a x 昏) 五 m a o c 伽) 南g 否则，若岛中还有其他工件被指派到加工p 1 的机器上，则有 c g 渤+ x z ) = 口( 仇+ 7 1 一p 1 ) 一q ( q 一1 ) p 2 + 口丑 一掣溉+ p 3 ) + 仍= 一掣噩+ 四 一掣( 1 + 石1 一而1 ) + 南虬 其中最后一个不等式等价于产( g ) 籍，f 1 3 ( 2 1 5 ) 知其成立。 子情形2 1 l 1 l = 2 _ 且1 l 2 l = 2 显然，l 1 = p 1 ，阳，l 2 = 沈，伽) ，所以口耽 p l + p 3 考虑最优排序对工件 集只的所有可能指派。若只中至少两个工件被指派到上，则只中至多两个工 件被指派到尬上，所以 p 。+ p 2 - i - x t 仇+ 昙( 轨+ 船) + 劫( 1 + 吉) ( p + 船+ 勋) 一船 c 1 + 石1 舯阳 ( 1 + 言) 南一( 1 + 石1 ) ( 1 一而1 ) 乳 其中最后一个不等式等价于产( q ) 呈2 出q + 1 ，由( 2 1 5 ) 知其成立。若只中最多只有一 个工件被指派到上加工，勘1 被指派到尬上加工，则由( 2 1 ) 和( 2 1 5 ) ，有 c + 口( 仇+ 以) = g ( 砌+ 乃一p l - p a ) 一q ( q 一1 ) 砌+ 口乃 s 一掣( p 2 + 乳) + 识= 一掣b + 弼 一掣( 1 + ；1 一而1 ) + 南g 若只中只有p l - - 个工件被指派到上加工，则由( 2 1 4 ) ，当以口 址乒时， 一1 4 一 第二章l p t 算法的最坏情况界 有 c + g 。- + 现) = 口( 噩一船， i 裔一口( 1 + 石1 ) ( 1 一b ) 1 ， 当垃乎q 1 + 怕时，有 c 砌+ 船+ 肌+ 规概+ 却 时船怕细a x 昏) 噩 m a x 昏) 南q 予情形3 i l l l = 3 且i 三2 i = 2 显然，l 1 = p 1 ，1 9 3 ，肌) ，l 2 = 耽，船) ，所以q p 2 p l + p 3 + p 4 考虑最优排序 对工件集r 的所有可能指派。若r 中最多只有一个工件被指派到尬上加工，则 c + 口0 1 + 劫) = g ( 五一p 3 一p 4 ) 口五一2 q p 5 南呐( 1 + 吉) ( 1 一南) q 其中最后一个不等式等价于产( q ) 丝2 q + 3 ，由( 2 1 5 ) 知其成立。否则，r 中至少两 个工件被指派到m j 上加工，即p 5 中最多3 个工件被指派到m 上) j h - r ，此时有 c n + 仇+ 仇+ x t p l + 芈+ 船+ 幻( 1 + 昙) 五一肌 ( 1 + 三) 土r l ( q ) 一( 1 + 石1 ) ( 1 一而1 ) 乳 情形b 由( 2 5 ) 和( 2 6 ) ，计算得到i 巩i 5 ，i 巩l 2 子情形1 1 u 1 l = 2 且1 u 2 i = 1 显然，巩= p 1 ，船) ，巩= 仇) ，所以p 1 q p 2 考虑最优排序对b 的所有可能 指派。勘1 是b 中唯一被指派到尬上加工的工件，则 c + p l + z u q p 2 + p u 口( 仇+ ) = g 正 1 一1 5 一 第二章l p t 算法的最坏情况界 若p 1 是b 中唯一被指派到上加工的工件，则由( 2 1 5 ) ，得 c + s 耽+ 船+ z 缸2 慨+ = 啦 南1 否则若p 3 还有其他工件被指派到加功1 的机器上，则伊q ( 仇+ p u ) = q 正 1 子情形2 1 仉i = 3 - 且1 u 2 i = 1 显然，阢= 勋1 ，船，m ) ，巩= 协) ，f i ) t p - j , p l + 册魄考虑最优排序对只的 所有可能指派。若只中至少两个工件被指派到尥上加工，则 c + n + 砌+ = ( 1 + 口) 乃 + z u ) 一 1 产( 口) 若只中至多一个工件被指派到尥上加工，且p t 被指派到尬上加工， 有泸口( 仡+ ) = g 死 1 否则，只中只郁1 被指派多j m 2 上) j l 由( 2 4 ) 和( 2 1 4 ) ，当以q 盐笋时，有 c g ( p 1 + z 让) 墨 南一g ( 1 当h 型2 笪g 1 + 锯时，有 则显然 工，则 c + 仡+ 船+ m + z u 概+ z u 3 ( 仡+ ) = 3 疋 而最而1 子情形3 1 仉l = 4 且l 觇l = 1 显然，仉= p 1 ，p a ，p 4 ，船) ，= 仡) ，所以p 1 + 船+ m 口耽考虑最优排 序对r 的所有可能指派。若尼中最多只有一个工件被指派到尬上加工，则 由( 2 4 ) 和( 2 1 5 ) ，有 c - 一1 6 一 ( g 正一2 p 4 ) 1 一 仇， 慨o 曲， + l g 1 + 引二r 一 + 一 嘞j 一 嘞纰钟 船 一 阮疋 l 如 一 一 ) 一g吼j _ r - 玩 卜 一 纰d “+ 口 l 一 一 钆 + 1 一 m 万 一 一 船o 一、j 陇l 一口 幢+ g 1 v i 厂，一 0 幻 z 一 斗 一)咖南 第二章l p t 算法的最坏情况界 否则，尼中至少两个工件被指派到 毛上加工，由( 2 4 ) 和( 2 1 5 ) ，有 c +p 1 + 耽+ 船+ z u q p 2 一p 4 + p 2 + z ( 1 + 口) 溉+ z u ) 一p 4 = ( 1 + q ) t 2 一舶 ( 1 刊而1 一( 1 + 石1 ) ( 1 一而1 ) g 紧例当钜q 学时，令工件序列为 j ，；，吾) 显然，l p t 算法蚴， p 3 指派到m 上加工，蚴2 指派到上加工，所以c 厶= 罟在最优排序中，p 2 ， p 3 被指派到尬上加工，p 1 被指派到尥上加工，所以c = 1 ，从而筘= ； 当学q 学时，令工件序列为 者熹，2 m 2 q + + 1 1 ) ，瓦1 ，南) 显然，l p t 算 法蚴1 ，船，肌指派到尬上加工，把耽指派到上加工，所以c l = 丝2在最优a+2 排序中，n ，p 2 被指派到尬上加工，p 3 ，p 4 被指派到上加工，所以c = 1 ，从 而= 丝2 q + 1 当学q 址乎时，令工件序列为 j ，韭q ( 2 q - i - 1 ) ，且q ( 2 q + 1 ) ，口( q 2 2 q - + - 1 1 ) j i 显 然，l p t 算法蛳1 ，船，p 4 指派到上加工，揿指派到上加工，所以c l = 丝2 0 + 1 在最优排序中，p 2 ，p 3 ，p 4 被指派到尬上加工，p 1 被指派到尬上加工，所 以伊= 1 ，从而= 丝a + 2 当址乎q 口。时，令工件序列为 ：，百1 ，否1 ， ) 显然，l 刀算法蛳1 ，p 3 ， p 4 指派到尬上加工，指派到上加工，所以c l = 在最优排序中，仇， 船，m 被指派到尬上加工，p 1 被指派到尬上加工，所以伊= 1 ，从而品= ： 当口o q 0 是一个任意小的实数。显然，l 刀算法把p 1 p 4 指派到尬上加工， p 3 指派到尬上加工，所以c l = 勰+ 2 e 在最优排序中，饥，仡被指派到尬上 加工，船，p 4 被指派到尥上加工，所以p = 1 ，从而岳一貉( e _ o ) 当1 + 锈口 1 + 怕时，令工件序列为 ；，綦赫，也q ( 3 q + 2 ) ，也q ( 3 q + 2 ) ，旦q ( 3 q - i - 2 ) 1 j 显然，l 刀算法蚴1 ，p 3 ，p 4 指派到尬上加工，把耽，p 5 指派到上加工，所 以c l = 端在最优排序中，p 2 ，p a ，p 4 ，船被指派到尬上加工，p l 被指派到上 加工，所以俨= 1 ，从而= 鬻 _ 引理2 2 3 ：当口【1 + 锯，o o ) 时，l 刀算法的最坏情况界恰为产( 口) = 墨 证明：由( 2 3 ) 和( 2 6 ) ，计算得i l 2 i 0 ，有c + m i n t l * ，g e ) ，所以 c 堕埤堡 ( 3 1 ) 记曰为功溉) 之后的工件在最优排序中被指派到机器必上的大小之和，i = 1 ，2 则研+ 晓= 锄( 田+ 晓= z u ) 且 n 畦+ b 5 ；m a x a ，b x t ( n 酊+ 蝇m a x a ，b x u ) ( 3 2 ) 3 1 算法l m l 及竞争比 算法l m l 1 把p 1 指派到慢机器上加工，把仇指派到快机器上加工； 2 若胁华仇，把船指派