（运筹学与控制论专业论文）具有非交叉维修时间的平行机在线排序.pdf

摘要 本文主要研究的是具有非交叉维修时间的平行机在线排序问题。在排序问 题中，平行机排序是其中最活跃的分支之一无论是对离线的还是在线的，数 十年来人们进行了大量的研究关于平行机排序问题的文献大都是假设所有 机器自始至终都是可使用的，然而这种假设在实践中可能不现实在生产过程 中，由于对机器的预防性维修或机器突然出现故障都会导致机器在某一段时间 内不能使用，有时候我们也把机器不能使用的这一段时间叫做这台机器的禁用 区间，所以我们有必要把这些因素考虑到排序问题中去，再做出合理的决策 非交叉维修时间指的是对于m 台平行机( p a r a l l e li d e n t i c a lm a c h i n e s ) 的集合 m = 必ii = 1 ，2 ，m ) 来说，每一台机器m 上有一个维修时间段k ，玩) ，且 0 a i b i ，i = 1 ，2 ，m ，并且这m 个维修时间段满足或者完全重合或者完全 分离，也就是说；或者满足a i = a ，b i = b ，a ，b 是常数，i = 1 ，2 ，m ；或者满足 a m 晚，i = 1 ，2 ，m 一1 在本文的讨论中，对于前者我们还假定b a p 一， 对于后者我们假定a m 一玩p m a x ，i = 1 ，2 ，m 一1 ，其中p m a , , 是工件集中工件 的最大加工时间前者所述我们用d 1 = “吼，玩) f0 a i 良，a i = a ，b i = b ，b a p m 。，i = 1 ，2 ，m 来表示，后者所述用d 2 = b ，) 10 a i b i ，n 州一b i p 。，i = 1 ，2 ，m 一1 ) 来表示 所谓在线指的是工件集是按照某个顺序到达的，是什么顺序我们事先不知 道，工件的所有性质在它到来之前是未知的，工件在到来之前不能被安排加 工只有当工件以一。已经被安排好之后工件易才到达，否则，工件易不出现， 并且工件 一出现就要立即被安排到某台机器上加工，一旦被安排就不能再 改变 在这种类型的排序问题中，又可分为两种情形来考虑：一种是中断后可继 续加工的情形，比如说在某个时刻某台机器上有某个工件正在加工还没有完 工，而这台机器在这个时刻需要进行维修，那么在这一时刻可以中断正在加工 的这个工件，等到这台机器维修完之后，再接着加工被中断的工件剩余的部 分一种是中断后不可继续加工的情形，也就是说；对于上面的情形而言，被 中断的工件在机器维修完之后必须被重新开始加工，相当于前面被加工的部 分作废这两种情形在排序模型中我们分别用符号 - 8 , ( r e s u m a b l ea v a i l a b i l i t y ) 和 l l - a ( n o n r e s u m a b l ea v a i l a b i l i t y ) 来表示，这是借文献【1 】的用法 在上述情况下，我们的任务是找一个把所有工件安排到机器集上之后使得 我们所要的某个目标函数值达到尽可能优的方案，用排序论的语言来说也就是 找一个尽可能好的算法 在这篇文章里，我们主要对m = 2 和3 的情形进行了讨论，我们研究的问 题的模型用三参数可表示为 p 2 j o n l i n e - l i s t ；r - a ；d i g p 2 i o n l i n e - l i s t ；n r - a ；d 1i p 2 1 0 n l i n e - l i s t ；i l r - a ；0 2 1 g m p 3 j o n l i n e - l i s t ；n r - a ；o l t g ，w 本文的主要结果是对问题p 2j o n 1 i n e - l i s t ；r - a ；d 1 i 瓯。，找到了一个竞争比是2 的最好的算法并给出了证明对问题p 2j o n 1 i n e - l i s t ；1 1 1 - 8 , ；d 1 i g 。，我们将证明此 排序问题的任意在线算法的下界不小于2 7 9 ，并给出一个竞争比不大于2 8 的 在线算法对问题p 2 1 0 n l i n e - l i s t ；j r - a ；晚f g ，我们将证明此排序问题的任意在 线算法的下界不小于1 9 9 ，并证明了l s 算法的竞争比不大于2 对于m = 3 的 情形，即对问题p 3 1 0 n l i n e - l i s t ；n r o a ；d 1 i a 一，我们将证明此排序问题的任意在线 算法的下界不小于3 一e ，并给了一个竞争比不大于警的在线算法 关键词平行机排序；非交叉维修时间；可中断排序；在线算法；l s 算 法；竞争比 2 a b s t r a c t h lt h i sp a p e r w ec o n s i d e rt h eo n - h u es c h e d u l i n gp r o b l e mw i t hn o n - o v e r l a p p i n gm a i n - t e n a n c et i m eo np a r a l l e lm a c h i n e s i ns c h e d u h n gt h e o r y , t h ep a r a l l e lm a c h i n e ss c h e d u l i n g i so n eo ft h em o s ta c t i v eb r a n c h e s ，n om a t t e rw h e t h e ro f f - l i n eo ro n - l i n ei sc o n c e r n e d ， p e o p l eh a v eb e e nr e s e a r c h i n gf o rd e c a d e s m o s th t e r a t u r ei np a r a l l e lm a c h i n e ss c h e d u l i n g a s s u m e st h a tm a c h i n e sa r ea v a i l a b l es i m u l t a n e o u s l ya ta l lt i m e s h o w e v e rt h i sa v a i l a b i l i t y m a yn o tb et r u ei np r a c t i c e i nt h er e a lw o r l d ，m a c h i n e sm a yn o tb ea v a i l a b l ea ts o m e t i m ed u et op r e v e n t i v em a i n t e n a n c eo rs u d d e nb r e a k d o w n ，w h i c hs o m e t i m e si sc a l l e dt h e m a c h i n ea v a i l a b i l i t yc o n s t r a i n t s s ow eh a v en e c e s s i t yt oc o n s i d e ri ss i t u a t i o ni ns c h e d u h n g p r o b l e m sa n dm a k ear e a s o n a b l ed e c i s i o n t h en o n - o v e r l a p p i n gm a i n t e n a n c et i m em e a n st h a te v e r ym a c h i n e 坛h a sam a i n t e - n a n e et i m ei n t e r v a l 【a i ，玩) ，w i t h0 a i 玩，i = 1 ，2 ，m ，a n d i nt h es e tmo f m p a r a l l e l m a c h i n e s ，t h e s emm a i n t e n a n c et i m ei n t e r v a l se i t h e rc o i n s i d eo rs e p a r a t ec o m p l e t e l y , i e a = a ，b i = b ，a a n db a r ec o n s t a n t ，f o r i = 1 ，2 ，m o r 啦+ 12b t ，f o r i = 1 ，2 ，m 一1 i n t h i s p a p e r ，w e a s s u m e t h a tb - a p m 缸f o r t h e f o r m e r a n d a i + 1 一玩p m 娃，i = 1 ，2 ，m 一 1f o rt h el a t t e r ，w h e r e 鳓“i st h el o n g e s tp r o c e s s i n gt i m ei nt h ej o bs e t i na b o v et w o c a s e s ， w ed e n o t eb yd 1 = 【啦，玩) l 0 啦 2 a 由题设条件可知ts2 c 2 a ，矛盾。) 断言2 ：在工件集中，至少有一个大工件这由问题的约束条件b a p m a x 可知 根据断言1 可设确定c a 。的工件为五，下面介绍两个记号：用厶表示由算 法a - 得到的排序中被安排在机器蚴上加工的所有工件( 除而外) 构成的集 合，岛表示工件集厶中所有工件的加工时间之和，i = 1 ，2 根据断言2 可知，在工件集中，至少有一个大工件如果工件集至少包含 两个大工件的话，那么工件集l 。与。中至少有一个集合包含大工件，因此z 。 与e 。中至少有一个大于或等于b a 下面我们证明当工件集中只包含一个大 工件时，上面的结论仍然成立 在工件集中，如果只有一个大工件，那么工件而必不是大工件。若不然，假 设而是大工件，由断言1 可知，山是在b 之后完工的唯一工件如果它是在算 法中第一个遇到的在b 之后完工的工件，则按照规则2 ，它应该是第一个安排在 尬上加工的又因为它是在b 之后完工的，故其工时9 0 a ，从而c + p o o ， 与假设矛盾如果矗不是第一个在b 之后完工的，则与断言1 矛盾因此工件 集l z 与l 2 中必有一个包含这个大工件，也就是说t 与如中至少有一个是大 于或等于b a 的 1 4 设这个大工件为以，并设c 4 - = n + p o + b a 如果j k l 。，那么由算法可知 工件而是按l s 算法被安排到机器m 上加工的，因此有岛。2b 一口又因 为c 蚍2 ，所以有 万cal1291+丽2po+2(b-a)c2 + 鬻p o _ 1 6 5 5 + 1 7 2 。6 = 1 8 2 7 6 ，而在最优序中很显然五可以在机器尬上a 之前完 工，江1 72 ，因而有c k 6 5 5 于是我们有譬百1 8 2 7 6 2 7 9 如果算法a 把以放在机器尬上n 之前加工，接着就来第二个工件如 = 1 7 2 6 ) 如果算法a 把如安排在机器集上b 之后加工，接着来第三个也 是最后一个工件以慨一6 5 5 ) 从而有c a 1 6 5 5 + 1 7 2 6 = 1 8 2 7 6 和c = 6 5 5 所 1 5 以有百c a 百1 8 2 7 6 2 7 9 如果把如放在机器尬上之前加工，接着来第三个工 件j 3 慨= 6 5 5 ) 如果算法a 把以放在b 之后加工，就不再来工件了我们 有c a 1 6 5 5 + 6 5 5 = 2 3 1 0 ，c + = 6 5 5 ，所以百c a 面2 3 1 0 2 7 9 如果算法a 把以放 在机器上a 之前加工，接着来第四个也是最后一个工件五溆= 6 5 5 ) 则 j ：l 不能在机器坛上a 之前完工，i = 1 ，2 此时我们有c a _ 1 6 5 5 + 6 5 5 = 2 3 1 0 ， c = 6 5 5 + 1 7 2 6 = 8 2 7 6 ，所以有百c a 丽2 3 1 0 2 7 9 如果算法a 把如放在a 之前尬上加工，接着来第三个也是最后一个工 件以p 3 = 8 2 7 5 ) 则以不能在机器舰上a 之前完工，i = 1 ，2 因此我们有 c a _ 1 6 5 5 + 8 2 7 5 = 2 4 8 2 5 ，c = 8 2 7 5 ，所以百c a 甏鬻2 7 9 综上所述，对任意在线算法a ，总有雾2 7 9 口 此定理证明了竞争比的下界下面将提供一个竞争比十分接近此下界的在 线算法 算法a 2 ： 当a = 0 时，将工件按l s 规则安排在机器集上加工 当a 0 时，下面分两种情形分别设计算法 1 当口 6 2 a 时算法a 2 如下t 让厶和丘分别表示在由算法a 2 得到的排序中安排在机器舰上的在a 之 前完工的所有工件的集合和b 之后完工的所有工件的集合岛和分别表示 厶和丘中所有工件的加工时间之和，i = 1 ，2 s t e p0 令l i = o ，l i = o 贝4 岛= o ，= o s t e p1 对于当前工件如，如果e l + p j _ a ，则令l i ：= l , u j j ，9 1 ：= 1 + 功，返回 s t e p l s t e p2 如果z 2 + 奶墨o ，则令l 2 ：= l 2 u 乃) ，如：= 2 + 功，返回s t e p l s t e p3 将工件以按l s 规则安排在机器集上b 之后加工，返回s t e p l 2 当警 6 2 0 时，算法a 2 如下； 厶，l ：，玫，的定义同上 】6 s t e p0 令l i = d ，l ：= o 贝0 段= o ，4 = 0 s t e p1 对于当前工件以，此时不妨设砭，如果塑丢挚警，则令工i ：= l iu j a ，：= 巧+ 岛，返回s t e p l s t e p2 如果型b ：- + a 聊，- - t 1 4 ，则令l ：= l ：u j a ，岛：= 岛+ 办，返回s t e p l s t e p3 如果1 十功o ，则令l 1 ：= 工1 u j j ，口1 ：= 1 + p j ，返回s t e p l s t e p4 如果e 2 + p j 0 时，分三种情形证明 情形1 ：当a a 所以t = 1 + 如+ 鼽+ p j 2 a 从另一方面我们知道，t 2 c + 2 a 矛盾) 】7 因此c a 2 = b + p o 又因为 c 吾：垒掣， 所以 丝 垫塾 c 一z 1 + 如+ p o 。 要证明 一c a 2 a ，z 1 + p o a ，如+ p o a 2 p o + 7 9 x + 7 9 2 5 b 2 ( b n ) + 7 a 一5 b = 5 a 一3 6 如果p o o ，因此有 2 p o + 7 f 1 + 7 9 2 5 b 5 a 一3 b 0 因此，当n 1 譬，故 6 + + 伽 警( 尘型生鸣塑刿) 1 + 如+ 巧+ 吒+ 加+ 2 ( b a ) 得a b ，与已知条件b a 矛盾所以有欲证的结果 情形2 ：当b 2 a 时，有a 盟半s ，并且由算法可知下面的几个不等式成立 f 1 + 如 a ，如+ p o a ，1 + 如 a 下面证明譬警为了方便，先给出几个记号和术语，然后逐个证明一系列论 断。用印表示在j 0 之前到达的被安排在机器舰上加工的所有工件的集合， 毋表示霹。中所有工件的加工时间之和，i = 1 ，2 由假设和算法可知 印+ 学 a ，霉+ 舶 a ，理o + 伽 a 1 9 大工件：加工时间大于或等于b a 的工件称作大工件 小工件：加工时间小于或等于丝e 的工件称作小工件。 中等工件：其余的工件称作中等工件 断言1 ：工件集砰u 霹中没有小工件 证明：如果有一个小工件，根据算法这个小工件应该被安排在b 之后加 工，这与我们的情形在b 之后完工的工件只有一个j o 且册 生产矛盾。 断言2 ：在而之后到达的工件中，不可能再有大工件 证明：若不然，假设有一个大工件j ： ，则a 6 一o 誓，又因为 口。 印+ 毋+ 伽 等 因此得 t 譬+ 毋- f p o + a 2 a 这与t 一 o ) ，故仍与上述大工件安排在同一台 机器上 断言6 ：在情形3 1 下，有b s 睾 事实上由断言5 可知 b 一口+ 9 b - i 一1 4 as 。， 得 b 了1 2 a 有了这些准备之后，现在来证明在情形3 1 下有譬警因为6 半，所以有 c a 2 ：b + 伽s7 1 2 a + 伽 而由断言4 和6 警可知 c + 伽+ 旦生亏j 竺p o + a 百， 所以 竺 酉2 0 2 r a ，于是有 苦i 1 4 c 一5 下面证明当p o b 一。，因此有告警如果c 也= b + + p o 且 坚挚s 警，同理可得皆警最后，如果兰笔挚 警，由算法可知下面的不等式 都是成立的 t l + p o n ，如+ 舶 口 p b ，如 9 b - r 1 4 a 由 及 c a 。：6 + 巧+ 娜n + 尸m 。+ + 期l + 如+ + 磊+ c + 吾 得 c a 2 譬，即t 。一f 墅4 一弘一；如) p o ；n 十；+ ；砭 亍n 十i 孽1 + j 掣2 锄+ 1 4 一1 0 b + 4 + ，4 幻萼。+ 亍8 + ；+ 1 4 a - - 1 0 6 + 4 + 1 4 2 2 ；半n + 雩+ 等幻半。一，o 。+ 7 ，1 ( 9 b - 。1 4 a i 半。州。+ 等( 半) = 丁2 8 9 b - 4 2 4 a o 即 4 _ 舶+ 1 4 n 一1 0 6 + 4 + 1 4 0 下面用反证法证明喾警若不然，假设c 如 警矿，即 6 + + 舻1 。4 ( 坠生竽) ， 整理得 4 加+ 1 4 a l o b + 4 i + 1 4 吒 o ) 证明：考虑下面的实例ta = 1 0 0 ，b = 1 6 0 如果算法a 把第一个工件 ( p ，= 2 0 + e ) 安排在机器集上在b 之后加工，接着到达第二个也是最后一个工件 如渤= 6 0 ) 因此由算法得到的目标函数值c 1 6 0 + 2 0 + e = 1 8 0 + e ，显然c k6 0 ， 所以有譬警3 一e 如果算法a 把 安排在机器尬上a 之前加工，接着来第二个工件也 ( p 2 = 2 0 + e ) ，如果算法a 把以安排在机器集上b 之后加工，第三个也是最后一 2 3 个工件也慨= 6 0 ) 到达，从而有c a 1 6 0 + 2 0 + e = 1 8 0 + e 和c = 6 0 ，所以有 万c a 1 8 丽0 + 一3 一e 如果把五安排在机器尬上a 之前加工，接着来第三个工件以慨= 2 0 + e ) ，如 果算法把五安排在机器集上b 之后加工，不再来工件，此时有c a _ 1 6 0 + 6 0 = 2 2 0 ， c k 6 0 ，所以有譬面2 2 0 之3 一e 如果算法把以安排在机器上n 之前加工，接 着来第四个工件j ! l 慨= 6 0 ) 如果算法把 安排在机器集上b 之后加工，不再 来工件，此时有c _ 1 6 0 + 6 0 = 2 2 0 ，c + = 6 0 ，所以有喾箬3 一如果把把j ：l 安 排在机器尬上n 之前加工，接着来第五个也是最后一个工件以( 船= 8 0 ) ，则以 不能在机器集尬上n 之前完工，i = 1 ，2 ，3 于是有d 4 1 6 0 + 8 0 = 2 4 0 ，c k8 0 + e ， 所以有萨c a 丽2 4 0 3 一e 如果算法把无安排在机器尬上a 之前加工，接着来第三个工件以慨= 8 0 ) ， 如果算法把以安排在机器集上b 之后加工，不再来工件，因此有1 6 0 + 8 0 = 2 4 0 ， c k 8 0 + e ，所以有万c a 一 。2 4 0 。一 一q 一如果把把以安排在机器尬上d 之前力n - r ， 接着来第四个工件五轨= 8 0 ) ，则 不能在机器集脱上a 之前完工，i = 1 ，2 ，3 于是有c a 1 6 0 + 8 0 = 2 4 0 ，c = 8 0 ，所以有万c a 喾3 一e 综上，对于任意一个在线算法4 ，总有雾3 一e 口 其次，我们给出一个在线算法 算法a 3 如下： 让厶和丘分别表示在机器尬上a 之前完工的和b 之后完工的工件的集 合以和分别表示厶和丘中所有工件的加工时间之和i = 1 ，2 ，3 s t e p0 令厶= o ，= 彩贝4 岛= o ，= o ，i = 1 ，2 ，3 s t e p1 对于当前工件乃，如果z l 把，则令l 1 ：= l t u j a ，1 ：= 1 + 奶，返回 s t e p l s t e p2 如果红慨口，则令l 2 ：= 三2 u 乃) ，岛：= 如+ 功，返回s t e p l s t e p3 如果3 + 功o ，则令l 3 ：= 厶u j j ，如：= 如+ 功，返回s t e p l s t e p4 将工件五按l s 规则安排，返回s t e p l 2 4 定理7 ： 对于问题p 3 1 0 n l i n e - l i s t ；盯- 8 ；d 1 i g 。，上面的算法a 3 使得譬警 其中c a s 和c + 分别是由算法a s 所产生的序的目标函数值和相应问题离线时 的最优的目标函数值 证明：下面分两种情形证明： 情形1 ：当n = 0 时，根据算法所有的工件都将在b 之后按l s 规则加工， 因此有 asb + lc + b + 妻， 所以有 霎币b+t 0 时，下面又分三种子情形证明： 子情形1 ：假设确定最终完工时间c a 。的工件在a 之前完工，则c a 。s t ， c + 吾所以喾3 子情形2 ：假设确定c a a 的工件在b 之后完工而确定的工件在a 之前完 工 断言：在由算法a s 产生的序中，在b 之后完工的工件至多有两个( 否则 假设有三个p i ，p c ，p k 根据算法可知：f 1 + p i a ，如+ 功 口，3 + p k a ，从而 t = g l + 如+ e s + a + 胁+ p k 3 a 3 c * ，从另一方面我们知道t 3 c + ，矛盾。) 如果在b 之后完工的工件只有一个，比如说而，则c a a = b + p o 当p o = 时，有 c a 3 = b + p o d + p m a x + p o = n + 如+ p o = 妄( 3 n + 6 p 0 ) ；( 1 + 2 + 如+ 如+ 如+ 1 + 2 p 0 ) + i m 】4 o o ；婴+孥6c-+竺：丝(t3c+，poc)3333 。 3 一 、。一 一。7 当p 0 3 c ，又因为b c + ，从而t + 磊+ 6 3 c + 从另一方面我们知道t 3 c ，矛 盾 综上所证，有害s 警， 口 下面的例子说明了在线算法a s 的竞争比等这个界是紧的n = 4 - - e ，b = 7 - e ， v e 0 p 1 = 1 ) ，也( 轧= 1 ) ，而慨= 2 ) ，五( p 4 = 2 ) ，五( 船= 3 ) ，容易看出由在线 算法得到的目标函数值c a = 1 0 一而最优的目标函数值c + = 3 ，因此当e 一0 时，有喾一百1 0 第三章具有分离维修时间的平行机在线排序问题 3 1模型介绍 t a n 和h e 在文献 6 】中对模型为p 2 o n 1 i n e - l i s t ；l l r - g t ； 。的排序问题进行了 研究即具有维修时间的两台平行机的在线排序问题，目标函数值是c i 。在 此模型中，假定【a i ，b i ) ( 0 a i 坟) ，i = 1 ，2 是机器尬上的维修时间段，并且这 两台机器的维修时间段不重叠，即b 。n 2 文中首先证明了l s 算法的竞争比 是3 并且是紧的，但不是最好的在线算法其次，设计出一个竞争比为2 5 的 在线算法c l s ，并且证明了这个在线算法是最好的在此基础上本文把上述模 型的条件b 。a 2 改成了a 2 一b t2p 。a x ，并证明了l s 算法是近似最好的在线算 法 3 2不可中断的两台平行机在线排序 这一节本文对维修时间段完全分离且分离区间的长度不小于工件的最大加 工时间的情形下两台平行机在线排序问题进行了研究这个问题的三参数模型 是p 2 o n j n e - s t ；a r - a ；d 2 c 一, ，其中d 2 = b ，坟) 10 啦 b i ，a i + l 一阮p m a x ，i = 1 ，2 定理8 ：对于问题p 2 o n 1 i n e - l i s t ；n r - a ；d 2 i g 。的任意一个在线算法4 ，有 喾1 9 9 证明：考虑下面的实例，n 1 = 1 ，b 1 = 2 ，a 2 = 1 0 0 2 ，5 2 = 1 0 0 3 ，首先到达第一 个工件 p 1 = 2 0 0 1 ) 如果算法把j l 放在尬上b 。之后加工，就不来工件了此时c a 4 0 0 1 ，而 c = 2 0 0 1 所以万c a 丽4 0 0 1 1 9 9 如果把j 1 放在m 2 上a 2 之前加工，接着来来第 二个工件也( p 2 = l o o o ) 则也不能在尬上a 2 之前完工如果把以放在尬上 b 2 之后a n - r _ ，就不来工件了则c a e 2 0 0 3 ，而c = 1 0 0 2 所以有害而2 0 0 i 3 1 9 9 如果把如放在m 上h 之后加工，接着来来第三个工件以( p 3 = 1 0 0 0 ) 如 果把以放在尬上6 2 之后加工，就不来工件了则c a 2 0 0 3 ，c + = 1 0 0 4 0 0 1 2 7 所以有万c a 而2 0 0 而3 1 9 9 如果把以放在尬上加工， 2 0 0 2 ，伊= 1 0 0 4 0 0 1 所以有万c a 揣1 9 9 综上，对于任一在线算法a ，有长1 9 9 也不来工件了此时c a 另一方面我们考虑l s 算法作为此问题的在线算法 口 定理9 ：对于问题p 2 o n - l i n e - l i s t ；n r - a ；d 2 i 。，l s 算法的竞争比不大于2 证明：用岛和分别表示机器舰上在啦之前和饥之后完工的所有工件 的加工时间之和，i = 1 ，2 显然驴；，其中t 是所有工件的加工时间之和。 在l s 序中，如果确定最终完工时间e 耶的工件能在n 。之前完工，则有c 埘t 所以c ，l s 一 2 如果确定d 埘的工件在啦之后完工，并且假定这个最后完工的工件在尬 上加工，则有c 船= b 1 + 由算法可知6 1 如，所以c 埘= b l + t 2 + t 因 此弓箬s2 如果这个工件在上加工，则有c 朋= 6 2 + 磊，又因为b ，+ 6 2 ，所 以g 。8 = b 2 + 岛6 1 + + 吒如+ + 吒t 因此有i c l r s 2 综上，结论得证。 口 后记 关于具有维修时间的平行机在线排序问题，本文只对两台和三台的两种特 殊情形进行了讨论。当机器上的维修时间段完全重合时，对于两台可中断的情 形找到了一个竞争比是2 的最佳在线算法；对于不可中断的情形找到了一个竞 争比非常接近其下界的在线算法对于三台可中断的情形本文没有讨论，而对 不可中断的情形找到了一个3 一e 的下界，并设计了一个在线算法，这个在线算 法的竞争比是等且是紧的，猜想此问题存在一个竞争比是3 的在线算法。当 所有机器上的维修时间段完全分离时，本文只考虑了两台不可中断的情形，证 明了l s 算法的竞争比不大于2 ，而对于三台的情形还没有考虑因此，这里 面还有很多工作有待以后去做 参考文献 【1 】c y l e e ，m a c h i n es c h e d u l i n gw i t ha na v a i l a b i l i t yc o n s t r a i n t ，j g l o b a lo p t i m i z a t i o n ，9 ( 1 9 9 6 ) 3 6 3 - 3 8 2 2 】r l g r a h a m ，b o u n d sf o rc e r t a i nm u l t i p r o c e s s i n ga n o m a l i e s ，b e l ls y s t e mt e c h ，4 5 ( 1 9 6 6 ) 1 5 6 3 - 1 5 8 7 【3 1u f a i g l e ，w k e r na n dg t n r ( m ，o nt h ep e r f o r m a n c eo fo n - l i n ea l g o r i t h mf o rp a r t i c u l a r p r o b l e m ，a c t ac y b e m e t i c a ，9 ( 1 9 8 9 ) 1 0 1 1 9 【4 】h c h w a n g ，s y c h a n g ，p a r a l l e lm a c h i n e ss c h e d u l i n gw i t hm a c h i n es h u t d o w n s ，c o r n - p u t m a t h a p p l ，3 6 ( 1 9 9 8 ) 2 1 3 1 【5 】h c h w a n g ，k l e e ，s y c h a n g ，t h ee f f e c to fm a c h i n ea v a i l a b i l i t yo nt h ew o r s t c a s e p e r f o r m a n c eo fl p t ，d i s c r e t ea p p l i e dm a t h e m a t i c s ，1 4 8 ( 2 0 0 5 ) 4 9 6 1 【6 】z y t a n ，y h e ，o p t i m a lo n l i n ea l g o r i t h mf o rs c h e d u l i n go nt w oi d e n t i c a lm a c h i n e sw i t h m a c h i n ea v a i l a b i l i t yc o n s t r a i n t s ，i n f o r m a t i o np r o c e s s i n gl e t t e r s ，8 3 ( 2 0 0 2 ) 3 2 3 - 3 2 9 闭y h e ，t h eo p t i m a lo 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 g ，c o m p u t e r sa n dm a t h e m a t i c sw i t h a p p l i c a t i o n s ，3 9 ( 2 0 0 0 ) 1 1 7 - 1 2 1 【8 】c y l e e ，t w om a c h i n ef l o w s h o ps c h e d u l i n gw i t ha v a i l a b i l i t yc o n s t r a i n t s ，e u r o p e a nj o p e r r e s 1 1 4 ( 1 9 9 9 ) 4 2 0 - 4 2 9 f 9 】c y l e e ，m i n i m i z i n gt h em a k e s p a ni nt h et w om a c h i n ef l o w s h o ps c h e d u l i n gp r o b l e mw i t h a na v a i l a b i l i t yc o n s t r a i n t ，o p e r r e s l e t t ，2 0 ( 1 9 9 7 ) 1 2 9 - 1 3 9 【l o e s a n l a v i l l e ，g s c h m i d t ，m a c h i n ee e h e d u l i n gw i t ha v a i l a b i l i t yc o n s t r a i n t s ，a c t ai n f o r m a t - i c a ，3 5 ( 1 9 9 8 ) 7 9 5 - 8 1 1 【1 1 】y a z a r ，l e p s t e i n ，o n - l i n es c h e d u l i n gw i t hp r e c e d e n c ec o n s t r a i n t s ，d i s c r e t ea p p l i e d m a t h e m a t i c s ，1 1 9 ( 2 0 0 2 ) 1 6 9 - 1 8 0 【1 2 】b 。c h e n ，x t d e n g ，w a z a n g ，o n - l i n es c h e d u l i n gab a t c hp r o c e s s i n gs y s t e mt om i n i m i z e t o t a lw e i g h t e dj o bc o m p l e t i o nt i m e ，j o u r n a lo f