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

摘要 摘要 排序( 调度) 理论是近年来组合优化方向很活跃的一个研究分支，受到众多学 者的关注对于排序问题的研究已有几十年的历史本文研究了近十几年发展起 来的若干在线排序问题全书共分为六章，第一章主要介绍与排序问题相关的一 些概念和预备知识 第二章主要研究工件具有相同的加工时间1 ，有到达时间和交货期且目标函 数为极大化按时完工的工件个数的两台机在线排序问题首先，我们对于m 台机 时的问题给出了该问题的一个下界；其次，我们对于m 台机的情形给出了一个简 单的具有竞争比为2 的在线算法；最后，对于两台机的情形，我们给出了一个最好 的在线近似算法，而且算法满足“立即通知”的性质 第三章研究上一章中当m 2 时的问题为方便起见，我们考虑工件具有相 同的整数加工时间p ，且有非负整数到达时间和交货期，目标函数为极大化按时完 工的工件个数的m 台机在线排序问题易知对于任意的p ，该问题与上述问题具有 等价性对于该问题我们给出了一个具有“立即决定”性质的在线算法，并证明了 该算法的竞争比为1 ( 1 一( 仇( m + 1 ) ) m ) ，其中当仇趋向于无穷大时，该竞争比趋 向于e ( e 一1 ) 1 5 8 2 另外，我们还给出了对于该问题具有“立即决定”性质的在 线算法的一些下界 第四章研究工件的加工长度任意，有到达时间和交货期，且工件可以“中 断重新”开始加工，目标函数为极大化按时完工的工件个数的m 台机在线排序问 题这里的可“中断一重新”开始加工指的是工件在加工过程中可以被中断，但当算 法在下次执行此工件时必须从头开始加工对于该问题，我们首先给出了一个：的 下界，然后给出了一个竞争比为2 的在线算法 第五章研究工件具有“任意”的到达时间，目标函数为最小化最大工件完工 时i h - ( m a k e s p a n ) 的m ( m 2 ) 台机的在线排序问题这里的问题模型指的是工件 按一定先后顺序出现，只有当前面的工件被安排后才知道下一个工件的信息与 经典在线模型不同的是前面的工件的到达时间有可能比后面的工件到达时间要 大此问题可以看成是经典的在线模型( j o b sa r r i v eo v e rl i s t ) 的推广对于机器台 数m = 2 时的问题，我们给出了一个竞争比为2 的最好的在线算法对于般的机 器台数为m ，并且所有- c 彳，t - 都有单位时间加工长度时的问题，我们证明了l s 算法 的紧界为鲁 摘要 第六章为后记简要的总结了一下本文的工作，讨论了未来的研究方向以及 一些公开问题 关键词：排序，计算复杂性，在线算法，竞争比分析，下界 a b s t r a c t a b s t r a c t s c h e d u l i n gi so n eo ft h ea c t i v eb r a n c h e si nc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s w h i c hh a sr e c e i v e dg r e a ta t t e n t i o ni nd e c a d e s t h i st h e s i sc o n c e n t r a t e so ns o m eo n - l i n e s c h e d u l i n gp r o b l e m so np a r a l l e lm a c h i n e sw h i c h c o n s i s t so fs i xc h a p t e r s w ei n t r o d u c e p r e l i m i n a r yc o n c e p t sr e l a t e dt oa p p r o x i m a t i o na l g o r i t h m sa n dc o m p l e x i t yt h e o r y i n c h a p t e r1 i nc h a p t e r2 ，w ei n v e s t i g a t et h eo n l i n es c h e d u l i n gp r o b l e mo fu n i tj o b so nm i d e n t i c a lp a r a l l e lm a c h i n e s t h eg o a li st om a x i m i z et h en u m b e ro f j o b sc o m p l e t e do n t i m e w eg i v eal o w e rb o u n do ft h ep r o b l e m ，a n dp r e s e n tas i m p l el sa l g o r i t h mw i t h c o m p e t i t i v er a t i oo f 2 ab e s tp o s s i b l eo n l i n ea l g o r i t h mm e d f , w h i c h h a st h ep r o p e r t y o f “i m m e d i a t en o t i f i c a t i o n ”，i sg i v e nf o r t h et w o - m a c h i n ec a s e i nc h a p t e r3 ，w eg oo nc o n s i d e r i n gt h eo n - l i n es c h e d u l i n gp r o b l e mo fu n i tj o b s o nmi d e n t i c a lp a r a l l e lm a c h i n e s f o rt h es a k eo fc o n v e n i e n c e ，w el e ta l lt h ej o b sh a v e a l le q u a ll e n g t hp ，a n da l lp a r a m e t e r sa s s o c i a t e dw i t haj o ba r ei n t e g e r s w eg i v ea n i m p r o v e do 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 oo f1 ( 1 一( m ( m + 1 ) ) m ) ，w h i c h t e n d st oe ( e 一1 、1 5 8 2 m o r e o v e rt h ea l g o r i t h ms a t i s f i e st h ep r o p e r t yo f “i m m e d i a t e d e c i s i o n ”i na d d i t i o n ，s o m el o w e rb o u n d sa r eg i v e nf o rt h eo n - l i n ea l g o r i t h mw i t ht h e r e s t r i c t i o n i nc h a p t e r4 ，w es t u d yt h ep r o b l e mo fo n l i n es c h e d u l i n gj o b so nmi d e n t i c a l p a r a l l e lm a c h i n e si nt h ep r e e m p t i o n r e s t a r tm o d e l ，i nw h i c hj o b sc a n b ep r e e m p t e d ，b u t p r e e m p t i n gr e s u l t si nt h ew o r kd o n eo nt h i sj o bs of a rb e i n gl o s t t h eo b j e c t i v ei st o m a x i m i z et h en u m b e ro f j o b sc o m p l e t e do i lt i m e w ef i r s ts h o wal o w e rb o u n do f ；f o r t h ep r o b l e m ，a n dt h e ng i v ea no 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 oo f2 i nc h a p t e r5 ，w ed i s c u s st h ep r o b l e mo fo n 1 i n es c h e d u l i n gas e to fj o b sw i t h a r b i t r a r yr e l e a s et i m e so nm i d e n t i c a lp a r a l l e lm a c h i n e s t h eg o a li st om i n i m i z et h e m a k e s p a n i nt h i sp r o b l e m ，j o b sa p p e a ri na l lo r d e r w e d on o tk n o wt h ee x i s t e n c eo f o t h e rn e w j o b st m t i lt h ec u r r e n tj o bi sg i v e n ap r o c e s s i n gs l o t i nt h i so n l i n es i t u a t i o n ， t h es e q u e n c eo fj o b s r e l e a s et i m ei sa r b i t r a r y , n o ta si nt h ec l a s s i c a lm o d e li nw h i c h t h es e q u e n c eo f j o b s r e l e a s et i m ei sn o n d e c r e a s i n g ab e s tp o s s i b l eo n - l i n ea l g o r i t h m i sg i v e nf o rm et w o m a c h i n ec a s e f o rt h es p e c i a lc a s et h a ta l lt h ej o b sh a v eu n i t p r o c e s s i n gt i m e ，w es h o wa l g o r i t h m 三sh a sat i g h tb o u n d o fi l l i ， a b s t r a c t f i n a l l y , i nc h a p t e r6w ep r e s e n tas u m m a r yo fo u rr e s u l t s ，a n dp o i n to u ts o m e f u t u r ew o r ka l o n gt h i sd i r e c t i o n k e yw o r d s ：s c h e d u l i n g ，c o m p u t a t i o n a lc o m p l e x i t y , o n l i n ea l g o r i t h m ，c o m p e t i t i v ea n a l y s i s ，l o w e rb o u n d l v 第一章绪论 1 1 组合优化简介 第一章绪论 组合优化又称离散优化，它是与连续优化相对立的一个概念通俗地讲，我 们可把关于连续变量的优化问题称为连续优化问题比如线性规划问题、非线性 规划问题等都是连续优化问题；而把关于离散变量的优化问题称为离散优化问题 或者是组合优化问题像众所周知的整数规划问题就是离散( 组合) 优化问题组 合优化问题有着悠久的历史渊源，比如著名的欧拉环游问题但是作为运筹学的 个独立分支而发展起来还是近几十年的事情二十世纪后半叶，伴随着工业 科技革命和现代管理科学的发展，特别是计算机技术的突飞猛进和在各行业的 广泛应用，组合优化己壮大成为一门新兴的学科分支一些数百年前数学家们 偶然想到的问题和方法，现在已在网络通信、物流管理、交通规划等领域发挥 了重要作用，这是他们当时所不曾想到的这正寓示了此学科的巨大前景下 面我们首先给出在算法和复杂性理论中问题以及组合优化问题的定义 定义1 1 1 ：问题是需要回答的一般性提问，通常含若干个参数，或自由变量，这些 自由变量的值还没有给定问题的描述是通过给定： ( 1 ) 所有参数的一般性描述； ( 2 ) 陈述答案或解必须满足的性质 给问题的所有参数指定了具体的值，就得到问题的一个实例 定义1 1 2 ：组合优化问题是一个极小( 大) 化问题，它由下述三部分组成： ( 1 ) 实例集合； ( 2 ) 对每一个实例，有一个有限的可行解集合s ( s ) ； ( 3 ) 目标函数。厂，它对每一个实例j 和每一个可行解s ( j ) ，赋以一个有理 数f ( i ，盯) 如果该问题是极小( 大) 化问题，则实例的最优解为这样一个可行 解盯+ s ( s ) ，它使得对所有的仃s ( ) ，都有( z ，盯+ ) f ( z ，盯) ( ，( ，仃+ ) ( z ，o r ) ) 例如，考虑经典的“旅行售货员问题”这个问题的参数是由有限的“城 市 集合e = c 1 ，c 2 。，c m ，以及c 中的每两个城市q ，g 之间的距离d ( q ，g ) 组 第一章绪论 成解是这些城市的一个排列次序( c 霄( 1 ) ，岛( 2 ) ，靠( m ) ) 使得 r n - - 1 d ( c 丌( 咖c 丌( 件1 ) ) + d ( c 丌( m ) ，c 7 r ( 1 ) ) i = 1 最小这个表达式给出从c 7 r 出发，依次经过每个城市，然后从最后一个城 市c 丌( m ) 直接回到c 丌( 1 ) 的“旅行 长度 常见的组合优化问题有适定性问题( s a t i s f i a b i l i t yp r o b l e m ) 、背包问题 ( k n a p s a c kp r o b l e m ) 、划分问题( p a r t i t i o np r o b l e m ) 、三划分问题( t h r e e p a r t i t i o np r o b l e m ) 、排序问题( s c h e d u l i n gp r o b l e m ) 、装箱问题( b i np a c k - i n g ) 、指派问题( a s s i g n m e n tp r o b l e m ) 、旅行售货商问题( t r a v e l l i n gs a l e s m a i lp r o b l e m ) 、斯坦纳最小树问题( s t e i n e rm i n i m a lt r e ep r o b l e m ) 等网 络中的组合优化问题还包括最短路问题( s h o r t e s tp a t h ) 、最小生成树问题 ( m i n i m a ls p a n n i n gt r e ep r o b l e m ) 、最大流问题( m a x f l o wp r o b l e m ) 、最 小费用流问题( m i n - c o s tf l o wp r o b l e m ) 、最大团问题( m a x i m u mc l i q u ep r o b l e m ) 等组合优化全貌可参见 2 5 ；5 8 ，在此，我们只对本文研究的排序问题作 一介绍 1 2 排序问题 排序( s c h e d u l i n g ) 问题是一类重要的组合最优化问题，它是利用一些处 理机( p r o c e s s o r ) 、机器( m a c h i n e ) 或资源，最优地完成一批给定的任务( t a s k ) 或工 件( j o b ) 在执行这些任务或作业时需要满足某些限制条件，如工件的到达时间， 交货期等最优地完成通常指的是使目标函数达到最小( 大) ，其实质是寻求对需 求完成任务的合理安排以得到某种意义下的最优结果它广泛地应用于管理科 学、计算法机科学和工程技术等很多领域同时，它与理论计算机科学和离散组 合数学也存在着密切的联系近几十年来，由于实际应用的需要，伴随着大量 具有实际背景的新问题的不断涌现，对于排序问题的研究已经非常的全而化、多 样化和深入化 一个排序问题一般来说可由三个要素来确定，即机器环境、工件特征和最 优准则通常我们采用国际上通用的一种所谓“三参数表示法”( 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 p 7 来表示一个排序问题 2 1 】，其中q ，p ，y 分别代表特定的 机器环境、工件特征和最优准则下面我们分别对这些信息作一简要介绍 一2 一 第一章绪论 机器环境用来描述机器的数量、不同机器之间的关系等与机器有关的性 质只有一台机器的排序问题称为单( 处理) 机( s i n g l ep r o c e s s o r , s i n g l em a c h m e ) 排 序问题，否则称为多( 处理) 机排序问题多( 处理) 机排序问题中，若机器具有相 同的功能，则称为同类机或平行机( p a r a l l e lm a c h i n e s ) 同类机按照处理的速度又 可分为三种类型：若所有机器的速度都相同，则称为同速机( i d e n t i c a lm a c h i n e s ) ； 若机器的速度不同，但每个机器的速度都是常数，不依赖被加工的任务，称它 们为恒速机( u n i f o r mm a c h i n e s ) ；若处理机的速度依赖被加工的任务，则称它们 为变速机( u n r e l a t e dm a c h i n e s ) 在三参数表示法中，上述三种机器系统分别 用p ，q ，尼表示 多处理机还有一种情况是多类型机( d e d i c a t e dm a c h i n e s ) 多类型机指的是各 机器具有不同的功能在这样的机器环境中，被加工的工件需要在不同的机器上 加工在这种情况下，每个工件一般来说有很多道工序这里的工序指的是在某 台机器上被加工的部分任务根据工序情况的和机器的差异，可以把这里的机 器系统分为三种，即流水作业( f l o ws h o p ) 、有序作业( j o bs h o p ) 和自由作业 ( o p e ns h o p ) 等把上述三种系统通常称为车间作业 工件特征一般是指工件的各种加工信息，主要包括以下几个方面：( 1 ) 工件的 加工时间( p r o c e s s i n gt i m e ) ，即工件需要在机器上被加工的时间；( 2 ) 工件的到达 时间( a r r i v a lt i m e ) 或准备时间( r e a d yt i m e ) ；( 3 ) i 期( d u ed a t e ) ，即工件限定完工的时 间如果不按期完工，应受到一定的惩罚绝对不允许延误的工期称为交货期或截 止期限( d e a d l i n e ) ；( 4 ) 优先因子，它指的是一个工件的权，它所表示的是一个工件 相对于其它工件的重要程度 任务或工件被加工时的一个重要约束是可中断( p r e e m p t i v e ) 或不可中断( n o n p r e e m p t i v e ) 若在排序问题中，每一个工件可以在加工过程中的任一时刻都可暂 停加工，并且以后可在任何时刻重新继续加工，则这种排序问题称之为可中断排 序而任何工件都不允许中断的排序问题称为不可中断排序 所谓最优准则，简单来说就是以什么为目标函数在排序问题中，目标 函数主要有以下几种时间表长( m a k e s p a n ) ：如果记c ；为某个排序问题的可行 排序中工件以的完工时间，则称a x = m a x jg 为该排序的工件最大完工时间 ( m a k e s p a n ) ，它即为某种最优准则下的目标函数，其最优准则为：找一个可 行排序，使得工件的最大完工时间觚在所有的可行排序中取得最小值，即最 小化目标函数小的时间表长意味着处理机有高的利用率其他常见的目标函 数还有( 加权) 总完工时间、最大延误时间、加权总误工、加权误工工件个数 第一章绪论 等有关排序问题的综述，可参看 7 ；4 0 根据排序者对工件信息的了解程度，可将排序问题分为离线( o f f - l i n e ) 、 在线( o n l i n e ) 和半在线( s e m i o n l i n e ) 等如果排序者在排序开始前就已经知 道工件的全部信息，例如工件数、每个工件的加工时间等，则称该问题是离线 的而如果工件的信息是随着排序过程逐个释放的，即只有在位于某个工件前 的全部工件均被安排完毕后，排序者才能知道该工件的有关信息，而且工件一 旦被安排就不能改变，则称这样的问题为在线的但在实际问题中，大量的问题 是介于两者之间的，即我们或者知道该问题的一些整体信息，或者知道后续工 件的部分信息例如，已知所有工件的总加工时间，或者已知工件是按加工时 间递减顺序排列的等等它们都不是离线问题，因为我们还不知道一共有多少 个工件，它们的加工时间具体为多少但与在线问题相比，这些信息可以用来 估计后续工件加工时间的范围，这是有利于算法设计的于是，我们把这样的 问题称为是半在线的 1 3 算法和计算复杂性 定义1 3 1 ：算法是指一步一步求解问题的通用程序具体一些，我们可以把它们 看成用某种精确的计算机语言写成的计算机程序如果一个算法可以应用于问 题丌的任何实例j ，并且保证得到实例珀勺解，那么就称该算法解问题7 r 一般地，我们感兴趣的是寻找解问题的最“有效的 算法在最广泛的意义 下，效率的概念包括执行算法所需要的全部计算资源通常最“有效的”算法就 是指最快的算法因为时间需求常常是决定一个具体算法是否由足够的效率用于 实际的主要因素 算法的时间需求可以用一个变量的函数来表示，这个变量就是问题实例的 “规模”通常，算法所用的时间是指算法中所含的加、减、乘、除、比较等基 本运算次数而算法所用的时间与实例的规模有关，为此我们用输入长度来刻 划实例的规模所谓实例的输入长度通常是指实例所用的计算机内存单元数 定义1 3 2 ：对于一个组合优化问题7 r ，如果给定任意一个实例j ，算法a 总能 找到一个可行解盯s ( j ) ，那么就称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 la l g o r i t h m ) 一4 一 第一章绪论 解离线问题( o f f - l i n ep r o b l e m ) 的算法称为离线算法，相应地，解在线问 题( o n 1 i n ep r o b l e m ) 的算法称为在线算法比较而言，关于离线问题的算法的研究 已有很长时间的历史，而关于在线算法的研究只是最近十几年才蓬勃发展起来 的在排序理论的研究当中，第一个分析算法的最坏情况的人是g r a h a m 。1 9 6 6 年， g r a h a m 给出并分析了现在大家众所周知的l s ( l i s ts c h e d u l i n g ) 算法 1 9 ，该算 法是排序理论中的第一个真正意义上的在线算法而l p t ( l a r g e s tp r o c e s s i n g t i m e ) 算法 2 0 】是一个经典的求解平行机排序问题的离线算法由于在离线问 题中，排序者在排序前知道工件的全部信息，因此l p t 算法先把所有工件按加 工时间的非增序排列，然后依次将它们安排在能使其最早完工的机器上加工 而对于在线问题，在排序进行过程中后续工件信息是未知的，因此l s 算法将工 件按到达的先后顺序安排在能使其最早完工的机器上加工 既然算法的好坏很大程度上取决于执行算法得到结果的“快慢为了准确 的描述算法的这一时问需求，下面我们引入算法的时间复杂性的定义 定义1 3 3 ：算法的时间复杂性是指关于实例输入长度n 的函数。厂( n ) ，用来表示算 法的时间需求，对每一个可能的输入长度，它是指在最坏情况下该算法解此输 入长度的实例时的所需时间( 基本运算步数) 即对于输入长度相同的所有实 例，把算法对这些实例的最坏情况作为时间复杂性的度量 根据算法的时问需求函数厂( n ) 与输入长度他的关系，可以把算法分为以下几 种如果存在一个多项式函数p ( 礼) ，使得算法的时间复杂性为0 ( p ( n ) ) ，那么称 该算法为多项式时间算法，否则称为指数时间算法还有一类算法叫伪多项式 时间算法，它的时间复杂性是关于实例输入长度7 , 和实例中最大数的二元多项式 函数在二进制编码下，伪多项式时间算法并不是多项式时间算法，而是指数 时间算法 由于当输入规模增加时，指数时间算法的算法效率降低特别快，以至于任何 一个多项式时间算法都变得比任一个指数算法更有效，所以我们把多项式时间算 法称为好的有效的算法并且对于组合优化问题的研究的重点，也都致力于寻找 好的多项式时间算法但是，并不是所有的问题都能够找到多项式时间的最优算 法，由此便引出了可以导出计算复杂性理论的一系列重要概念和结论【1 7 定义1 3 4 ：一个组合优化问题如果己找到了多项式时间算法，那么就称它为多项 式时间可解问题把所有这样的问题集合记为p ，所有多项式时间可解的问题就 称为p 类问题 第一章绪论 定义1 3 ，5 ：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的 实例i ，该算法首先给出一个猜想，该猜想的规模不超过i 的输入长度的某个多 项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于p 类 定义1 3 6 ：如果p 类中所有问题都可以多项式时间归约到n p 类中某个问题7 r ， 则称7 r 是p 一完全问题。 定理1 3 7 ：除非p = p ，p 一难问题没有多项式时间算法 关于计算复杂性理论的研究兴起于二十世纪六十年代，它和算法的设计与 分析密切相关关于p 是否等于p 的问题，已经有很多有才华的数学家进行了 研究，但遗憾的是都以失败而告终。多年来通过人们在计算复杂性方面的研究， 虽然不能证明p 是否等于尸，但是现在人们对于p p 的猜想已经被基本接 受在这个前提下，所有的n p h a r d 问题就不可能在多项式时间内找到最优 解所以，人们在解决方法的有效性、精确性和时间可行性上寻求平衡这 样，一个自然的想法就是放弃对最优解的寻找，而把研究的重点转向寻找能在 较短时间( 多项式时间) 内得到接近于最优解的可行解，称为近似解这种寻 求近似解的算法也就是如前所述的近似算法同时n p h a r d 问题中有一类更 难的问题，称为强p h a r d ( s t r o n g l yn p h a r d ) 问题，这类问题不存在伪多 项式时间最优算法 1 7 】 前面我们讨论了衡量一个算法的优劣，首先是算法的时间复杂性必须是可 以接受的对于这些不存在多项式时间最优算法的问题，我们往往放弃对最优解 的寻找，转而寻找一个可以快速得到的可行解，把它作为最优解的近似值那么 我们自然会希望得到的近似解与最优解最大可能的接近，以增加算法的有效性 为了衡量算法得到的近似解值与最优解值的接近程度，一般的我们采用最坏情 况界或竞争比进行分析。最坏情况界或竞争比刻画的是算法得到的解的值与最优 解的值的之间的接近程度当前做算法研究的人，基本上都是通过设计一些最坏 情况界或竞争比较好的多项式时间算法来求解那些难解的问题下面我们给出最 坏情况界和竞争比的定义 定义1 3 8 ：如果_ 7 r 是一个极小( 大) 化问题，是任意实例设a 是丌的一个近 似算法用巳( ，) 和c o r ( 1 ) 分别表示算法a 解实n i # ) i 得的目标函数值和离线 情况下实例，的最优目标函数值记r a ( ，) = 麦等南( 兄4 ( ，) = 群) ， 一6 一 第一章绪论 则近似算法a 的最坏情况界( 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 ) ( 对于在线和半在线情形) 定义为 吼( 丌) = i n f r 1ii 宅a ( i ) r ，v ，) 上述定义指出了对于任意实例，算法解在最坏情况下与最优解的接近程 度，这是一个正面i 拘( p o s i t i v e ) 的结果另外，如果确实可以找到一个实例，使得 算法解与最优解的比值与上界相同，则说明算法的界已经不能再改进了，这样 一个负面的( n e g a t i v e ) 结果也是同样重要的，此时称算法的界是紧的。 进一步的，对于一个组合优化问题而言，它也存在一个下界，它可以刻画 对于任意的多项式时间近似算法，在最坏情况下与最优解至少要差距多少，即不 可近似性 定义1 3 9 ：问题丌的下界( 1 0 w e rb o u n d ) 定义为 ( 丌) = s u p ir a ，v a 如果r a ( t r ) = ( 丌) ，则称算法a 对于问题丌来说是最好的( t h eb e s tp r o s s i b l e ) 算 法 定义1 3 1 0 ：如果某问题有一系列近似算法 也】，对于任意给定的 o ，( 4 ) 是一个多项式时间算法，而且r 屯1 + ，则称它为多项式时间近 似方案( p 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 ) ，简记为p t a s 进一步的， 如果 a ) 的时间复杂性是关于输入长度以及的某个二元多项式，则称它为完 全多项式时间近似方案( 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 3 1 l ：启发式算法是一个基于直观或经验构造的算法在可以接受的花费 ( 指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一个可 行解，该可行解与最优解的偏离程度不一定事先可以预计 一7 第一章绪论 评价启发式算法的性能主要分为两类，一是看算法占用的时间、空间等， 二是分析算法的效率算法效率往往采用大规模的随机数据进行实验验证，从 平均的角度以及最坏的角度来进行衡量 定义1 3 1 2 ：分枝定界法( b r a n c ha n db o u n d ) 以巧妙地列举一个组合优化问题 的切可行解为依据分枝指的是把可行解集分为互不相交的子集，定界是计算 目标函数在给定可行子集上的下界如果这一可行子集上的下界大于或等于这一 时刻最小的目标函数值，就把这一可行子集杀死，这一过程称为剪枝。反复利用分 枝、剪枝和定界，找出函数值最小的可行解 定义1 3 1 3 ：动态规划( d y n a m i cp r o g r a m m i n g ) 方法是求解组合优化问题的一 个重要方法，特别适用于求解n p 一难问题它与分枝定界法思想有相同之处，也是 巧妙地穷举一个问题的所有的可行解动态规划方法是一个多阶段决策过程，其 基本思想是从最后的决策倒退地工作到较早的决策 1 4 论文概述 早期的算法研究只是关于离线问题的研究，但是随着社会的发展，涌现出了 大量的所谓在线问题。这些问题的本质是对未来的任务具有不可预测性，排序者 只知道当前已经到达的任务或工件的信息，而对未来的情况一无所知此时作为 一个决策者往往需要一个如何执行下一步任务的算法在这样的实际背景下，在 最近十几年的研究中，对于在线算法的研究迅速发展了起来本文研究了几个有 关在线平行机排序的问题，主要结果如下： 1 第二章主要研究了工件具有相同的加工时间1 有到达时间和交货期且 目标函数为极大化按时完工的工件个数的两台机在线排序问题首先，我们对 于m 台机时的问题给出了该问题的一个下界；其次，我们对于m 台机的情形给出 了一个简单的具有竞争比为2 的在线算法；最后，对于两台机的情形，我们给出了 一个最好的在线近似算法，而且算法满足“立即通知”的性质 2 第三章主要研究上一章中当m 2 时的问题为方便起见，我们考虑工件 具有相同的整数加工时间p ，且有非负整数到达时间和交货期，目标函数为极大化 按时完工的工件个数的仇台机在线排序问题易知对于任意的p ，该问题与上述问 题具有等价性对于该问题我们给出了一个具有“立即决定”性质的在线算法，并 证明了该算法的竞争比为t ( 1 一( m ，( m + 1 ) ) m ) ，其中当m 趋向于无穷大时，该竞 一8 一 第一章绪论 争比趋向于e ( e 一1 ) 1 5 8 2 另外，我们还给出了对于该问题具有“立即决定”性 质的在线算法的一些下界 3 第四章研究工件的加工长度任意，有到达时间和交货期，且工件可以“中 断重新”开始加工，目标函数为极大化按时完工的工件个数的m 台机在线排序问 题这里的可“中断重新”开始加工指的是工件在加工过程中可以被中断，但当算 法在下次执行此工件时必须从头开始加工对于该问题，我们首先给出了一个下 界百4 ，然后给出了一个竞争比为2 的在线算法最后简单考虑了单台机且工件有相 同的交货期的情形 4 第五章研究工件具有“任意”的到达时间，目标函数为最小化最大工件完工 时间( m a k e s p a n ) 的m ( m 2 ) 台机的在线排序问题这里的问题模型指的是工件 按一定先后顺序出现，只有当前面的工件被安排后才知道下一个工件的信息与 经典在线模型不同的是前面的工件的到达时间有可能比后面的工件到达时间要 大此问题可以看成是经典的在线模型( j o b sa r r i v eo v e rl i s t ) 的推广对于机器台 数m = 2 时的问题，我们给出了一个竞争比为2 的最好的在线算法对于一般的机 器台数为m ，并且所有工件都有单位时间加工长度时的问题，我们证明了l s 算法 的紧界为芸 9 第一二章工件具有到达时问和交货期的两台机的在线排序问题 第二章工件具有到达时间和交货期的两台机的在线排序问题 2 1 引言 在线排序问题是一类非常重要的排序问题在这一章，我们考虑工件 有“硬”交货期( h a r dd e a d l i n e s ) 的在线排序问题这里的“硬”交货期指的是任意 一个在其交货期之前未能按时完工的工件都将丢失工件是在线到达的，并且工 件加工过程中不可被中断很多的关于排序理论的经典结果都是关于离线情形 的，在线排序问题正在变得日益重要，尤其是在高速网络应用中工件有“硬”交货 期的排序问题在高带宽的多媒体应用( h i g h b a n d w i d t hm u l t i m e d i aa p p l i c a t i o n s ) 以 及共用分组网络( s h a r e dp a c k e t s w i t c h e dn e t w o r k s ) 中有着特别重要的应用在实 际的网络流的应用当中，由于带宽是有限的，所以很多问题可以归结为带有容许 控带l j ( a d m i s s i o nc o n t r 0 1 ) 的在线排序问题 本章研究带有在线容许控制的实时在线排序问题，问题可以正式描述如下： 给定m 台同型机( i d e n t i c a lp a r a l l e lm a c h i n e s ) ；每个工佑有到达时间r f ，这是事先 并不知道的，只有当工件j 到达后，我们才能知道它的交货期幽所有的工件的加 工时间都是1 工件在加工过程中是不可被中断的在任何时刻一旦有机器出现空 闲，我们不得不做出决定：是否开始加工一个“接受”的工件，如果是，那么选择哪 个工件去加工只能依据当前已经到达的工件的信息来做出决策那些不能在各自 交货期或之前按时完工的工件将会丢失目标函数是最大化在交货期或之前能够 按时完工的工件的个数 关于单台机器时的问题已有很多的结果对于工件有相同的加工时间的离 线情形下的问题，g a r e ye t a l 【1 3 给出了一个计算复杂性为0 ( 礼f 凹几) 的最优算法 对于在线情形下的问题，g o l d m a ne ta 1 1 6 分别给出了随机算法的一个下界；和 确定性算法的下界2 ，并且证明了一个简单的贪婪算法的竞争比为2 他们进一步 证明了如果所有工件歹的交货期满足d ，一7 ，2 ，那么这个贪婪算法的竞争比为g 这说明了如果所有工件都有充分大的松弛时间( d j r f ) 的话，那么可以得到竞争 比小于2 的在线算法进一步，g o l d w a s s e r 【1 4 对于该问题做出了个参数的推广： 如果对于所有工件j 米说都满2 ：d j r 3 1 + a ，这里a 0 是一实数，则竞争比可 以改进为1 + 裔石2 0 0 3 年g o l d w a s s e r 和k e r b i k o v 【15 】把前面的一些结果【1 4 推 广到算法带有性质“立即通知”( i m m e d i a t en o t i f i c a t i o n ) 的条件下这个条件要求决 一l o 第一：章工件具有到达时问和交货期的两台机的在线排序问题 策者在每个工件j 的到达时间做出以下决定：是否接受该工件? 如果是，则该工件 必须要在它的交货期或之前完工我们说“立即通知”( i m m e d i a t en o t i f i c a t i o n ) 这个 条件在实际中是合理的这是由于在实际的应用当中，工件可以看成为客户的某 个需求，当需求到达时，客户自然的可以要求在其到达时间被告知该需求能否被 满足若否的话，客户就可以避免了等下去而最后需求又不能被满足的结果 c h r o b a ke ta 1 5 】对于单台机最大化按时完工的工件个数问题给出了个竞 争比为；的随机算法而且对于另一模型：工件“可中断重新开始加工”模型( t h e p r e e m p t i o n r e s t a r tm o d e l ) ：即工件在加工过程中可以被中断，并且中断的工件可以 在后面从头开始重新加工，他们给出了一个最好的竞争比为；的在线算法 相比较而言，关于m 台机的研究结果很少离线情形下的m 台机时的问题 是多项式可解的【3 】对于在线情形l e e 3 6 】给出了一些结果在每个加工长度 为l 的工件j 都有至少尼l 的松弛的条件下，即d f 一吩k l 他给出了一个竞 争比为o ( 1 0 9 ( 1 k ) ) 的随机算法；对于m 2 ，给出了一个竞争比为m + 1 + 仇 ( 1 k ) ( 1 加) 1 的确定性在线算法 我们的结果如下：首先给出了该问题的一个下界；其次，对于机器台数 为仇时的问题给出了一个简单的竞争比为2 的在线算法；最后，对于两台机时 的问题给出了一个最好的在线算法，其竞争比为3 2 ，并且该算法满足“立即通 知”( i m m e d i a t en o t i f i c a t i o n ) 的性质 2 2 问题的下界 本节，我们给出当机器台数为m 时的问题的下界 定理2 2 1 ：对于工件长度为l 的m 台机的最大化按时完工的工件个数的问题，任 何确定性在线算法的竞争比都不小于 兄= 睫葛 证明：首先证明当m = 1 ，2 的下界在零时刻一个工件到达，该工件的交货期 为5 对于任何的在线算法a ，令t ( o t 4 ) 表示该工件的开工时间( 若算法 不在4 2 前开工，则此工件不能按时完工，这样导致算法的竞争比是无界的) 一 岛 l 2 一七 1 3 3 3 = = = l l 仇 仇 m m 第二- ：章工件具有到达时间和交货期的两台机的在线排序问题 在t + x ( o z 1 ) 时刻，m 个工件到达，它们的交货期为t + 1 + x 因此这m 个工 件中至少有一个工件不能按时完工，因此算法至多可以接受m 个工件但是显然 最优解可以接受所有的m + 1 个工件故当m = 1 ，2 时任何算法的竞争比都不会 d , , - t - ( 1 - - i - 去) 下面证明当m 3 时问题的下界在零时刻，一个交货期为5 的工件矗到达 对于任何算法a ，令t ( ost 4 ) 表示工件如的开工时间在t + x ( o x 1 ) 时 刻，p 个工件到达，并且这些工件的交货期都为t + 3 + z 令q 表示由算法a 安排 在t + 1 一z 之前开工的工件个数 i n s