（运筹学与控制论专业论文）同类机半在线机器覆盖问题研究.pdf

摘要 摘要 本文主要研究两台同类机半在线机器覆盖问题全文共分为三章 第一章是绪论部分，主要介绍排序问题，近似算法和竞争比分析等基本概念 第二章主要研究了两台同类机已知工件总加工时间的半在线模型，目标是 极大化最小机器完工时间根据机器速度之比s 的不同，我们分别给出了优先考 虑速度快的机器的算法f j l ( 当1sssl 乎时) 和优先考虑速度慢的机器的算 法s f ( 当s 兰牟时) 并且证明了这两个算法都是最优的，竞争比是： 1 s , 2 ， 以 垃2 述 第三章主要研究了两台同类机已知工件最大加工时间的半在线模 型，目标是极大化最小机器完工时间根据机器速度之比s 的不同，我们分 别给出了优先考虑速度快的机器的算法f f l s ( 当1 ss 兰乎时) 和优 先考虑速度慢的机器的算法s f l s ( 当s 生2 监时) 其中算法f f l s 对1 ss ! 之乎是最优的，算法s f l s 对s 【1 6 1 8 ，2 1 4 7 9 ) u ( 3 8 3 5 9 8 ，+ o o ) 是最优的， 在s f 2 1 4 7 9 ，3 8 3 5 9 8 ) 时，算法s f 三s 的竞争比和问题的下界的差距最多不超 过0 0 6 4 关键词：排序，算法的设计与分析，半在线，竞争比分析 一 业鬻。差j a b s t r a c t t h i st h e s i sm a i n l yc o n c e r n sd e s i g na n d a n a l y s i so fa p p r o x i m a t i o na l g o r i t h m so n s e m i o n l i n eu n i f o r mm a c h i n ec o v e r i n gp r o b l e m s w ef i r s ti n t r o d u c eb a s i cn o t i o n s s c h e d u l i n gp r o b l e m ，a p p r o x i m a t i o na l g o r i t h m sa n dc o m p e t i t i v ea n a l y s i s i nc h a p t e r2 w ei n v e s t i g a t es e n l i o n l i n es c h e d u l i n gp r o b l e mo nt w ou n i f o r mm 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 1 eo b j e c f i v ei st om a x i m i z et h em i n i m u ml o a do ft w om a c h i n e s w ep r e s e n tt w oo p t i m a la l g o r i t h m sf ff o r 1 s 学a n d s ff o rs 学r e s p e c f i v e l y f fg i v e sp r e f e r e n c et ot h ef a s t e r m a c h i n e ，a n ds fg i v e sp r e f e r e n c et ot h es l o w e rm a c h i n er e s p e c t i v e l y , t h e no b t a i nt h e c o m p e t i t i v er a t i o ： 5 + 2 目+ 1 s 1 学r e s p e c t i v e l y t h e n w es h o w t h a t f f l s i so p t i m a lf o rt h i sp r o b l e mw h e n1ss 生华，a n ds f l si so p t i m a lf o rt h i sp r o b l e mw h e n s 遍盟，2 1 4 7 9 ) u ( 3 8 3 5 9 8 ，+ 。) a n dt h el a r g e s tg a pb e t w e e nt h ec o m p e t i t i v er a t i o a n dt h el o w e rb o u n di sa b o u t0 0 6 4w h e ns 1 2 1 4 7 9 ，3 8 3 5 9 8 ) k e yw o r d s ：s c h e d u l i n g , d e s i g na n da n a l y s i so f a l g o r i t h m ，s e m i o n l i n e ，c o m p e t i - f i v ea n a l y s i s ， 一i i 第一章绪论 1 1 排序问题 第一章绪论 排序( s c h e d u l i n g ) i 司题是研究满足一定要求下，如何安排有限资源以达到某种 意义下的最优结果的研究分支，是一类有着重要理论意义和广泛实际背景的问 题，它在生产计划调度、信息处理、公用事业管理等诸多方面具有大量的应用 从1 9 5 4 年j o h n s o n 第一篇经典排序论文【1 1 】问世以来的半个世纪中，全世界已经发 表的排序文章已经达到两千多篇，排序研究的长足发展，特别是新型排序模型的 丰硕成果使得排序论已经成为发展最迅速，研究最活跃，成果最丰硕，前景最诱人 的学科领域之一 根据排序研究的最初背景，我们习惯上把需要完成的任务称为工件( j o b ) ，工 件集用j = 以，以，厶 来表示把完成任务需要的资源称为机器( m a c h i n e ) ， 机器集用m = 蝎，m 2 ， ) 来表示工件以的加工时间用n 表示我们希望 能够找到一个可行的排序使给定的目标函数达到最大( 或最小) 这里的可行一般 指在同一时刻，一台机器最多能加工一个工件，一个工件也只能在一台机器上加 工并且该排序满足问题的特定要求 按照学术界多年来形成的惯例，一般用所谓的三参数表示法( t h r e e - f i e l dr e p r e s e n t a t i o n ) a z ，y 8 来表示一个具体的排序问题，这是g r a h a m 等在c o n w a y 等提 出的四参数表示法的基础上于1 9 7 9 年提出来的，其中o ，口和7 分别刻画了机器环 境，工件特征和最优准则，它们是排序问题的三个组成部分 机器环境用来描述机器的数量，不同机器之间的关系等与机器有关的性质， 只有一台机器的排序问题称为单机( s i n g l em a c h i n e ) 排序问题，否则称为多机排序 多机排序问题又分为两大类：平行( p a r a l l e l ) 机和车问捧序平行机是指所有的机 器都具有相同的功能，分为三类：所有机器具有相同加工速度的同型( i d e n t i c a l ) 机，具有不同加工速度但此速度不依赖于工件的同类( u n i f o r m ) 机和随加工工件 的不同加工速度也不同的不同类( u n r e l a t e d ) 机在三参数表示法中分别用p q ，r 来表示本文主要研究同类平行机排序问题车间排序也分为三类：每个工件阻 特定的相同的机器次序在机器上加工的流水作业( f l o ws h o p ) ，工件依次在机器 上加工的次序是任意的自由作业( o p e ns h o p ) 和每个工件以各自特定的机器次序 进行加工的异序作业o o bs h o p ) 第章绪论 工件特征一般可用工件的加工时间，工件可以开始加工的时间，工件之间的 依赖关系，工件在加工时是否可中断来刻画在经典的排序理论文献中，我们根据 排序者在排序时掌握工件信息的多少把排序问题分为离线( o f f l i n e ) 和在线( o n l i n e ) 两类在离线问题中，全部工件的所有信息都已知，排序者可以充分利用这些 信息来进行安排，而对于在线问题，其基本假设有两条：( 1 ) 工件的信息是逐个释 放的，即工件功+ 1 的信息只有在排序者e m # p ，p z ，p ，作出安排后才会被排序 者所知( 2 ) 工件加工不可改变，即一旦排序者将t 件安排给某台机器加工，在其 后的任何阶段不能以任何方式进行改变在实际需要的大力推动和理论工作者的 不懈努力下，近年来出现了一种新的排序概念半在线( s e n l i o n l i n e ) 排序问题，它 是指排序者掌握的信息位于离线和在线之间，我们将在后面的小节中给出半在线 排序问题的详细讨论 排序作为一个最优化问题的优化目标通常是一个一维实数，我们用a 表示 在某一排序_ t 件功的完工时间，j = 1 ，2 ，用2 ，表示在某一排序机器 毛的完 工时间，j = 1 ，2 ，m ，记c 2 燃q ，g 篇n 。2 。m a xl j 分别称为最大机器 完工时间和最大工件完工时间( 极小化目标) 在经典的平行机排序理论中，总是 假设机器自零时开始可以加i i 件，此时有c 。= c 。，统称为m a k e s p a n ，记 为c k 。记c k 。= m i p 称为最小机器完工时间( 极大化目标) 有时也称此目标 为机器覆盖本文主要讨论目标函数是c k 。的排序问题常见的其他的目标函数 还有总完工时间，最大延误时间，最大误工时问等，在此我们就不一一介绍了 有关排序问题的专著可参看 1 5 】 1 2 近似算法和竞争比分析 算法( a l g o r i t h m ) 是指一个预先制订执行的程序，对这个问题的任何一个实 例( i n s t a n c e ) ，按照这个程序操作后都可以得到一个可行排序，解离线问题的算法 称为离线算法，解在线问题的算法称为在线算法，l p t 算法0 0 】和l s 算法【9 分 别是经典的离线和在线算法 对于极小化目标函数的优化问题，记j 是这个优化问题的实例，p 是所有实 例的全体，并且记c d 胛( j ) 是实例，的最优解值，e 4 ( ) 是算法a 解实例j 的目标 函数值衡量近似算法的优劣可咀从两个方面来看，一是算法的时间复杂性，二是 算法所得到的解值和最优解值之问的接近程度这里，接近程度常常用所谓的最 坏情况界( w o r s t c a s er a t i o ) 来刻画：假设a 是求解极小化目标的离线排序问题的 一2 一 第章绪论 任意算法，称 r a = i n f r l i e a ( ，) r c o p r ( ，) ，v ，p ) 为算法a 的最坏情况界 对在线问题和在线算法的研究中，在最坏情况界的基础上逐渐形成了竞争比 分析( c o m p e t i t i v ea n a l y s i s ) f 去，俗称对手法( a d v e r s a r ym e t h o d ) 7 ；1 6 假设a 为求解 一极小化目标的在线排序问题的任一算法，它的对手( a d v e r s a r y ) - - 方面预知a 对 实例的执行结果，另一方面可以得到任一实例的最优解，称 c a = i n f c 1 1 c “( ，) sc c o ”( n v i p ) 为算法a 的竞争比( c o m p e t i t i v er a t i o ) 称在线问题的竞争比一卜界( 简称为下界， l o w e r b o u n d ) 为c ，如果不存在该问题的竞争比小于c 的在线算法下界可以通过 对手给出一系列的实例使得任何算法都不能很好地求解它们的全部来得到竞争 比反映了算法且得到的近似解在最坏情况界下与最优解的接近程度，下界体现了 一个在线问题由于部分信息未知而给求解带来的困难。这是不依赖算法设计的固 有性质，若算法a 的竞争比等于问题的下界，我们就称a 是最优( o p t i m a l ) 算法，这 是从竞争比的意义看一个在线算法可以得到的最好的结果对于极大化目标的问 题，算法的最坏情况界，竞争比分别定义为： r a = n ， r 1 i e o ”( ，) r c 4 ( n v i p c = i n f e 1 i g o p r ( j ) r c ( ，) ，v i p ) 1 3 半在线排序问题 由在线和离线的定义可以看出，从排序者对工件信息的掌握程度来看，他们 分属于两个极端的情形在实际问题中出现这两种情况的机会并不是很多大量 存在的问题是排序者一方面不可能知道工件的所有信息，一方面可能掌握着比 经典在线排序更多的信息，或者有着更大的排序自由度，因此使问题变的比在线 问题相对容易一些，即可能得到比在线算法更好的算法我们把排序者掌握信息 位于在线和离线之间，或者掌握部分信息的排序问题称为半在线( s e m i o n l i n e ) j 序 1 3 ；1 4 不同类型的部分信息形成不同类型的半在线模型，常见的有： 3 第章绪论 已知工件总加工时间( s u m ) ：即：lp j 已知工件最大加工时间( m a x ) ：即m a xp ， 1 s ，s n 已知工件加工时问非增( n o n - i n c r e a s i n g j o b ) ：即有如功+ l ，1 茎j 7 2 已知工件加工时间在已知区间( i n t e r v a l ) ：即已知功囟，r p ，l j n ，其 中p 20 ，r 1 已知实例的最优解( k n o w no p t i m u m ) ：即对每个实例j ，c o 尉( ，) 已知 己知工件加工时间序( o r d i n a l ) ：即己知工件的加工时问大小顺序，而其确切 值未知 为描述排序问题方便起见，我们将表示各半在线模型的记号写在三参数表示 法的第二个邻域( e p 国中尽管半在线模型不完全满足在线模型的两条假设，但它 与在线之间只是程度上的差别，而与离线问题有着本质的差别，因此我们仍用竞 争比分析法来研究半在线近似算法的性能和问题的下界 半在线研究的兴起并非偶然，它是排序理论研究深入和实际应用发展的必然 要求，半在线研究使我们能够根据实际情况的不同量身定制算法，以此来提高算 法的近似性能，并且随着半在线研究的深入，我们可以有意识地充分调动问题中 的有用信息，从而最大限度地提高算法的效能 另一方面，对半在线问题的系统研究可以在实践中指导我们，为得到近似性 能好的算法出发创造条件，面对一个实际问题，如果我们想得到近似性能更好的 算法，那么就要掌握更多的信息，从目前已有的研究来看，各种部分信息对算法近 似性能改进的程度是不一样的，有些改进多一些，有些没有改进，称在某机器环境 及目标函数下，某部分信息有价值，若存在求解相应半在线问题的算法，其竞争比 严格小于在线问题的下界，反之，若半在线的下界等于最好在线算法的竞争比，则 称该部分信息是无价值的，如已知工件的总数目n 值显然是无价值的在实践中 我们应努力寻找价值大的部分信息，而避免把精力花在无价值信息的获取上对 半在线问题，【1 3 ；1 4 】作了全面的介绍 1 4 两台同类机在线半在线排序问题 对两台同类机在线半在线排序问题通常考虑两种类型的竞争比分析，一种 是把问题的下界和算法的竞争比都视为两台机器速度比s 的函数，以下分别称为 参数下界和参数竞争比另一种是考虑参数下界和参数竞争比在s 1 时的极大 值。分别称为常数下界和常数竞争比 一4 一 第章绪论 当目标为极小化机器最大完工时间时，c h o 和s a h n i 【2 1 】得到了l s 算法对在 线问题q 2 1 1 口的常数竞争比是1 孚e p s t e i ne ta l 6 1 i 乖u j t l s 算法解此问题的 参数竞争比是 事2 s + l ：擘 并证明t l s 是参数最优算法对在线q 2 1 p m p t l g 。问题( 工件可中断) w e n 和d u 2 0 】给出了参数竞争比为14 - 南的参数最优算法t a n 和h e 【1 7 】研究了半在 线i h q 题q 2 1 0 r d i n a l l c m 。得到了关于s l 的参数下界，然后他们又给出了此问题 的算法，对大多数s i ? i i 言该算法取得最优e p s t e i n 和f a v r h o l d t 【2 】研究t o 在线问 题q 2 1 p m p t ，d e e r i g 。给出了竞争比为 s 3 的参数最优算法在另一篇文献【3 】里，她们又研究t q 2 1 d e c r l c , 。，证明t l p t 算- 法解此问题是常数最优算法，常数竞争比为竽但是l p t 并不是参数最优算 法，e p s t e i n 和f a v r h o l d t 找出t l p t 为最优的s 的区间，而对其余的区间又设计了新 的参数最优算法e p s t e i n 5 研究了半在线问题q 2 1 0 p t l g 一，给出竞争比为速度 比s 的函数的算法，竞争比为 2 s + 2 2 8 + i s 5 + 2 1 ss 址产， 学 2 对于半在线问题q 2 l s u 圳。，t a n ：手【l h e 【1 8 】给出了常数竞争比为、，压的算法，并 给出了此问题的常数下界学在同一篇文献里，他们又考虑了半在线问 题q 2 i m o 圳c 。，给出了常数竞争比为i 的算法，并给出了该问题的常数下界厄 当目标为极大化机器最小完工时间时，e p s t e i n 4 研究了在线问题q 2 1 1 c k m ， 并证明t l s 算法是解此问题的最好参数算法，参数比是s + 1 同时，她又给出了 氛，、 第一章绪论 半在线问题q 2 1 哪i c k 。的参数最优算法算法的竞争比为 恳薹 对于半在线问题q 2 聊引c k j i a n ge ta 1 【1 2 】给出了参数最优算法，算法的竞争 比为专等1 he ta 1 在文献 1 9 】中给出了半在线问题q 2 l o r 出n n f l c r m i 。的参数最优 算法 需要说明的是，对于两台同类机排序问题，目标是g 时和目标是c k 。时， l s 算法通常有着不同的含义当目标是c k 。时，l s 是按照最早完工的贪婪原则来 安排工件，而当目标是c 。时，l s 是按照最早开工的贪婪原则来安排工件 1 5 论文综述 本文着重研究两台同类平行机半在线问题近似算法设计及其竞争比分析第 一章介绍了排序问题，算法的竞争比分析等基本概念以及相关问题的已有结果 第二章主要研究两台同类平行机在已知工件总加工时间的前提下，极大化最小机 器完工时间的半在线问题，a p q 2 1 s u m l c , 。m 给出了该问题的参数下界及参数最 优算法算法的参数竞争比为 1 s 2 ， 以 学 图1 1 i ； 题q 2 l s u m l a 。的参数界 一6 一 业 署。一 第一章绪论 第二三章主要研究两台同类平行机在己知工件最大加工时间的前提下，极大化 最小机器完工时间的半在线问题，b j q 2 1 m a x i c k l n 该问题的参数t j ? - # j 给出了参数竞争比为 的算法 s + 2 + 1 s 盟 5 ，+ 5 + 1 + i c ：孑f 干夏丽 奢干嚣一 1 s s 以， 以 s 学， 出2 s s1 + 以 5 l + 以 1s8 以， 以 s s 学， 学 s 2 1 4 7 9 ， 2 1 4 7 9 3 8 3 6 0 图1 2 问题q 2 m 口。i g 。的参数下界和算法的参数竞争比 对目标为极大化最小机器完工时间的两台同类机半在线排序问题，模 型假设如下：有n 个彼此独立的工件j ； ，也，厶) 需在两台机器m = m 1 ，尬) 上加工，机器尬的加工速度分别为0 = 1 ，2 ) ，记导为两台机器的速 度比工件以的加工时间是b ，( 有时为了方便起见也用p ，表示工件) ，因此工 件 在机器慨上的加工时间是p j s bj = 1 ，2 ，n ，i = l ，2 工件在加工时不 允许中断，机器不允许空闲工件一旦安排好不允许以任何方式加以改变工 件是一个一个独立地到来。仅在当前工件排定后才知下一个工件的全部信息 爹学萃 第章绪论 用t 表示所有工件的总加工时间，即t = 孓l 功用厶一表示第个加工时 问为z2 攫嚣功的工件- 用工( 尬) 表示所有工件加工完之后，机器尬的负载， t = 1 ，2 n c 4 = m a x l ( m j ，n - - t 丝。，i 8 第二章已知工件总加工时间的两台同类机排序 第二章已知工件总加工时间的两台同类机排序 2 1 问题q 2 旧u m l g 。伽的下界 不失一般性假设t = 1 + s ，这时有c 。”1 本节首先给出了问题的下界 定理2 1 1 ：任意算法a 求解q 2 s u m l c k 。的竞争比至少是 0 霉靠 在 4 】中已经证明了半在线排序i q 题q 2j o p t l c , , i 。的下界至少是 舞1 s 以， s 以 学 其中舞在l 1 学时有 1 + s s 防，从而有g 邝= 墨字= 生产，但是在最优解中我们把p 安排在 如上加工，把其余工件安排在尬上加工可得至e j c o r = 14 - s p ，从而 有茹= ss 击 ( 2 ) 若算法停止在情形( 1 2 ) 我们可以断定三( 如) 1 + s 一卢1 ，否则有p 工( ) 一s 胁 卢- ，这种情况已经包括在情形( 1 1 ) 中，因此s 卢sl ( m 2 ) l + s 一胁， 从而l ( 尬) = l + s l ( m 2 ) 胁，所以我们有c f f = 旦竽= 生产，因而 有最薪= s 击 一 算法s f l 一直把当前工件l ，记其加工时间为p 放到上加工，直到出现工件五其加 工时间是p d ，使得出现下面几种情形之一： ( 1 1 ) 如果把厶放到 矗上加工，m 1 的新负载在慨，1 + s s 卢2 】之间，则把山放 到m l 上加工，然后把剩余的工件都放到m j 上加工，停止 ( 1 2 ) 如果把五放到a 矗上加工，m i 的新负载至少是1 + s s 岛，并且p 8 s 岛，这 时我们把五放到尬上加工，然后把剩余的工件都放到m 上加工，停止 ( 1 3 ) 如果把五放到m 1 上加工，m i 的新负载至少是1 + s s 侥，并且p d l + s - 侥， 安排 在使得它最早开工的机器上加工，然后把剩余工件都放到另外一台 机器上加工，停止 定理2 2 2 ：当s 1 学时，算法s f 解问题q 2 | s 叫c 。的竞争比至多是击 一1 1 第二章已知工什总加工时间的两台同类机排序 证明：如果算法停止在情形( 1 1 ) 或者情形( 幺1 ) ，即院l ( 尬) 茎1 + s s 岛， 因此有上( 尬) = 1 + s l ( m 1 ) 1 十s 一( 1 + s s 虎) = s 岛，即g 5 f 岛，又 有c o p t 1 ，因l 比c o p ts 击 如果算法停止在情形( 12 ) ，由算法s f 我们知道l ( 如) 一p 。如果s 屈p 。 1 + s 一历，因此有s 侥三( 毛) 1 + 8 一屈，从而三( 以) = l + s 一三( 尬) 1 + s 一( 1 + s 一侥) = 阮也就是g 8 f 历，进、l i u 伺刁c o f p t 击如果m 1 + s 一胰， 算法s f 在这种情形下得到最优解 如果算法停止在情形( 2 2 ) ，我们有s 历sl ( 如) 墨1 + s 一如，从而l ( m i ) = 1 + s l ( m 2 ) 成，且c 5 7 如，因此可c o 矿p t 壶 如果算法停止在情形( 2 3 ) ，我们按算法中以被安排在哪台机器上加工分情况 考虑令p 为 到来后，所到来的所有工件的加工时间之和令l j ( 尬) j = a ，b ，i = 1 ，2 为工件 到达时，机器舰的当前负载 情形1 五被安排到尬上加工 一方面，我们有三( 尬) = p 。+ p b 1 + s 一岛 8 ，c 8 p = l ( 矗) = 1 + s l ( ) = 1 + s p 。一m 另一方面，由算法s f 可知，p ( 尬) 墨兰i 掣，从而有 1 + s = l b ( 尬) + l b ( 毛) + 拂+ p l 6 ( m ) - 4 - s l 6 ( 尬) + 琊+ ( s + 1 ) p = 0 + 1 ) ( 五6 ( m j ) + p ) + p 6 ， 即有c 卵= l ( m 1 ) = l b ( ) + p 纽8 + 1 ， 考虑最优解的情况，如果五和五被安排在同一台机器上加工，则有e d 刀 1 + s p 。一p b = c 卵，算法得到最优解9 n 果j 和以被安排在不同的机器上加 工，由于和都大于l _ 因此最优解的解值取决于工( 尬) 如果以被安排在上加工，从而有c d 胛! 等丑，c 8 f 出s + 1 因此有 如果 被安排在尬上加工，从而有g o 刀s ! 专也 一1 2 一成 + 一s = 善 l + s - - s 成+ 量量搿 = 堕h 篇攀 = 1 + s 矛盾其中最后一个等式是由( 2 1 ) 得到的如果 则有 否则， 因此有 t m s 铡 t + s m 谢 伊刀，生挚 面矿订i i i 磊 = ( ：( 茎；( 鼍p ap b ) + s 一一 + 而当纛) + 焉再p b ) ( 1 ) 国 ，d7 = ；( t + 茅可p i b 而) = ；( - + 吾可再1 丽) 1 3 一 一恳 1 + s s 疡 1 ，c 5 7 = 垡笋= 芝些竽竺= 2 学- z 一方面，由算法s f 可知p ( m js 墨等盟又有 1 + s = l 6 ( 尬) + l 6 ( ) 十p b + p 掣+ l b ( 坞) + m + 半尸ss = s + 。l ( l 6 ( 尬) + p ) + 娜， 即有e 5 7 = 出等世静又由算法可知( m ) + p n 1 + s s 侥， 乳 s l b ( 尬) s l 。( m d ，所以有 s 一品岛考虑最优解的安排情况 如果五和五被安排在不同的机器上加工若以在尬上加工，a o 胛! 专妞， c 5 9 s l b ( m j 因此有哿c o 矿p t ! - k 若以在上加工，e o 胛挚，从 而有 笳等 1 + 8 一s 侥可知g o 刀岛因此有 c o w ，岛 伊匠受 堡 其中最后一个不等式可由下式得到， ! 鱼 一s 一簧岛 历1 ( s 2 + s ) 鹾+ 8 2 阮一( s 2 + s ) = s 2 鹰+ ( s 2 + s + 1 ) 岛一( s 2 + s ) + s 鹾一( 占+ 1 ) 恳 = 0 + s 詹一0 + 1 ) 屁 s0 一1 5 一 第三章已知最人工件加工肘间的两台同类机捧序 第三章已知最大工件加工时问的两台同类机排序 3 1 问题q 2 1 m a x c f m m 的下界 这一节我们考虑问题q 2 i m n 。i g m ，其中工件加工时间最大值是已知的不 失一般性，我们设这个值为l - 记厶。为第一个加工时间是1 的工件我们给出这 个问题的下界 定理3 i 1 ：对排序问题q 2 i m n z l c k 。的任何半在线算法的竞争比至少是 0 1 s 以， 以 鬻否则，如果把以安排到尬上加工，最后一个工件以，其 加工时间是1 ，因此有c 4 = l _ 通过安排 和以在 矗上加工，并把其余工件安排 到上加工，可得到伊坩= 雨s + l ，因此写孚= 者 情形2 如果 被安排到 如上加工再来一个工件j 2 ，其加工时i , ，。l + 叠s 百- s 2 如果以也被安排到上加工，则不再来工件，因而我们得到g a = o ，且g o 刀= 1 ；i s 干- f s 2 ，从而有；孑= o 。 而s + 2 - 如果我们把也安排在婀上加工，第三个工 件以，其加工时间是= ；到达如果把它放到且如上加工，则有c 峭= l + ；耳s - s 一2 ，且 通过安排 在m 上加工，其余工件在尬上加工，可以得到g o 刀= ：1 ，从而 有1 亨c o r p t = i 干s i + = l 雨s + 2 否则，如果安排j a 在尬上) r ot ，最后一个工件山，其加 1 6 第三章已知最大工件加工时间的两台同类机排序 工时问为1 到达，因此我们得到e 4 = ：通过安排 和无在尬上加工，并且把其 余工件放在 如上加工，有刀= 。2 ：s + + 。l ，因而有可c o r p t = 酉2 8 + 1 鬲s + 2 一 引理3 1 3 ：当、，压s 1 + 以时，任何半在线算法a 求解问题q 2 i m n z l e k 。的 竞争比是少是m i n s ，! 盟8 ) 证明：第一个工件 ，其加工时间为= 1 我们考虑两种情形 情形1 如果 被安排到m - 上加工再来一个工件也，其加工时间是1 如果以 也被安排到尬一h n i ，就不再来工件了，我们得n c = 0 ，且有c o ”= ；，从而 得到；茅= 0 0 m i n s ，半) 如果把也安排到 如上加工，最后一个工件到达， 其加工时间是i 我们得n c “= 通过安排如在尬上加工，其余工件都安排 到 如上加工，有e d ”= m i n 2 挚，1 ) ，c 万o r p t = m i n s ，! 芋) 情形2 如果 被安排到 如上加工再来一个工件如，其加工时间是1 显 然，以应该被安排到尬上，否则就不再来工件了，从而我们得到g 4 = 0 ，且 有c o ”= ；，从而有；：= 0 0 m i n s ，2 芋) 所以以被安排到上加工，故 有c 4 = 击，且有c o 刀= ；，从而有号= s m i n s ，学) - 令a 2 = k ! 兰土近亨旺西是关于z 的方程百l + x = 平2 的较大的根注意到 当s i + j 时，有o 2 等因此我们把它安排到地上，再来工件如，其加工 时间是1 如果我们也把它安排到尬上加工，可以得到g a = 0 2 且通过安排五 到m 上其余工件在尬上有c o p t = 1 挚，从而有；= 1 甚如果安排以 到尬上，最后一个工件五到达，其加工时间是；一0 2 ，得n c “= 兰i 通过 安排以和五到m 上加工，并且把其余工件都安排到尬上有a o 刀= ；，从而 有譬= 南= 等 情形2 如果 被安排到 毛上最后一个工件以，加工时问为1 i 件到达，显 然我们不能把这两个工件都安排到 如上加工，否则就不再来工件了，我们得 一1 7 一 第三章已知最人工件加工时间的两台同类机排序 到g 4 = o ，且有e d p r = i 1 ，从而得到弓箬= o 。 等因此安排它们在蝇上加 工得到g 4 = 警有g o 刀= n 2 ，因此有了c o r p t = s 訾 因此当s 1 + 以时有可c o r p t 等 _ 3 2 f 循q 2 1 m a x l c k 。的算法 这一节我们将给出问题q 2 1 m a x l 。的两个算法算法f a s tf i r s tl i s t s c h e d u l i n g ( 简记为f f l s ) 和算法s l o wf i m tl i s ts c h e d u l i n g ( 简记：为s f l s ) 分 别为优先考虑慢机器和快机器而设计当满足一定条件时两个算法都用到了l s 规则下面这个定理描述了l s 规则的个性质 引理3 2 1 ：( 1 ) 如果l ( m 1 ) 等堕h m i 上最后一个工件是按l s 规则安排的， 则有l ( 尬) s 掣+ 1 ( 2 ) 如果锷盟三( 尬) 且上最后一个工件是按l s 规则安排的，则 有l ( ) ss l ( m , ) + 1 证明：( 1 ) 设尬上的最后一个工件是j ，其加工时间记为p 由三s 规则我们知 i 苣l ( m 1 ) 一p 锷盟，也就是工( m ) 避盟+ p 茎生学+ 1 因此有工( ) 掣+ 1 ( 2 ) 于( 1 ) 相似地，设上的最后一个工件是其加工时间是一由l s 规则 我们知道垡! 冬巡l ( m i ) ，也就是工( ) s l ( m j + p s l ( m ) + 1 - 1s s 、2 讵 ss 学 算法f f l s 阶段1 一直把当前工件| 7 安排到尬上加工，直到下面情形之一发生 ( 1 1 ) 如果当前- t 件j 是厶。，安排t ，在 矗上加工，转到阶段2 ( 1 2 ) 如果安排j 到坞上加工，的新负载至少是面可苦两，则安排j 在上 加工，转到阶段2 阶段2 按l s 规则安排剩余工件 一1 r 一 辫。 ，f，l = 等 p 旺m | i 令 第三章已知最大工件加工时问的两台同类机排序 引理3 2 - 2 ：如果l ( 尬) 研可苦两，则必有l ( m 1 ) 兰两可苦两 证明：如果j k 一被安排到上，则有工( 以) 12 两桶雨= 玎丽1 否 她q ，厶。必定在阶段2 被安排到必上加工，当厶。被安排之前，我们记尬， 岛的 当前负载分别为工m 。z ( m 1 ) ，l m “( 尬) 如果l m 。( 尬) 面可雨1 = 可，厶n 。将在阶 段1 被安排到尬上m i ，矛盾 因此，l (