（基础数学专业论文）工件有到达时间排序问题的ls算法分析.pdf

摘要 排序问题是组合优化领域中的一类重要问题，它是利用一些处 理机、机器或者资源，最优地完成一批给定的任务或作业，在生产 管理与调度、网络通信、理论计算机科学等方面有广泛的应用。 本文主要研究在m 台同型机上工件有到达时间的排序问题的l s 算法。目标函数是使机器的最大完工时间( m a k e s p a n ) 达到最小。 第一章介绍了排序问题，算法的竞争比分析等基本概念，描述了 ( 半) 在线排序和工件有任意到达时间的在线排序模型的一些特性。 第二章研究了m 台同型机上有到达时间工件的l s 排序问题，研究了 l s 算法的最坏性能比。给出了l s 算法的紧性能比的一个简单证明。 第三章讨论了m 台同型机上工件有到达时间且加工时间非增的l s 算 法问题，得到如下的两个结论，一个是证明了对于任意工件序列 三= 以，以，以) ，如果 ，i 眨名 且置最只，有 尺( 聊，三s ) 三一去；另一个是若到达时间为任意的且加工时间为单调非 增序列，则l s 算法的最坏性能比不大于2 。 关键宇：在线排序；订单排序；l s 算法；最坏情况性能比；半 在线；机器最大完工时间。 a b s t r a c t s c h e d u li n gi s a n i m p o r t a n t b r a n c ho fc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ， w h i c hu s e ss o m ep r o c e s s o r s ， m a c h i n e s o rr e s o u r c e st oa c c o m p li s ho p t i m a l1 yab a t c ho fg i v e nt a s k so r j o b s i th a sb e e n e x t e n s i v e l ya p p li e d i nt h ef i e l d so f m a n u f a c t u r em a n a g e m e n ta n da 1 1 0 c a t i o n ，n e t w o r kc o m m u n i c a t i o n ， t h e o r e m so fc o m p u t e rs c i e n c ea n ds oo n t h i st h e s i si sm a i n l y o nt h ea n a l y s i so ft h el i s ts c h e d u l i n g ( l s ) a l g o r i t h mf o rj o b s w i t hr e l e a s et i m e so n mi d e n t i c a lp a r a l l e lm a c h i n e s t h e o b j e c t i v ef u n c t i o ni st om i n i m i z et h em a k e s p a n t h r e ec h a p t e r s a r ei n c l u d e di nt h i st h e s i s i nc h a p t e ro n es o m ed e f i n i t i o n s ， n o t a t i o n sa n db a s i ci n f o r m a t i o na b o u tt h ec o m p e t i t i v e p e r f o r m a n c eo fa l g o r i t h m a r eb r i e f l yi n t r o d u c e da n dt h e c h a r a c t e r i s t i c so fm o d e lo fo n 一1i n e( s e m i o n li n e ) s c h e d u li n g f o rj o b sw i t hr e l e a s et i m e sa r ed e s c r i b e d i nt h es e c o n dc h a p t e r ， am u c hm o r es i m p l ep r o o fi sg i v e nf o rt h et i g h tp e r f o r m a n c e r a t i oo ft h el sa l g o r i t h mw h e nt h er e l e a s et i m e si sa n o n d e c r e a s i n gs e q u e n c e i nc h a p t e rt h r e e ，t h el sa l g o r i t h mi s a n a l y z e df o r t h es e m i o n li n es c h e d u li n gm o d e li nw h i c ht h e j o b s p r o c e s s i n g t i m e sisn o n i n c r e a s i n go r d e r t w or e s u l t s a r eg i v e n f i r s t l yi t i ss h 。w n t h a t 尺( 肌，朋) 主一玄 w h e n 1 吃吒 s e c o n d l yi tiss h o w nt h a tr ( m ，l s ) 2i ft h e r e l e a s et i m e sa r ea r b i t r a r y k e y w o r d s ： o n li n e s c h e d u l i n g ； o r d e rs c h e d u li n g ；l i s t s c h e d u li n g ；w o r s t c a s ep e r f o r m a n c er a t i o ；s e m io n 一1i n e ； m a k e s p a n 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承 学位论文作者签名：铷砌毅 8 玛。 湖南师范大学学位论文版权使用授权书 日 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 n( 请在以上相应方框内打“ ) ，作者鲐静磅魄砷年6 月 日 导师签名：歹车匀乡门、日期：力矽年 月77 日 工件有到达时间的排序问题的l s 算法分析 1 1 排序问题 第一章绪论弟一早珀t 匕 排序( s c h e d u l i n g ) 问题是组合优化中一类有着重要理论意义和 广泛实际背景的问题，其实质是寻求对需求完成任务的合理安排以得 到某种意义下的最优结果。它在生产管理与调度、网络通信、理论计 算机科学等方面有着广泛的应用。 近几十年来，排序问题得到了运筹学、工程学、管理学和计算机 科学界的极大关注，并且随着对经典问题研究的日趋深入，大量具有 实际背景的新问题不断涌现，使排序问题极具有生命力和研究价值。 可以这样说，对排序问题的研究正进入成熟期。 排序问题主要研究如何利用一些机器或资源，尽可能优地完成一 批给定的任务或作业。习惯上，我们把需要完成的任务称为工件( j o b ) ， 工件集用 ，以，以 来表示，把完成任务需要的资源称为机器 ( m a c h i n e ) ，机器集用 m ，心，坂) 来表示。工件以的加工时间大小 用肛表示。机器在加工这些工件的时候需要满足某些限制条件，如工 件的到达时问、完工的限定时间、工件的加工顺序、机器对加工时间 的影响等。我们希望找到一个可行的排序使给定的目标函数达到最大 ( 或最小) 。这里的可行一般指在同一时刻，一台机器最多只能加工一 个工件，一个工件也只能在一台机器上加工，并且该排序满足问题的 特定条件。 机器、任务和目标函数三要素组成了排序问题。机器的数量、类 高校教师在职硕士学位论文 型有很多种，任务和资源的约束条件更是错综复杂，再加上不同的目 标函数，形成了种类繁多的排序模型。我们一般用三参数表示法 ( t h r e e f i e l dr e p r e s e n t a t i o n ) 口，n 5 1 来表示一个具体的排序问 题，这是g r a h a m 等在c o n w a y 等提出的四参数表示法的基础上于1 9 7 9 年提出来的，其中口，和y 分别刻画了机器环境，工件特征和目标函数， 它们是排序问题的三个组成部分。 机器环境描述了机器数量、不同机器之间的关系等与机器有关的 性质。只有一台机器的排序问题称为单机( s i n g l em a c h i n e ) 排序问 题，否则称为多机排序问题。机器可以分成两大类：通用平行 ( p a r a l l e l ) 机；专用串联( d e d i c a t e d ) 机。平行机又可以分成三类： 具有相同加工速度的同型( 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 ) 机，在三参数表示法中分别用p 、q 、 r 来表示。串联机也分为三类：每一个工件以特定的相同的机器次序 在机器上加工的流水作业( f l o ws h o p ) 、工件依次在机器上加工的次 序并不指定可以任意的自由作业( o p e ns h o p ) 和每一个工件以各自特 定的机器次序进行加工的异序作业( j o bs h o p ) 。 工件特征一般可用工件的加工时间，工件可以开始加工的时间， 工件之间的依赖关系，工件在加工时是否可中断来刻画。在经典的排 序理论文献中，我们根据排序者在排序时掌握工件信息的多少把排序 问题分为离线( o f fl i n e ) 和在线( o n1 i n e ) 两类。在离线问题中， 全部工件的所有信息都己知，排序者可以充分利用这些信息来进行安 工件有到达时间的排序问题的l s 算法分析 排，而对于在线问题，其基本假设有两条：( 1 ) 工件的信息是逐个释放的， 即工件z + ，的信息只有在排序者对工件以，以，以作出安排后才会被排 序者所知。( 2 ) 工件加工不可改变，即一旦排序者将工件安排给某台机 器加工，在其后的任何阶段不能以任何方式进行改变。 但在实际问题中，大量的问题是介于两者之间的，即我们或者知 道该问题的一些整体信息，或者知道后续工件的部分信息。例如，已知 所有工件的总加工时间，或者已知工件按加工时间递减( 递增) 顺序 排列的等等。它们都不是离线问题，因为我们还不知道一共有多少工 件，它们的加工具体时间是多少。但与在线问题相比，这些信息可以用 来估计后续工件加工时间的范围，这是有利于算法设计的。于是，我们 把这样的排序问题称为是半在线的。 排序作为一个最优化问题的优化目标通常是一个一维实数，我们 用g 表示某一排序下工件以的完工时间，f = l ，2 ，刀，用j ，表示在某_ 排序机器m ，的完工时间，_ ，= l ，2 ，m ，记毫2 罂豸巳，践2 罂凳q 分 别称为最大机器完工时间和最大工件完工时间( 极小化目标) 。在经 典的平行机排序理论中，总是假设机器自零时刻开始就可以加工工件， 此时有c ：= c 二，统称为排序的m a k e s p a n ，记为，而当机器存在 准备时间时，两者未必相同。是一个最基本的目标函数。记 c m h2 罂曼l ，称为最小机器完工时间( 极大化目标) ，有时也称以此 为目标函数的排序问题为机器覆盖问题。常见的其他的目标函数还有 总完工时间，最大延误时间，最大误工时问等。 高校教师在职硕士学位论文 1 2 近似算法与竞争比分析 计算复杂性理论兴起于二十世纪六十年代，和算法的设计与分析 密切相关。通过几十年来人们在计算复杂性方面的研究，现今p n p 的猜想己被基本接受。如果我们接受p n p 的猜想，那么对于所谓的 n p h a r d 问题就不可能在多项式时间内找到最优解的算法，也就是说， 随着问题实例的规模的增大，对这种n p h a r d 问题的每一个实例要用 统一的算法找出最优解，从计算时间上来看几乎是不可能的。因此， 一个自然的想法就是放弃对最优解的寻找，而把研究的重点转向寻找 能在较短时间( 多项式时间) 内得到接近于最优解的可行解，称为近似 解。这种寻求近似解的算法称为近似算法j 衡量近似算法的优劣可从两个方面来看，一是算法的时间复杂 性，二是算法得到的解的值与最优解的值的接近程度。另外一个在实 际中常用的方法是对n p h a r d 问题作一些限制从而得到一些子问题， 使其具有多项式时间算法。这是因为一个问题是n p h a r d 的，并不能 排斥它的些特殊子问题是多项式时间可解的。由于绝大多数排序问 题是n p 难题，其最优解很难找到，而且在实际应用中往往也没有必 要去找到最优解，只需要找到满足一定要求的启发式解或近似解。因 此研究排序问题主要有两个方向。一是对p 问题，即可解( s 0 1 v a b l e ) 问题，寻找多项式时间算法( 又称为有效算法) 来得到问题的最优解， 或者对n p 难题在特殊情况下寻找有效算法也就是研究n p 难题的可解 情况。二是设计性能优良的启发式算法和近似算法。当然，无论是启 发式算法还是近似算法都应该是多项式时间算法。实际上，n p 难题 可解情况的多项式时间算法往往是可以作为n p 难题本身的启发式算 法和近似算法。 4 工件有到达时间的排序问题的l s 算法分析 衡量算法的“优良”程度有三种办法：数值算例计算，最坏情况 分析和概率分析n 引。这三种办法各有优点也各有不足，在理论分析( 最 坏情况分析和概率分析) 之前进行大量数值计算是非常有用的方法， 一则可以对理论分析给出估计和提供思路；再者可以与已有的算法进 行实际比较。顾名思义，最坏情况分析是分析算法在最坏情况下的形 态；概率分析是分析算法的“平均”形态。目前在理论上用得最多的 是最坏情况分析。 对于使目标函数f 为最小的优化问题，记，是这个优化问题的一 个实例，p 是所有实例的全体：并记f ( i ) 是实例，的最优目标函数值， 厶( ，) 是算法h 解实例，的目标函数值。如果存在一个实数r ( r 1 ) ， 对于任何i p 有厶( ，) 矿( ，) ，那么称r 是算法h 的一个上界。i 对 于使上式成立的最小正数r 称为是算法的最坏情况性能比，简称为最 坏比、最劣比，也称为是算法的紧界。 j ，7 对于使目标函数f 为最大的优化问题，同样可以定义算法的一个 下界和紧界。如果存在一个实数r ( 0 r 1 ) ，对于任何，尸有 厶( ，) 矿( ，) ，那么称r 是算法h 的一个下界，而紧界是使上式成立 的最大正数。 在最坏情况比的基础上逐渐形成了竞争比分析( c o m p e t i t i v e a n a l y s i s ) 法，俗称对手法( a d v e r s a r ym e t h o d ) 乜。它属于最坏情况 分析。对极小化排序问题，称 删两u p 器) 为在线( 半在线) 算法a 的竞争比( c o m p e ti t i v er a t i o ) ，这里巴( ，) 和 c = ( ，) 分别表示算法a 解实例i 所得的目标函数值和相应问题离线情 形的最优目标值：同样地，对极大化排序问题，称 高校教师在职硕士学位论文 删) - s u p 器) 为在线( 半在线) 算法a 的竞争比。若算法a 的的竞争比为c ，也称a 为c 一可竞争的。若不存在该问题竞争比小于c 的在线( 半在线) 算法， 则称在线( 半在线) 问题( 极小化目标或极大化目标) 的竞争比下界( 简 称为下界，l o w e rb o u n d ) 为c 。下界一般可以通过给出一系列实例使 得任何在线( 半在线) 算法都不能够很好地求解所有实例来得到。竞争 比反映了算法得到的近似解在最坏情况下与最优解的接近程度，下界 体现了一个在线问题由于部分信息未知而给求解带来的困难，这是不 依赖算法设计的固有性质，若算法a 的竞争比等于问题的下晃，就称 算法a 是最优( o p ti m a l ) 的算法，这是从竞争比的意义看一个在线算 法可以得到的最好的结果。 1 3 离线和在线排序 经典排序是假设排序问题一个实例的所有信息，包括工件的个 数、到达时间、加工时间等在开始排序前都是事先知道的。这种情况 称为是离线( o f f l i n e ) 的。对离线问题，已知的工件信息非常充分， 排序者可以对数据进行整序、运算、比较等操作以得到性能较好的算 法。其中l p t ( l a r g e s tp r o c e s s i n gt i m e ) 算法乜3 是经典平行机排序 问题的离线算法。由于在离线问题中，排序者在排序前知道工件的全 部信息，因此l p t 算法先把所有工件按加工时间的非增序排列，然后 依次将它们安排在能使其最早完工的机器上加工。 在线排序中，工件的信息是逐个释放的，在决定当前工件的加工 时，对其后面到达的工件的信息是一无所知的，并且一旦决定工件的 安排后就不允许改变。在线排序分为2 种： 工件有到达时间的排序问题的l s 算法分析 l 列表( o v e r1 i s t ) 在线排序：工件排列成一个表逐个出现，一 个工件只有当表中排在其前面的工件安排以后才“知道 这个工件的 有关信息。 2 时间( o v e rt i m e ) 在线排序：工件随着时间进行安排，在任何 时刻只“知道”当前已经到达工件的信息。 上述两种情况中工件安排后就不能够再改变了。所谓“知道”一 个工件是表示这个工件的加工要求已经清楚地给出。对于工件的在线 排序，g r a h a m 于1 9 6 9 年提出了一种l i s ts c h e d u l i n g ( l s ) 算法乜1 ， l s 算法按工件到达顺序将它们安排到能使其最早完工的机器上加工。 1 4 半在线排序 从前面的讨论可以看出，离线和在线是排序问题的两种极端对立 的情形。对离线来说，排序者知道工件的全部信息，而对在线来说， 排序者对后续工件的信息一无所知，甚至于不知道是否还会有工件到 达。因此，离线一般能够设计出比在线性能比好一些的算法。但是， 在实际问题中，出现上述两种极端情形的可能性都不大。现实中的问 题往往是介于两者之问。也就是说，对于现实中的在线问题，虽然工 件的全部信息不知道，但根据问题的实际背景，我们往往知道后续工 件的部分信息，而且常常是利用了这些部分信息后能够设计出比不利 用这些信息的在线算法性能更好的算法。我们把这样的问题称为半在 线( s e m io n l i n e ) 问题，相应的算法称为半在线算法。当然，半在线 问题的提法仅仅是为了与经典的在线问题进行区别。从排序者在做出 决定前那一刻并未掌握实例的全部信息以及一旦安排好某个工件就 不允许改变来看，半在线问题本质上仍然是“在线 的。因此，我们 仍旧沿用竞争比一词来研究半在线问题。若在给定的机器环境和目标 高校教师在职硕士学位论文 函数下，求解半在线排序问题的算法的竞争比严格小于相应在线问题 的下界，则说明此时该半在线模型是有价值的，它降低了问题的难度。 反之，若半在线问题的下界等于相应在线问题的最优算法的竞争比， 则说明此时该半在线模型不会使问题变得更为简单，因而没有价值。 自从人们在二十世纪九十年代中期提出半在线的概念以来，仅在 排序领域内就有十余个不同的模型出现。下面我们就简要地介绍几 个： l 预先知道工件总加工时间的半在线模型( s u m ) 。 假设所有工件的总加工时间p 预先知道。文 1 8 ，1 9 分别给出了 最i s 甜聊l c 帆x ，i s “朋i c 幽的竞争比为詈和；的最好算法。何勇、杨 启帆、谈之奕和姚恩瑜在文 2 1 给出了己l s “聊i c m x 的竞争比为 2 一j 一的半在线算法。 2 预先知道工件最大加工时间的半在线模型( m a x ) 。 假设所有工件中加工时间最大的工件的加工时间预先知道。何勇 和张国川在文 2 3 给出了罡i m a xl c 眦x 的竞争比为詈的最好算法。对 i m a x i c m i n 情形，何勇在文 1 8 给出了竞争比为；的最好算法。 3 预先知道工件从大到小到达的半在线模型( n o n i n c r e a s i n g j o b ) 。 假设工件按加工时间从大到小到达，g r a h a m 证明了l s 算法的竞 争比为昙一当乜1 。何勇等在文 1 2 给出当m = 2 时，l s 算法是最优算法， jj 刀， 其竞争比为吾。当m = 3 时只h 。刀一f 刀c 陀口s i n g 弘6 l 的下界至少为 工件有到达时间的排序问题的l s 算法分析 l + 3 7 6 。 另外，还有预先知道实例最优解值，预先知道工件加工时间落在 一区间内，工件加工时间非增( n o n i n c r e a s i n gj i b ) ，带缓冲区 ( b u f f e r ) ，工件分两批到达( t w o - b a t c h ) 等等半在线排序的模型。关 于这方面的讨论可参见综述文献 1 1 ，1 2 。可以预见，随着研究的不 断深入，将会有更多的半在线模型出现。 1 5 工件有任意到达时间的( 半) 在线排序 自从r lg r a h a m 阮1 提出第一个在线模型问题的算法以来，经过近 3 0 几年的研究与发展，目前在线排序模型可分为三类：第一种是r l ； g r a h a m 提出的古典在线模型心1 。第二种模型工件是有到达时间的，而 工件的到达时间和加工时间是预先未知的，只有工件到达后其加工时 间才变成已知，且只有这个工件被安排后下一个工件才能出现。第三 种模型是在第二种模型的假设条件下，再假设工件到达后其加工时间 仍是未知的，只有当其被加工完后才知道加工时间。 ： 需要指出的是，以上模型中工件的到达时间有一个共同之处，即 工件序列所对应的到达时间序列是一个不减序列，工件的信息是在工 件到达后才已知。另一类问题是工件的信息是在工件到达以前知道的， 这类问题就是我们通常所说的订单问题，工件的信息是以订单形式在 工件到达以前给出的，订单的到达并不代表工件的到达，工件的信息 ( 即订单) 先出现并不意味着工件的到达时间在先。决策者对工件的加 工是以订单的信息为依据来作出安排的。基于这样一种实际背景，我 们提出另外一种平行机的在线模型哺1 ，我们称为工件有到达时间的平 高校教师在职硕士学位论文 行机订单在线模型。这种模型假设工件的信息是在线给出的，工件的 信息没有实质上的到达时间，一个工件的信息到达后必须立即安排这 个工件的加工程序，且只有在这个工件的加工程序被安排后，下一个 工件的信息才到达。工件的信息包括两方面，一方面是工件的到达时 间，另一方面是工件的加工时间，工件序列所对应的到达时间序列不 是单调递增的。这个问题的正式定义如下：给定工件序列 三= “，：，。) 。工件，到达时间为0 ，加工时间为p ，( j = 1 ，2 ，n ) 。 假定当前待安排工件是，的订单，包含两部分信息：其一是到达时间 为尸f ，其二加工时间为p ，而且在安排它之前决策者不知道其他未 到达工件的任何信息。如果我们令所有工件的到达时间为零，那么该 问题就变成g r a h a m 的古典在线排序。 1 6 论文概述 本文主要研究m 台同型机上工件有到达时间的排序问题的l s 算 法分析。我们考虑的目标函数是使机器的最大完工时间( m a k e s p a n ) 达到最小。本文的结构是第一章介绍了排序问题和算法的竞争比分析 等基本概念，描述了( 半) 在线排序和工件有任意到达时间的在线排 序模型的一些特性。第二章研究了m 台同型机上工件有到达时间的 在线排序问题，给出了l s 算法，并将工件的到达时间分成到达时间 单调增加以及到达时间是任意的两种模型，分析了最坏情况下l s 算 法的性能比。第三章讨论了m 台同型机上工件有到达时间且加工时 间为单调非增序列的l s 算法分析，得到如下的两个结论，一个是证 工件有到达时间的排序问题的l s 算法分析 明了对于任意工件序列= 以，以，以) ，如果，i 吃且 e 只只，有尺( m ，三s ) 三一去；另一个是若到达时间为任意且加 工时间为单调非增序列，则l s 算法的最坏性能比不大于2 。 高校教师在职硕士学位论文 2 1 引言 第二章同型机上有到达时间工件的l s 排序 自从经典的胁台平行同型机上的在线排序问题由g r a h a m 在文【2 】 中提出，在线排序己被以不同的方式从不同的角度得到广泛的研究， 在经典的在线排序问题中，无论工件何时到达，排序者必须在对未来 工件毫无所知的情况下立即安排工件到某台机器上，目的是使得所有 工件的最大完成时间最少。h a l la n ds h m o y s 【3 1 推广了关于渤h a m s 所 提出的经典的肌台同型机在线排序问题，他们假设工件按照到达时间 逐个出现，后来“a n dh u a n g 【6 1 将问题进步地推广，在文【6 】中要求 工件以订单形式出现。在这种在线情形，假设工件的到达时间是任意 的。如果所有工件的到达时间都为0 ，那么“a n dh u a n g 【6 】的问题与 g r a h a m s 经典在线排序问题是一致的；如果工件的到达时间是不减序 列，则与h a l la n ds h m o y s 【3 】所提出的问题一样。因而它是指广义的在 线排序问题或者是具有任意到达时间的工件在线排序问题。对工件有 任意到达时间的在线排序问题，l ia n dh u a n g 【6 l 证明了l s 算法的最 坏性能比是r ( 加，三s ) ：3 一上，并给出了一个性能比不超过2 9 2 4 1 9 算 法m l s 。在文【1 3 】中给出了一个更好的性能比不超过2 7 8 4 3 6 的算法。 2 2 有关定义及算法 定义l 设工件序列l = j ，j ：，。) ，其中工件j ：j ( j = l ，2 ，n ) 的 工件有到达时间的排序问题的l s 算法分析 到达时问为l 且其加工时间为乃，有m 台同型机。算法a 是一个启 发式算法，巴( l ) 与c = ( l ) 分别表示算法a 的机器最大完工时间和 离线下最优情况的机器最大完工时间。算法a 的最坏性能比定义为： 川= s u p 器。 定义2 假定当前待安排的工件是j ，其到达时间为乃，加工时 问为乃，在机器m 上有相对于工件的一个空闲区间是指存在区间 【7 ：，正】满足： ( i ) 机器m 在区间【瓦，砭】内没有加工任何工件； ( i i ) m 在正时开始加工某一产品，五= o 或m 在7 i 时加工完某一 工件： ( i i i ) 互且正一正p ，。 很显然，在安排工件，的时候，如果机器m 有相对于i ，的空闲 时间段【瓦，咒】，则可安排，。在m 上的空闲区间 正，瓦1 上加工。 定义3 工件序列l = ，j ：。) 称为某结论的最小反例：若某结论 对工件序列l 不成立，但是对任意满足i 三，l 的工件序列它都 成立。 l s 算法 步骤1 假设厶是机器m ( f _ 1 ，2 ，3 ，肋) 上的排序完工时间。我们 根据厶岛乙对机器进行重新编号。假设以是最新的工件，其 到达时间为，加工时间为以。设s = m a x ，厶) 。 步骤2 假设有若干台机器上存在能够安排工件以的空闲时间区 间【五，艺】，那么我们选择其中具有最小墨的那台机器m ，并把工件以 高校教师在职硕士学位论文 安排到机器m 上，工件的开始加工时间为m a x 五，) 。否则转入步 骤3 。 步骤3 设s = m a x ，厶) ，工件以在机器m 。上以s 为开始加工时 间进行加工。 2 3l s 算法的最坏性能比 定理l 对于任意工件序列三= ，。，：，。) ，如果，i 吃， 则有 尺( 聊，s ) 2 。 此定理由h a l la n ds h m o y s 【3 】给出。 下面的定理2 给出了更准确的性能比。 定理2 对于任意工件序列三= 。，j ：，。 ，如果吒吃， 则有 r ( 掰，朋) = 2 一击。 ( 1 ) r ( m ，l s ) 的紧界( 定理2 ) 由l ia n dh u a n g 【7 】给出。这里我们给出定 理2 的另外一个更加简单得多的证明。 证明：利用反证法证明定理，假设( 1 ) 式不成立，则存在最小反 例l ，使得 躺江 设三= “，以，以 是具有最少工件数的反例，根据l s 算法，易 证噬( l ) = 厶+ 以成立。 工件有到达时间的排序问题的l s 算法分析 我们考虑以下两种情况的性能比。 下面两式是很明显的结论： 聊暖( ) ：。b ； 谨( 三) 仇。 情形1 工件序列l 的l s 排序不包含空闲时间。 在这种情形，我们得到 c 三：x ( ) 一上+ p 门：。( 三，+ p 以) c ：2 ( l )c ：2 ( l ) 一所c ：量( l ) ：。p ，+ ( 聊一1 ) p h 聊c 婴( ) m c 黧( ) + ( 聊一1 ) c ：2 ( 三) 一 朋c = ( 上) = 2 一土。 情形2 在l s 排序中，至少存在一个空闲区间，在此期间有一台机 器是空闲的。设【口，6 】是空闲区间，其中b 是所有空闲区间中的最大值， 设。s = l ，2 ，n ) 为工在l s 排序中的开始加工时间，并设 e = l s ( 厶) 6 。 容易看出排序中当前工件，f 的执行在b 之后的而在其它排序中可执 行在b 之前的最大加工时间是m i n b ，i 。设 高校教师在职硕士学位论文 = m i n 6 ，m a x ji l ，聊 ， 材f 是由l s 算法产生的机器必上的总空闲时间，因为至少有一个 ，= o ，从而有： ， l ，c = x ( l ) 一厶+ 以 。聊、口( ) c 黧( ) 三! ! 刍垦! 一所暖( 三) 4 且m = 2 时，l s 算法的最 坏性能比是丢箸去；文【5 】预先知道所有工件的总加工时间；文【4 】预 先知道工件的最大加工时间以及所有工件加工时间属于区间 p ，垆】， 其中p o ，l ；文【4 ，8 】工件加工时间非增等等。近来有更多关于半 在线排序算法出现于【l ，9 ，l o 】。本章讨论在m 台同型机上工件有到达 时间且加工时间为非增序列的l s 算法分析。 3 2 工件有到达时间且加工时间为非增序列的l s 算法分析 定理4 对于任意工件序列= ，如，以 ，如果吃 且p l p 2 p 。，那么 工件有到达时间的排序问题的l s 算法分析 尺( 吼s ) 三一去 ( 2 ) 证明：利用反证法。假设( 2 ) 式不成立，则存在工件序列l ，使得 鬟艘 三一上 c 器( 三) 2 2 朋。 设己= 以，以，。) 是( 2 ) 的最小反例，对这个序列，由l s 算法， 易证c 念( l ) = 厶+ 以成立。 首先我们将l 规范化，使得，i = o 。因为若巧o ，我们可以通 过将所有工件的到达时问减少吒来实现。这种改变将l s 排序和最优 排序的总完工时间减少相同的时间_ ，而完工时间比增大。从而改变 后的工件序列仍然是工件数最少的反例。i 。 接下来我们证明，在l s 排序中，在c 怂( 三) 之前，至少有一台 机器不是空闲的。否则，则在l s 排序中，在罐( ) 之前存在一个 共同的空闲时间段。这样一来，根据l s 算法规则，安排在这个共同 的空闲区间之后的工件必须在这个时间以后才到达，如果我们除去在 这个空闲时间之前完成的工件，则l s 算法的总完工时间m a k e s p a n 不发生改变，然而相应的最优完工时间不增加。因此，这个新的工件 实例具有更少的工件数，从而与最小性矛盾。 现在我们考虑以下两种情形的性能比： 情形l ：工件序列l 的l s 排序不含有空闲时间。 在此情形，我们可以得到： 3 l c 念( 三) 一厶+ 见 2 2 朋、口( 三) 曙( 三) 高校教师在职硕士学位论文 z 7 聆，朋厶z 7 一，门一z 乃 p 聆 i 厶l f 朋q 一 只 i 厶1 垡门一l “ 暖( 三) 。朋暖( ) 曙( ) 。珑爱( 三) ! 竺二! ! 旦+ 尘! 呈三丝丝 掣。 这意味着在任意的最优排序中，任意一台机器至多只有一个工 件。于是，工件序列l 至多只有m 个工件。容易看出，如果在工件 序列l 至多只有m 个工件，那么l s 排序是最优的。矛盾。 情形2 ：l s 排序中一台机器至少存在一个空闲区间。 在此情形，设【口，6 】是空闲区间，其中b 是所有空闲区间中的最大值。 取彳= k 是在l s 排序里在时刻b 后完成的工件) 。 设b 是a 的子集，它包含开始于以或口之前的所有工件。用 s ( ，) ( _ = l ，2 ，2 ) 表示l s 排序中工件的开始时间于是集合b 可 以表示为以下形式 b = j 6 一马 口。若某工件 彳b ，同时满足o 6 且，： s ( ) ，下面我们可以推出矛盾。根 据假设，区间【口，6 】的长度大于零，在l s 排序中至少有一台机器在此 区间是空闲的。设机器m 在【口，6 】区间空闲，安排工件的机器为 m 更进一步地，分别设机器m 和m ，的完工时间为叠，和叠? ) 。 工件有到达时间的排序问题的l s 算法分析 因为一 s ( ) 且工件被安排到机器m ，上，则有口 s ( ) = 蟛。 另一方面，由0 c 景量( 三) 。 这意味着在任何最优排序中最多只有一个工件能被安排在b 之后。在 此条件下，不难证明尺( 朋，三s ) 三一击成立。 定理5 对于任意工件序列= 以，以，以) ，如果 p l 见成且工件的到达时间是任意的，则有： 尺( 朋，l s ) 2 。 证明：下列不等式是显而易见的： 聊c = ( 三) ，：。b ； c 三娶( l ) m a x ，i + p l ，吃+ p 2 ，+ p ”) 。 设是由l s 算法产生的机器够上的总空闲时间( 江1 ，2 ，聊) ，更 进一步地，可得： 工件有到达时间的排序问题的l s 算法分析 “，+ 仇c 器( ) ，江1 ，2 ，聊 因为工件以+ 的加工时间是最短的，不失般性， 设g 急( ) = 厶+ 仇，于是得到： 堡垒= 刍丝 兰! ! 刍鱼2 口( 三) 口( 三) 一m 暖( 三) ：。乃+ 三，( 吩+ 见) 一见 。 聊谨( 三) q 一南“。聊锱( 三) 。 3 3 小结 本章讨论了m 台同型机上工件有到达时间且加工时间为单调非 增序列的l s 算法分析，证明了对于任意工件序列三= “，以，。) ， 如果，i 乞，；f 且n 仍b 见，那么尺( 朋，船) 寻一去；当到达时间 zz m 任意而a 仍儿时，证明了l s 算法的最坏性能比不大于2 。 本章我们研究的是几个半在线排序问题的l s 算法分析，考虑的 目标函数是使机器的最大完工时间( m a k e s p a n ) 达到最小。如果我们 将机器由具有相同速度的同型机改为具有不同速度的同类机，上述几 个半在线排序问题的l s 算法的最坏性能比又是什么? 更进一步需要 研究的是怎样设计比l s 算法更好的半在线算法。 高校教师在职硕士学位论文 总结与展望 本文主要研究m 台同型机上工件有到达时间和非增加工时问的 l s 排序问题。我们考虑的目标函数是使机器的最大完工时间 ( m a k e s p a n ) 达到最小。文章首先研究了m 台同型机上工件有到达 时间的在线排序问题，给出了l s 算法，并将工件的到达时间分成到 达时间单调增加以及到达时间是任意的两种模型，分析了最坏情况下 l s 算法的性能比。对于任意工件序列三= “，j ：，j 。 ，如果 ，i 吃，则有尺( m ，s ) = 2 一去。并给出了该结论的一个简单证 明；对于任意工件序列三= “，：，。 ，如果工件的到达时间是任意 则有尺( 朋，三s ) ：3 一土。然后研究的是几个半在线排序问题的l s 算法分析，证明了对于任意工件序列三= ，j ：，。 ，如果 ，i 吒厶且p l p 2 以，那么r ( m ，s ) 昙一去。当到达时间任 。 z2 胁 意而a p ：见时，证明了l s 算法的最坏性能比不大于2 。 关于工件有到达时间的在线( 半在线) 排序问题还有许多有待解 决的问题，如果考虑机器速度不同、带机器准备时间、分批排序等诸 多因素，寻找性能优良的排序算法及其证明都是一项十分困难的工 作。这是因为这类问题基本上都是n p “a r d 的。 对于排序问题的研究目前以及以后的若干年，仍将是国际热点。 随着研究的深入，将涌现出更多的排序模型，不同的模型需要用不同 的方法去处理，有时，即使是同一模型，由于参数取值范围的不同， 工件有到达时间的排序问题的l s 算法分析 问题的难度就有天壤之别。这些问题都有待于研究者深入思考，进一 步研究。 参考文献 1 d 6 s a ，g h e ，y ， s e m i o n l i n ea l g o r i t h m sf o rp 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 j c o m p u t i n g ，v 0 1 7 2 ，p p 3 5 5 3 6 3 ， 2 0 0 4 2 g r a h a m ，r l ：b o u n d so nm 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 j s i a mj a p