（运筹学与控制论专业论文）含有双重在线限制的排序问题.pdf

摘要 排序论是运筹学的一个非常活跃的分支，具有广泛而又直接的应用前景 排序问题是组合最优化领域中的一类重要问题而在线排序因其研究的内容非 常具有实际意义，从而更加引人关注 在线排序一般分为两种；列表在线排序和时间在线排序。在前一种模型 里，工件是排列成一个表逐个出现的，一个工件只有当表中排在其前面的工件 都安排以后才知道这个工件的有关信息。在后一种模型中，工件随着时间进行 安排，在任何时刻只知道当前已到达的工件信息在二种模型中，工件一旦被 安排就不允许改变。 本文研究的模型是同型机在线排序问题，其中工件的到达方式是o n - l i n e o v e r t i m e ，并且工件之间具有序约束( p r e c e d e n c ec o n s t r a i n t s ) ，目标函数是最小化最 大完工时间所以从某种意义上说，本文的排序模型是两种在线排序模型的复 合( 即使n 个工件同时到达，它们的信息也是逐个释放的) 在第一章中，我们 主要向大家介绍了排序问题产生的背景和一些相关基础知识在第二章中，我 们研究了同型机条件下双重在线复合排序问题，并证明了g r e e d y 算法是最优 的，其竞争比是2 一磊1 在第三章中，我们研究了工件带有机器限制的上述模 型的两种特殊情况，证明了g r e e d y 算法仍然是这两种特殊问题的最好算法， 竞争比分别是o ( 1 0 9 m ) 和m ( 其中m 为机器台数) 关键词：平行机；先后约束；到达时间；在线排序；在线算法；竞争比 a b s t r a c t s c h e d u l i n gi sav e r ya c t i v eb r a n c ho fo p e r a t i o n sr e s e a r c h a n di th a sa ne x t e n s i v ea n d d i r e c ta p p l i c a t i o nf o r e g r o u n d s c h e d u l i n gp r o b l e m sa r eak i n do fi m p o r t a n tp r o b l e m si n t h ed o m a i no fc o m b i n a t o r i a lo p t i m i z a t i o n m o r e o v e r ，o u l i n es c h e d u l i n gp r o b l e m sa t t r a c t m o r ea t t e n t i o no fp e o p l eb e c a u s eo fi t sa p p l i c a t i o n si np r a c t i c e i ng e n e r a l l y , t h e r ea r et w od i f f e r e n to n - l i n em o d e l si no n l i n es c h e d u l i n g t h e ya r e o n - l i n eo v e r l i s ta n do n l i n eo v e r t i m e i nt h ef o r m e r ，j o b sa r eo r d e r e di ns o m el i s ta n da r r i v e o n eb yo n ea c c o r d i n gt ot h i sl i s t ，a n dt h ec u r r e n tj o bn e e d st ob ei r r e v o c a b l ys c h e d u l e d b e f o r et h en e x tj o ba n da l li t sc h a r a c t e r i s t i c sb e c o m ek n o w n i nt h el a t t e r ，j o b sa r r i v eo v e r t i m e ，t h ec h a r a c t e r i s t i c so faj o bb e c o m ek n o w nt h ej o bb e c o m e sk n o w n ，w h i c hh a p p e n s a ti t sr e l e a s ed a t e s i nb o t hm o d e l s j o b sm u s tb ei r r e v o c a b l ys c h e d u l e d t h i sp a p e rc o n s i d e r st h eo n f i n es c h e d u l i n go f i d e n t i c a lp a r a l l e lm a c h i n e si nw h i c h j o b s a r r i v eo v e rt i m ea n dw i t hp r e c e d e n c ec o n s t a i n t s t h eg o a li st om i n i m i z et h em a k e s p a n s oi nas e n s e t h es c h e d u l i n gm o d e lc o n s i d e r e di nt h i sp a p e ri st h ec o m b i n a t i o no ft h e t w oo n - l i n em o d e l sd e s c r i b e da b o v e ( e v e vi ft h e r ea r en j o b sw h i c ha r r i v e da tt h es a m e t i m e ，t h e i ri n f o r m a t i o ni sr e l e a s e do n eb yo n e ) i ns e c t i o n1 ，w em a i n l yi n t r o d u c et h e b a c k g r o u n do fs c h e d u l i n ga n ds o m er e l a t e db a s i ck n o w l e d g e i i ls e c t i o n2 w es t u d yt h e o n - l i n es c h e d u l i n go fi d e n t i c a lp a r a l l e lm a c h i n e si nw h i c hj o b sa r r i v ei nt h ec o m b i n e do n - l i n es c h e d u l i n go fi d e n t i c a lp a r a l l e lm a c h i n e si nw h i c hj o b sa r r i v ei nt h ec o m b i n e do n - l i n e f a s h i o n t h eg o a li st om i n i m i z et h em a k e s p a n w eo b t a i nt h a tg r e e d ya l g o r i t h mi s o p t i m a la n dt h ec o m p e t i t i v er a t i oi s2 一鬲1 i ns e c t i o n3 ，w ec o n s i d e rt w os p e c i a lc a s e s o ft h ea b o v ep r o b l e mu n d e rt h ea s s u m p t i o nt h a tt h ej o b sh a v et h em a c h i n ec o n s t r a i n t s w ep r o v et h a tg r e e d ya l g o r i t h mi sa l s oo p t i m a lf o rt h e m ，a n dt h ec o m p e t i t i v er a t i o sa r e 0 ( 1 0 9 m ) a n dm ，r e s p e c t i v e l y , w h e r em i st h en u m b e ro fm a c h i n e s k e yw o r d s ：p a r a h e lm a c h i n e ，p r e c e d e n c e ，r e l e a s ed a t e ，o n - l i n es c h e d u l i n g ，o m l i n ea l g o r i t h m ，c o m p e t i t i v er a t i o 2 第一章引言 排序论，是运筹学的一个分支其作为组合最优化的一个重要组成部分， 有着深刻的实际背景和广阔的应用前景从深层次和长远看，排序论对提高效 率，资源的开发和配置，工程进展的安排以及经济运行等方面都起到辅助科学 决策的作用排序问题产生的背景是机器制造。随着大型制造业的兴起，人们 逐渐意识到排序问题研究的重要性。早在二十世纪初，第二次工业革命期间， t a y l o r ，g i l b r e t h ，和c a n t t 就发表了许多相关的研究文章他们的目的是进行有 意义的科学管理，提高劳动生产率今天，排序论不仅仅应用于机器制造业， 它更广泛的应用于管理科学、计算机科学和工程技术等领域而在这些领域取 得的丰硕成果使排序论成为发展最迅速，研究最活跃，成果最丰硕，前景最诱 人的学科领域之一 下面我们就从组合最优化，排序和在线排序三个方面向大家介绍一下排序 理论的基本概念和特征 1 1排序问题 排序，是在一定条件下分配时间资源去完成一些任务，使得某一个或某一 些目标达到最优它是一类重要的组合最优化问题，是运筹学研究的一个非常 活跃的分支排序问题产生的背景是机器制造二战之后，随着大型制造业的 兴起，人们逐渐意识到排序问题研究的重要性从第一篇排序论文问世以来的 半个多世纪中，排序问题的研究有了迅速的发展，全世界已经发表的文献3 千 多篇，其中包括排序专著和教材5 0 余种可以预见，排序论因其广阔的应用前 景必将应来更加辉煌的明天 排序论一般分为理论部分和应用部分在唐国春，张峰等人2 0 0 3 年的现代 排序论 1 】一书中提到，排序理论研究可分为经典排序( c l a s s i c a ls c h e d u l i n g ) 和 现代排序现代排序就是非经典的，新型的排序相对经典排序而言，其最大特 】 点就是突破了经典排序的基本假设。从上个世纪8 0 年代以来，新型排序模型不 断涌现。常见的1 0 余种排序模型有：可控排序、成组分批排序、在线排序、同时 加工排序、准时排序、不同时加工排序、资源受限排序、随机排序、模糊排序、 多目标排序等( 参见文献 1 】【2 】) 按照学术昊多年来形成的惯例，我们把需要完 成的任务称为工件( j o b ) ，把完成任务需要的资源称为机器( m a c h i n e ) ，我们希 望找到一个可行的排序( s c h e d u l e ) ，使得某个给定的目标函数达到最小( 大) 这 里可行一般指在同一时刻，一台机器至多加工一个工件，一个工件排序也只在 一台机器上加工，并且该排序满足问题特定的约束条件因此，排序，又称调 度，实质是把需要加工的工件，安排在给定的机器上加工，使给定的目标达到 最优给定一个具体的排序问题，需要明确以下三方面的信息：机器环境、工 件特征、最优准则这就使得我们可以用一种所谓。三参数表示法”( t h r e e - f i e l d r e p r e s e n t a t i o n ) a f l ? 来表示一个排序问题( 参见文献【2 】) ，其中q ，卢，y 分别 代表特定的机器环境，工件特征和最优准贝| j 下面我们分别对这些信息作一简 要介绍 机器环境描述了机器数量、不同机器之间的关系等与机器有关的性质平 行机( p a r a l l e lm a c h i n e s ) 是其中最重要的机器类型之一，用m = 尬，m 2 ，尬。) 表示机器集，其中m22 ，每个工件只需在其中一台机器上加工一次即可完 成常见的平行机类型有： 同型平行机( i d e n t i c a lp a r a l l e lm a c h i n e s ) ，即所有机器的加工速度一样，通常 用p 表示，若写成p m ，则表示系统中共有m 台同型平行机； 同类平行机( u n i f o r mp a r a l l e lm a c h i n e s ) ，即机器有其各自不同的速度，但任 意工件在不同机器上的加工时间有相同的比例关系，通常用q 表示； 不同类平行机( u n r e l a t e dp a r a l l e lm a c h i n e s ) ，即机器的加工速度不同，且工 件在不同机器上的加工时间有比例不完全相同，通常用r 表示 工件特征，一般是指工件的各种加工信息，包括工件的加工时间，工件的 开工时间，工件之间加工顺序以及工件和其开工时间的依赖关系，工件加工时 是否允许中断以及中断恢复后再加工时是否要受惩罚等等。根据排序者对工 2 件信息的了解程度，又可将排序问题分为离线( o m i n e ) 、在线( o n l i n e ) 和半在线 ( s e m i - o n l i n e ) 三类下面作一简要介绍： 如果排序者在排序开始前就已经知道工件的全部信息，例如工件数、每个 工件的加工时间等，则称该问题是离线的 如果工件的信息是随着排序过程逐个释放的，即只有在位于某个工件前的 全部工件均已被安排完毕后，排序者才知道该工件的信息，而且工件一旦被安 排就不能改变，这样的排序问题称为是在线的( 我们将在第三节详细描述) 所谓最优准则，也就是以什么为目标函数如果记g 为某个排序问题的 可行排序工件五的完工时闯则称g 一= m a , x g 为该排序的工件最大完工时 间( m a k e s p a n ) ，它即为某种最优准则下的目标函数，其最优准则为：找一个可 行排序，使得工件的最大完工时间g 一在所有的可行排序中取得最小值，即 最小化目标函数文献中常见的其它目标函数还有极大化最小机器完工时间、 最大延误时间、最大误工时间、最小误工个数等有关排序问题的综述( 最 优性质的的刻画我们将在第二节详细描述) 1 2排序问题的复杂性刻画 评价一个问题的难易程度，我们就要借助于算法复杂性理论算法复杂性 是由数理逻辑，运筹学和计算机科学家共同研究发展起来的一个新兴理论，它 对研究组合最优化问题的算法非常有用 定义1 2 1 ：算法是指一步步求解问题的通用程序，它是解决问题的程序步 骤的一个清晰描述确定性算法从前一步到后一步的运行由当前状态唯一确 定如果存在一个算法，它对组合优化问题7 t - 的每个实例( i n s t a n c e ) ，在有限 步后一定可以得到该实例的关于丌的提问的答案，那么称该算法解此组合优化 问题” 定义1 2 2 ：对于一个组合优化问题丌，如果给定任意一个实例，算法a 总能找 3 到一个可行解盯s ( 1 ) ，那么就称a 为7 r 的近似算法( a p p r o x i m a t i o na l g o r i t h m ) ； 如果进一步这个可行解的目标值等于最优解值，则称a 为最优算法( o p t i m a l a l g o r i t h m ) 解离线问题的算法称为离线算法( o f f i i n ea l g o r i t h m ) ，相应地，解在线问题 的算法称为在线算法( o n l i n ea l g o r i t h m ) 其中，l s ( l i s t s c h e d u l i n g ) 算法【7 】【8 】 和l p t ( l a r g e s t p r o c e s s i n g t i m e ) 算法【1 4 】分别是经典平行机排序问题的在线和 离线算法由于在离线问题中，排序者在排序前知道工件的全部信息，因此 l p t 算法先把所有的工件按加工时间的非增顺序排列，然后依次将它们安排 在能使其最早完工的机器上加工而对于在线问题，在排序进行过程中后续工 件信息是未知的，因此l s 算法将工件按到达时间的先后顺序安排在能使其最 早完工的机器上加工 算法求解问题是需要时间的，通常，算法所用的时间是指算法中所含的 加、减、乘，除、比较等基本运算次数而算法所用的时间与实饲的规模有关， 为此我们用输入长度来刻划实例的规模所谓实例的输入长度通常是指实例所 用的计算机内存单元数。 定义1 2 3 ：算法的时间复杂性是指关于实际输入长度礼的函数f ( n ) ，用来表示 算法的时间需求，对每一个可能的输入长度，它是指在最坏情况下该算法解此 输入长度的实例时所需时间( 基本运算步数) 即对于输入长度相同的所有实 例，把算法对这些实例的最坏情况作为时间复杂性的度量 如果存在一个多项式函数p ( n ) ，使得算法的时间复杂性为d p ( n ) ) ，那么 称该算法为多项式时间算法，否则称为指数时间算法还有一类称为伪多项式 时间算法，它的时间复杂性是关于实例输入长度n 和实例中最大数据的二元 多项式函数在二进制编码下，伪多项式时间算法并不是多项式时间算法，而 是指数时间算法由此出发，可以导出时间复杂性理论的一系列重要概念和结 论 计算复杂性兴起于二十世纪六十年代，它和算法的设计与分析密切相关 通过几十年来人们在计算复杂性方面的研究，现今p n p 的猜想已基本被 4 接受在此前提下，所谓的n p h a r d 问题就不可能在多项式时间内找到最优 解。从而，人们在解决方法的有效性、精确性和时间可行性上寻求平衡这样， 一个自然的想法就是放弃对最优解的寻找，而把研究的重点转向寻找能在比较 短的时间( 多项式时间) 内得到接近于最优解的可行解，称为近似解这种寻求 近似解的算法也就是如前所说的近似算法同时n p h a r d 问题中有一类更难 的问题，称为强n p h a r d ( s t o n g l yn p h a r d ) 问题，这类问题连伪多项式时间 最优算法都不存在 我们衡量近似算法的优劣可以从两个方面来看，一是算法的时间复杂性， 二是算法得到的解值与最优解值的接近程度另外一个在实际常用的方法是对 n p h a r d 问题加些限制从而得到一些子问题，使其具有有多项式时间算法 这是因为一个问题是n p h a r d 的，并不能排斥它的一些特殊子情形是多项式 可解的 定义1 2 4 ：如果丌是一个极小( 大) 化问题，j 是任意实例设a 是丌的一个近 似算法用c a ( i ) 和p t ( ，) 分别表示算法a 解实例，的目标函数值和离线情 况下实例i 的最优目标函数值记肌( ，) = c 1 ，t i ( ) j ) ( p a f f ) = c “o p r ( ， ) i ) ，) ，则近似算法 的最坏情形界( w o r s t c a s er a t i o ) ( 对于离线情形) 或竞争比( c o m p e t i t i v er a t i o ) ( 对 于在线和半在线情形) 定义为 p a ( t 7 r ) = i n f p l l p a ( 1 ) p ，v z 而问题，r 的下界( 1 0 w e rb o u n d ) 定义为 ( ”) = 8 印 胁( ，) 之，v a 如果p a ( r ) = ( 丌) ，则称算法a 对于问题7 1 来讲是最优的( o p t i m a l ) 在不引起混淆的前提下，我们通常将上述定义中的以( ，) 、c o p t ( i ) 和p a ( ”) 分别简记为瓯、岛盯和p a 。 定义1 2 5 ：如果某问题有一系列近似算法 a ) ，对于任意给定的 0 ， a ) 是 一个多项式时间算法，而且p a 。s ( 。，则称它为多项式时间近似方案( p o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e ) ，简记为p t a s 进一步，如果 也) 的时间复杂性 5 是关于输入长度以及；的某个二元多项式，则称它为完全多项式时间近似方案 ( f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ，简记为f p t a s 由于某些组合优化问题本身固有的难度以及最坏情况界估计需要很强的 数学基础和技巧，导致很多情形下无法证明某些算法的最坏情况界，而实际问 题又迫切需要给出一些方案来求解，在这样的前提下，我们给出了启发式算法 的概念。 定义1 2 6 - 启发式算法是一个基于直观或经验构造的算法在可以接受的花费 ( 指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一个可行 解，该可行解与最优解的偏离程度不一定可以事先预计 评价启发式算法的性能主要分两类，一是看算法占用的时间，空间等，二 是分析算法的效率算法效率往往采用大规模的随机数据进行实验验证，从平 均的角度以及最坏的角度来进行衡量 1 3在线排序 和所有现代科学理论一样，排序论也是在和实践生活相互作用逐渐成熟起 来的 经典排序是假设排序问题一个实例的所有信息，包括工件个数，就绪时 间，加工时间等在开始排序前都是事先知道的，这种情况，我们称为是离线的 ( o f f - l i n e ) 然而现实生活的实际情况往往并非如此，而是在所有信息知道之前 就必须排序，这种情况我们称为是在线( o n - l i n e ) 的在线排序中工件信息是逐 个释放的，在决定当前工件的加工时间对其后面就绪的工件的信息是一无所知 的，并且一旦决定工件的安排后就不允许改变；而离线排序则在排序之前知道 所有工件的信息 在线排序分2 种常见模型： 6 ( 1 ) 列表( o v e r - l i s t ) 在线排序：工件是排列成一个表逐个出现的，一个工件 只有当表中排在其前面的工件都安排以后才。知道”这个工件的有关信息 ( 2 ) 时间( o v e r - t i m e ) 在线排序：工件随着时间进行安排，在任何时刻只“知 道”当前已经就绪工件信息 上述两种情况中工件安排以后就不能再改变了所谓“知道。一个工件是 表示这个工件的加工要求已经清楚地给出因而，上述两种模型称为是可预测 的( c l a i r v o y a n t ) 在不可预测的( n o n - c l a i r v o y a n t ) 的情况下，工件的加工要求只有 到加工完成后才能知道，所以共有4 种在线排序：可预测的列表在线排序，可 预测的时间在线排序，不可预测的列表在线排序和不可预测的时间在线排序 衡量一个在线排序算法最常用的指标是它的竞争度( c o m p e t i t i v e n e s s ) ，即把 在线排序算法的结果与相同工件运用离线排序算法得到的结果进行比较，更确 切的说，我们用竞争比( c o m e t i t i v e - r a t i o ) p 来衡量一个在线排序算法的性能对于 使目标函数为最小的在线排序问题，竞争比p 定义为对问题的所有实例的比值 罴的上确界，其中c 和q 分别表示由这个在线排序算法得到的目标函数值和 相应的离线排序的最优值。这时这个在线排序算法称为是p 竞争( c o m p e t i t i v e ) 算法如果不存在别的在线排序算法的竞争比小于在线排序算法h 的竞争比， 那么称这个在线排序算法h 是最有竞争性的这是h 的竞争比又称为是在线 排序算法竞争比的下界对于使目标函数为最大的在线排序问题，可以类似定 义竞争比的上界 一个在线排序算法的竞争度是与离线排序的最优算法进行比较的因而， 竞争度是表示由于问题实例没有获得完全信息所造成的损失假设加工工件的 一个次序需要一个固定的费用这个费用是由相应的离线排序的最好算法所确 定的，因而也能够把这个费用减小到最小同时，还假设在线算法对于给定的 一个工件次序的性能是可以用竞争比来衡量的，能够达到这个固有的费用的 因而能够把在线排序算法的排序过程看成是寻找工件次序的过程。这个工件次 序是度量给定的在线排序算法的竞争度的基础。 7 对于在线排序更为详细的阐述我们可以参考文献【1 3 】 8 第二章同型机上的双重复合在线排序问题 本章讨论的是在同类机条件下o v e r t i m e 和o v e r l i s t 两种约束下要求总完工 时间最短在线排序问题，即工件既有先后约束又有到达时间约束的在线排序问 题 2 1引言 我们知道，在线排序问题有两种一般形式一是o v e rl i s t 另一种是o v e rt i m e 在o v e r l i s t 在线排序模型中，工件是排列成一个表逐个出现的，即工件之 间有一个序关系，一个工件只有在其前面的工件都安排以后才知道这个工件 的有关信息 在o v e r t i m e 在线排序模型中，工件随时间进行安排，在任何时刻只知道当 前已经就绪的工件信息 但是实际问题往往比这两种分类更复杂，甚至有可能是这两种情形的复 合 比如，我们考虑这么一个实际情况：有一台设备，它需要输入一族指令 它有m 个指令输入接口，同时指令存储在一定数量的存储器之中，在输入指令 时需要将存储器中的信息按一定顺序进行输入，即存储器在输入信息时其标号 有一个先后次序但是在刚刚开始输入时，我们除了第一组可以输入的存储器 标号已知外其余存储器的标号只有在其前任存储器都已完工后才会被告知，且 存储器是分批到达，其到位时间各不相同 从以上实例可见，此类问题的数学模型是o v e r l i s t 和o v e r t i m e 的复合，我们 既需要考虑工件之间的序列关系又需考虑工件本身是否就绪本文对解决此类 问题的方案进行了探讨 9 2 2预备知识 为了更加清晰的阐明往后讨论的问题，我们还需定义几个术语： 我们说，一个工件在m 台平行( p a r a l l e l ) 机上加工是只需在这m 台机器的 任何一台机器上加工一次其中具有相同加工速度的平行机称为同型( i d e n t i c a l ) 机 一个工件在加工过程之中，如果可以被别的工件抢先而中断加工，并稍后 在原来机器或在其他机器上继续加工，这种性质称为中断加工( p r e e m p t i o n ) 如果要求工件以完工之后才能开始加工工件 我们称在这两个工件之间 存在先后( p r e c e d e n c e ) 并用易一磊来表示先后约束是一种偏序关系，如果工件 之间不存在先后关系就称其为独立工件先后关系可以用一个有向图来表示， 如果结点以到以存在一条有向边，就表示工件乃和工件 之间存在先后关 系o j 一致， 如果工件有一个到达时间( r e l e a s ed a t e ) 则这个工件信息只有在其到达之后 才会知道，其自身只有在到达之后才可以被机器加工 如果机器在加工工件，我们称机器是不空闲的反之，如果机器不在加工 工件，则我们称之为空闲机器 2 3问题，算法，及证明 在我们讨论的在线模型当中，工件信息只有在其所有前任都加工完成并且 其自身已经到达的情况下才会被知道，这时我们称此类工件为a v a i l a b l e 工件 很明显可以看出，如果在0 时刻没有a v a i l a b l e 工件则我们可以将第一个 a v a i l a b l e 工件到达时刻当成0 时刻，不影响闫题的分析往后的分析中我们都 假设有a v a i l a b l e 工件在0 时刻到达 我们称空闲的在等待a v a i l a b l e 工件的机器为待工机器。 我们的目标函数是工件最晚完工时间，要使其最短，记为g 】0 我们考虑两种在线模型，一种情况下工件信息在其a v a i l a b l e 之后已知，另 一种情况下工件信息只有在其加工完成之后才知道很明显，加工时间未知情 况下的算法也一定可用于加工时间已知的情况，因而在已知加工时间的模型之 下，其下界也一定不大于未知加工时间的模型下界 我们在本章讨论的模型为；m 台同型机，工件带有先后约束，并且每个 工件都有自己的到达时间，在这双重约束的条件下对工件进行在线排序，目标 函数是最晚完工时间用三参数法表示即为： p r o o n l i n e ，p r e c ，r ji 我们知道同型机排序是一个非常古老的问题，g r a h a m 【7 】【8 】曾经给出以 下模型： p m i o n - l i n e - l i s t i g m 一个竞争比为2 一磊1 的在线算法，此竞争比即使在工件信息加工完成前未 知的情形也成立e p s t e i n 9 证明了对于p 州o n l i n e - l i s tl g 。，而言，2 一鬲1 是最优的 本文即将证明对于问题p i n i o n 一豇n e p r e c ，巧l a 一，而言，g r e e d y 算法 给出的竞争比至多为2 一磊1 ，其中r o 且即使在工件加工完成前信息未知的情况 下2 一击这个竞争比也是最优的 首先我们给出g r e e d y 算法； 任何时刻，如果一个新工件a v i l a b l e ，则安排它去空闲机器i ( 如果存在) 上 加工 任何时刻，如果一台机器空闲，则安排一个a v a i l a b l e 工件，( 如果存在) 去它上面加工 口 我们记由g r e e d y 算法给出的排序为g 我们记在排序g 当中最后一个机器全待工时刻之后，到达的第一个工件 的到达时间为r o 则我们给出以下命题： 命题2 1在已排好的序列g 当中，我们将排在r o 之后部分的工件取出 重新排序，则其所得的新的最优排序所费时长必不大于原问题最优排序在r o 之后的剩余时长。 证明：我们称链p l - - , p 。一一p f 在r 时刻为已到达序链，即在r 时刻之前， 链上所有工件的到达时间均不大于r 由r o 定义可知，在r o 之前有一段时间所有机器都待工于是由g r e e d y 算 法性质可知在r o 之前的所有序列已到达工件都已完工而在最优离线算法里 面，最多也就只能加工这么些工件。因而我们得出以下结论；r o 之前最优离 线算法所能加工的工件在g r e e d y 算法中必也已在r o 之前加工完成。从而我们 说最优离线算法在r o 之后部分加工的工件必也已包含了所有在g r e e d y 算法中 排在r 0 之后部分的工件 因此我们只要从最优离线排序之中截取出r o 之后部分，并从中保留由 g r e e d y 排序给出的排在在r o 之后的部分工件，便得到一个g r e e d y 在r o 之后工 件的排序，则其即为新排序的一种可行排序 由以上讨论，我们得到结论：g 排序在r o 之后部分的工件重新排序之后 所得的最优排序所得时长，一定不比原模型离线状态所得的最优排序在r o 之 后所费的时长更长 1 2 命题2 1 给出了我们将g r e e d y 算法给出的排序排在r o 之后的那部分工件 重新排序之后所得的最优排序和原最优排序排序之间的一个关系，下面在命题 2 我们给出r o 之后的工件重新排序后所得的最优排序和g r e e d y 算法所得排序 之间的关系 命题2 2令g 在r o 之后的工件重新排序后所得的最优排序所费时长为 三则g r e e d y 算法在r o 之后给出的加工时长至多为( 2 一去) l 证明：对于任何一个实例，设其由g r e e d y 算法给出的排序为g ，假设在g 当中以是最晚完工的工件我们观察 的前任集，从中选出最晚完工的工件 如继续观察以的前任集，从中选出最晚完工工件以依次类推向前追溯，我 们可以得到一条链j 1 一如一以一一占一- 一占其中如先后关系中没有前任 由g r e e d y 算法性质可知，g 排序只有在没有a v a i l a b l e 工件到达时机器才 1 2 可能空闲，我们研究在有机器空闲情况下链 一以一以一一占一- 一易上工件 的加工情况，我们说在时刻t 只有在以下二种情况g 中机器才可能空闲： ( 1 ) 在t 时刻存在链 一如一以一一易一，一如上的某个工件正在加工； ( 2 ) 在t 时刻存在链以一以一以一一占一。一占中的某一工件其链中前任 已完工，但其自身还未到达 设在链 一以一以一一占一，一占中最后一个具有性质( 2 ) 的工件是以， 其到达时间为r i ，则我们有在r i 时刻之后只有在情形( 1 ) 才会出现空闲机器， 即链 一如一以一一易一t 一如中的工件正在加工时，m 台机器中才会出现空 闲机器 令h 为g 在r o 时刻之后所费时长，令a 为链在矗之后部分的链长，即链 j 1 一如一一 的总加工时长令e p 为所有r o 之后工件的总工作量，则我们 有： h n r o + 墅堕兰型+ o 上式之所以成立是因为我们假设排序g 遇到最坏情况，即在链 一以一 一j ：i 上工件加工时，除了工作的这台机器外其他机器都空闲同时由r o 定义 可得在r o 到吩之间至少有一台机器在加工，所以满负载加工的工件在这种情 况下至多为e p 一+ 以一r o ) 将r o 之后的所有时段求和因而我们得到即使在 最坏情形下，h 也不会比r i r 0 + 2 二型鲁；垒二型+ a 大 化简上式我们有t 危n r 0 + p - ( a + r i - t o ) + 口 m = 以一+ 鲁一磊a 塑m + 口mm 因为最优排序时长l 辛，( 即使全部机器都满负载加工，所花费时间也需 要辛) 所以我们有： 1 3 n r 0 + l 一兰一r i - - r 0 + n mm = l + r i 一翔+ 口一( 警+ 象) = l + ( r i r o + d ) ( 1 一云) 又因为r i r o + a l ( 因为即使在最优排序中，链 一以一如一一占一- 一山 中工件也需要按先后次序进行加工，其中工件 即使在最优排序中它的开始 加工时间最早也要等到其到达时间r i ，同时件五后的链上工件加工总时长至 少还要为a ) 于是我们有： h l + l ( 1 一磊1 ) 综上所述我们比较h 和l 可得到： 一h 墨墨! ! 二盍2 ：2 一三 llm 因而我们说g 在r o 之后的工件重新排序后所得的最优排序所费时长为l 则g r e e d y 算法在r o 之后给出的加工时长h 至多为( 2 一鬲1 ，l 1 ：3 命题2 1 告诉了我们将排在r o 之后部分的工件取出重新排序，则其所得的 新的离线最优排序所费时长必不大于原问题离线最优排序在r o 之后的剩余时 长，同时命题2 2 告诉我们f 0 之后的工件重新排序后所得的最优排序时长工和 g r e e d y 算法给出的r o 之后时长之间的关系是2 2 一鬲1 我们结合命题2 1 和命题2 2 给出如下定理； 定理2 3 对于问题p m l o n - l i n e , p r e c ，r i g 一而言，g r e e d y 算法给出的 竞争比不会大于2 一击 1 4 证明：命题2 1 告诉我们如果排在r o 之后部分的工件取出重新排序，则 其所得的新的最优排序所费时长必不大于原问题最优排序在r o 之后的剩余时 长，用数学公式表示即为： o p t r o l 同时我们知道g r e e d y 算法所得得时长为a c = r o + h 因而，我们有： 丝 r o + h o p t r 0 + 三 又因为h 至多为( 2 去) l 所以我们有： 坐 三业 尘! ! 二三些 o p t r 0 + l 7 0 + l ：塑f ! 二壶! f ! 二盎! 墨二尘釜 7 0 + l ：! 尘望堡二盎! 二尘釜 l + r o = 2 一示1 一鬲i r 0 ：( 1 + 磊1 ) 2 h 一1 l 【鲁j l 唧+ ， 字 尘竺! 盟二兰i 2 c 碱一n + t o + m n m 2m 2 可了i 一2 ( n + r o ) 十2 ( n + r o ) 当n + r o 的取值相对于m 2 很大时我们有= m 一业n + r o 其中如果i 0 取值为0 时，我们说下界取得最大，为m 口 综上所述，我们可得： 定理3 7g r e e d y 算法对于问题p i n i o n f i n e ，r e s t r i c t e da s s i g n m e n t ，p r e c ，勺l g w 而言是竞争比最小算法，其竞争比为m 参考文献 1 唐国春，张蜂，罗守成，刘丽丽，现代排序论，上海科普出版社，2 0 0 2 2 】唐恒永，赵传立，排序引论，科学出版社，2 0 0 2 【3 】y a z a r ，l e p s t e i n ，o n h 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 ，( 2 0 0 2 ) 1 6 9 - 2 0 2 f 4 jy a z a r ，j n a o r ，r r o m ，t h ec o m p e t i t i v e n e s so fo n l i n ea s s i g n m e n t ，j a l g o r i t h m s ( 1 9 9 5 ) 2 2 1 2 3 7 ( 5 】a b o r o d i n ，r e i - y a n i v ，o n l i n ec o m p u t a t i o na n dc o m p e t i t i v ea n a l y s b ，c a m b r i d g eu n i v e r s i t yp r e s s ，c a m b r i d g e ，1 9 9 8 f 6 】f a c h u d a , k ，d b s h m o y s ，a p p r o x i m a t i o na l g o h t h m sf o rp r e c e d e n c ec o n s t r a i n e ds c h e d u l i n gp r o b l e m so i lp a r a l l e lm a c h i n e st h a tr u