（运筹学与控制论专业论文）具有特殊工件的平行机在线排序问题.pdf

摘要 本文研究一类具有特殊工件的平行机在线排序问题，目标是最小化最大 完工时间用g r a h a m 等人【1 2 】提出的三参数法，我们的问题可以表示为t p m l o n - l i n e 4 k ，t ；p e 出j 如蜮尬) i g 。其中m 表示特殊工件要在第一台机器上 加工当工件集中没有特殊工件时，问题就退化成了经典的平行机在线排序 p m l o n - l m e - l i s t l g w 所谓在线，本文指的是列表在线：工件被排成一个队列，然后逐个释放 一旦某个工件被释放，必须马上决定在哪台机器上加工它工件被释放之前， 我们不知道它的任何信息只有当前面个工件被安排之后，后个工件的信 息才知道一旦工件被安排到机器上，我们不允许再移动它到另一台机器上 在本文考虑的排序问题中，有两种类型的工件；正常工件和特殊工件正常 工件能够在平行机的任何一台机器上加工，而特殊工件仅仅能够在它被指定的 机器上加工，并且每个特殊工件的指定机器是唯一的在本文讨论的模型中， 所有的特殊工件都被指定到机器m 上去加工 在生产实践中，特殊工件是普遍存在的它们有一些特殊的性能使得它们 必须到指定的机器上去处理这样，就使得我们的生产安排变得复杂化 本文的主要结果如下： ( 1 ) 两台机器的情形：l ，2 o n 1 i n e - l i s t ；s p e c i a lj o b s ( m 1 ) l c m a x 证明了任意在线 算法的竞争比不小于5 3 ，并提供了一个最好可能的在线算法 ( 2 ) 三台机器的情形；p 3 o n f i n e - l i s t ；s p e c i a lj o b s ( m ) i 。证明了任意在线 算法的竞争比不小于1 6 8 6 ，并提供了一个竞争比不超过1 8 5 7 的在线算法 ( 3 ) 仇( m 4 ) 台机器的情形：p i n i o n - l i n e - l i s t ；s p e c i a lj o k ( 胍) i g 。此时的下 界至少是p m o n - l i n e 1 i s c , , l , 的下界，并提供了一个竞争比不超过丽2 t t t 2 丽- - 2 mi 的 在线算法 关键词：平行机排序；列表在线；特殊工件；近似算法；竞争比；下界； 上界 a b s t r a c t i nt h i sp a p e r w ei n v e s t i g a t ep a r a l l e lm a c h i n eo n - l i n e8 c h e d a t m gp r o b l e m 诵t hs p e c i a l j o b st om i n i m i z et h em a l 昭| p 蛐u m gt h e3 - f i e l dn o t a t i o no fg r a h a me ta 1 1 1 2 ，t h e p r o b l e mi sd e n o t e d 瞄p m l o n - l i n e j i s t ；, s p e c i a lj o b 6 【 f 1 ) l q ，w h e r em lr e p r e s e n t st h a t t h es p e c i 8 lj o b sm u s t _ b ea i g n e dt ot h e 矗r s tm a c h i n e w h e nt h ej o bl i s th e s s p e c i a l j o b s ，t h ep r o b l e md e g e n e r a t e s8 , st h ec l a s s i c a lp a r a l l e lm a h i n eo n j i n es c h e d u l i n gp r o b l e m p m i - j i n e _ i i s t f g 。 o n - l i n e i nt h i sp a p e rm e a d so n - l i n e - l i s t ：t h ej o bc o m e 8o v e rl i s ta n dw eg e tt h ej o b s o n eb yo n e o n c ea j o bi sr e l e a s e d ，w em u s ti m m e d i a t e l yd e c i d eo nw h i c hm a c h i n e t h ej o b i sp l 烈瑚8 e d t h ej o b sa 弛n o tk n o w nbp r i o r i ：j o b 五b e c o m e sk n o w no n l yw h e nj o b 与二l h a sa l r e a d yb e e ns c h e d u l e d o n c eaj o bi sa s s i g n e dt ot h em a c h i n e w e 啪n o ta l l o w e dt o m o v et h ej o bt oa n o t h e rm a c h i n e i nt h e8 c h e d u l i n gp r o b l e mu n d e rc o n s i d e r a t i o n ，w eh a v et w ok i n d so f j o b s ：n o r m a lj o b s a n ds p e c i a lj o b s t h en o m m lj o b 8c a nb ep r o c e s s e do na n yo n eo ft h ep a r e u e lm a c h i n e s ， w h i l et h es p e c i a lj o b sm u s tb ep r o c e s s e do nt h e i ro w ns p e c i f i e dm a c h i n e i nt h i sp a p e r ，a n t h es p e c i a lj o b si ne a c hi n s t a n c ea r es p e c i f i e dt oh ep r o c e s s e d0 1 1m a c h i n em 1 i np r o d u c t i o np r a c t i c e ，s p e c i a lj o b sw i d e l ye x i s t t h e yh a v es o m es p e c i a lp r o p e r i e s t h a tt h e ym u s tb ep r o c e s s e do nt h e i ro w ns p e c i f i e dm a c h i n e s i nt h e s ec a 滞t h e d s t a l l c e o fs p e c i a lj o b sw i l lm a k et h ep r o b l e mb e c o m i n gm u c hm o r ec o m p l e x t h em a i nr e s u l t so ft h i sp a p e r & r e 鹪f o l l o w s ： ( 1 ) t h ec a 辩o ft w om a c h i n e s ：p 2 1 0 n - n e - i i s t ；s p 鲥a lj o k ( 帆) i g w w e s h o wt h a t t h e r ei sn oo n - l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i ol e s st h a ns 3 ，a n dp r e s e n tab e s t p o s s i b l eo n - l i n ea l g o r i t h m ( 2 ) t h ec a s eo ft h r e em a c h i n e s ：p 3 o n - i n e - l i s 亡；删j o 蜮m 1 ) 1 x w es h o wt h a t t h e r ei sn oo n - l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i ol e s st h a n1 6 8 6 ，a n dp r e s e n ta no n - l i n e a l g o r i t h mw h i c hh a st h ec o m p e t i t i v er a t i oo fa tm o s t1 8 5 7 ( 3 ) t h ec a s eo fm ( m 4 ) m a c h i n e s ：p i n i o n - l i n e - l i s t ；s p e c i a lj o 蜮m 1 ) i t h e l o w e rb o u n di nt h i sc s s ei sa tl e a s tt h el o w e rb o u n do fp m i o 小j i n e - l i s 亡l c l i _ ，a n dp r e s e n t 8 , 1 1o n - l i n ea l g o r i t h mw h i c hh a st h ec o m p e t i t i v er a t i oo fa tm o s t 絮2 丽_ i k e yw o r d s ：p a r a l l e lm a c l l i n e8 c h e d u l j n g ；o n - l i n e - l i s t ；s p e c i 且lj o b b ；a p p r o x i m a t i o n a l 蓉o r i t h m ；c o m p e t i t i v er a t i o ；l o 嗽b o u n d ；u p p e rb o u n d m 第一章绪言 1 1排序的介绍 所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排 次序，使某一个或某一些目标达到最优它是一类重要的组合最优化问题，是 运筹学研究的一个非常活跃的分支在排序论中，工件是被加工的对象，是要 执行的任务；机器是提供加工的对象，是完成任务所需要的资源这样我们就 可以把形形色色的实际问题纳入一种简明的模型之中 排序论作为一门重要的应用学科，有着深刻的背景和广阔的应用前景随 着机器制造业的迅速发展，人们也越来越意识到排序问题研究的重要性1 9 5 4 年，j o h n s o n 【l s 完成了论文。o p t i m a lt w o - a n dt h r e e - s t a g ep r o d u c t i o ns c h e d u l e sw i t h s e t u pt i m e si n c l u d e d 。人们普遍认为这是第一篇关于排序问题研究的论文从 这篇论文问世以来的半个多世纪中，全世界已经发表排序文献3 0 0 0 多篇，其 中包括排序专著和教材5 0 余种今天，排序论不仅仅应用予机器制造业，它 更广泛应用于管理科学、计算机科学和工程技术等领域而在这些领域取得的 丰硕成果使排序论成为发展迅速，研究活跃，成果丰硕，前景诱人的学科领域 之一 在唐国春，张峰等人2 0 0 3 年的鬣现代排序论一书中，他们把排序理论分 为经典排序( c l a s s i c a ls c h e d u l i n g ) 和现代排序( m o d e ms c h e d u l i n g ) b r a c k e t 和k n u s t 在。c o m p l e x i t yr e s u l t so fs c h l u l i n gp r o b l e m s ”( 参见h t t p ：w w w m a t h e m a t i k u n i - o s n a b m e c k d e r e s e a r c h o r c l 啷) 中使用c l a s s i c a l 和e x t e n d e d 两个词来区别经典排 序和非经典的( 推广的) 两类排序问题他们也用n e wc l a t e 8o f s c h e d u l i n gp r o b l e m s ( 新型排序) 来表示非经典的排序问题因此，现代排序就是非经典的，新型的 排序相对于经典排序而言，其最大特点就是突破了经典排序的基本假设在 最近的二十多年间，现代排序模型不断涌现最常见的1 0 余种现代排序模型 有；可控排序、成组分批排序，在线排序，同时加工排序，准时排序和窗时排 序，机器不同时开工排序，资源受限排序、随机排序、模糊排序，多目标排序 等( 参见文献【1 7 1 ) 给定个组合最优化问题，如果我们能够找到它的一个多项式时间算法， 我们称它为p 同题，这是我们往往追求的目标但不幸的是，对于大多数问题 而言，我们并不知道它是否存在一个多项式时间算法然而，我们知道有这样 一类问题，一旦其中的一个问题能够在多项式时间内解决，那么所有其它的问 题皆可以在多项式时间内解决，我们称之为n p - 难问题排序同题作为组合 优化问题的重要分支，其中的大多数都属于p - 难问题因此最优解往往很 难在多项式时间内找到在实际应用中我们往往没有必要去寻求最优解，而是 找出满足一定条件的近似解就够了于是，设计这类问题的近似算法就显得尤 为重要 目前，在排序研究中，我们通常用最坏执行比来评定个近似算法的优良 设p 是一个带有非负权的优化问题，常数k 1 若存在个多项式时间算法 a ，对户的任何实例，皆有 o p t ( i ) a c t ) s 的p t o ) 成立，则我们称a 是优 化问题p 的一个缸因子近似算法，也称算法a 具有执行比k 其中，o p t ( ) 是实例，的最优值，a ( ，) 是算法a 产生的近似解的目标函数值 1 2在线排序、平行机排序和特殊工件 本节我们将重点介绍在线排序，平行机排序和特殊工件等三个最重要的概 念，这也是本文排序问题的三个主要特征 在介绍在线排序的定义之前，我们首先看一下离线的定义离线排序指的 是工件在被安排之前，它的所有信息，如到达时间、加工时间、工期、截止期 限，身份特征( 是否特殊工件) 等等，都已经知道了经典排序都属于离线排 序然而，在现实生活中，许多情况并非如此，这就为我们开辟了现代排序的 一个新领域，在线排序所谓在线，就是工件的信息是逐个释放的，在决定当 前工件的加工时对其后面工件的信息是一无所知的，并且一旦决定了工件的安 排就不允许再改变 2 根据工件的到来方式，在线排序又可分为两种：( 1 ) 列表( o v e rl 哦) 在线排 序t 工件被排成个队列，然后逐个释放一个工件只有当队列中排在其前面的 工件都安排好后( 安排在哪台机器和哪个时间段) 才知道这个工件的信息；( 2 ) 时间( o v e rt i m e ) 在线排序t 每个工件均有一个到达时间( 事先也是未知的) ，随 着时间的增长过程机器安排工件加工在任何时刻只知道当前已到达工件的信 息在线排序又可分为可预测的和不可预测的模型在不可预测的情形下，工 件的加工要求只有加工完后才知道组合起来，目前常被人们研究的在线排序 共有四种，列表可预测在线排序，列表不可预测在线排序，时间可预测在线排 序、时闻不可预测在线排序特别指出t 本文的在线属于第一种 因为在线排序中工件到来之前它的所有信息都是未知的，所以直观上来理 解在线排序要比相应的离线排序难针对一个在线排序问题，我们设计出一个 在线算法那么如何衡量一个在线算法的好坏呢? 通常我们用的指标是竞争 比对一个使目标函数达到最小的在线排序问题来说，竞争比p 定义为此问题 所有实例的比值善粤的上确界，其中c o n 和a o p t 分别代表在线排序算法得到 的目标函数值和相应的离线情形下的最优值我们用构造尽可能坏的实例( 找 对手) 的方法寻找在线排序问题的下界如果一个在线排序算法的竞争比p 恰 与该问题的下界相吻合( 相等) ，我们就说该算法是最具竞争性的这是我们追 求的最高境界 在线排序的研究具有相当重要的现实意义很多源于生产组织、网络通讯、 理论计算机科学的排序模型都具有在线的特征例如在集成电路的生产过程 中，如果要检测的集成电路是随时到达的此时决策者就得决定：当前要检测 的集成电路中，哪些要立刻放入烤箱中开始烘烤，哪些留待以后再检测如何 决策将直接影响生产的效率研究在线排序，设计出高效能的在线算法，会对 许多生产活动起到重要的指导作用 下面我们来介绍平行机排序平行机排序是多处理机排序问题的一种情 况平行机排序问题的研究在理论上和应用上都有重要的意义在理论上，平 行机排序是单机排序同题的推广；在应用上，平行机排序则具有更广泛的实际背 景在平行机排序问题中，通常有n 个工件 ，以，厶，m 台机器尬， 3 平行机器可分为三类：具有相同加工速度的恒同( 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 ) 机本文中m 台平行机属于恒同机 最后，我们给出特殊工件的概念这是原晋江教授提出的个新的名词， 在以前的文献中未曾见到过，也是本论文有新意的地方原老师最先提出的是 一类具有更广泛含义的霸王工件顾名思义，这类工件具有非常霸道的一面， 般具有如下三个特点( 1 ) 在单机排序中，此类工件一到来，其它工件必须 停止加工，为其让位；( 2 ) 在平行分批排序中，此类工件不跟别的工件放在一 批，要求独自成批；( 3 ) 在平行机排序中，此类工件要求必须到指定机器上去 加工本论文选取了第三个特点来研究，并为其取一新名。特殊工件于是，在 本文考虑的排序问题中，我们有两种类型的工件t 特殊工件和正常工件特殊 工件仅仅能够在它被指定的机器上加工，并且每个工件的指定机器是唯一的 正常工件是相对于特殊工件而言的，能够在平行机的任何一台机器上去加工 在本文讨论的模型中，所有的特殊工件都被指定到机器蝇上去加工，也就是 说，具有相同的指定机器特别指出，本论文我们研究的是一种基本的情形 对于更一般的情形，即特殊工件的指定机器不尽相同，我们会在以后的工作中 继续加以研究 在实际的生产活动中，特殊工件的例子随处可见比如，有些工件具有特殊 的形状，必须到具有特定设备的机器上去加工；有些工件具有腐蚀性，必须到 具有抗腐蚀性的机器上去加工；有些工件很容易褪色，必须指定到防褪色的机 器上去加工等等诸如此类的例子举不胜举由于这些工件的存在，就需要我 们安排工件的加工时作出特殊的决策这就使得我们的问题变得更加一般化， 复杂化，具有更广泛的实际意义和应用背景 1 3排序的记号 1 9 7 9 年，g r a h a m ，l a w l e r 等人【1 2 】提出用三参数来表示一个排序问题这也 是目前国际上通用的表示法在这里，我们采用a 吲7 来表示个排序问题， 4 其中口域用来描述。机器的环境。，卢域主要描述。工件的特征”，7 域表示 。优化的目标。下面我们分别具体来说明 ( 1 ) n 域z 口；1 单台机器 口= p 相同的平行机 a = q 一致的平行机 口= r 无关的平行机 ( 2 ) 卢域t 卢= r j 工件的到达时间 p = d j 工件的工期 卢= p r m p 工件允许中断抢先 卢= p r e c 工件间有序约束 p = o n - l i n e - l i s t 工件是列表在线 卢= o n - l i n e , r j 工件是时间在线 p = o n - n e - s 厶n c l v 工件是不可预测的列表在线 p = o n 1 i n e - n c l v , r j 工件是不可预测的时间在线 卢= s p e c i a lj o b 工件是特殊工件 卢= s p e c i a lj o b ( m 1 )所有特殊工件被指定到机器尬上去加工 ( 3 ) 7 域， 我们先来介绍几个常见的符号： q 工件乃的完工时间 嵋工件以的权 岛工件乃的延迟时间这里，岛= g 一由 乃工件如的延误时间这里，乃= m a x 岛，0 ) 工件乃的误工数如果q d j ，则= o ；否则= l 一些常见的目标函数介绍如下， 7 = g 。最大完工时间此处，g 。= m 麟 q 1 1 j n 7 = l 一最大延迟此处，l 。= m 腻 岛l l j s n ) 5 - f = q 完工时间和 7 = t 吩g 加权完工时间和 7 = 乃误工时间和 7 = t 吩马加权误工时间和 ，y = 误工工件数 7 = t 吩加权误工工件数 1 4已知结果及本文主要结果 本节主要介绍文献中已有的关于经典的平行机在线排序的结果以及我们 所研究的排序模型的由来，最后列出本文的主要结果 我们知道，经典的平行机列表在线排序被人们广泛地研究了好多年用三 参数法此模型可表示为：p i n i o n n e - s t c 一关于这个模型，文献中已有大量 的结果下面，我们按照时间顺序将它们列举如下z ( 1 ) 1 9 6 9 年，g r a h a m 【2 】提出了一个竞争比为2 一示1 的l s 算法 ( 2 ) 1 9 8 9 年，f a i g l e ，k e r n 和t a r a n 【3 】证明了当m = 2 和m = 3 时，l s 算法 是最具有竞争性的，也就是最好可能的算法但当m 4 时，他们提供了一个 1 7 0 7 的下界，显然此时l s 算法不是最好可能的于是，当m 4 时，吻合上 下界是一直困扰人们的问题 ( 3 ) 1 9 9 3 年，g a l a m b o s 和w o e g i n g e r 【4 】，【1 9 】提出了一个竞争比为2 一鬲1 5 。 的算法，显然它比l s 算法略好，但当m 充分大时，趋向于零，所以几乎没 有多大改进于是，好长一段儿时间内，人们一直在想，当m 4 时，到底有 没有竞争比严格小于2 的近似算法的存在 ( 4 ) 1 9 9 4 年，c h e r tb o e ta 1 5 】提供了一个在线的m l s 算法，它的竞争比为 m a x 雨4 m 2 - 3 m ，篆蓦筹筹；i 鲁暑等) 当m = 4 ，5 ，6 ，7 时，经计算，m l s 算法的竞争 比分别为1 7 3 3 3 ，1 7 7 0 8 ，1 8 0 0 0 和1 8 2 2 9 且当4 m 2 0 时，m l s 算法是迄今为 6 止竞争比最小的算法作者还提供了m = 4 5 ，6 ，7 时的下界，它们分别为1 7 3 1 0 ， 1 7 4 6 2 ，1 7 7 3 0 ，1 7 9 1 0 ( 5 ) 1 9 9 4 年，b a , r t a e ta 1 | 6 】证明了当m 3 4 5 4 时，任何在线算法的竞争比 都不小于1 8 3 7 。 ( 6 ) 1 9 9 5 年，b s r t a le ta 1 闭对m 7 0 ，给出了个竞争比为1 9 8 6 的在线算 法 ( 7 ) 1 9 9 6 年，k a r g e r ，p h i l l i p s 和t o r n g 【8 】一般化了文献【7 】中的算法，证明了 个竞争比为1 9 4 5 的算法 ( 8 ) 1 9 9 7 年，a l b e r sf 9 】提供了个竞争比为1 9 2 3 的在线近似算法，且当 m 2 1 时，这是迄今为止最好的算法当m 8 0 时，作者还给出了个更好 的1 8 5 2 的下界 ( 9 ) 2 0 0 0 年，g o r m l e ye ts 1 2 2 】对m 8 0 ，提供了个1 8 5 3 5 8 的下界 ( 1 0 ) 2 0 0 0 年，f l e i s c h e r 和w a h l 2 3 1 提出了一个竞争比为1 + 、量学 5 3 如果在线算法安排工件 在机器上加工那么第二个正常工件以到 来，其加工时间胁= 1 如果在线算法也将其放在机器肠上加工，则列表中不再 出现任何工件在这里，我们很谷易得到。c 日= 2 ，p t = 1 ，则c h p t = 2 5 3 如果在线算法安排正常工件j 2 在机器尬上加工那么第三个正常工件以 到来，其加工时间仍为1 如果在线算法安排它在机器上加工，则第二个 特殊工件五到来，其加工时间p | = 3 此时，我们有g h = 5 ，c o p t = 3 显然， c 8 c o p t ：s 3 ， 如果在线算法安排正常工件以在机器上加工那么第四个正常工件 出现，其加工时间为3 如果在线算法安排它在机器上加工，则不再来其它 工件我们有g 日= 5 ，c o d t = 3 显然，c 耳c o p t = 5 3 如果在线算法安排正常工件五在机器上加工那么第三个特殊工件以 出现，其加工时间p 5 = 6 此时，我们有e 日= 1 0 ，c o p t = 6 显然，c h c o p t = 5 3 这样我们就完成了定理1 的证明 口 9 下面，我们给出在线算法日 算法日 当个工件按列表在线到来的时候，如果它是一个特殊工件，则安排它到 机器帆上去加工否则，令此正常工件的加工时闻为p 在加工它之前，我 们用t 。和t 2 分别表示第一台机器上的加工长度和第二台机器上的加工长度 如果五书生丽_ 5 3 ，m a x l 争盐，p ) 7 “ 注意到 g 日= t l + p 结合引理1 和p 的定义，我们有 蚴 半，p ) i 1 0 如果芈p ，那么 我们可以推出 要：业 5 3 ， m 弧 且产，p 一p ” 再结合芈p 我们有 如 1 t l j p 因此 竺诵tl-t-pcopt = 字 p ，我们有 因此 忑厕t 2 + p = 蛊 5 3 ， m x 2 吐争垃，p ) 一写 垃7 丽c ks 丽篙与= 平t l + p - p 2 ， 1 o l - p 。 如果t 3 2 p ，那么 业学s p + 百t 3 妯， 27 2 一引 则 c o p t 粼 坐掣粤垒 p 。 硝， 因此 若s 面雹t l + p 巧+ t s 丽= 半墨z + 警瓦3 面孕雩皿瓦可2 百一十下 1 + 訾= 5 3 否则。t s 2 p 那么 若盂币t 1 蓦+ p 面+ t 历3 两3 。t l + 平p + 虿t 3 t 3 p 此时，我们有 钸一 生咩世 p ，t 3 = 一 业警出，t a 类似于情形1 1 的讨论，我们有 如果警s ，那么 蛆学堕 型1 学3 = 学妯 因此 罢 r 假如在线算法将正常工件兄放在机器上加工，那么第三个正常工件以 到来其加工时间船= 2 如果在线算法放工件以在机器尬上加工，那么第二 个特殊工件 到来，且具有加工时间p 4 = 2 ，没有别的工件出现此时c h = 4 ， c o p t = 2 显然我们有g 日d t = 2 r 假如在线算法安排工件以在机器尬上加工，那么第四个正常工件五出 现其加工时间p 4 = z ，其中z = 击= 垒嘻盟* 4 3 7 2 如果在线算法将正常工件 安排在机器尬上加工，那么第三个特殊工件五到来，其加工时间p 5 = 霸 且列表中不再出现其它工件那么c 日= 2 z ，c o p t = 矗因此c h c o 。t = 2 r 假如在线算法将其安排在机器尬上加工则列表中无任何工件到来此 时，我们有c 日= 3 + z ，p t = 矗因此c 日p t = 擎= 三 = r 假如在线算法将其放在机器慨上加工，那么第五个正常工件j 5 到来其 加工时间p 5 = z 如果在线算法将正常工件 放在机器上加工，则无其它 1 4 工件到来那么g 抒= 3 + 王，p t = 善因此c 日p t = 半= r 假如在线算法将正常工件五放在机器 毛上加工，则工件列表中无其它工 件出现此时c 日= 1 + 缸，c 缸= 矗因此c 啊p t = 3 挚 2 r 假如在线算法放工件五在机器尬上加工，那么第四个特殊工件五到来 其加工时间翔= x + 2 ，且列表中无任何工件到来此时c 啊= 2 z + 2 ，p t ；茹+ 2 因此c x = 嚣= 鬻= 学= 尼 至此，我们完成了定理3 的证明 口 下面，我们给出在线算法日 算法日 * 当个工件按照列表在线到来时，如果它是个特殊工件，那么安排它到 机器m 上加工否则，令此工件的加工时间为p 在决定它的加工之前，设机 器，和 毛上的加工长度分别为t 1 ，t 2 和t 3 ，我们按照如下规则安排它t 1 如果忑西盏錾霸 l + 卢且盂西美刍丽 1 + p ，安排它到机器尬上； 2 如果忑翠盏鍪霸1 + 3 r 二西捌蠹砑 l + 反安排它到机器上； 3 如果忑甬倒錾丽 1 + 3 r 二霜蔓萝丽1 + 卢，安排它到机器慨上； 4 如果；西美丽i + s r 面百翌丽s 1 + 反安排它到负载多的机 器上 定理4 ：对于排序问题p 3 i d n - 妇e - i i 观s p e c i a l 0 b s ( m ) i 。，在线算法日的竞 争比不会超过1 + 卢1 8 5 7 证明：我们考虑任一工件列表设工件j 是算法h 中最后一个完工的工 件我们分下面两种情形来证明 情形l ：工件j 是一个正常工件令其加工时间为p ，且在安排此工件之前， 机器胍，尬和蝎上的加工长度分别为t ，t 2 和t 3 我们再分下面三种子情形 来讨论： 情形1 1 ：工件，在机器尬上完成它的加工由算法日， 面再t z 嘲+ p l + p ，面萨t 3 蕊+ p l + 卢 i 注意到 结合引理1 和p 的定义，我们有 我们可以推出 泸= t l + p ， c o p t m a x 生字也，p ) 生竺 1 + 反 p 再结合址纽手垒控sp t 我们有 因此 垒二竺 1 + 口， p p 刍( t 2 + t 3 ) ， t 1 2 ( 1 一卢) p 兰二毒堡芸妊：业 2 ( 1 - 卢) p - l - p ：3 2 卢 1 + 卢 33 1 1 垒兰兰竺 3 再运用址纽3 鱼控 p ，我们有 因此 粥，学 粥 p 去( 2 + 屯) ， p 菇( 2 + 龇 抓字m + t 3 ) 器面= 平h + p t 3 结合引理1 和p 的定义，我们有 c 日= t 2 + p 一 丛等业，p ， 因此 嚣s 面啊t 2 + p 外p 情形1 3 ：工件，在机器脶上完成它的加工由算法日， 或者 注意到 面萨t 2 写+ p 匝可 1 + 威m a ) 【 址2 纽盐，p ) “ts两+pmax3p 1 + 卢她， 2 一” i 五王才王t 2 匝+ 手p 啊l + p ，五五i f t 五s 互+ 芋p 啄sl + 鼠t ： 1 + p ，；五i 互t s 丑+ 雩p 两 1 + 厣 c 玎= t 1 + p + “， 结合引理1 和t t 的定义，我们有 o o p t _ m a x 址半乒出，她 情形2 1 ：址等纽盐p 类似于情形1 1 的讨论，我们知 如果t 4 ；p ，那么 则 因此 p 去( 如+ t 3 ) p 芴( 如+ t 3 ) t l 2 ( 1 一卢) p 业型等坐出p + 百t 4 t 3一。3 一r c o p t 一 丛生掣，川t = “ 葡c h 面面t l - - 酾p - b t 4 = ! 业t 4 1 + 警p t 3 m “ 蛐生5 纽垃，p ，t 4 ) 一。；p l + 兰学= 3 一= 4 3 口= l + 卢 护 否则，t 4 和那么 c h c o p t五币t 巫l + 孚p 4 啊- t 4s 豇t l + 平p - b t 4 t l - b t 。- b l 4 - b t 2 + t 3 p c o p t _ _ _ m a x 址哼产盟肭 = 叫业尝学生，“】 类似于情形n 的讨论，我们有 如果警警，那么 t l + p + t = 4 + t 2 + 一t 3 3 因此 一c h ；黩；妻；：! ! 旦些 l + 仉i ；2 ，m j 2 0 注意到 结合引理1 和p 的定义，我们有 曼+ p 如果午s p ，那么 我们可以推出 曼。+ ， 再运用主i ；- p ，我们有 因此 c 日= t l + p ， c o p t z 字 竹渊，m p 志耋t t虾而芭k t l ( m 一1 ) ( 1 7 ) p 罢挲：业 p ，我们有 拿竺 1 + 7 ，江2 ，m e t j + p 生生一 带，t 咄，m p 南参外而毛如， 却 白磊 m 趸j 氏 m 字殂 “ 因此 ，t ，+ pt 。+ p ，导量缸+ 由邑厶 = _ ：f 。1 一；f 一* o p t 1 ei j + ，三亏i “+ “+ i 鬲兰可亍e “ 圭生一_ | 三兰_ 三兰_ 土扎 = m 一( ，l 一1 ) ，y l 江2 ，m 注意到 c 日= t l + p + t m + l ， 结合引理1 和+ t 的定义，我们有 t l + p + t m + l + 如 m a x _ 产川pm + t ) 量l ，+ ， 情形2 1 ：誓s p 类似于情形1 1 的讨论，我们有 如果t t ，l + l ；备a 那么 从而 因此 p 志塾外丽薹k t l ( m 一1 ) ( 1 一们p t l + p + t ，i + l + 曼t 曼幻+ p + k 件l 主! l ：兰一mmp + ! 警s t ，件- 如+ p + k + l + 曼 c o p t m x 1 - _ 圭l ，p ，k + 1 ) = l ， 竺c o p t 熹争= 业。m 地q - 1 外筹 2 t ，槲t m + 。+ 曼h。；啬p m a x 百且，p ，t m + 1 ) t + 坠铲 否则，t l 惫p 那么 c 耳 c o p t t l + p + t m + l ；m 一虹= ! 乙；l + 1 m “+ 舛i m + l + t t s 旦塑埤 “+ p + h + i - f t t m a x 1 - 三l i p t m + 1 ) 1 - “l p ，此时 t t + p + t m + l + e 缸t l + p + t m 4 1 + 如 c o p t2m a x 产，p ，t m + l ，= m a x 1 产，+ l 类似于情形1 1 的讨论，我们有 p 丽1 薹m 缸虾丽荟缸 2 3 如果蔡；s 鲤7 ，那么 因此 n 字耋如，y 葛 t l + p + t 。+ i + 苎t 生 m g 宇墨t + 而b 墨如+ t ，件- + 墨厶 ：i 至= 2 t i + 一t m + l t m + l ， m t x + p + t r n + lt l + p + t m + 1 t i 协t _ + 1 + t m + l m 缸 1 r 业，t ，件l 兰叁! 壶叁! ! = ： 譬1 那么 竺 g p t t 1 + p + m + 1 t l + f + t r a + l + t 。 垒塑兰警 t l + p + t m + l + t 。 m 强 1 广生，t 1 ) 1 r 业 ，宁墨如+ t 杀而墨“+ 赢墨如 孚量“+ - ；而量而邑一至t ：m 一业1 ：1 + ，y 综合以上各种情形，我们完成了定理5 的证明 口 后记 本文我们考虑排序模型p m i o n - 丘n 争馘驴e d 且jj o 蜮m ) i q 。，在两台，三台以 及大于等于四台机器的情形下分别给出了在线算法和下界但在算法的竞争比 与下界之间还存在着。空隙”我们进一步的工作就是弥补这些。空隙。，改进 我们的在线算法或者提高下界，以至于达到吻合另外，当特殊工件的指定机 器不尽相同时，排序模型变为p m l o n - l i n e - l i 甜；s p e c i a ly o 酬。此模型我们正在 考虑之中，而且已经有了进展我们会继续努力 更进一步，我们还可以考虑工件允许中断的情况 参考文献 f 1 1l l lg r a h a m ，b o u n d sf o rc e r t a i n l l t 蛐m i 珥a n o m a l i e s ，b e l ls y s t e mt e d m o k 唱yj o n r - m 1 1 4 5 ( 1 9 ) ，1 5 6 3 - 1 5 8 1 2 1r l g r a h a m ，b o u n d s m u l t i p r o c e s s i n gt i m i n ga n o m a l i e s 。s i a mj o u r n a lo na p p l i e d 【3 | u h i g l e ，w k e r n ，a n dg 1 t u a n ，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 t i o n f 4 】g g a l a m b c ea n dg w o e g i n g e r , a no n - l i n es c h e d u l i ：n gh e u r i s t i cw i t hb e t t e r 期嘲挣c 嘲 r a t i ot h a ng r a h a m 。l i s ts c h e d u l i n g ，s i a mj o u r n a lo nc o m p t t t i n g ，2 2 ( 1 9 9 3 ) ，3 4 9 - 3 5 5 【5 lb c h e n ，a v a n i e t ，a n dg w o e g i n g e r ，n e w e w