(基础数学专业论文)工件有到达时间排序问题的ls算法分析.pdf_第1页
(基础数学专业论文)工件有到达时间排序问题的ls算法分析.pdf_第2页
(基础数学专业论文)工件有到达时间排序问题的ls算法分析.pdf_第3页
(基础数学专业论文)工件有到达时间排序问题的ls算法分析.pdf_第4页
(基础数学专业论文)工件有到达时间排序问题的ls算法分析.pdf_第5页
已阅读5页,还剩27页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 排序问题是组合优化领域中的一类重要问题,它是利用一些处 理机、机器或者资源,最优地完成一批给定的任务或作业,在生产 管理与调度、网络通信、理论计算机科学等方面有广泛的应用。 本文主要研究在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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论