（运筹学与控制论专业论文）一致平行机上在线排序.pdf

摘要 排序问题是经典组合优化的问题，在线排序是排序论当前研究的热点 问题之一本文主要考虑一致平行机器上工件有到达时间一些在线模型， 并分析算法下的竞争比全文共分三章 第一章是绪论部分，主要介绍排序问题，竞争比分析和近似算法等基 本概念，总结近年来出现在线模型及其有关的结论 第二章考虑工件到达时间任意，机器加工速度为岛= 1 ( 1 i m 一 1 ) ，s 。= s 1 ，目标函数为极小化最大机器负载的在线模型，主要讨论两个 问题：1 当m = 2 时，给出来竞争比为2 + 三且界是紧的2 m 台同类机器的 5 n ，、 情形，根据l s ，算法并证明此算法的竞争比为3 + 墨掣 若t 。t 1 第三章讨论了工件有到达时间任意，机器加工速度为s 。，s 2 ，s 。( 8 ， s 2 s m ) 在线排序问题，目标函数为极大化最小机器负载的在线模 型提出了新的算法，并证明了算法下的竞争比为常数2 0 关键词：在线排序问题，竞争比，空闲，同类机器 a b s t r a c t s c h e d u l i n gp r o b l e mi st h ec l a s s i c a l lc 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 锄，o n l i n e s c h e d u l i n gi so n eo ff o c a lp r o b l e m si n 、髑t i g a t e di ns c h e d u l i n ga tp r e s e n t t l l i st h e s i s m a i n l yd e a l sw i t hs o m em o d e l sw h i c ha r ej o b 8r e l e a s et i m eo nu n i f o r mm a c h i n e s a n da l g o r i t h i 璐c o m p e t i t i v ea n a l y s i s t h et h e s i 8a r em a d eu po ft h r e ec h 印t e r 8 i nc h a p t e r1 旭百v eab r i e fi n t r o d u c t i o na n db a u s i cn o t i o no f 妯e d u l i n gp r o b _ l e m ，c o m p e t i t i 、r ea n a l y s i s ，印p r o 茹m a t i o na l g o r i t h m s u m m a r i z eo n l i n em o d e l sa n dt h e i r r e s u l t 8w h i c ha p p e a ri nr e c e n ty e a r s c h a p t e r2i n v e s t i g a t e st h eo n l i n es c h e d u l i n gm o d e lf o rj o b sw i t ha r b i t r a l 了r e l e a s e t i m ea n dm a c h i n e si sas p e e do 级= 1 ( 1 i 仇一1 ) ，s 。= s 1 t h eg o a li 8 t om i n i m i z et h em 脚m u mm 村l i n ec o m p k t i o nt i m e i nt h ec h a p t e r ，w em a j n l y c o i l s i d e rt w op r o b l e i n s ：1 w h e nm = 2 ，w ep r e s e i l tat i g h tb o u n do ft h ep e r f o r m a n c e r a t i 0 2 + 2 f o rt h ec a u s e 。fml l n i f o mm 溅n e sw ef o u 。w e r 铺l s ，a 1 9 0 r i t l l ma n d s 8 h o wi t sc o m p e t i t i v er a t i ol s 3 +2 ( m 一1 ) s + m 一1 i nc h a p t e r3w ec o i l s i d e rt h eo n l i n es c h e d u l i n gp r o b l e 脚f o rj o b s 丽t ha r b i t r a 叮 r e l e a s et i m ea n dm 纵血i i l ei sas p e e do f s l ，s 2 s m ( s 1 s 2s s m ) ，w h e r et h e g o 甜i st om i n i m 眈t h em a 函m u mm a l c h i n ec o m p l e t i o nt i m e w r eg i v en e wa l g o r i t h m a n d p r o 、r et h ec o m p e t i t i v er a t i oi sc o u n t2 0 k e yw o r d s ：0 1 1 l i n es c h e d u l i n gp r o b l e m ，c o m p e t i t i v er a t i o ，m 出【e s p a nm l i f b r m m a c h i n e i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何 其他个人或集体已经发表或撰写过的作品成果，对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本声明 的法律结果由本人承担 学位论文作者签名：仍哆穸加夕彩月g 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权单位属湖南师范大学同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借凰本人授权湖南师范大学可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打“ ”) 作者签名： 导师签名： 炳西衫 磊眷均 日期略月钼 日唧年月留日 一致平行机上在线排序 1 绪论 1 1 组合优化简介 组合优化又称离散优化它的一个通俗定义是指在离散的，有限的数 学结构上，寻找一个( 或一组) 满足约束条件并使其目标函数达到最小或 最大的解其正式定义如下： 定义1 1 1 ：组合优化问题是一个极小( 大) 化问题，它由下述三部分 组成： ( 1 ) 实例集合； ( 2 ) 对每一个实例，有一个有穷的可行解集合s ( n ( 3 ) 目标函数，它对每一个实例，和每一个可行解集合盯s ( n 赋以 一个有理数，( ，矿) 如果该问题是极小( 大) 化问题，则实例j 的最优解为这样个可行解矿 s ( i ) ，它使得对所有的伊s ( ) ，都有，( ，仃+ ) ，( ，矿) ( 或，( j r ，矿) ，( ，伊) ) 组合优化是一门古老而又年轻的学科，说他古老，是因为一些组合优 化问题有着悠久的历史渊源著名数学家费马( f e m a t ) 欧拉( e u l e r ) 等都 对它们进行过相关的研究说它年轻，是因为其作为运筹学的一个独立分 子而发展起来还是近几十年的事二十世纪后半叶，伴随着工业科技革命 和现代管理科学的发展，特别是计算机技术突飞猛进和在各行业的广泛 应用，组合优化已壮大成为一门新兴的学科分支一些百年前数学家们偶 然想到的问题和方法，现在已经在网络通信，物流管理，交通规划等领域发 挥了重要作用，这是他们当时所不曾想到的这正预示了此学科的巨大发 展前景 尽管大部分组合优化问题可以转化为整数规划( 或混和整数规划) 问 1 硕士学位论文 题，但由于整数规划的求解同样也是困难的，而组合优化又涵盖甚广，因此 人们致力于研究各个问题的组合结构，试图找到一些好的性质和有针对 性的求解方法 常见的组合优化问题有划分问题( p a r t i t i o np r d 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 gp r o b l e m ) ，背包问题( k n a p s a c kp r o b l e m ) ， 指派问题( a s s i g i l m e n tp r o b l e m ) ，旅行售货商问题( n a v e u i n gp r o b l e m ) ，斯坦纳 最小树问题( s t e i n e rm i i l i m a ln e ep r o b l e m ) 等网络中的组合优化问题还包 括最短路问题( s h o r t e s tp a t hp r o b l 锄) ，最小生成树问题( m i n i m a ls p a n 血g n e ep r o b l e m ) ，最大流问题( m 躲f l o wp r o b l 锄) ，最小费用流问题( m i n - c o s t f l o wp r o b l e m ) 等组合优化全貌参见【1 ，2 】在此，只对本文研究的排序问题 作一下介绍 1 2 排序问题 排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问 题其实就是寻找需要完成任务的合理安排以得到某种意义下的最优结 果【3 ，4 1 它在理论计算机科学和离散组合数学也存在着密切的联系近几 十年来，排序问题得到了运筹学，工程学，管理学，和计算机科学的极大关 注，并且随着对经典问题研究的日趋深入，大量具有实际背景的新问题不 断涌现，使排序问题极具有生命力和研究价值可以这样说，对排序问题 的研究正进入成熟期 按照学术界多年来形成的惯例，我们把需要完成的任务称为工件o o b ) ， 把完成任务需要的资源称为机器( m a c h i n e ) ，我们希望找到一个可行的排序 ( s c h e d u l e ) ，使得某个给定的目标函数达到最大( 小) 这里了性一般指在同 一时刻，一台机器至多加工一个工件，一个工件排序也只在一台机器上加 2 一致平行机上在线排序 工，并且该排序满足问题的约束条件 排序问题按照静态( s t a t i c ) 和动态( d y n a i i l i c ) ，确定性( d e t e r m i n i s t i c ) 和 非确定性( n o n d e t e r 耐n i s t i c ) 可以分为四类对于静态的确定性排序问题， 我们习惯上用三参数法来表示。1 9 6 7 年c o n 锄y f 5 | 等首先提出用四个参数 来表示排序问题，1 9 7 9 年g r a h 啪 6 】等提出改用三参数即用q 俐7 来表示 一个排序问题其中q ，p ，y 分别代表特定的机器环境，工作特征和最优准 则 机器环境用来描述机器的数量，不同机器之间的关系等与机器有关的 性质机器可以分为两大类：通用平行机( p a r a l l l e l ) 和专用串联机( d e d i c a t e d ) 对于不许中断加工的情况来讲，一个工件在矾台平行机器上加工 只需要在仇台机器中的任何一台机器上加工一次即可；一个工件在m 台 串联机上的加工则需要在这m 台机器中的每一台机器上都加工一次常 见的平行机类型有： 同型平行机( i d e n t i c a lp a u r a j l e lm a c h i n 骼) ，即所有机器的加工速度一 样，通常用p 表示若写成p m ，则表示系统中共有m 台同型平行机且m 为固定常数； 一致平行机( u n i f o r mp a r a j l e lm a c h i n 稍) ，即机器有各自不同的速度， 但任意工件在不同机器上的加工时间有相同的比例关系，通常用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 表示 串联机也可以分为三类：每个工件以特定的相同的机器次序在机器上 加工的流水作业( a o ws h o p ) ，工件依次在机器上加工的次序可以任意的 自由作业( 叩e ns h o p ) 和每一个工件以各自特定的机器次序进行加工的异 序作业0 0 bs h o p ) 工件特征一般是指工件的各种加工信息，包括工件的加工时间，工件 3 硕士学位论文 的到达时间，工件之间加工顺序以及工件和其开工时间的依赖关系，工件 加工时间是否允许中断以及中断恢复后再加工时是否要接受惩罚等等根 据排序者对工件信息的了解程度，又可以将排序问题分为离线( o m i n e ) ，在 线( o n l i n e ) 和半在线( s e m i - o n l i n e ) 三类在离线问题中，全部工件的所有 信息都已知，排序者可以充分利用上述信息对工件进行安排，而对在线问 题，其基本假设有两条：( 1 ) 工件的信息是逐个释放的，即工件p j + 。信息只 有在排序者对工件p t ，仇，功作出安排后才会被排序者所知道；( 2 ) 工件 加工不可以改变，即一旦排序者将工件安排给某台机器加工，在其后的任 何阶段不能以任何方式加以改变1 9 9 6 年出现了一种新的排序概念半在 线排序问题在实际问题中，出现离线和在线的情况并不多，大量存在的 问题是排序者一方面不可能知道工件的所有信息，另一面可能掌握着笔 经典在线模型更多的信息或有着更大的排序自由度，因此使问题变得比 离线相对困难些，但比在线相对容易些在1 9 9 6 后，各种不同的半在线模 型，随之何勇等【1 4 ，1 5 】把半在线模型分为3 类把排序者掌握后续工件的 部分信息，称为第一类半在线排序模型；把已安排的工件加工进程可通过 某种方式加以改变，称为第二种半在线模型；不能列入这两类的半在线模 型统称为第三类半在线模型 最优准则通俗的讲，就是以什么为目标函数排序问题中的目标是多 种多样的常见的是机器数给定，对完工时间这一目标寻求最优按全部机 器的完工时间可分为两类：一类是使最后一台完工机器的完工时间达到 最小，简称为极小化最大机器完工时间，通常用g m = 仇口z c k 表示另一 类是使最早一台完工机器的完工时间达到最大，简称为极大化最小机器完 工时间，通常用c k 。= m 锄c k 表示按全部工件的完工时间可分为两类： 一类是使最后一个完工工件的完工时间达到最小，简称为极小化最大工 件完工时间，通常用g 。= m n z o 表示另一类是使最早完工工件的完工 时间达到最大，简称为极大化最小工件完工时间，通常用n = m 饥。表 4 一致平行机上在线排序 示当机器准备时间为。时，显然有c i m 。霉( m ) = c 啪z ( j ) ，c k 。( m ) = c k 。( j ) 因此，在不引起混淆的情形下常用g 眦或c 名n 表示目标函数有关排序 问题的综述，可参见【7 ，8 】， 1 3 算法和计算复杂性 定义1 3 1 ：算法是指一步步求解问题的通用程序，它是解决问题的程 序步骤的一个清晰描述确定性算法从前一步到后一步的运行由当前状 态唯一确定如果存在一个算法，它对组合优化问题丌的每个实例，在有 限步后一定可以得到该实例的关于丌的提问的答案，那么称该算法解此 组合优化问题丌 定义1 3 2 ：对于一个组合优化问题丌，如果给定任意一个实例，算法 a 总能找到一个可行解伊s ( n 那么就称a 为丌的近似算法( a p p r o 癖 m a t i o na l g o r i t h m ) ；如果进一步这个可行解的目标值总等于最优解值，则 称a 为最优算法( o p t i i n a l la l g o r i t h m ) 解离线问题的算法称为离线算法，相应地，解在线问题的算法称为在 线算；去其中，l s ( h ts c h e d u l i n g ) 算法( 9 】和l p t ( l a r g e s tp r o c e s s i n gt i m e ) 算 法【1 0 】分别是经典平行机排序问题的在线和离线算法由于在离线问题 中，排序者早排序前知道工件的全部信息，因此l 尸t 算法先把所有工件按 加工时间的非增序排列，然后依次将它们安排在能使其最早完工的机器 上加工而对于在线问题，在排序进行过程中后续工件的信息是未知的， 因此l s 算法将工件按到达的先后排序安排在能使其最早完工的机器上 加工 通常算法所用的时间是指算法中所含的加，减，乘，除，比较等基本运 算次数而算法所用的时间与实例的规模有关，为此我们用输入长度来刻 划实例的规模所谓实例的输入长度通常是指实例所用的计算机内存单 5 硕士学位论文 元数 定义1 。3 3 ：算法的时间复杂性是指关于实例输入长度挖的函数，( 住) ， 用来表示算法的时间需要，对每一个可能的输入长度，它是指在最坏情况 下该算法解此输入长度的实例时所需时间( 基本运算步数) 即对于输入 长度相同的所有实例，把算法对这些实例的最坏情况作为时间复杂性的 度量 如果存在一个多项式函数p ( n ) ，使得算法的时间复杂性为d ( p ( 佗) ) ，那 么称该算法为多项式时间算法，否则称为指数时间算法还有一类算法叫 伪多项式时间算法，它的时间复杂性是关于实例输入长度他和实例中最 大数的二元多项式函数在二进制编码下，伪多项式时间算法并不是多项 式时间算法，而是指数时间算法由此出发，可以导出计算复杂性理论的 一系列重要概念和结论【1 1 】 通过几十年来人们在计算复杂性方面的研究，现今p p 的猜想已 被基本接受所谓的p 一 o r d 问题就不可能在多项式时间算法内找到最 优解从而，一个自然的想法就是放弃对最优解的寻找，而把研究的重点 转向寻找能在较短时间( 多项式时间) 内得到接近于最优解的可行解，称 为近似解这种寻找近似解的算法也就是近似算法 定义1 3 4 ：丌是一个极小( 大) 化问题，j 是任意实例设a 是丌的一个 近似算法用吼( j ) 和刀( ，) 分别表示算法a 解实例，的目标函数值和 离线情况下实例，的最优目标函数值记p a = 害坐煞为近似算法的最 坏情形比 在最塔隋形比的基础上逐渐形成了竞争比分析法( c o m p e t i t i v e r 8 t i om e t h o d ) 俗称对手法( a d v e r s a 叮m e t h o d ) 1 2 ，1 3 】它属于最坏情况分析对极小化排序 问题问题，称 p a = i n ， p 1 l p a ( ，) p ，v ，】 6 一致平行机上在线排序 为在线( 半在线) 算法a 的竞争比( c o m p e t i t i v e ) 而问题丌的下界( 1 0 1 盹r b o u n d ) 定义为 f ( 7 r ) = i n ， i p a ( j ) f ，v a ) 同样地，对极大化排序问题问题，称 肌= s 叩 p 1 i 吼( ，) p ，w ， 为在线( 半在线) 算法a 的竞争比( c o m p e t i t i v er a t i o ) 若算法a 的竞争比 为p ，也就称a 是p c d m 卵删秒e 的而问题丌的上界( s u p p e rb o u n d ) 定义 为 ( 7 r ) = s 叼矧纵( ，) 。v a 如果以( 丌) = ( 7 r ) ，则称算法a 对于问题丌来讲是最优的( o p t i m a l ) 在不引起混肴的前提下，我们通常将上述定义中的( n 刀( n 肌( 丌) 分别简记为吼，驴，朋 定义1 3 5 ：启发式算法是一个基于直观或经验构造的算法在可以接 受的花费( 指计算时间，占用空间等) 下给出待解决组合优化问题每一个 实例的一个可行解该可行解与最优解的偏离程度不一定可以事先预计 评价启发式算法的性能只要分为两类，一是看算法占用的时间，空间 等二是分析算法的效率算法效率往往采用大规模的随机数据进行实验 验证，从平均的角度以及最坏的角度来进行衡量 7 硕士学位论文 1 4 论文概述 本文主要研究了工件有到达时间的一致平行机在线排序问题，模型假 设如下：有n 个彼此独立的工件，= ，以，厶) ，需要在m 台一致平行 机器m = m ，尬，) 上加工，其中岛表示第i 台机器舰的加工速 度，工件乃的大小为乃且到达时间为巧，如果工件乃放在机器坛上加 工则加工时间为( 譬，歹= 1 ，2 ，n ，i = 1 ，2 仇) 工件是一个一个独立地到 来，仅在当前工件安排后才知下一个工件的全部信息工件在加工时不允 许中断，机器在没有加工工件时机器这时候为空闲的工件一旦安排好不 允许以任何方式加以改变 对于一致平行机排序问题，通常考虑两种类型的竞争比分析，一种是 把问题的下界和算法的竞争比都视为机器速度s 。，s 2 ，s m 的函数，以下 分别称为参数下界和参数竞争比另一种是考虑参数下界和参数竞争比在 & 1 ，i = 1 ，2 ，m 时的极大值，分别称为常数下界和常数竞争比本文主 要针对两类一致平行机的在线问题，第一类s 产1 ( 1 i m 一1 ) ，= s 1 第二类1 = s 1 s 2 s m 本文的主要结果如下： 在第二章中，我们主要讨论工件到达时间是任意的，机器加工速度为 瓯= 1 ( 1 i m 一1 ) ，s m = s 1 ，根据著名的三s 7 算法当m = 2 时得出了竞 争比为2 + 兰并证明了三算法是紧的，当m 机器时竞争比为3 + 3 竺兰 5 甚十：| | t 一1 在第三章中，我们主要讨论工件到达时间是任意的，机器加工速度为 s ，& ，8 针对三s 7 算法提出了新的算法a ，并证明了算法a 的竞争比 为常数2 0 8 一致平行机上在线排序 2 机器加工速度为1 ，s 的一致平行机上厶s 7 算法 2 1 引言 文章讨论m 台一致平行机的在线排序问题，目标为极小化机器最大 完时间，模型如下扎个彼此独立的工件，= ，以，五) ，需要在m 台一 致平行机m = 尬， 上加工，s t 表示第t 台机器舰的加工速 度，m 台一致平行机加工速度为s 。= s 2 = = s t = 1 ，s 仇= s 1 工件如 的大小为所且到达时间为巧，工件乃放在机器尬( i = 1 ，2 ，m 一1 ) 上则 加工时间就是为p ，如果放在机器a 如上则加工时间为盟工件是一个 一个独立地到来，仅在当前工件安排后才知下一个工件的全部信息工件 在加工时不允许中断，机器在没有安排工件，工件还有来到达时机器在这 时候就是空闲的工件一旦安排好不允许以任何方式加以改变对于这类 问题，所指的l s 7 算法是按照最早完工的贪婪原则来安排工件，即将当前 到达的工件安排在能使其最早完工的机器上加工 对于同型机且工件到达时间为零问题，g 妇在解i i 提出了解 在线问题的著名的l 算法g r a h 锄证明了l 算法竞争比为2 一1 8 9 8 年蹦g e ，k e m ，m 龃证明当m = 2 ，3 时算法l 为解此问题是最优在线算 法对m 4 文【1 6 】证得l s 7 算法得竞争比下界为l + 以= 1 7 0 7 之后 对m 芝4 时，b a r t e l e t a 1 进一步证得竞争比的下界为1 8 3 7 c h e n e t a l 给出了 m l s 算法优于l s 算法，当4 m 2 0 是目前最好的算法，m 足够大时，类 似于己s 7 算法其竞争比也趋近2 1 9 9 7 年a l b e r s 证明当仃l 8 0 时i i 竞争比下界为1 8 5 2 ，并给出了竞争比为1 9 2 3 的近似算法，中间的间隙已 足够小 对于工件到达时间不为零同型机器问题，这类模型首先由玩日u 口n g ( 2 0 0 4 ) 2 0 】提出的，在这篇文章中得到了以下结论：1 ，l s 7 算法得到竞争比为3 一圭 ， 9 硕士学位论文 并证明了l s 7 算法是紧的2 ，当m 2 时提出了一种优于l 算法的m l s 3 ， 证明了在启发式算法中，没有一个算法得到的界会小于2 对于一致平行机上且工件到达时间为零这类模型，该模型由g 伽之o f e z 等人【1 6 在1 9 7 7 年第一次提出对于离线情形，已经知道当机器数目为m 作为参数输入时，问题是强p 一 o r d 的，而当m 固定时，问题是p 一 n 州 的；后来，h o c h b a u m 等给出了该模型离线情形的多项式时间近似算法对 于在线情形，关于一般机器数m ，目前最好的结果是b e 咖a n 等人 1 7 】得到 的且他们给出了竞争比为3 + 插5 8 2 8 的在线算法，并证明这类模型的 下界为；芸鲁4 3 1 1 当m = 2 ，e p s t e i n 等人证明了三算法是可能存在 的在线算法，其竞争比为m 讥 竺等，芏坠 这里5 为加工速度最快的机器 于加工速度最慢的机器两者的加工速度的比值当m = 3 时闵啸 1 8 1 考 虑了s 。= s 1 ，3 2 = s 3 = 1 这一特殊情形，他证明了l s 7 算法的竞争比为 m 饥 竺等，翌兰) 并证明了s 2 时，l s ，算法是可能存在的最好的在线算 法蔡圣义在文【1 9 】考虑的模型和闵啸的类似，也是针对三台机器，三台同 类机器中由两台机器加工速度一样，只是另外一台机器加工速度比其它两 台要慢，不失一般性，设三台机器的加工速度分别为s 。= s 。= s l ，s 3 = 1 他证明了在这种特殊情形下，三s 7 算法竞争比为”漱 芸等，等) ，同时证 明了当s 3 时l s 7 算法是可能存在的最好的在线算法 1 0 一致平行机上在线排序 2 2 q m 凹问题 常用的符号表示： 舰表示第i 机器 机器集合m = 尬，舰，) 阢表示在算法下第t 机器上面的空闲总和 叼在d p 丁算法下第l 机器上面的空闲总和 巧和乃分别表示工件歹的到达时间和加工时间 砖表示工件j 被安排机器上加工并且砖= 笔 广表示d 刀算法下机器最大完工时间 广o ) 表示在d p t 算法下安排工件j 之后机器最大完工时间 ，a 表示算法a 下机器最大完工时间，在这章中指算法 e 表示在l s 算法下安排所有工件完工之后第l 机器上的最大完工 时间 膨表示安排工件j 之前第i 台机器上的最大完工时间 巧表示安排工件j 之后第i 机器的最大完工时间 厶表示有i 个工件的集合也就是 广假设阢后面紧跟的工件为歹，那么阢巧 有： 阢+ 譬吩+ 警，s s ，一堕阢 ， 矛盾，命题成立 定理2 1 ：在三s 算法下，如果岛= 1 ( 1 t m 1 ) s m = s ，则 厂删口。2 ( m 一1 ) 广且f 有在。尸t 算法下工件t 一定安排在机器工件 上加工，又在下t 安排给机器 根据l s 算法下有： f + t ， f m 一兰丝丝一 又因为t 7 一2 广又，l f 一定有： ，l s 7 f f m 一2 ，+ 从第1 台机器到第m 一1 机器的最后完工时间都缩小到f 结合f f m 一2 广： m 一1 墨+ s f m ( m 一1 ) ( 矗一2 ，) + s f m = l 銮1 只+ 8 如表示在l 算法下所有工件之和加上第1 台机器到第m 一 1 台机器的空闲和的总和再加上第m 机器空闲和的8 倍，有：。聊 ( s + m 一1 ) 广又从上面结论2 2 2 和结论2 2 3 知：阢 巧+ 警那么三 f l s f 1 3 广d m+s 缸 ，且吃， f 因为是最后一个在l 算法下在机器a 上加工，在d p t 算法下从机 器m 。上移走的工件，那么工件在d p t 算法下就不在机器a 上加工， 一定存在： ，+ r t ，+ 又我们知道工件t 7 在三s ，算法下在机器上加工，根据l s 算法和付 f 有： 印+ 晶一翌塑一 根据工件亡是三算法安排在机器 一。最后一个工件，由l 算法得： f m + 三 ，l s 兰 f l g f 将跏严7 吖和华+ 代从州7 矗一半圳氇 r t | + t l l 一2 f 综合广n ，+ 7 和r t ，+ ，l 一2 广得到： ，l ，口，口。2 ( m 1 ) qq + 萧 一致平行机上在线排序 情况1 3 ：广 根据工件t 是l s 7 算法安排在机器 一t 最后一个工件，由三s 7 算法得： 整理得： r + 三， s 又工件t 是三s 7 算法安排在机器m 。一- 没有安排在其他机器坛( 1 i m 一2 ) 由l 算法得 f + t2f l s f 整理得 f2f l g t 结论2 2 2 和结论2 2 3 知道阢 ，工s + ( m 一2 ) f + s f m i = i 把s s ，工一舌和f ，一t 代人上式： m 一1 只+ s f m ，+ ( m 一2 ) ( ，嬲一t ) + s ，一t t = l 整理得： 露+ s f m ( s + m 一1 ) ，一( m 一1 ) 亡 t = l 因为t 广得到： m 一1 只+ s f m ( s + m 一1 ) ，朋7 一( m 一1 ) ， 1 5 硕士学位论文 综合刍1 只+ s 如2 ( s + m 一1 ) 广 ( s + m 一1 ) ，l 一( m 一1 ) ，2 ( s + m 一1 ) ，+ 得到： s2 + 高南3 + 辈等 情况2 ：，倒= 情况2 1 f 7 r t ，其中f 7 = m 饥 只，( 1 i m 一1 ) ) 工件是l s 7 算法安排在机器没有安排在其他机器必( 1 i m 一1 ) 由l s 算法得： f ，+ ， 厂l s ，一堇竺g ( ! ! ! 一扩， 整合掣+ u t 广和t ， | l s 一2 f 结论2 2 2 和结论2 2 3 知道阢 s ，聆+ ( m 一1 ) f ， i = l 把f 7 ，删一2 广代人上式： ，n 一1 e + s f m s ，+ ( m 一1 ) ( ，删一2 ，+ ) = 1 1 6 一致平行机上在线排序 上式结合等1 只+ s f m 2 ( s + m 一1 ) ，+ 得 t r i l ( m 一1 ) ( ，工一2 ，) + s ，l s 乏二只+ s 2 ( s + m 1 ) ，4 扛= l 等姗志c s + m 叫3 + 兰等 情况2 2 ：f 7 f 有： r t ，+ ，删一掣一 挖印+ 矿 ，拶一半掣一巩 又因为墨塑+ s 广 l 芝l l s l ，删，n ，o 。2 ( m 一1 ) 号 ，工s + s ，l 一t t 广得到 r + 3 f 2 l s ”+ s f l s l 又结论2 2 2 和结论2 2 3 知道仉，广得到： n1 只+ s 易= 易+ 巩+ s 巩易+ ( s + 1 ) ， s2 ( s + 1 ) ， 整合f l + s 易2 ( s + 1 ) ，+ 和f l + s 岛 ，l + s ，l s ，一广所以： 得到： ( s + 1 ) ，工y 一厂+ 2 ( s + 1 ) ，+ 等姗南 情况2 ：，l = 易 r 在d p ? 算法下移出机器尬的工件和因此在d 刀算法下有 舱r 一吾一巩 1 9 硕士学位论文 因为有t 广，。 f + u 2 之f l s 一f 攀2 + 三 p 一一。s 命题成立 定理2 3 2 ：在s 7 算法下，当m = 2 时s l = 1 ，s 2 = s 2 ，定理2 3 1 得到的 这个界是紧的 ，l j 1 证明：由定理2 3 1 我们得到每2 + 我们只需找一个实例说明它 是紧的 实例：假设前面2 s 个工件为： r l ：1 一三，p l ：，r 2 = 1 一，p 2 = e r 3 = 2 一三，船= e ，n = 2 一哪4 = e p r 2 。12 s 一三，勉- l5 毛r 2 8 = s + 1 一岛p 2 s = e 勉+ 1 = o ，孙+ l = s ，物+ 2 = 0 ，纯葶+ 2 = s 2 在l s ，算法下，前面2 s 个工件安排是 ，以，厶一。安排在机器上，如，以，如 安排在机器舰上，这时两台机器的最大完工时间都为s ，对于工件也州， 又因为 s + 1 2 s 所以如+ 。安排在机器坞上对于工件以。+ 。因为 2 s + 1 5 人 设r 表示在安排第j 一1 个工件后机器最大完工时间满足小于或等于4 人 所有机器中，速度最快的那台机器，也就是： r = m 矧露_ 1 4 人) 定义r = 矧i r ) ，由，a 得出： 7 1 ，2 ，扎) ，吩，+ 笔，+ a 从假设知在安排工件j 的时候，算法a 输出，o 钉，有： 暂1 + 硪 5 a 上述式子综合： l 翥1 5 a 一以 4 a 因此r d ，又因为用算法三s 单独考虑机器l 上加工的工件的在线排序， 也是按照工件到达时间先后排的，与算法a 在机器t 加工顺序最一样，因 此从引理3 2 1 得出 忱r ，玩十胁o ) = 2 ( 玩+ 疵 4 a j 厶 j e f ，玩+ 露 2 a j e 一致平行机上在线排序 我们这里定义k6 】为机器集合m 中最后一个空闲，且t 是它后面紧跟的 工件 c a s e l 如果r t a 这里有n + 导 a 这与n + 箬a 矛盾( 因为广a 也就是对于任意工 v t nu l 件歹7 有呓+ 箬，。人) c 躯e 2 如果n a r t a ， j z ： 假设v ，u 时厶都有u r 鬈则窿= ， 尸二翌 竺! ! 垒：! 竺垒：a ， ! ! 竺兰二一 竺! ! 垒：! 竺垒： 。 一s r + l + + s