（运筹学与控制论专业论文）平行机半在线排序问题.pdf

2 0 0 5 年上海大学博士学位论文 摘要 本文主要考虑平行机半在线排序问题本文首先简要介绍了排序问题、竞争 比分析和近似算法等基本概念，总结了近年来出现的各个半在线模型及其有关结 果 第二章考虑已知工件最大加工时间的半在线模型，目标为极大化最小机器负 载主要讨论两个问题1 三台同类机的情形，我们给出m m 3 算法并且证明此算法 的竞争比为m a x r + 1 ，百3 s + 鬲r + 1 ) m e n 3 算法是紧的且当1s ss2 、r = 1 时是最优 的2m 台特殊同类机问题，我们给出c 矗。算法及其竞争比m a x i t 一1 ，等圭；导 ， 并证明c m ：。算法是紧的且当1 ss ( m 一1 ) ( m 一2 ) ( m 3 ) 时是最优的 第三章考虑已知工件最大加工时间的半在线问题，目标为极小化机器最大负 载主要讨论四个问题1 对于两台同类机的问题，我们给出竞争比分别为毪掣 ( 1 s52 ) 和睾( s 2 ) 的q m a x 2 算法，并且证明此算法是紧的且相应某些s 的特殊值是最优的 2 对于三台同类机半在线问题，我们给出q m a x 3 算法并证明 此算法的竞争比不大于2r ；+ i 百s + l u ( 1 2 ) 且严格小于23 对于 三台特殊同类机问题，给出口m 凹3 t 算法并证明其竞争比不大于! 擎( 1ss 2 ) 和串( s 2 ) 且憔小于24 最后我们考虑m 台同型机问题，给出一个竞争比为 2 m - 量，3 的c 。算法并证明此算法对任何m 3 是紧的 第四章中，我们考虑已知工件总加工时间的两台同类机半在线问题，目标为 极大化最小机器负载我们给出q 2 m m 算法并证明此算法的竞争比小于骂卑，而 此问题竞争比的下界为过净同时证明当s = 咎竽时q 2 m m 算法最优的 在第五章中，我们考虑带机器准备时间的已知工件总加工时间的半在线问题 第一节考虑p 2 ，r “s u m c k 。问题，给出p r s u m 算法并证明此算法的竞争比为； 且是最优算法在第二节则考虑q 2 ，r ，i s u 1 l c k 。问题，给出9m a x 算法并证明 此算法的竞争比为、2 ，同时给出此问题的一个下界 第六章我们首先引进一个新的半在线木语半在线模型的松弛，然后我们介绍 一个新的半在线模型已知工件最大加工时间在某一区域内，即k n o w nl a r g e s t3 0 b m t e r v a t 模型第一节考虑p 2 l k n o w nl a r g e s tj o bz n t e 7v a l g 。问题，我们给出 p m t e r t a l 算法及其竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过 去第二节考虑p 2 j k n o z u nl a r g e s t3 0 bm t e r v a l l c m ，n 问题，我们给出pz n t e r v a l 算 法的竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过i 1 关键词排序问题，半在线，竞争比 上海大学博士研究生论文 a b s t r a c t t h i sp a p e rs t u d i e ss e m io n l i n ep a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m si nt h e f i r s tw ei n t r o d u c eb a s i cn o t i o n so fs c h e d u l i n gp r o b l e m s ，c o m p e t i t i v ea n a l y s i sa n d a p p r o x i m a t i o na l g o r i t h m ，s u m m a r i z es e m io n l i n em o d e l sa n dt h e i rr e s u l t sw h i c h a p p e a ri nr e c e n ty e a r s i nc h a p t e r2 ei n v e s t i g a t es e m io n l i n es c h e d u l i n gp r o b l e m sw h e r et h el a r g e s t p r o c e s s i n gt i m eo fa l lj o b si sk n o w n i na d v a n c et h eg o a l1 st om a x i m i z et h em i n i - m u mm a c h i n ec o m p l e t i o nt i m ei nt h i nc h a p t e r ，w em a i n l yc o n s i d e rt w op r o b l e m s 1f o rt h ec a s eo ft h r e eu m f o r mm a c h i n e s ，w ep r e s e n tr a m 3a l g o r i t h ma n ds h o wi t s c o m p e t i t i v er a t i oi sm a x r + 1 ，塾l + r d + 生a ) w h i c h1 st i g h ta n do p t i m a lf o r1 墨s 2 、r = 12f o ras p e c i a lc a s eo fmu n i f o r mm a c h i n e s ，w ep r o v i d ec m 2 na l g o r i t h m a n ds h o wi t sc o m p e t i t i v er a t i oi sm a x m 一1 ，舞 w h i c hi st i g h ta n do p t i m a l f o r1 8 ( 竹2 1 ) ( m 一2 ) ( m 3 ) i nc h a p t e r3 、ec o n s i d e rt h es e m lo n l i n es c h e d u h n gp r o b l e m sw h e r et h el a r g e s t p r o c e s s i n gt i m eo fa l lj o b si sk n o w ni na d v a n c e t h eo b j e c t l v ei st om i n i m i z et h e m a x l m u mm a c h i n ec o m p l e t i o nt i m ew em a i n l yc o n s i d e rf o u rp r o b l e m s1w eg i v e q m a x 2a l g o r i t h m h o s ec o m p e t i t i v er a t i oi s 必s + 2 ( 1 s 2 ) a n d 丁s + ls 2 ) f o r t w ou n l f o r mm a c h i n e sc a s e ，a n ds h o wq m a x 2a l g o r i t h mi st i g h ta n do p t i m a lf o r s o m es 2f o rt h ec a s eo ft h r e eu n i f o r mm a c h i n e s ，w ep r e s e n tq m a x 3a l g o r i t h m w h o s ec o m p e t i t i v er a t i oi sn o tg r e a t e rt h a n 攀( 1 2 ) b u ts t r i c t l yl e s st h a n23i ft h em a c h i n ea r et h r e es p e c i a lm a c h i n e s ，w ep r o v i d e q m a x 3 ta l g o r i t h mw h o s ec o m p e t i t i v er a t i oi sn o tg r e a t e rt h a nt s + 2 ( 1 s 冬2 ) a n d _ _ s + 2 ( s 2 ) b u ts t r i c t l yl e s st h a n2 4f m a l l 3 ，w ei n v e s t i g a t emi d e n t i c a lp a r a l l e l m a c h i n e sc & s ew e g i v ec 毛a l g o r i t h ma n d s h o wi t sc o m p e t i t i v e1a t l o1 s 等等w h i c h l st i g h tf o re v e r 3 m 3 i nc h a p t e r4 w es t u d ys u c hs c h e d u l i n gp r o b l e mw h e r et h et o t a lp r o c e s s i n g t i m e so fa l lj o b sl sk n o w ni na d v a n c eo nt w ou m f c i r mm a c h l n e sw i t ho b j e c t i v et o m a x i m i z et h em i n i m u mm a c h i n ec o m p l e t i o nt l m ew ep r o p o s ee 2 m ma l g o r i t h m a n ds h o wi t sc o m p e t i t i v er a t i o1 sl e s st h a n 学，w h i l et h el o w e rb o u n di s 学w e a l s op r o v et h eq 2 m ma l g o r i t h mi so p t i m a lf o rs = 半c a s e i nc h a p t e r5 ec o n s i d e rs e m io n l i n es c h e d u l i n gp r o b l e mw h e r et h et o t a lp r o c e s s l n gt l m ei sk n o 、ni na d v a n c ew i t hn o n s l m u l t a n e o u sm a c h i n ea v a i l a b l et i m e s i n t h ef i l s ts e c t i o n ，w ei n v e s t i g a t ep 2 ，n l s m i c k t np r o b l e mw ep r e s e n tp r s u ma l g o - i i i2 0 0 5 年上海大学博士学位论文 r l t h ma n ds h o wi t sc o m p e t l h 、j er a t i oi s w h i c hi so p t i m a li nt h es e c o n ds e c t i o n ，w e s t u d ) 7q 2n l s u m l c k o zp r o b l e m w ep r o p o s eq r m a xa l g o m t h mw h o s ec o m p e t l t l 、e r a t i o l s , 5 i nc h a p t e r6 w ei n t r o d u c ean e wt e r m i n o l o g yr e l a x a t i o no fs e m io n h n e m o d e la n dan e ws e m io n l i n em o d e lk n o w nl a r g e s t3 0 bz n t e r v a li nt h ef i r s t s e c t i o n 、w ei n v e s t i g a t ep 2 l k n o w nl a r g e s t3 0 bi n t e r v a l g n n zp r o b l e mw ep r e s e n t p m t e r v a la l g o r i t h mw h i c hi st i g h ta n ds h o wt h et h ed i f f e r e n c eb e t w e e ni t st o m p e t l t l 、j er a t ma n dt h eo p u m u md o e sn o te x c e s s 去i nt h es e c o n ds e c t i o n ，w es t u d y p 2 1 k n o w nl a r g e s t3 0 bm t e r v a l i c 矗i np r o b l e m w es h o wt h ec o m p e t i t i v er a t mo f p m t e r v a la l g o r i t h ml st i g h ta n dt h et h ed i f f e r e n c eb e t w e e nl t sc o m p e t i t l v er a t i o a n dt h eo p t i m u md o e sn o te x c e s s ；1 k e yw o r d s ：s c h e d u h n g ，s e m lo n l i n e ，c o m p e t i t i v er a t i o 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究 工作。除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已发表或撰写过的研究成果。参与同一工作的其他同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 签名： 本论文使用授权说明 日期：硅堕、1 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅和 借阅；学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：绷导师签名鹦日期：之亟，夕 1 2 0 0 5 年上海大学博士学位论文 第一章绪论 5 1 1 排序问题 排序( s c h e d u l i n g ) 问题是一类有着重要理论意义和广泛实际背景的组合优化 问题f 5 5 ，5 6 ，6 4 ，其实质是寻求对需完成的任务的合理安排以得到某种意义下的最 优结果它在生产计划调度、信息处理、公用事业管理等诸多方面具有大量的应 用，美国国防部与数学科学研究f 65 1 的报告认为：2 0 世纪9 0 年代以至整个 2 1 世纪数学发展的重点将从连续的对象转向离散的对象，并且组合最优化将会有 很大的发展“因为在这个领域内存在大量急需解决而又极端困难的问题，其中 包括如何对各个部件进行分隔、布线和布局的问题”而分隔、布线和布局就与排 序有关同时排序问题与理论计算机科学和离散组合数学存在密切的联系从 1 9 5 4 年j o h n s o n 第一篇经典排序论文1 3 6 l 问世以来的半个世纪中全世界已经发表 了排序文献2 干多篇排序问题的长足发展，特别是新型排序的丰硕成果使排序 论已经成为发展最迅速，研究最活跃、成果最丰硕、前景最诱人的学科领域之一 在排序文献中，习惯上把需要完成的任务称为工件( j o b ) ，工件集用j = ，以，矗) 来表示，把完成任务需要的资源称为机器( m a c h i n e ) ，机器集用 m = m h 她，) 来表示工件五的加工时间用岛表示，在文中也用p ，指 代工件 对某个给定的目标函数我们希望能够找到一个可行的排序( s c h e d u l e ) 使其达到最大( 或最小) 这里的可行一般指在同一时刻一台机器上至多能加工一 个工件，一个工件也只髓在一台机器上加工，并且该排序满足问题的特定要求 排序问题按静态( s t a t i c ) 和动态( d y n a m i c ) 、确定性( d e t e r m i n i s t i c ) 和非确定 性( o n d e t e r m i n i s t i c ) 可以分为四类对于静态的确定性排序问题，我们习惯上用 三参数法来表示 1 9 6 7 年c o n w a y 1 l 】等首先提出用四个参数来表示排序问题， 1 9 7 9 年g r g h a m 2 0 】等提出改用三参数即甩吲7 来表示一个排序问题其中、 卢、7 分别代表特定的机器环境，工作特征和最优准则， 2 上海大学博士研究生论文 机器环境用来描述机器的数量，不同机器之间的关系等与机器有关的性质 机器可以分为两大类通用平行( p a r a l l e l ) 机和专用串联( d e d m a t e d ) 机对于不允 许中断加工的情况来讲，一个工件在m 台平行机器上加工只需要在m 台机器中 的任何一台机器上加工一次即可，一个工件在m 台串联机上的加工则需要在这m 台机器中的每一台机器上都加工一次 平行( p a r a l l e l ) 机又可以分为三类；具有相 同加工速度的同型( 1 d e n t m a l ) 机、具有不同加工速度但此速度不依赖于工件的同 类( u m f o r m ) 机和随加工的工件不同加工速度也不同的非同类( u n r e l a t e d ) 机在 三参数表示法中它们分别用p 1q ，r 表示 串联( d e d i c a t e d ) 机也可以分为三类 每个工件以特定的相同的机器次序在机器上加工的流水作业( 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 h n e ) 两类在离线问题中，全部工件的所有信 息都已知，排序者可以充分利用上述信息对工件进行安排而对在线问题，其基 本假设有两条( 1 ) 工件的信息是逐个释放的，即工件岛+ l 的信息只有在排序者 对工件p l ，p 2 ，乃作出安排后才会被排序者所知，( 2 ) 工件加工不可改变，即一 旦排序者将工件安排给某台机器加工，在其后的任何阶段不能以任何方式加以改 变在实际需要的大力推动和理论工作者的不懈努力下，1 9 9 6 年出现了一种新的 排序概念一半在线( s e m lo n h n e ) 排序问题有关半在线排序问题，我们将在后面 的小节中详细讨论 排序作为一个最优化问题的优化日标通常是一个一维实数我们用q 表示 在某排序下工件p j 的完工时间，j = 1 ，2 ， ，n ，用f 。表示机器 磊的完工时间 ，2 = 1 ，2 ， ，m 记c z = m ；a x l t ，c 篇一= m ，a x c j ，分别称为最大机器完 工时间和最大工件完工时间( 极小化目标) 在经典的平行机排序中，总假设机器 自零时刻开始可以加工工件，此时有c 紫m 。= 。，统称为排序的m a k e s p a n ， 2 0 0 5 年上海大学博士学位论文 3 记为e 一而当机器存在准备时间时，两者未必相同 4 1 】记c k h 2r a i n l i ， 称为最小机器负载( 极大化目标) 本文主要讨论c k 。e k 。这两个目标函数文 献中常见的其他目标函数还有总完工时间、最大延误时间、最大误工时间等 1 2 ，5 0 】_ 1 2 近似算法和竞争比分析 排序问题的算法( a l g o r i t h m ) 是指一个预先制定执行的程序，对这个排序问题 的任何一个具体的实例( i n s t a n c e ) ，按照这个程序操作后都可以得到一个可行的 排序解离线问题的算法称为离线算法，解在线问题的算法称为在线算法工p t 算法 2 3 1 和l s 算法【2 2 分别是经典的离线和在线算法 将实例通过某种规则编码后输入计算机所占用的字节数称为该实例的输入长 度对某一个可能的输入长度，算法解此输入长度的最坏可能实例所需要的基本 运算次数称为该算法的时间复杂性( 函数) 如果存在一个多项式函数p ( n ) ，使得 算法的时间复杂性0 ( p ( n ) ) ，这里n 为输入长度，那么称该算法为多项式时间算 法，否则称为指数时间算法本文中讨论的排序问题都是已被证明为| v p h a r d 的。除非p = n p ，否则不存在求这些问题最优解的多项式时间算法 由于绝大多数排序问题是p 难题，其最优解很难找到，而且在实际应用中 往往也没有必要去找到最优解，只需要找到满足一定要求的启发式解或近似解 因此研究排序问题主要有两个方向一是对p 问题，即可解( s o l v a b l e ) 问题，寻 找多项式时间算法( 又称为有效算法) 来得到问题的最优解，或者对| v p 难题在 特殊情况下寻找有效算法也就是研究难题的可解情况二是设计性能优良的启发 式算法和近似算法衡量算法优劣有三种办法：数值算例计算、最坏情况分析和 概率分析r 1 7 这三种办法各有优点，也各有不足在理论分析( 最坏情况分析和 概率分析) 之前进行大量数值计算是非常有用的方法，一则可以对理论分析给出 估计和提供思路；再者可以与已有的算法进行实际比较最坏情况分析是分析算 法在最坏情况下的形态概率分析是分析算法的”平均”形态，算法的概率分析 可以参考专著 2 5 目前在理论上用得最多的是最坏情况分析 对于使目标函数，为最小的优化问题，记j 是这个优化问题的一个实例，p 是 所有实例的全体；并记f ( i ) 是实例j 的最优目标函数值，扬( ，) 是算法打解实例 4上海大学博士研究生论文 j 的目标函数值如果存在一个实数r ( r 1 ) ，对于任何i p 有知( j ) r 厂( ，) ， 那么称r 是算法日的一个上界如果不能确定算法是否有界，或者能够确定算法 的上界是无穷大时，这个算法称为启发式算法当r 是有限数时，这个算法称为 近似算法因此近似算法是有界的启发式算法对于使上式成立的最小正数r 称 为是算法的最坏情况性能比，简称为最坏比、最劣比，也称为是算法的紧界例 如，在经典排序中l s 算法【2 2 】和l p t 算法【2 3 j 对强p 困难的平行机排序问 题p i | c 。的最坏性能比分别为2 一去， 一去，其中m 是机器的台数 对于使目标函数，为最大的优化问题，同样可以定义算法的一个上界和紧 界如果存在一个实数r ( r 1 ) ，对于任何j p 有，( ，) r ，h ( ，) ，那么称r 是 算法日的一个上界 对在线( 半在线) 问题和在线( 半在线) 算法的研究，在最坏情况比的基础上逐渐 形成了竞争比分析( c o m p e t m v ea n a l y s i s ) 法，俗称对手法( a d v e r s a r y m e t h o d ) j 1 9 ，5 3 j 它属于最坏情况分析对极小化排序问题，称 c u p t 器) 为在线( 半在线) 算法a 的竞争比( c o m p e t l t l v er & t l o ) ，这里c a ( ，) 和c + ( ) 分别 表示算法a 解实例i 所得的目标函数值和相应问题离线情形的最优目标值，在不 引起混淆的情况下分别简记为c _ 和c + 同样地，对极大化排序问题，称 c u ，p 黜) 为在线( 半在线) 算法a 的竞争比( c o m p e t i t i v er a t i o ) 若算法a 的的竞争比为c ， 也称a 为c c o m p e t z t w e 的称在线( 半在线) 问题( 极小化日标或极大化目标) 的竞争比下界( 简称为下界，l o w e rb o u n d ) 为c ，若不存在该问题竞争比小于c 的 在线( 半在线) 算法为了得到下界，一般可以通过给出一系列实例使得任何在线 ( 半在线) 算法都不能够很好地求解所有实例来得到算法a 称为是最优( o p t i m a l ) 的算法，如果不存在竞争比小于c a 的确定性在线( 半在线) 算法近年来，对排序 问题的研究又出现了一类新的算法随机算法( r a n d o m i z e da l g o r i t h m ) 所谓随机 算法是指在算法执行过程中可以作出随机选择的一类算法，前面提到的算法均为 2 0 0 5 年上海大学博士学位论文 5 确定性算法有关随机算法可以参考m o t w a m 和r a g h a v e n 的专著1 4 9 相对确定 性算法而言，随机算法在排序中的应用虽逐渐增多，但还远未成熟本文所指的 算法均为确定性算法 1 3 半在线排序问题 由在线和离线的定义可以看出，从排序者对工件信息的了解程度来看，他们 分属于两个极端情形在实际问题中，出现这两种情况的机会并不多大量存在 的问题是排序者一方面不可能知道工件的所有信息，另一方面可能掌握着比经典 的在线模型更多的信息或有着更大的排序自由度，因而使问题变得比离线相对困 难些，但比在线相对容易些，即可能得到比在线算法更好的算法我们把不完全 满足在线排序问殛的两条基本假设，难度介于在线和离线之间的模型称为半在线 模型( 文中所说的“在线4 是经典意义上的或称为o n h n eo v e rh s t ，近年来人们赋 予其新的含义，或称为o n l m eo v e rt i m e 【9 ，5 4 i ) 在实际需要的大力推动和理论工作者的不懈努力下，自1 9 9 6 年半在线概念 ( 其实对其它的组合最优化问题，如装箱、网络优化也有相应的概念 2 4 ，4 6 】) 提出后 的近8 年间，各种不同的模型不断涌现，初步形成了排序研究的一个新的分支何 勇等【3 3 ，3 4 】把半在线模型分为3 类把不满足在线基本假设( 1 ) 的半在线模型， 即排序者掌握后续工件的部分信息，称为第一类半在线模型；把不满足在线基本 假设( 2 ) 的半在线模型，即已安排的工件的加工进程可通过某种方式加以改变， 称为第二类半在线模型，不能列入这两类的半在线模型统称为第三类半在线模 型为描述排序问题方便起见，我们将表示各半在线模型的记号写在三参数表示法 的第二个域中尽管半在线模型不完全满足在线模型的两条假设，但它与在线之 间只是程度上的差别，在后续工件信息不完全已知这一点上是相同的，而与离线 i 可题有着本质的区别我们仍用竞争比分析法来研究近似算法的性能和问题的下 界若在给定的机器环境和目标函数下，求解半在线排序问题的算法的竞争比严 格小于相应在线问题的下界，则说明此时该半在线模型是有价值的反之，若半 在线问题的下界等于相应在线问题的最优算法的竞争比，则说明此时该半在线模 型不会使问题变得更为简单。因而没有价值当然，半在线排序问题研究的意义 6上海大学博士研究生论文 并不局限于其本身，某些半在线模型的研究可为在线和离线问题的研究提供新的 思路和方法，使这些经典问题取得突破 根据实际情况的不同，我们可以提出不同的符合要求的半在线模型尽管半 在线排序出现的时间很短，然而已有十多个不同的模型出现下面我们对其中主 要的几个模型作简要的介绍 1 已知工件总加工时间的半在线模型( k n o w ns u m ) 假设所有工件的总加工时间已知k e l l e r e r ，e ta l 3 7 在研究p 2 1 1 c k 。时首 先提出并研究的文f 37 给出上b 算法并证明此算法是解p 2 1 s u m l g k 。问题的最 好算法，其竞争比为；文【2 8 证明算法凰也是解p 2 l s u m l c k 。问题的最好算 法，其竞争比为g 对p 2 ，n i s 札m l e _ 。问题，文【6 1 】给出算法p s u m 算法，并证 明此算法最优，其竞争比为 对q 2 1 s u m c k 。问题，文【5 7 ，5 9 】给出其竞争比为 、2 的s u l a 算法，同时证明了问题的下界为1 挈i 对p m l s u m l c k 。( m 3 ) ，文 3 2 】给出其竞争比为2 一鬲与的近似算法 2 已知工件最大加工时间的半在线模型( k n o w nl a r g e s tj o b ) 假设所有工件中加工时间最长的工件的加工时间是已知的，文 3 5 】首先讨论 了这一模型并给出了求解p 2 l k n o w nl a r g e s t3 0 b l c k 。的最优算法p l s ，其竞争比 为；事实上，p l s 算法也是求解p 2j k n o w nl a r g e s t ：o b l c f m ；。问题的最优算法 2 8 】而对p 2 ，r t i k n o w nl a r g e s t ：o b l c 暴。问题，文【6 1 1 给出了竞争比为；的最优算 法m p l s 对q 2 1 k n o w nl a r g e s t3 0 b c m 。问题，文【5 7 】给出竞争比为i 的m l s 算法，而该问题的下界为、2 3 已知加工时间位于同一区间内的半在线模型( i n t e r v a l ) 假设所有工件的加工时间位于一有限区间加，r p 内，这里r 1 ，p 0 文【3 5 首先讨论了这一模型，并证明l s 算法是求解p 2 1 z n t e r v a l i g k 。的最优算法，其竞争 2 0 0 5 年上海大学博士学位论文 7 比为；( r 2 ) 和1 垃2 ( 1 r 2 ) 文【z 7 证明l s 算法也是求解p m l m t e r v a l l c m 。 的最优算法，其竞争比为m ( r m ) 和r ( 1 r m ) 若1 r ：等，文 2 7 】 证明l s 算法也是求解p m l z n t e r v a l i c m 。的最优算法，其竞争比为1 十垃= 等 丑 众所周知l s 算法是求解p 3 1 1 。的最优算法 1 8 】，然而l s 算法是否是求解 p 3 1 2 n t e r v a l l c m 。的最优算法尚未可知对此问题，文【3 2 】证明了如下结论 c ， 两3 1 r 警； r ； ； 2 4 已知工件加工时间非增的半在线模型( n o n i n c r e a s i n gj o b ) 假设工件按加工时间的非增序到达，即有岛p j + 1 ，j = 1 ，2 ， ，n 一1 此时 在研究l s 算法的竞争比时可以利用l p t 算法最坏情况分析的某些结果有如 下结论。 1 ) p m l n o n z n c r e a s o n g3 0 b l c k o z 问题 ( 1 ) 文【2 3 证明l s 算法的竞争比为 一击( 2 ) 文【3 4 】证明当m = 2 时l s 箅法为最优算法，其竞争比为；，当m = 3 时问题的下界至少为l 乎文 5 2 】还 给出了解p 2 l n o n i n c r e a s i n g3 0 b l c m 。问题的竞争比为；的最好随机算法 2 ) p m ，r 3 n o 礼一m c r e a s m g3 0 b l 。问题 ( 1 ) 文【4 0 ，4 1 】证明三s 算法的竞争比为 一赢1 ( 2 ) 文【6 1 证明当m = 2 时， l s 算法为最优算法，m = 3 时问题的下界至少为! 享盟 3 ) p m l 礼。礼一z n c r e a s z n gj d 6 l c m 问题 ( 1 ) 文【1 0 证明l s 算法的竞争比为i 4 m 示j - - 2 ( 2 ) 文【3 1 】证明当m = 2 ，3 时，工s 算法为最优算法，当m 4 时问题的下界至少为； 4 ) qm i n o 札一2 钆凹s m 99 0 b l c k 。问题，文【3 1 给出竞争比为m 的最优算法 b z a s g r e e d y 对该半在线模型的研究的一个突破是得到了一些问题的最佳随机算法f 5 ，4 9 ， 5 1 ( 在线问题p 2 i | c k 。与p 2 | l c k 。的最佳随机算法已经得到【1 , 8 】有些随机算法 8上海大学博士研究生论文 在算法的进行过程中只需作一次随机选择，因而几乎是不随机的 6 】文 5 2 】证明 对p m n o n 一。n c r e a s z n gj o b ，p m p t c 。问题存在竞争比为学的确定性算法， 并且任何确定性或随机算法的竞争比都不会优于它 5 工件分两批到达的半在线模型( t w o - b a t c h ) 该模型由 6 6 首先提出假设工件分两批到达，同一批工件的全部信息在 工件到达时全部给出，排序者可以根据整批工件的信息来优化排序不妨假设， j = j 1u 如，j 1nj 2 = 0 ，工件集以( 如) 到达后，j 1 ( 以) 中所有工件的全部信息 同时释放给排序者，若1 i = n l ，i 以l = n 2 ，则将其记作p ( n ，n z ) 显然有n l 2 ， n 2 1 且扎l + 7 1 , 2 m + 1 文【6 6 】证明对p m l t w o b a t c h c k 。问题不存在竞争比 小于 的近似算法上述结论即使对p ( n 1 ，1 ) 和p ( k ，n 2 ) ，2 sm 仍成立在 同一篇文献中，作者给出g l p t w 算法并证明此算法解p r o l t w o b a t c h c k 。的 竞争比为2 一鬲与，当m = 3 时算法是最佳的，特别地对p ( n 1 ，1 ) ，算法g l p t w 的竞争比为；且为最优算法 6 已知实例最优解的半在线模型( k n o w no p t i m u m ) 假设实例的最优解值c o p t ( 当然不是最优解本身) 可在零时刻( 此时工件尚 未到达) 为排序者所知该模型有比较强的应用背景，可应用于文件分配问题中 4 假设我们需将m 台原始服务器( 容量已知) 上的全部文件逐个传送到另m 台 新服务器上，由于算法不知道文件在原始服务器上的存储方式，新服务器可能需 要更大的容量使得所有文件都能不被分割地放置在其上我们的目标是使得新服 务器的容量尽可能地小由于我们要求上述过程对所有能在原始服务器上放置的 文件均能做到，原服务器的容量即为最优解值，两种服务器容量之比即为算法的 竞争比对于此模型有如下的结果， 对p m l k n o w no p t z m u m c k 。问题，文 4 证明存在竞争比为警的近似算法 进一步对固定的m 3 存在竞争比为i 5 鬲r n 玎- - 1 的近似算法对m 2 上述问题的下 界至少为j 4 2 0 0 5 年上海大学博士学位论文 9 对p m l k n o w no p t z m u m c k 。问题，文【3 给出近似算法f d l ，并证明此算法 的竞争比为2 一去，当m = 2 ，3 时算法是最佳的对m 4 ，上述问题的下界至少 为； 对q m l k n o w no p t z m u m i c k 。问题，文 3 】给出近似算法s l o w f a s t ，并证明 此算法的竞争比为m ，且对任意m ，算法均为最佳的 对q m i 扎d n z n c r e a s z n g3 0 b & k n o w no p t z m u m1 m 问题，文 3 】给出 n e x t c o v e r 算法，并证明此算法的竞争比至多为2 7 带缓冲区的半在线模型( b u f f e r ) 假设在机器系统之外还存在着一个长度为k 的缓冲区( b u f f e r ) 工件到达时 可以立即安排在某台机器上加工，也可以将其暂时安置在缓冲区中当缓冲区中 已存放的工件数为k 时，新到达的工件若需暂时安置在缓冲区中，则缓冲区中某 一工件必须取出并立即在某台机器上加工该模型由k e u e r e r ，k o t o v ，s p e r a n z a 和 t u z a 3 7 以及张国川【6 6 分别研究 文f 37 】给出算法研并证明此算法是求解p 2 1 b u f f e r i c k 。问题的最优算法， 其竞争比为 一个有趣的事实是缓冲区的长度不影响算法的竞争比，只要有长度为1 的缓 冲区就够 8 已知工件加工时间序的半在线模型( o r d m a l ) 该模型可能是最早研究的半在线平行机排序问题 4 5 】该模型的基本假设可 归纳为以下两条( 1 ) 已知每个工件加工时间的相对大小，但其确切值未知，即 若 ，p 。，p 。) 为对所有工件加工时间重排组成的有序集，满足p ，仇。 p 。对任意1 ，礼，p ，在有序集中的位置均为已知，但p j 的精确数值未 知，( 2 ) 在零时刻排序者需对所有工件作出安排，且不能随加工进程而改变 由于o r d m a l 模型中，工件完工前其确切加工时间未知，它也是n o d c l a t m v o y a n t , 排序f 4 7 1 的一种比之更为严格的是，o r d m a l 排序要求在零时刻安排好所有工 1 0上海大学博士研究生论文 件，因此不能使用经典的l p t ，l s 算法求解l m ，s i d n e y 和v a n y a h e t l 4 5 给出了 求解p m o r d z n a l i c m 。的算法p m ，并证明此算法竞争比为1 + ；筹备当m = 2 ，3 时算法是最佳的文 4 5 还证明了当m = 4 时问题的下界为籍，并给出了竞争 比为等的算法p ( 4 ) 文 4 5 的作者还给出了p m l o r d m a l i c m 。问题的下界，当 m 1 8 时下界至少为g 文【6 0 】研究了带机器准备时间的同型机o r d i n a l 半在线排序问题p ) r 。i o r d m a l i c k 。该文证明了对c 景。将所有工件安排在准备时间最短的机器上加工即为最 优算法，其竞争比为m 该文还考虑了一种特殊情况假设机器 一l + l ，尬。 有相同的准备时间该文证明了此问题的下界至少为m a x 2 ，早 ，求解该问题的算 法为m 尸，它用求解p m l o r d m a l c k 。的算法p m 规则，将所有工件分给机器 一l + 1 ， 加工该算法的竞争比为 当l 为奇数时 当f 为偶数时 对g 盟。问题，算法o m 当m = 2 ，3 ，4 时是最佳的，竞争比分别为 ，警，；当 m 5 时，算法的竞争比为2 一杀i 而问题的下界至少为； 文【3 0 】研究了极大化机器最小负载目标函数下同型机o r d m a l 半在线排序问题 p m l o r & n a l l c m 。文章证明了问题的下界为，并给出了竞争比为 + 1 的 算法m i n 对m = 3 ，该文献给出了竞争比为2 的最优算法对q 2 l o r d m a l i c m 。 ，文【5 8 给出了问题的参数下界和近似算法o r d i n a l ，并证明了s 【1 ，5 等盟 u 【1 半，2 t _ 【1 土笋，产 u 【l + 、5 ，o 。) 时算法是最佳的，算法的竞争比与问题下界 不相等的s 的区间总长度小于07 7 8 4 ，当s = 箜苎1 1 堡2 1 丑= 11 4 1 3 时，两者之差达 到最大值00 5 2 0 o r d i n a l 模型不仅出现在排序问题中，在组合优化的其他领域中如拟阵3 9 ， 装箱 4 3 】和装填 4 4 】问题等也大量存在 o r d i n a l 算法的一个重要特点在于它得 到的解在保序变换下有某种不变性【4 8 o r d i n a l 模型独特性的另一个体现是关于 m a k e s p a n 的两种不同目标下问题的下界和算法的竞争比都有显著区别 莘兰。叫叫 2 0 0 5 年上海大学博士学位论文 9 半在线模型的复合 称s l & s 2 为半在线模型s 1 和s 2 的复合，若该模型同时满足半在线假设s 1 和s 2 ，这里s 1 ，s 2 是任两个半在线模型 文【3 4 选择六个第一类半在线模型 k n o w nn u m b e r ，k n o w ns u m ，k n o w n l a r g e s t j o b ，k n o w ns m a l l e s ty o b ，n o n i n c r e a s i n g3 0 b 和帆一d e c r e a s i n g3 0 b ， 将它们两两复合，研究p 2 1 s l & s 2 c m 。的下界和近似算法主要结果如下表所示 火 k n o w uk n o w i lk n o w n k n o w i ln o n n o i l s m a l l e