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

摘要 排序论是运筹学的一个重要分支。排序问题经常在实际应用中出现，比如 网络通信中信道分配均衡问题，大型的并行计算问题，柔性生产系统中任务排 序问题，等等。在线排序是排序论当前研究的热点问题之一而对于现实中的 在线问题，虽然工件的全部信息并不知道，但根据问题的实际背景，我们往往 知道后续工件的部分信息，而且常常是利用了这些部分信息后能够设计出比 不利用这些信息时更好的在线算法。我们把这样的问题称为半在线( s e m io n l i n e ) 问题，相应的算法称为半在线算法 本文主要研究两类两台平行机( t w op a r a l l e lm a c h i n e s ) 的半在线排序问题，并 分析确定性半在线算法的竞争比( c o m p e t i t i v er a t i o ) 论文中主要研究了三个模 型，并针对每个模型都给出了相应的半在线算法全文共分三章 第一章是绪论部分，主要介绍排序问题的背景内容以及相应的准备知识 第二章主要研究了两类带机器准备时间的两台同类机半在线排序问题假 设两台机器的速度和准备时间分别为s ，= 1 ，8 。= s 1 ，r ，= r 0 ，r 2 = 0 ，一类问 题是最大工件加工时间已知的半在线排序，目标函数为极大化最小机器完工时 间，即q 2 ，r lj p 。j c k 。我们给出了竞争比至少为。s 州+ l 的m i n 半在线算法，且 此算法对于该问题的竞争比是紧的另一类问题是所有工件总加工时间已知的 半在线排序，目标函数为极小化最大机器完工时间的问题，即q 2 ，r lj s u m l g 。 我们给出了竞争比不超过坐2 s 业+ l 的m h 半在线算法 第三章主要介绍了带缓冲区的两台同型机半在线排序问题，其中缓冲区的 长度为( 即每次至多容纳k 个工件) 目标函数为极大化最小机器负载的问题， 即p 2 l b u f f e r l i n 我们设计了竞争比至少为；的半在线算法 关键词：排序问题，准备时间，半在线，竞争比 a b s t r a c t s c h e d u l i n gi so n eo ft h ei m p o r t a n tb r a n c h so fo p e r a t i o n sr e s e a r c h s c h e d u l i n gp r o b - l e mo c c u r si nm a n ya p p l i c a t i o n ss u c ha sl o a db a l a n c i n gn e t w o r k ，c o m m u n i c a t i o nc h a n n e l a s s i g m n e n t ，p a r a l l e lp r o c e s s i n gi nl a r g es i z ec o m p u t i n g ，t a s ka s s i g n m e n ti nf l e x i b l em a n - u f a c t u r i n gs y s t e m s ，e t c o n l i n es c h e d u l i n gi so n eo ft h ef o c a lp r o b l e m si n v e s t i g a t e di n s c h e d u l i n ga tp r e s e n t a l li n f o r m a t i o n o u tt h ej o b si su n k n o w nt ou si nt h ea c t u mo n 一 l i n es c h e d u f i n g a c c o r d i n gt ot h ef a c t d a lc o n d i t i o n s ，w eo f e nk n o wt h ep a r t i a la v a i l a b l e i n f o r m a t i o no ft h es u b s e q u e n tj o b s i ta d m i t st h ep o s s i b i l i t yo fc o n s t r u c t i n gas c h e d u l e w i t hab e t t e rc o m p e t i t i v er a t i ot h a no n l i n ea l g o r i t h m s w ec a l ls u c hap r o b l e ms e m io n l i n e s c h e d u l i n gp r o b l e m i nt h i st h e s i s ，w em a i n l ys t u d yt w os e m i - o n l i n es c h e d u l i n gp r o b l e m so nt w op a r a l - l e lm a c h i n e s ，a n da n a l y s ec o m p e t i t i v er a t i oo fd e t e r m i n i s t i cs e m io n l i n ea l g o r i t h m s w e c o n s i d e rt h r e em o d e l sa n df o re a c hm o d e lw ep r e s e n tas e m io n l i n ea l g o r i t h m t h et h e s i s c o n s i s t so ft h r e ec h a p t e r s i nc h a p t e r1 ，w eg i v eab r i e fi n t r o d u c t i o na n db a s i ck n o w l e d g ef o rs c h e d u l i n gp r o b - l e m s i nc h a p t e r2 ，w em a i n l yc o n s i d e rt w od i f f e r e n ts e m io n l i n es c h e d u l i n gp r o b l e m sw i t h n o n - s i m u l t a n e o u sm a c h i n ea v a i l a b l et i m eo nt w ou n i f o r mm a c h i n e s w es u p p o s et h a tt h e s p e e da n da v a i l a b l et i m eo f t w om a c h i n e sa r e8 1 。1 ，8 22s21 ，r l2r 0 ，7 2 = 0 ，s e p a - r a t e l y o n ep r o b l e m i ss e m io n l i n es c h e d u l i n gw i t ht h el a r g e s tp r o c e s s i n gt i m eb e i n gk n o w n i na d v a n c et om a x i m i z et h em i n m t u nm a c h i n ec o m p l e t i o nt i m e i ti sq 2 ，r l i p m “i a n i nb y at h r e e - f i e l dr e p r e s e n t a t i o nm e t h o d w eg i v ea nm i ns e m io 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 oa tl e a s t 2 s 址+ 1 a n dt h i sb o u n di st i g h tf o rt h ea l g o r i t h m t h eo t h e ri ss e m i o n l i n es c h e d u l i n gw i t ht h et o t a lp r o c e s s i n gt i m eb e i n gk n o w nb e f o r e h a n d ，t om i n i m i z et h e m a x i m u mm a c h i n ec o m p l e t i o nt i m e ，i e ，q 2 ，n l s u m l g n i n w ep r e s e n ta nm hs e m io n l i n e i i a l g o r i t h mw i t hc o m p e t i t i v er a t i oa tm o s t 黜 i nc h a p t e r3 ，w ec o n s i d e ras e m io n l i n es c h e d u l i n gp r o b l e mo nt w oi d e n t i c a lp a r a l l e l m a c h i n e sw i t hab u f f e r ，t h e r e i n t o ，t h el e n g t ho ft h eb u f f e ri sk ( i tc o n t a i n sa tm o s tkj o b s e v e r yt i m e ) ，t h eo b j e c t i v ei st om a x i m i z et h em i n i m u mm a c h i n ec o m p l e t i o nt i m e ，n a m e l y , p 2 b u f f e r c m i n w ep r o v i d eas e m io 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 oa tl e a s t ； k e yw o r d s ：s c h e d u l i n g ，a v a i l a b l et i m e ，s e m i o n f i n e ，c o m p e t i t i v er a t i o i i i 第一章绪论 1 1 组合优化简介 组合优化又称离散优化它的一个通俗的定义是指在离散的、有限的数学 结构上，寻找一个( 或一组) 满足给定约束条件并使其目标函数值达到最小或 最大的解。其正式定义如下： 定义1 1 1 ：组合优化是一个极小( 大) 化问题。它由下述三部分组成； ( 1 ) 1 实例集合； ( 2 ) 对每一个实例j ，有一个有穷的可行解集合s ( 耽 ( 3 ) 目标函数，它对每一个实例j 和每一个可行解盯s ( n 赋以一个有理 数f ( 1 ，盯) 如果该问题是一个极小( 大) 化问题，则实例j 的最优解为这样一个可行解 矿s ( n 它使得对所有的盯s ( o ，都有，( ，口) f ( 1 ，a ) ( 或f ( i ，矿) f ( f ，盯) ) 组合优化是一门古老而又年轻的学科说它古老，是因为一些组合优化问 题有着悠久的历史渊源著名数学家费马( f e r m a t ) ，欧拉( e u l e r ) 等都对它们进 行过相关的研究。说它年轻，是因为其作为运筹学的一个独立分支而发展起来 还是近几十年的事。二十世纪后半叶，伴随着工业科技革命和现代管理科学的 发展，特别是计算机技术的突飞猛进和在各行业的广泛应用，组合优化已壮大 成为一门新兴的学科分支一些百年前数学家们偶然想到的问题和方法，现在 已经在网络通信、物流管理、交通规划等领域发挥了重要作用，这是他们当时 所不曾想到的。这正预示了此学科的巨大发展前景 尽管大部分组合优化问题可以转化为整数规划( 或混合整数规划) 问题，但 由于整数规划的求解同样也是困难的，而组合优化又涵盖甚广，因此人们致力 于研究各个问题的组合结构，试图找到一些好的性质和有针对性的求解方法。 常见的组合优化问题有划分问题( p a r t i t i o np r o b l e m ) 、排序问题( s c h e d u l i n g p 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 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 np 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 hp r o b l e m ) 、最小生成树问题( m i n i m a ls p a n n i n gt r e e p r o b l e m ) 、最大流问题( m a x - f l o wp r b l e m ) 、最小费用流问题( m i n - c o s tf l o wp r o b - l e m ) 等。组合优化全貌可参见【1 ，2 卜在此，只对本文研究的排序问题作一下介 绍 2 1 2 排序问题 排序( s c h e d u l i n g ) 问题是组合优化中一类有着重要理论意义和广泛实际背 景的问题。其实质是寻求对需要完成任务的合理安排以得到某种意义下的最优 结果【2 8 ，2 9 它在生产计划调度、信息处理、公共事业管理等诸多方面有着大 量的应用。同时，它与理论计算机科学和离散组合数学也存在着密切的联系 近几十年来，排序问题得到了运筹学、工程学、管理学和计算机科学界的极大 关注，并且随着对经典问题研究的日趋深入，大量具有实际背景的新问题不断 涌现，使排序问题极具有生命力和研究价值可以这样说，对排序问题的研究 正进入成熟期。 按照学术界多年来形成的惯例，我们把需要完成的任务称为工件( 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 dr e p r e s e n t a t i o n ) a 例，y 来表示一个排序问 题【3 】 其中o ，卢，1 分别代表特定的机器环境、工件特征和最优准则。下面我们 分别对这些信息作一简要介绍 机器环境描述了机器数量、不同机器之间的关系等与机器有关的性质平 行机( p a r a l l e lm a c h i n e s ) 是其中最重要的机器类型之一用m = 尬，m 2 ， ) 表示机器集，其中m 2 每个工件只需在其中一台机器上加工一次即可完成。 常见的平行机类型有： 同型平行机( 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 ) ，即机器有其各自不同的速度，但任意 3 工件在不同机器上的加工时间有相同的比例关系，通常用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 表示 工件特征一般是指工件的各种加工信息，包括工件的加工时间，工件的到 达时间，工件之间加工顺序以及工件和其开工时间的依赖关系，工件加工时 是否允许中断以及中断恢复后再加工时是否要受惩罚等等。根据排序者对工 件信息的了解程度，又可将排序问题分为离线( o f f l i n e ) 、在线( o n l i n e ) 和半在线 ( s e m i - o n l i n e ) 三类。下面作一简要介绍： 如果排序者在排序开始前就已经知道工件的全部信息，例如工件数、每个 工件的到达时间和加工时间等，则称该问题是离线的 如果工件的信息是随着排序过程逐个释放的，即只有在位于某个工件前的 全部工件均已被安排完毕后，排序者才知道该工件的信息，而且工件一旦被安 排就不能改变，这样的排序问题称为是( 列表) 在线的。 但在实际问题中，大量的问题是介于两者之间的，即我们或者知道该问题 的一些整体信息，或者知道后续工件的部分信息例如，已知所有工件的总加 工时间，或者已知工件按加工时间递减( 递增) 顺序排列的等等它们都不是离 线问题，因为我们还不知道一共有多少工件，它们的加工具体时间是多少但 与在线问题相比，这些信息可以用来估计后续工件加工时间的范围，这是有利 于算法设计的。于是，我们把这样的排序问题称为是半在线的。 所谓最优准则，通俗地讲，也就是以什么为目标函数。如果记g 为某个 排序问题的可行排序工件乃的完工时间，则称g 一= m v g 为该排序的工件 最大完工时间( m a k e s p a n ) 。是一个最基本的目标函数。其最优准则为：找 一个可行排序，使得工件的最大完工时间c k 。在所有的可行排序中取得最小 值，即最小化目标函数。文献中常见的其它目标函数还有极大化最小机器完工 时间( c k 为最小机器完工时间) ，最大延误时间、最大误工时间等有关排序 问题的综述，可参见 4 ，5 】 4 从前面的讨论可以看出，离线和在线是排序问题的两种极端对立的情形 对前者来说，排序者知道工件的全部信息，而对后者来说，排序者对后续工件 的信息一无所知，甚至于不知道是否还会有工件到达。因此，前者一般能够设 计出比后者性能比好一些的算法。但是，在实际问题中，出现上述两种极端情 形的可能性都不大。现实中的问题往往是介于两者之间。也就是说，对于现实 中的在线问题，虽然工件的全部信息不知道，但根据问题的实际背景，我们往 往知道后续工件的部分信息，而且常常是利用了这些部分信息后能够设计出 比不利用这些信息的在线算法性能更好的算法。我们把这样的问题称为半在线 ( s e m io n l i n e ) 问题，相应的算法称为半在线算法。当然，半在线问题的提法仅仅 是为了与经典的在线问题进行区别从排序者在做出决定前那一刻并未掌握实 例的全部信息以及一旦安排好某个工件就不允许改变来看，半在线问题本质上 仍然是“在线”的因此，我们仍旧沿用竞争比一词来研究半在线问题。 由于“半在线”这一概念切合实际，因此有着强有力的生命力自从人们 在二十世纪九十年代中期提出半在线的概念以来，仅在排序领域内就有十余个 不同的模型出现下面我们就简要地介绍几个： 1 预先知道工件总加工时间的半在线模型( s u m ) 假设所有工件的总加工时间p 预先知道【1 8 1 9 】分别给出了p 2 1 s u m l g 一， p 2 i s u m t c 。；。的竞争比为；和；的最好算法何勇、杨启帆、谈之奕和姚恩瑜 2 0 】 给出了p l s u m l g 的竞争比为2 一击t 的半在线算法 2 预先知道工件最大加工时间的半在线模型( m a x ) 假设所有工件中加工时间最大的工件的加工时间预先知道何勇和张国川 给出了p 2 1 m a xj g 。竞争比为；的最好算法【1 3 】对p 2 1 m a x l c m t 。情形，何勇给出 了竞争比为；的最好算法【1 8 】， 3 预先知道工件从大到小到达的半在线模型( n o n - i n c r e a s i n gj o b ) 假设工件按加工时间从大到小到达g r a h a m 2 6 】证明了l s 算法的竞争比 为一击何勇等【1 6 】证明当m = 2 时l s 算法是最优算法，其竞争比为；当 5 m = 3 时p 3 1 n o n i n c r e a s i n gj o b g 。的下界至少为学 2 3 另外，还有预先知道实例最优解值，预先知道工件加工时间落在一区间内， 带缓冲区( b u f f e r ) ，两批工件( t w ob a t c h ) ，o r d i n a l 等等半在线排序的模型关于这 方面的讨论可参见综述文献【1 5 ，1 6 】可以预见，随着研究的不断深入，将会有 更多的半在线模型出现 最后指出一点，并不是所有的部分信息都是有利于算法的设计的。例如在 p 2 1 0 n l i n e l c m 。中，预先知道工件从小到大到达的半在线情形不会改变原先在线 问题的下界因此这种半在线模型是平凡的，其意义也有限 6 1 3 算法与时间复杂性 定义1 3 1 算法是指一步步求解所给定问题的通用程序基础。它是解决问 题的程序步骤的一个清晰描述。确定性算法从前一步到后一步的运行由当前状 态唯一确定。如果存在一个算法，它对组合优化问题丌的每个实例，( i n s t a n c e ) ， 在有限步后一定可以得到该实例的关于丌的提问的答案，那么称该算法解此组 合优化问题丌 定义1 3 2 ：对于一个组合优化问题丌，如果给定任意一个实例，算法a 总能 找到一个可行解伊s ( n 那么就称以为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 ts c h e d u l i n g ) 算法【2 翻和 l p t ( l a r g e s tp r o c e s s i n g 死m e ) 算法f 2 6 】分别是经典平行机排序问题的在线和离 线算法。由于在离线问题中，排序者在排序前知道工件的全部信息，因此l p t 算法先把所有的工件按加工时间的非增顺序排列，然后依次将它们安排在能使 其最早完工的机器上加工而对于在线问题，在排序进行过程中后续工件信息 是未知的，因此l s 算法将工件按照它们在列表中的先后顺序将当前工件安排 在能使其最早完工的机器上加工 算法求解问题是需要时间的。通常，算法所用的时间是指算法中所含的加、 减，乘、除，比较等基本运算次数而算法所用的时间与实例的规模有关，为 此我们用输入长度来刻划实例的规模。所谓实例的输入长度通常是指实例所用 的计算机内存单元数。 定义1 3 3 ：算法的时问复杂性是指关于实际输入长度n 的函数，( 铊) ，用来 表示算法的时间需求，对每一个可能的输入长度，它是指在最坏情况下该算法 解此输入长度的实例时所需时间( 基本运算步数) 即对于输入长度相同的所有 实例，把算法对这些实例的最坏情况作为时间复杂性的度量 7 如果存在一个多项式函数p ( n ) ，使得算法的时间复杂性为0 ( p ( 咒) ) ，那么称该 算法为多项式时间算法，否则称为指数时间算法。还有一类称为伪多项式时 间算法，它的时间复杂性是关于实例输入长度札和实例中最大的二元多项式函 数。在二进制编码下，伪多项式时间算法并不是多项式时间算法，而是指数时 间算法。由此出发，可以导出时间复杂性理论的一系列重要概念和结论【6 】 计算复杂性兴起于二十世纪六十年代，它和算法的设计与分析密切相关。 通过几十年来人们在计算复杂性方面的研究，现今p n p 的猜想已基本被 接受在此前提下，所谓的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 ) 问题，这类问题连伪多项式时 间最优算法都不存在【6 】另外一个在实际常用的方法是对n p h a r d 问题加些 限制从而得到一些子问题，使其具有有多项式时间算法这是因为一个问题是 n p h a r d 的，并不能排斥它的一些特殊子情形是多项式可解的 我们衡量近似算法的优劣可以从两个方面来看，一是算法的时间复杂性， 二是算法得到的解值与最优解值的接近程度。 定义1 3 4 ：丌是一个极小( 大) 化问题，j 是任意实例设a 是霄的一个近 似算法。用瓯( ，) 和c o p r ( r ) 分别表示算法a 解实例j 的目标函数值和离线情 况下实例，的最优目标函数值记肌( d = 刁；为近似算法的最坏情形比 在最坏情形比的基础上逐渐形成了竞争比分析法( c o m p e t i t i v er a t i om e t h o d ) ， 俗称对手法( a d v e r s a r ym e t h o d ) 【3 0 ，3 1 ，它属于最坏情况分析对极小化排序问题 问题，称 p a ( 丌) = i n f p 1ip a ( i ) n v ， 为在线( 半在线) 算法a 的竞争比( c o m p e t i t i v er a t i o ) ，而问题丌的下界( 1 0 w e r 8 b o u n d ) 定义为 f ( 7 r ) = i n f f l p a ( 1 ) s ，v a 同样地，对极大化排序问题问题，称 m ( 7 r ) = s u p p 1p a ( i ) p ，v t 为在线( 半在线) 算法a 的竞争比( c o m p e t i t i v er a t i o ) 若算法a 的竞争比为p ，也 称4 是p c o m p e t i t i v e 的。而问题，r 的上界( s u p p e rb o u n d ) 定义为 f ( 丌) = s u p f l p a ( i ) ，v a 如果m ( 丌) = f ( 丌) ，则称算法a 对于问题丌来讲是最优的( o p t i m a l ) 在不引起混淆的前提下，我们通常将上述定义中的e a ( o ，c o m , ( i ) 和p a ( ，x ) 分别简记为瓯，刀和肌 由于某些组合优化问题本身固有的难度以及最坏情形比估计需要很强的数 学基础和技巧，导致很多情形下无法证明某些算法的最坏情形比而实际问题 又迫切需要给出一些方案来求解。在这样的前提下，人们给出了启发式算法的 概念 定义1 3 5 ：启发式算法是一个基于直观或经验构造的算法在可以接受的 花费( 指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一 个可行解该可行解与最优解的偏离程度不一定可以事先预计 评价启发式算法的性能主要分两类，一是看算法占用的时间、空间等，二 是分析算法的效率。算法效率往往采用大规模的随机数据进行实验验证，从平 均的角度以及最坏的角度来进行衡量。 9 1 4 论文概述 本文主要考虑两台平行机半在线排序问题。在文中，我们用j = ( zm ) 表 示排序问题的一个实例，其中m 表示机器集 m 1 ，m 2 ，m 。 ，表示工件集 j 1 ，j 2 ，厶) 工件乃的标准加工时间用岛表示。工件加工不可中断。用p 表 示所有工件的总的加工时间，即p = 妻p j 用p m a x 表示加工时间最长的工件， 即。= m a x p j 本文主要结果如下： 第二章主要介绍了两类带机器准备时间的两台同类机半在线排序问题。一 类是最大工件加工时间已知的半在线排序问题，目标函数为极大化最小机器完 工时间，即q 2 ，r t f 。f e m 。本文给出了竞争比为两8 + 了1 的m i n 半在线算法，且 此算法对于该问题的竞争比是紧的 算法m i n ， s t e p1 若当前工件不是最大工件且机器舰的完工时间不超过p 一s ，那么 当前工件就安排在机器m 上加工，否则转入s t e p3 ； s t e p2 若当前工件是最大工件且机器m 的完工时间不超过p 一8 ，那么当 前工件就安排在机器上加工，否则转入s t e p3 ； s t e p3 对所有剩余工件按l s 算法加工 而另一类是所有工件总加工时间的半在线排序问题，目标函数为极小化最 大机器完工时间的问题，即q 2 ，r t s u m c m 。本文给出了竞争比为坐2 8 + 出1 的m h 半在线算法 算法m h ： s t e p l 若p 2 r s ，则将到达的工件安排在m 2 上； s t e p2 若p 2 r s ，将到达的工件安排在尬上，直至存在工件p 使得 m 1 + p 并且m 1 r 此时我们假设两台机器的最终完工时间分别为c m ， 和c f 则由引理2 1 可知有以下两种情形： 若c m i n 为机器瓶的最终完工时间，则c ，为机器的最终完工时间， 且c 0 c m j 从而由引理2 1 和2 2 知 c ，m 慊一c m l n 曼弘一 sa c o 叮s 8 c t m i n 五 。f c m i n 一 从而我们可以得到 c m i n ! ! ! ! 鱼型( ! ! ! 垒型 c o p t c m * n + 8 c 0 ，n c m i n 十s c m t n + p i i l a x 鱼1 2 9 竺! 盟 ! ! ! ! g 坚! 盟：! ! 三 若c m t n 为机器的最终完工时间，则c ，为机器鸠的最终完工时间， 1 6 且c 幺，_ 2c m 肌从而由引理2 1 和2 2 知 ，一c m ，p 。且c o 刀c m i r n + r s c m m 从而我们可以得到 坠 f ! ! ! 里竺! 盟 ( ! 1 2 里堑! 盟 e o 盯一8 c m i n + c f m l n 一8 c m i n + c m i n + p m 瓦磊( s 干+ 面1 ) c 赢m z 鬲n ； 面磊再( 8 刁- - 1 赢) c 再m i 丽n= 砉暑 情形2 当r p 一s 时，我们有胛丝s 逝+ 1 此时我们考虑以下三种 情形： 子情形2 1 = 0 这意味着在最后一个工件之前所有工件按算法s t e p1 执 行都放在机器尬上加工，还没有一个最大工件到来。因此最后一个工件为最 大工件，即= 。，且m 放在机器上加工 如果尬p 一s 则机器舰的完工时间不超过机器尬的完工时间，则此 时算法最优 如果m p 一s 则有c m j _ = m 2 + p s = 鸲+ p 。s = p m 。s ，并由引理 2 1 可知尬一c k = 尬一p 。a x 加p 。a x ，即m 1 姓! 娑一从而有 c m i n 、( 8 + 1 ) p m 。( 3 + 1 ) p 。 c o p r 页厩干；瓦+ ；。：两一s m 一，+ p m = 垒1 2 翌翌竺：! ! 1 2 翌翌竺：! 旦 一 ( s + 1 ) p m 强+ p m 娃( 2 s + 1 ) p m “ 2 s + 1 子情形2 20 f ! 1 2 些：三旦 ( 局胛一 4 l + s 口2 + p m “一 4 1 + s m l + s 埘l 2 s + 1 当尬 + p 一sh 寸，有c m ，= + p 一s 由引理2 1 可知m 一( + p 。a x s ) p 。a x ，即m 1 m 2 + p 。+ p 。s ，从而 、( 8 + 1 ) ( m 2 + p m a x 8 ) 、s + 18 m ：p 里竺 二- 尬+ s 如+ p m “ 一 s ( s + 1 ) 如+ 2 p m a x + 鼽n 械8 ! ! ! 丝翌坐竺2 ：三旦 s ( 2 s + 1 ) m 2 + ( 2 s + 1 ) p m “ 2 s + 1 b ) 若p 。s m 2 m 1 ，此时两台机器的完工时间均不少于p m 。s ，因此算 法按s t e p3 执行，即按l s 算法安排工件因此我们可以知道最后一个工件p n 放在机器上加工。从而有 c m ，n = m i n 尬，+ p n s 当m + m s 时，有，_ = m i 因此 c m i n 、! ! ! ! 塑鱼1 2 丝! f ! 1 2 丝!：三旦 c o 刀2 尬+ s + p 。：- 尬+ 8 m 1 + “一尬+ s m l + s 尬 2 s - t - 1 当m 1 尬+ s 时，有c m ，= 尬+ m s 由引理2 1 可知尬一m 2 p m “， 即尬+ p 。，从而 ( s - t - 1 ) ( m 2 - t - p s ) 型土 兰! 堕堕 二- 尬+ s 尬+ 陬 一 s ( s - t - 1 ) 尬+ p 一+ 旦坐 ! 丝! 丝 旦丛 一2 s + 1 子情形2 3m 2 m 1 由l s 算法知，最后一个工件放在机器尬上加工， 从而有 c m i n = m i n t m l + m 矗 我们分以下两种情形： a ) 若尬 p 。s 则有c m ，_ = 如= p m 。8 由引理2 1 可知，尬+ 陬一 m 2 = m l + m 一a x 8 p 一即尬+ 肌墨姓訾纽从而 c m i n 、( 8 + 1 ) 尬、 ( s + 1 ) p 。s 3 + 1 c o p r m 1 + s m 2 + p 五j 币干瓣2 互鬲 b ) ，若尬2p 一s 此时两台机器的完工时间均超过了p 。s 因此按l s 算 法规则最后一个工件m 应放在机器尬上加工 若m + 肌尬，则有c m f _ = m i + p n 由引理2 1 可知，尬一( + ) p 一s ， 即m 2 矗+ p 。+ p 。a x s ，从而 c m i n 、( 8 + 1 ) ( m l + p 。) 、0 + 1 ) ( m l + p 。) ( 汤胛一m 1 + s 尬+ p ”一( s + 1 ) m 1 + p 麟4 - 0 + 1 ) 鲰 、 ( s + 1 ) ( m 1 + m ) 、0 + 1 ) ( 舰+ m ) 一8 + 1 一( 2 8 + 1 ) m 1 + ( s + 1 ) p n7 ( 2 s4 - 1 ) ( m 1 + p 。) 2 s + 1 若尬+ p n 则有c m ，= ，从