（运筹学与控制论专业论文）机器带准备时间的两台同类机半在线排序.pdf

濒江大学硕士拳臻论文 摘要 本文研究了机器带准备时间两台同类机半在线排序问题及其近似算法 全文共分三章。第一露篱要介缓了藉 亭闻运静背景、蓉本穰念、半奁线簿 序问题、机器带准备时间的排序问题第二章讨论了机器带准备时间的两螽同 类执已知工件总麴正时问半在线排序问题，目标函数为极小化最大机器完工时 州和极小化最大工 牛完工时间，给出了此间题的返似算法，证明了其竞争魄走 2 ，并证明了不存在竞争比小于( 1 + 3 ) 2 的近似算法籀三章讨论了机器带 准餐时阗鹃嚣台爨类辊已躲工舞载大鸯羹工嚣雩霹半在绫蓑 摩翊题，强标函数麓援 小化最大机器完工时间和极小化最大工件究工时间，给出了此问题的近似算法， 一 证明了其竞争比为兰，并证明了不存在竞争比小于2 的近似算法可以看出 z 对予已露王件蓉霸王对窝帮已知工传最大翔工时闻酌两台黼类枫半在线撵序| 、嗣 题，机器带准备时间与否不改变其宽争比 关键词：排序；同类机：半在线算法；机器准备时间；竞争比 浙江大学硕士学位论竞 a b s t r a c t i nt h i st h e s i s ，t w os e m io n l i n e s c h e d u l i n gp r o b l e m s o nt w ou n i f o r m m a c h i n e sw i t hn o n s i 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 sa r ec o n s i d e r e d 。 t h et h e s i si so r g a n i z e da sf o l l o w s c h a p t e r 1 g i v e s ab r i e fi n t r o d u c t i o no ft h ep a r a l l e lm a c h i n es c h e d u l i n g p r o b l e m s ，i n c l u d i n gb a s i ck n o w l e d g ea b o u ts c h e d u l i n g ，s e m io n - l i n es c h e d u l i n g ， s c h e d u l i n gp r o b l e m sw i t hn o n s i 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 a n dt h e s c h e d u l i n gp r o b l e m so nt w ou n i f o r mm a c h i n e s c h a p t e r 2d e a l sw i t ht h ef i r s ts e m i o n l i n e s c h e d u l i n gp r o b l e m s o nt w ou n i f o r m p a r a l l e l m a c h i n e sw i t h n o n - s i 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 ，w h e r et h et o t a lp r o c e s s i n gt i m ei s k n o w ni na d v a n c e t om i n i m i z e 血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 o m i n i m i z et h em a x i m u mj o bc o m p l e t i o nt i m e w eg i v ea p p r o x i m a t i o na l g o r i t h m s w i t hac o m p e t i t i v er a t i oo f4 2 ，w h i l et h e r ei sn oa p p r o x i m a t i o na l g o r i t h mw i t ha c o m p e t i t i v er a t i oo f s m a l l e rt h a n 娃+ 3 ) 2 。c h a p t e r3d e a l sw i t ht h es e c o n ds e m i o n - l i n e s c h e d u l i n gp r o b l e m so nt w ou n i f o r mm a c h i n e sw i t hn o n - s i m u l t a n e o u s m a c h i n ea v a i l a b l et i m e s ，w h e r et h el a r g e s tp r o c e s s i n gt i m ei sk n o w ni na d v a n c e ，t o m 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 i n i m i z et h em a x i m u m j o bc o m p l e t i o nt i m e 。w eg i v ea p p r o x i m a t i o na l g o r i t h m sw i t hac o m p e t i t i v er a t i oo f 3 2 ，w h i l et h e r ei sn oa p p r o x i m a t i o na l g o r i t h mw i t ha c o m p e t i t i v er a t i oo fs m a l l e r t h a n4 2 i tc a nb ec o n c l u d e dt h a ta b o u tt w os e m io n l i n es c h e d u l i n gp r o b l e m so n t w ou n i f o r mm a c h i n e sw h e r et h et o t a lp r o c e s s i n gt i m ei sk n o w na n dt h el a r g e s t p r o c e s s i n gt i m ei s k n o w ni na d v a n c e ，r e s p e c t i v e l y , i ti sn o te f f e c to nt h e i r c o m p e t i t i v er a t i ow h e t h e rn o n - s i m u l t a n e o u sm a c h i n ea v a i l 西l et i m e se x i s to rn o t 。 k e y w o r d ss c h e d u l i n gp r o b l e m ：u n i f o r mm a c h i n e s ；s e m io n l i n ea l g o r i t h m ； n o n s i 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 ：c o m p e t i t i v er a t i o 斯江大学磺士学位论文 第一章引言 1 1 排序阂遂概述 捧窿问瑟的毽论与应奔l 研究爨二十鳘笼六十年 弋兴怒龌来，经过四十多年 的发展，已经藏蕊组合忧纯鹱域戆重溪缝成都分。撼序阚题被广泛应曩到网络 透信、蠡动纯生产调度_ 靼浆滚管理等多令方覆，弓| 起运筹学雾、计爨枫科学界、 工程学爨和铃理学界的极大关注在实践中，商实际背景的瓤问题瑶出不穷， 使瓣序阉题极具生命力和研究价值， 蓑 黟，又穆调度，实矮是把爨要加工瓣工 牛，安排农绘定豹机器上加工， 使绘定的旦标达到最优。对于接序阉题模型的描述，通常采用三参数方法 搿l 声l y 【g l l r 7 9 】，其中搿，p ，y 分别表示特定的机器状况，工件特征和目 标函数下预，我们分别对三个参数作简单介绍 机器状况描述了机器数量、类激以及与机器相关的各种信息平行机 ( p a r a l l e lm a c h i n e ) 是其中最重要的机器类型之一，用m = t m l ，m 2 ，j 】i f 。) 表 示机器集，其中埘2 ，每个工件只需在其中一台机器上加工一次即可完成常 见的平行机类型有： 同挺( i d e n t i c a l ) 平行机，即所有机器的加工速度一样，通常用p 表示，着 写成p m ，则表示系统中共有晰台同型平行视； 同类( u n i f o r m ) 平行梳，鄯梳器有各鸯不黼的速度，僵经意工件在不围税 器上的船工辩闻有相嗣酶毙铡关系，逶常奔l 坌表示； 不阂类( u n r e l a t e d ) 豹平行裰，帮辊嚣豹热工逮菠不同，豆王件在不露极 器上匏鸯工器重阕毙倒不宠全糨羁，遥零用灾表示。 工件特，蠖，一般是撑工件绩患是在线还是离线。根据安搀工 牛对掌握工l 牛 绩息豹多少w 把搀序嬲题分为离线( o f f i i n e ) 和在线( o n l i n e ) 两类在离线闽题中， 浙江大学硕士学位论文 全部工件的所有信息在排序时均已知，排序者可以利用工件信息对工件进行安 排而对在线问题，当前工件的信息，只有将之前到达的所有工件安排好后， 才能得知，即后续工件的情况是未知的，而且一旦对工件做出安排，就不能更 改工件集通常用j = j i ，j z ，以) 表示，本文中假设工件相互独立，工件j ，的 加工时间为n ，在文中也用p ，指代工件所有工件均可在零时刻开始加工， 且只需在其中一台机器上不间断地加工一次 目标函数，即最优准则用c ，表示在某种满足要求的排序下工件p ，的完 工时间，用c 。= m a x c j 表示该排序的最大完工时间( m a k e s p a n ) 因此目标 j 为极小化最大完工时间就是要找到一个可行排序，使c 腑、在所有可行排序中尽 可能地小 2 浙江大学硕士学位论文 1 2 算法与竞争比 所谓排序问题的算法( a l g o r i t h m ) 是指一个预先制定的执行程序，对这个 排序问题的任何一个具体的例子( 简称为实例，i n s t a n c e ) ，按照这个程序操作 后都可以得到一个可行的排序 设有一个在线算法一，称 c = i n f c 1 i c “( ，) c c o r 7 ( nv 1 ) 为算法4 求解该问题的竞争比( c o m p e t i t i v er a t i o ) 这里c 。( ，) 和c ”( ) 分别 表示算法a 所得的目标函数值和实例，的最优离线目标函数值，在不引起混淆 时简记作c 。和c ”7 ，取遍该问题的所有实例称c 为一个在线问题的下界， 如果对该问题不存在竞争比小于c 的在线算法若算法a 的竞争比等于问题的 下界，则称a 为最好( b e s tp o s s i b l e ，o p t i m a l ) 算法 同型机在线排序问题中的经典算法是g r a h a m 在六十年代提出的求解 砌1 | c 眦。在线问题的l s ( l i s ts c h e d u l i n g ) 算法 g r a b 6 6 l s 算法是按照工 件到达的顺序，把工件安排在当前负载最小的机器上加工g r a h a m 证明了l s 算 法的竞争比为2 1 m l s 算法提出二十余年后，在1 9 8 9 年，f a i g l ee t a l i f k t 8 9 】 证明了当m = 2 , 3 时三s 算法是最好在线算法近几年来，对m 4 的情况，出现 了许多比l s 更好的在线算法，【b f k v 9 5 】、【k p t 9 6 】、 a l b e 9 7 分别给出了竞 争比为1 9 8 6 、m 8 时1 9 4 5 、1 9 2 3 的算法，而目前最好的在线算法是2 0 0 0 年 f l e i s c h e r 和w a h l 【f w 0 0 】提出的m r 算法，当m 斗时，竞争比趋近于 14 - ( 1 4 - i n 2 ) 2 1 9 2 0 1 另一方面，对在线问题下界的寻找也取得了很大进展， r u d i n 年t l c h a n d r a s e k a r a n 【r c 0 3 】于2 0 0 3 年提出= 4 时的下界为3 “1 7 3 2 ， f a i g l ee ta 1 f k t 8 9 1 提出m 4 时问题下界为1 7 0 7 ，b a r t a le ta 1 【b k r 9 4 】给 出m 3 4 5 4 时下界为1 8 3 7 ，到1 9 9 7 年a l b e r s 【a l b e 9 7 】给出当m 是4 0 的倍数的 时候下界为1 8 5 2 ，在此基础上，2 0 0 0 年g o r m l e ye ta 1 g r t w 0 0 用穷举法 浙江大学硕士学饺论文 在诗算援上褥爨下器至少为1 8 5 3 5 8 。最i 笈r u d i n r u d i 0 1 】在毽戆簿士论文中 证明了不存在竞争比好于1 8 8 的在线算法 瓣q 2 镕c 二。在线闷题瓣研究，_ = 卡年采己毒了较多懿结果，c h o 翥s a h n i 证明了三s 算法的竞争比c “= ( 1 + 5 ) 2 c s 8 0 ；e p s t e i n e t ，a l 。进一步证盟了s 算法的参数竞争比为 1 + 4 5 s _ s 堡2 查。 虽对任何s ，l s 算法皆是最好算法 e n s s w 0 1 】，这里5 为两台机器的速壤比。 4 筹孚 浙江大学硕士学位论文 1 3 半在线排序问题 离线问题和在线问题从排序者对工件信息的了解程度来看，属于两个极端 情况但在实际的生产、管理中问题中，这两种情掘并不是经常出现，情况往 往介于两者之间一方耐事先不可能知道工件的所有信息，另一方面根据实际 清凝，遭常可以掌握工件熬部分信憨，虽不怒缀充分，毽晓经冀的在线模登骞 更多可利用的信息，从而w 能得到比在线算法近似性能更好的算法我们把这 耱难发分子在线器离线之瓣熬蓑 彦润蘧稼受立| 蠡在线搀澎瓣蘧，求解半在线瓣蘧 的算法称为半夜线算法 耄予半在线接序蠲题程事先也不掌握工终麴全部痿感，嚣虽王孛一旦被安 排就不允许改变。所以是一种特殊的在线问题我们仍用讨论在线问题的下羿， 和在线算法竞争跳豹方法采衡量半焱线算法的近议程度自从1 9 9 6 年半在线平 行机排序问题的提出 l s v 9 6 1 ，由于实际中大量此类问题的不断涌现，半程线 问题的研究已经取得长足的进展，大量的模型和优秀的簿法不断被提出，半在 线问题已经成为排序闻题的一个富裔生命力静新分支 下面就简要介绍与本文讨论问题有关的半在线模型和相关结果，并且通过 和裙斑在线阉熬结栗的眈较，可爨发凌它稻麓缀大的挺麓在线闻憨算法静淫黯， 是有价值的 1 工件馨加工时闭= p i 已知半在线模型( s 狮磅 扛l k e l l e r e re t a t 【8 t 9 7 】给出了p 2 | s u m | 气豹最好算法，竞争比为4 3 ； h ee t a 1 h y t y 0 2 】给出了砌| s u m f 的宽争比为2 - 1 ( m - 1 ) 的半在线算 法对q 2 ；5 材瑙 气；，t a n 和h e t h 0 1 】绘爨了竞争魄为2 麴s u m 算法，潮 时证明了问题的下界为( 1 + 3 ) ，2 2 工黪最大熬互瓣霆p 。；2 鬻登乃鼹鲤拳在绞模型捌瑚。 h e 和z h a n g 【h z 9 9 】给出了p 2 i m a x l ：的竞争比为4 3 的最优算法 p l s 谈之突和何鹦 t h o i 】给出了0 2 f m a xi g 。的竞争眈为3 2 i 獬m l s ， 嗣辩证弱了趣邃静下界为压 6 浙江大学硕士擎戡论文 1 4 机器带准各时间的排序问题 在经媳排序中，我们总假设机器在零时刻可以开始加工，但在现实生产环 境中雾 期藏，铡懿掇嚣程开工 ；蓼震强硬耱性维护，在藏期阕不辘秀嚣工王俘， 这段时间就是机器准备时间又比如生产调度是分阶段进行的，上一阶段已分 配虢工 孛在瓶除段开始对秘未热王完残，在不允许踅薪分鬻的倍凝下，每台税 器上前一阶段最后个工件的完工时间可蓉成下一阶段的机器准备时间显然 上述问题怒经典排序问题的一个捺广，若簿台机器的准备时间均为零，朝为经 典搀序问题。 需要特别指出的是，在机器有准备时间的情况下，最大完工时间有两种含 义：一秘怒最嚣一个完王王 孛戆完工薅阂，麓豫为最大王l 孛完工瓣阕；曼一耱 是最后一台完工机器的完工时间，简称为艘大机器完工时间，两种含义都有其 实际背景仍激薪蠢静钢予寒诺骥，第一耱逶矮予梳器鬻骰预耱性维爹靛情 形，此时可能有一些机器，它们所需要的维护时间特别长，甚至在其它机器已 完成所有的工件翩工任务后，它们还不能开始加工篓子加工任务已经完成， 我 l 、1 不再对这些机器作开工前的准餐丽认为已“完工”，在其它机器上加工的最 后个完工工件的完工时间即为该排序的究工时间第二种含义邋用于分阶段 生产调度捺影。囊予兹一除段已分配豹工l 譬也是整个热工任务的一部分，姥对 可能有一魑机器在其它机器己完成本阶段的加工任务时，尚未完成前一阶段的 热王我们黉要等待这些秘器完王筹才靛谈秀萁“完工”，溺戴瑟焱磊一台完工 机器的完工时间作为排序的完工时间根据这两种不同的含义，可定义排序问 题的两个不同的极小纯目标函数勇外，德可暖祀这两种鳍标看作是由予顾客 和生产者的不同要求丽产生的。像为顾客总希望彝己的那批工件尽早完工，而 生产者更多考虑尽快完成所有需加工的工件，包括前一阶段的顾客交付的工件 在本露中，我销嗣e 。( 乃表示最大工件完工辩闻，g 。( 掰) 交示最大糗襄 完工时间，用c 。，。泛指遂两个目标上述排序阅题用三参数袭示法可记作 浙江大学硕士学位论文 p ，；| | 。 机器带准备时间的排序问题是l e e 【l e e 9 6 首先提出的，在 l h t 0 0 中， l e ee ta 1 指出了在p ，i l i c 眦。中，c 。( ，) 和c 。( m ) 是两个不同的目标，而在 p i ic 唧中它们是完全相同的 在 t h 0 2 中，谈之奕和何勇证明了三s 算法仍是求解p 2 ，| l c o 的竞争 比为3 2 的最好算法，并给出了半在线问题p 2 ，i s u m i c 一和p 2 ，l m a x i c 腽。 竞争比均为4 3 的最好算法 浙江大学硕士学位论文 1 5 论文内容介绍 举义看重饼冗机器雨准备时 司两台同类机两种半程线模型的近似算法和问 题下界设机器集搀 m ；，m ：) ，其中机器呜的准备时间为0 ，速度为已， ，= l ，2 ；不妨设岛= 1 ，屯= s 1 ，工件集j = “，五l ，以 ；工件t 的加工时间 为只，i = l ，2 ，l ，托：为方便起见用砖指代，记p ( 屿) 为( 当前) 在机器m ，上 加工工件的总加工时间，称r j + p ( m i ) 。仉。，。m f ( 当前) 的负载，配为，( 肘，) 本 0 文, 3 论酶两种半在线模黧分弱为 ( 1 ) 工件的想加工时闽r = z p ；已知； ( 2 ) 工件最大加工时间p 。；= m 。a x 。p ，己知 f 嚣虢葶l 璞说明，在谨鞠翼法豹竞争院辩，不薪骰设萁孛一台辊箍黪准备 时r , j0 ，即只需考虑以下两种情形 m l 存狻餐薅润：_ = r 0 ，吃= 0 ； m 2 有准备时间：1 = 0 ，吃= ，0 。 l | 瑾1 。 ( 1 ) 麓算法_ 辩获毒滚是t = 0 豹实铡( j ，m ) 骞 端c ，则对所有满足- 实例c m ，有善：台c ； ( 2 ) 若算法4 对所有满足r l = 0 的实例( 九m ) 有黜c ， 则对所有满足 1 时，因为t + r = t + s ，敬t s ，可褥t ( m 1 ) = ， l ( m ：) = 二 1 i ，由引理2 2 ，该情形只能出现在下述时刻：在加工某工件p 前 t ( m ，) 届，易知诧时算法得到的怒最优 鳃若在p 至g 达对，已有工件在m ：上加工，记这些工件构成集会暑，则我们断 言，占= p 。 且p 。为大工件事实上，在肘2 上加工的工件只能为大工件，否则 将该工件交穗m ；麓工，蝎的受载纛不会超过压( 滏寿 l s ( 互一1 ) + 0 + 1 ) ( 互一1 ) = j ) ，由算法的定义知，该童件将出m ；加工因 此有且只有一个大工件在m 2 上n i 这样我们有 c = m i n l o ( m ，) + 热( p 。p ) a ， 游汪大学颈士掌位论文 这里f 0 ( m 1 ) 为工件p 到达时m ，的负载 下面我们考虑此情形下最优解的结构，从而得出矛鹰若在最优解中，p o 霸p 在同一台枫器上加工，则c ( p 。+ p ) 知c o e 7 ，即棼法得到最优解。蕊 在最税簿孛，蕊巍p 在不同的秘爨上热工，辩e 泖- m i n p 。，p ；。懑予 ，o ( m 1 ) + p + p o t + ，= 1 + s 故 l o ( m 1 ) 十p l + s 一( j 1 ) 0 + 1 ) = ( 2 一j ) ( s + 1 ) = 掘五一驰+ 1 ) 压m i n p ，p 。 厨一， 铎c “、s 五c ，这与c 8 l | c o * 矗秀露 算法的竞争比不会小于2 ，也就是说竞争比是紧的，这可由下例得到令 s = 压，r = 1 4 ，p t 。压一1 4 ，p 2 = 1 4 ，p ，：3 4 易知c 。压，c o , v ：t 诞 挚。 定理2 ，毒冀法圈求解窖2 ，1 s , t m i 气。豹竞争耽为压 证明：当r 1 时，f ( m ，) ：r ，( m 。) ：一t 1 _ i 因此我们需对s u m 作适溺修改得虱s u m l 算法s u m l 0 。f = 1 。 t 。拳将工件只放在吖：上加工，使m ：的总负载仍不大予2 ，则将工件n 放在吖：上加工，否则将n 放在能使其最快完工的机器上加工 2 若此时f ( m ) 1 - s ( j 一1 ) ，压】，将剩余的工件均交由m ：加工，停止； 若此时z ( m ：) e 【1 一( 互一1 ) 厶，习，将剩余的工件均交由膨，加工，停止； 若a 放在能使其最快完工的机器上加工仍使得该机器负载大于2 ，则 将剩余的工件放在另台机器上加工，停止 3 若i s ，将全都工件安拱# 在埘，上热工，搏止； 2 。 m i n s ，( 三一1 ) ( 五一1 ) ( 5 + 1 ) r s ，按算法s u m l 加工工件： 濒江大学硕士学位论天 3 若，sm i n s ，( 压1 ) ( 玉一1 ) 秘+ 1 ) ，按冀法s u m 热工工传。 浪意到仅当( 压叫( 厄啪+ 1 ) s 霹，i ( m ，) = t 1 ，t ( m ：) = 二，因拢g = c 。7 = t ，靼冀法 得到的是最优解 当，- 2 类似于定理2 3 的证明，该情形只能出现 在下述时刻：在加工大工 牛p - 巅f f t ( m ；) - m i n 上兰，p ，困越 c 2 型2 ( 、- 2 - 1 ) ( 4 2 s - 1 ) ( s + 1 ) + p l + s 一蠢 l o ( m 1 ) + 芦c 村2 ， 矛盾若程最优簿中+ 帮p 在不溺静辊器上麓工，粼c ” m i n p 。，p ， 6 l o ( m ，) + p l + s 一( 4 7 一1 ) 擘+ 1 ) 一蘧压l 淞+ 1 ) - x 2 m i n p ，p 。 函”， 即c ”2 尻m r ，矛盾 当m i n s ，( 4 7 1 ) ( 2 s 一1 ) 0 + 1 ) ( j 1 ) 抽+ 1 ) l + s 一4 2 s ，故p 2 ，否刚将p 安排在m 。上加工，t ( m ，) 满飚弓l 理2 2 ( i ) ， c “e ”2 ，矛矮。由予c ”= m i n p ，i ( m 2 ) + s z ( 掰2 ) + p s ， c 。7 m i n p ，( ，十p ) j ( r + p ) s ，若诞得1 + s 一4 7 秀+ ( 至一1 ) p ，贝u 有 c l 竺壁：! 坠坦 = 2 j 三 ( 正一1 ) ( 届一1 ) + 1 ) ，只嚣证 l + s 一应扭压一1 ) ( 厄一1 ) ( j + 1 ) + ( 压一1 ) 压， s f ( 2 4 7 2 ) s 2 + 0 4 7 5 ) s + ( i 1 ) 0 令 ，( s ) = ( 2 4 5 2 ) s2 + ( 3 压一5 ) s + ( 砸一1 ) ， 由二次函数性质，( s ) 当s = ( 2 4 7 0 4 1 时取得最小值，且有 ，( 1 ) = 6 , 5 8 0 ，露_ l 毙， o 辩s l 成立。 算法努是紧的，这可幽下例褥刘。令s = 云，= 1 2 ，p ；= 1 ，p ：= 扼1 易 知c “= 压，c = 1 证毕 定理2 ，6 算法t 2 求解簖，龟 s “珥l ；( 掰) 瓣竞争院为在 证蹦：当， s 封，t ( m 1 ) = t l 三，i ( m 2 ，= 三，戮戴e ”：c ”7 。t ， od 算法得到的仍是最优解当r s 时，c 卯7 1 仍成立，与定理2 。5 类似的证明 可得结论证毕 1 7 浙江大学硕士学位论文 第三章已知工件最大加工时闯半在线排痔闯题 3 。1 弓| 言 本章研究已知工件最大加工时间半在线排序问题，记p 为第一个加工时 黼为p 玎扭，豹工件对与之穗关的四个排序阉题，荔知下面的定理成立 定理3 1 ( t h 0 1 】) 对机器带准备时间的两台闻类机已知工件最大加工时 阀半在线撵海阏题，不存在最环情况赛小予0 2 静：j 疆秘算法 证明：令l = 吃= o ，s = 2 ，p 。= i ，p l = i ，糟算法爿将p 1 分给m i 加工， 鬟不再来其他工件，淑有c 。= 1 雨c 一= 在意，c 一c 一：应若髯法a 将 p 1 分给膨2 加工，则令p 2 = 2 - i 若算法a 将p 2 分绘鸩加工，则不褥来其他 工件，c 。= l 丽c ”= , 5 2 ，同样有c 4 c ”= 压；若算法a 将扔分绘蝎加 工，令p 3 = l ，见不论在哪螽机器上加工均鸯g 4 = 2 丽c ”7 = 1 ，即 c 。| c ”= 厄诖枣 在算法 正明过程中，我们将部分采用三s 规则作为子过稷，我们肖下面的 结论 引理3 2 对q 2 ，i lc 。，肖c “c 。e 7 0 + 1 ) s 。 证明：著膨有准锯对阈，则s 算法褥弼的解不会比将所肖工件全部安排在 m = 上加工所得排序熨箍因此对c 二，( 肼) 目标，若r t s ，则c ”= c ”；r ， 若r t s ，c 5 t l s ，c 卯( f + ，) 饪s + 1 ) ，c 。c n 9 7 ( 苫+ i ) s 对c 嘲。( j ) 隧标，若r t s ，贝uc 3 = c o p 7 = t s ，若， t s ，贝c “t s ， c 。产7 ( t + ，) 酗+ i ) ，不论哪种情形，均有c ”，c ”7 0 + 1 ) s 若m ，肖准备时间，贝4 三s 算法得到的解不会比将所有完工时间大于r s 的 工件全部移猁m 2 上加工所得排序更差戮此对c 。( 膨) 目标，c 8 p 十t ) l s ； 浙江大学硕士学位论又 若r s t ，则c o p 7 = r s ，若r s t ，则c ”7 ( t + r ) ( s + 1 ) ，不论哪种情 形，均有c “c ”7 0 + 1 ) s 对c 。，( ，) 目标，若r s t ，则c ”= c o ”= t ， 若r s t ，则c ” ( t + r ) l s ，c ”7 ( t + r ) ( s + 1 ) ，不论哪种情形，均有 c 站c 。阿o + 1 ) s 证毕 引理3 3 ( t h 0 1 】) 若某算法a 自某步起，采用l s 规则，且目标函数值 由按l s 规则安排的工件决定，则c 。( r + t + p 。) 0 + 1 ) 证明：若i ( m 1 ) i ( m 2 ) ，考虑在m 。上加工的最后一个工件p ，p 分给m i 加工而未给m ：加工，由l s 算法规则知t ( m 。) t ( m ：) + p 扣，即 t ( m i ) 一，( m 2 ) p s p 。s ；i ( m 1 ) + s i ( m 2 ) = t + r ，故 i ( m 1 ) p + 丁+ p 。) 0 + 1 ) 若l ( m 1 ) 2 或卷s 2 k r p 。，攘嬲算法热羔工蛰。 2 若j 2 且r 2 畦，鑫l 辱| 理3 2 知c “3 ，c ”f s + 1 ) i s 3 2 ：当s 2 且 ，p 瑚；时， 丁+ ，2 p 嘲。， 由弓l 理3 3 ， c 3 ( ，+ r + p 一) 0 + 1 ) ，而 c 脚7 ( r + r ) ( s + 1 ) ，故c 岸3 ，c 洲( r + r + p 嗍) ( r + d 3 2 。当s 9 2 且 r p 。时，视村；上的难豁对问为虚拟工件热，将q 2 ，tl 崩裂l g 。( 膨) 任一 实例( j ，m ) 看作q 2j 删1 。的实例( ，m 。) ，其中j = ，u ，m = m 由 予p 。= ，2 p 一s ，m l s 冀法求熊两实馕所褥捧寄裙弱，舔 c ( ，m ) c ”( 了，凹) ，故 璺：! z ：丝! j 3 ， 鄹蠢淼 主瑚f 五3 sr ，阳 2 2 s 一+ 。2 r 2 r s 2 。矛瓣 若尹k 不是最后一个工件，幽萼l 理3 ，3 懿证明过程可知，c n 4 _ i 3 测有等 吾一等，即n 孚毕， p 。 阮一矛盾 2 浙江走学硕士学位论文 3 3 q 2 ，如| m a x l ( ；。 f ) 耱9 2 ，r 2l m a x | c 。( ，) 本节研究m 。榭准备时间的两台同类机半在线排序问题，同样预先已知工 件的最大加工时问 此时我们仍用冀法嚣3 求解该阔鼷，惶定理3 4 的证明不舞适碍，以下我 们绘出薪夔 垂鞠 定理3 6 算法粥求解q 2 ，吃i 掰鼎f 。( m ) 的竞争比为3 1 2 证明：当s 2 时或s s 2 9 _ r p 。时，易知c “c ”3 2 成立，以下考 虑s 2 a r 3 2 ，骧p + 尧赛将燕工分梵游爱两个除段( p + 聪惹浚段) ，l o ( 甄) 为p 到达时m 。的负载，显然f 。( m ，) 墨2 p 。s 若算法的目标函数值由第一阶 段的安排决定，则c ”= r s 或c ”= l o ( 肘) 若为前者，辨法得到的是最优解； 麓隽腻因为c 。p r 峄，出筹 吾删裔 孕，s lo zz s ls 矛盾以下只考虑算法目标函数值由聪一阶段，即以三s 法则安排的工件所决 定的情况若p + 不为p o 。，则出l o ( m ，) 十p 2 p , m x p 。，知t f 。( m 1 ) + p + + p 一 2 或。，由号 遴3 3 可得e 8 3 ，g 挪7 3 1 2 ，矛詹。以下缎设p + 即为p 。0 ， 分谣； 孛清流讨论 情形1 p 。o 。农m 2 上加工 此时有z 。( m 。) + 。 三鳖，若c “3 兰三监，则糟在最优解中，p 。 程捣秘工，算法德舅熬簿鸯最臻簿：羞不然，裂广。尹一，霰没 c n 3 c o e r 3 2 ，妣+ 3 2 sc o v r i 3 s ，又有岛。) + 。 警， 故r + ，f 0 ( m ) + p 。+ r 妄。+ 去 2 ，矛盾 浙江大学硕士学位论文 若c ” ! 等k ，将峨上在p ：后加工的工件全部移到m 上加工，所 得排序不会比算法h 3 给出的排序好，因此有c ”3 t p 由c ”7 三等， s + 1 c c 矿h 3 孤三等棚r 去z 褂藕 情形2 p o 在m 1d h i 由三s 规则，有( m ，) + p 。 三，贝, l j t o ( m ，) + 。 吾p 一， 即z 。( m ) 丢p 一，又，+ p 。 s ( 1 0 ( m 。) + p 。) 婺p 。，故 丁+ r l o ( m 1 ) + p 一+ ， j 1p 。+ 了3 s p 。 2 ， 矛盾 若c ” z 。( m ，) 一p 一，将m 上在p 后加工的工件全部移到m ：上加工， 所得排序不会比算法h 3 给出的排序好，因此有c 一，三兰二里坠由 c t 刚+ r ，若万c h 3 吾，则等粤 吾鬲t + r o t + r 2 2 ( s 一+ 。1 ) p 一 2 。，矛盾证毕 定理3 7 算法h 3 求解q 2 ，匕im a x lc 啪。( ，) 的竞争比为3 2 证明：当s 2 时或s 2 且，p 。时，易知c ”c o t 7 3 1 2 n 揽- j ，当s 2 r r s p 。时，若p 。在m 2 上加工，c ”p + p 。) i s ；若p 。在m l 上加工， c ”7 p 。r s ，因此定理3 6 证明中关于c ”7 的估计仍成立证毕 浙江大学硕士学位论文 参考文献 a l b e 9 7i s a l b e r s ：b e t t e rb o u n d sf o ro n l i n es c h e d u l i n g np r o c e e d i n g so f t h e2 9 “ a n n u a l a c m s y m p o s i u mo nt h e o r yo f c o m p u t i n g , 1 3 0 1 3 9 ，1 9 9 7 【a e 9 7 ya z a r , l e p s t e i n ：o n l i n em a c h i n ec o v e r i n g a l g o r i t h m s - e s a 97 l e c t u r en o t e si nc o m p u t e rs c i e n c e s1 2 8 4 ，2 3 - 3 6 ，s p r i n g e r - v e r l a g ，1 9 9 7 b f k v 9 5 】yb a r t a l ，a f i a t ，h ，k a r l o f f , r v o h r a ：n e wa l g o r i t h m sf o ra na n c i e n t s c h e d u l i n g p r o b l e m j o u r n a l o f c o m p u t e r a n d s y s t e m s c i e n c e s , 5 1 ，3 5 9 - 3 6 6 ，1 9 9 5