（基础数学专业论文）多台平行批处理机在线排序和带有运输时间的在线排序.pdf

摘要 在线排序是近年来现代排序领域发展最为迅速的模型之一与经典的离线排序相比 较，在线排序最明显的的特点是工件的所有信息是分阶段逐步释放给决策者的，并且，决 策者只能根据当前已有的信息来做排序决策这样的特点不仅仅为研究工作带来大量的 困难，而且也让研究者们产生了很大的兴趣在工业生产和计算机系统中，在线排序都 有着广泛的实际应用背景文献中有很多关于在线排序的定义最常见的两种是列表在 线( o n l i n e - l i s q 排序和时间在线( o n l i n e - t i m e ) 排序在列表在线排序问题中，工件事先排在 一个列表中，并且按照列表中的顺序一个接一个的呈现给决策者在下一个工件出现之 前，决策者必须将当前工件安排在某一台机器上工件一旦出现，决策者就知道该工件的 所有信息在时问在线排序问题中，工件是随时间到来的每个工件的信息在其到达后决 策者才被告知在工件到达时，决策者可以不立即安排此工件在本学位论文中，我们考 虑的是后一个模型，即，时间在线排序 一个在线算法的优劣往往是通过它的竞争比来衡量的我们称一个在线算法是伊竞 争的是指：对于任何一个实例，在线算法产生的目标函数值至多是离线情形下最优排序 目标函数值的p 倍给定一个在线排序问题p ，称算法以是问题p 的一个最好可能的在线 算法是指不存在比算法a 具有更好竞争比的在线算法 批处理排序也是近2 0 年来被研究者们广泛研究的一个现代排序模型它一般包括两 种模型：继列分批( s e r i a l - b a t c h ) 排序和平行分批( p a r a l l e l - b a t c h ) 排序在继列分批排序模 型中，若几个工件在同一台机器上共享一段安装时间，则称这些工件在同一批中加工机 器一次只能加工一个工件，即，批的加工时间等于安装时问加上该批中所有工件的加工 时间之和在平行分批排序中，在不超过批的容量范围内机器允许同时加工多个工件批 的加工时间是由该批中最长的加工时间来决定同一批中的工件具有相同的开工时间 和相同的完工时间在文献中平行分批排序一般包含两种模型：一个是批无界情形，即， b = o o ；另一种是批有界情形，即，b 奶，则= 1 ；否则，= 0 ，y = 加权误工工件数 4 1 3 在线排序 1 3在线排序 近些年来，在线排序是现代排序领域发展最为迅速的模型之一在经典排序中， 决策者都是在知道实例的所有信息的前提下做排序决策的这种排序模型我们称之 为离线排序( o f f - l i n es c h e d u l i n g ) 然而，在现实生活许多情况下决策者需要在实例的 所有信息到来之前做决策( 比如，1 1 节中的实例3 ) 这种排序模型我们称之为在线排 序( o n n n es c h e d u l i n g ) 或者半在线排序( s e m i - o n l i n es c h e d u l i n g ) 在在线排序中，工件的信 息是逐步释放的，决策者在做当前时刻的排序决策时对未来的实例信息是全然不知的， 并且排序决策一旦决定后就不允许改变在文献中有关在线排序的定义有很多，而常见 的定义有三种，我们介绍如下( 参见p r u h s 等人【5 7 1 ) ： 1 列表在线( o n l i n e - l i s t ) 排序：工件事先排列在一个列表中，并且按照列表中的顺序 一个接一个的呈现给决策者在下一个工件出现之前，决策者必须将当前工件安排在一 台机器上工件一旦出现，决策者就知道该工件的所有信息 2 时间在线( o n l i n e - t i m e ) 排序：工件是随时间到来的每个工件的所有信息在其到 达后决策者才被告知在工件到达后，决策者可以推迟安排此工件工件一旦被安排就不 允许改变 3 不可预测的时间在线( o n l i n e - t i m e - n c l v ) 排序：工件是随时间到来的每个工件的 信息在其加工完毕后决策者才被告知在工件到达后，决策者可以推迟安排此工件工件 一旦被安排就不允许改变 对于一个在线排序问题，由于决策者在做决策时只知道实例的部分信息，所以一般 不存在可以找到最优排序的在线算法( 个别模型除外) 因此，很自然地，我们就需要寻求 在线排序问题的近似解这就需要用到1 1 节近似算法的方法在在线排序中，我们称这 种方法为竞争分析( c o m p e t i t i v ea n a l y s i s ) 一个在线算法的优劣往往是通过它的竞争比( c o m p e t i t i v er a t i o ) 来衡量的给定一个 在线排序问题p 和它的一个在线算法a 算法的竞争比( 不妨设为吼) 的定义如下： r a = 溜器t j o d t ， 汀 l 上， 其中，c o n ( 刁表示实例z 在在线算法a 作用下产生的目标函数值；c o p t ( 刁表示实例z 在离 线情形下最优的目标函数值一个在线排序问题的所有在线算法的竞争比往往都有一个 下界越靠近竞争比下界的算法也就越优良若算法a 是问题p 的一个最好可能的在线算 法是指算法4 的竞争比等于问题p 所有在线算法竞争比的下界 5 第1 章绪论 有关在线排序方面的结果已有大量的文献进行了研究下面我们就简单地回顾一下 文献中关于在列表在线排序和时间在线排序方面的工作 列表在线排序问题中最经典的模型是p m o n l i n e - l i s t g 懈：g r a h a m 【2 6 1 i 正明 了l i s ts c h e d u l i n g 算法( 总是将当前工件安排到当前负载最小的机器上) 是( 2 1 m ) 一竞争 的g a l a m b o s 和w o e g i n g e r 【2 2 1 以及c h a n d r a s e k a r a n 等人【7 】分别给出了一个( 2 一x m c m ) 一竞争的在线算法，其中，当m _ o o 时，e m _ o 当m = 4 时，c h e n 等人【9 】提供了一个 竞争比为1 7 3 3 的在线算法当m 7 0 ，b a r t a l 等人f 4 】给出了一个( 2 1 7 0 ) 竞争的在线 算法当m 较大时，k a r g e r 等人【3 4 1 和a l b e r s 2 】分别给出了1 9 4 5 - 竞争的和1 9 2 3 - 竞争的 在线算法后来，f l e i s c h e r 和m i c h a e l a 【1 9 提出了竞争比为( 1 + x ( 1 + i n2 ) 2 ) 1 9 2 0 1 的 在线算法在在线算法竞争比下界方面，f a i g l e 等人【1 6 1 证明了此模型在m = 2 ，3 时 所有在线算法的下界为2 1 m ；在m 4 时所有在线算法的下界是1 7 0 7 这就表 明在m = 2 ，3 时，文献【2 6 】中的l i s ts c h e d u l i n g 算法就是最好可能的在线算法b a r - t “等人f 5 1 和a l b e r s 2 1 证明了所有在线算法的下界分别为1 8 3 7 和1 8 5 2 后来，g o r m - l e y 等人f 2 5 i 正明了所有在线算法的下界为1 8 5 3 5 8 对于工件可中断的在线排序模 型p m l o n l i n e - l i s t ，p m t n c m 双，c h e n 等人【1 0 】给出了一个竞争比为1 ( 1 一( 1 1 m ) m ) 的最 好可能的在线算法对于机器需要购买费用且目标函数是最小化最大完工时间和机器 费用之和的平行机列表在线排序问题，i m r e h 和n o g af 3 2 】证明了所有在线算法下界为4 3 ， 并给出了一个竞争比为( 砺+ 1 ) 2 的在线算法；后来，d 6 s a 和h e 【1 4 提供了个竞争比至 多为( 2 怕+ 3 ) 5 的在线算法 关于时间在线排序问题文献中也已经有大量的研究结果对于排序模型p m l o n l i n e , 巧f 瓯敬，c h e n 和v e s t j e n s 8 】证明t l p t 算法( 当有机器空闲且存在已经到达但未被安排 的工件时，总是从中挑选最长加工时间的工件放在当前负载最小的机器上加- r ) 的竞争 比为3 2 ，并且证明了当m = 2 w t 所有在线算法竞争比的下界是( 5 一x 亏) 2 ；当3 时所有 在线算法竞争比的下界是1 3 4 7 3 后来，当m = 2 时n o g a 和s e i d e n 【4 8 提供了一个竞争比 为( 5 一锯) 2 的最好可能在线算法对于排序模型l l o n l i n e ，r j l q ，v e s t j e n s 【6 6 】，l u 等 人【4 3 】以及p h i l l i p s 等人f 5 2 】分别给出了不同的竞争比为2 的在线算法，并且他们都是最好 可能的在线算法对于工件允许重启模型l o n l i n e ，吩，r e a t a r t s j c j ，s t e e 和p o u t r d 【5 8 给 出了一个竞争比为3 2 的最好可能的在线算法 除了上述文献之外，有关其它在线排序模型的研究可以参见以下文献：【1 】，【1 7 ，【1 8 ， 【4 7 】，【5 7 ，【5 9 ，【6 6 等等 6 1 4 平行分批排序 1 4 平行分批排序 批处理排序也是近2 0 年来被研究者们广泛研究的一个现代排序模型文献中一般包 含两种批处理排序模型：继列分批排序和平行分批排序我们简单地介绍如下： 1 继列分批( s e r i a l - b a t c h i n g ) 排序：若几个工件在同一台机器上共享一段安装时间， 则称这些工件在同一批中加工机器一次只能加工一个工件，即，批的加工时间是安装时 间加上该批中所有工件加工时间之和 2 平行分批( p a r a l l e l b a t c h i n g ) 排序：在不超过批的容量的条件下，机器可以同时加 工多个工件批的) j n - v 时间是由该批中最长的加工时间来决定同一批中的工件具有相 同的开工时间和相同的完工时间在文献中，平行分批排序一般包含两种模型：一个是 批无界情形，即，b = ；另一种是批有界情形，即，b c o ，其中，6 表示批的容量 在本学位论文中，我们考虑的是平行分批排序的无界模型平行分批排序模型最早 被应用在半导体生产制造过程中在1 1 节中的实例2 中我们简单的描述了半导体的制作 步骤事实上，u z s o y 等人【6 4 ，6 5 j ，a v a r a m i d i s 等人【3 】以及m a t h i r a j a n 和s i v a k u m a r 【4 6 】分 别对半导体的制作过程进行了更为详细的描述此外，平行分批还被广泛的应用于铸造 业，家具制造业，金属冶炼以及航空工业等工业生产领域中 研究者们普遍认为i k u r a c 和g i m p l ef 3 1 完成了第一篇关于平行分批处理机上排序问 题的研究从此以后大量的关于平行分批处理机上的排序文献不断出现对于排序 模型l i p - b a t c h ，b = o 。，吩l 蜮，l e e 和u z s o y 【3 8 】给出了一个o ( n 2 ) 多项式时间的动态规划 算法对于排序模型l i p - b a t c h ，b 佗，巧i g 龇，当工件的都在0 时刻到达时，b a r t h o l d i ( 参 见文献f 3 8 1 ) 给出了著名的f b l p t 算法( 将工件按加工时间下降的顺序排列，按照上 述列表每阶工件形成一批( 最后一批可能少于蚧) ，然后以任意顺序加工这些形成的 批) 当工件的到达时间不同时，l i u 和y u 【4 2 i 正明了此问题是n p 一困难的( 即使工件只 有两个到达时间) ，并在工件的到达时间的个数固定时给出了一个拟多项式时间算法； b r u c k e r 等人【6 】证明了此问题是强n p 一困难的对于排序模型p i p - b a t c h ，b 扎，巧l a 一， l e e 等人【3 9 】给出了一个( 4 3 1 3 m ) 一竞争的近似算法；l i 等人f 4 0 】给出了一个多项式逼 近方案( p t a s ) 上述文献所考虑的排序模型中工件都是来自于同一个工件组，即，任意两 个工件都可以放在一批中加工事实上，文献中也有很多关于工件属于不相容 工件组( 不同工件组的工件不能放在同一批中加工) 的平行分批处理机排序模型 1 第1 章绪论 方面的研究对于排序模型1 i f a m i l i e s j o b s ，p - b a t c h ，b = 。，吩i 缸，y u a n 等人【6 9 】证 明了此问题是强n p 困难的，并提供了两个动态规划算法和一个多项式逼近方 案( p t a s ) 对于排序模型1 i a m i l i e s j o b s ，p - b a t c h ，b n ，巧i g 一，n o n g 等人【5 0 】在不 相容工件组个数是常数的情形下给出了一个多项式逼近方案( p t a s ) 对于排序模 型p l f a m j l i e sj o b s ，p - b a t c h ，b ，吩j 戤，在不相容工件组个数是常数条件下，l i 等人f 4 1 】给 出了一个多项式逼近方案( p t a s ) 除了上述结果外，关于批处理机排序模型的复杂性和离线近似算法方面的结果可以 参见下列文献：【6 | ，【1 1 ，( 1 2 ，【1 3 ，【1 5 j ， 2 4 ，【4 5 ，( 5 6 】，f 6 3 】等等 以上结果都是关于平行分批处理机离线情形下文献中出现的研究结果对于在线情 形下平行分批处理机上的排序文献，我们将在论文后面的章节中详细说明，在这里我们 就不再一一介绍 1 5 本文的结果 本学位论文中我们主要考虑了两类排序问题在第二章和第三章中，我们考虑了多 台平行批处理机上的在线排序问题目标函数是最小化最大完工时间其中，第三章中是 关于具有不相容工件组的排序模型从第四章至第六章，我们考虑了工件具有运输时间 的在线排序问题在这些模型中，工件在机器上一旦完工，我们就立即用车辆将其送往目 的地目标函数是最小化所有工件被送到目的地的时间，即，最后一个工件的完工时问和 运输时间的总和其中，第四章考虑的是具有限制运输时间的单机在线排序问题；第五章 考虑的是具有限制运输时间的单个平行批处理机在线排序问题；在最后一章中，我们讨 论了具有无限制运输时间的单个平行批处理机在线排序问题具体地，本论文主要结果 如下： 1 在第二章中，我们考虑了m 台批无界平行分批处理机在线排序问题目标函数是 最小化最大完工时间我们证明了该问题所有在线算法的竞争比的下界是1 + q m ，其中， 口仇是方程q 。2 + m r m 一1 = 0 的正根，并且给出了一个最好可能的在线算法同时，我们 还考虑了此问题的稠密算法：证明了所有稠密算法的下界为3 2 ，并且也给出了一个最好 可能的在线算法 2 在第三章中，我们考虑了具有不相容工件组的m 台批无界平行分批处理机在线排 序问题假设工件组的个数与机器的台数相等目标函数是最小化最大完工时间我们 证明了此问题所有在线算法的下界为( 怕+ 1 ) 2 ，并提供了一个在线算法( 口) ，其中， 8 1 5 本文的结果 0 k 一个参数当同一个组的工件加工时间相同或者机器数目m = 2 时，我们证明了算 法( 理) 是最好可能的在线算法，其中，q = ( 锯一1 ) 2 当机器数目m 3 时，我们证明 了算法( ) 的竞争比为( 3 + 3 ) 2 ，其中，p = 讵一1 同时，我们还证明无论p 取何值， 当m 3 时算法( 口) 的竞争比不会小于为1 + 而5 3 在第四章中，我们考虑了具有限制运输时间的单机在线排序问题我们假设所有 工件的运输时间都不超过其本身的加工时间目标函数是最小化所有工件被送到目的地 的时间我们证明了此模型所有在线算法竞争比的下界是以，并给出了一个最好可能的 在线算法 4 在第五章中，我们考虑了具有限制运输时间的单个平行分批处理机在线排序问 题我们假设所有工件的运输时间都不小于其本身的加工时间目标函数是最小化所有 工件被送到目的地的时间我们证明了此模型所有在线算法竞争比的下界是( 锯+ 1 ) 2 ， 并给出了一个竞争比是( 锯+ 1 ) 2 的在线算法 5 在第六章中，我们考虑了具有无限制运输时间的单个批无界平行分批处理机在线 排序问题目标函数是最小化所有工件被送到目的地的时间t i a n 等人 6 1 1 证明了此问 题所有在线算法的下界是( 锈+ 1 ) 2 ，并且给出了一个竞争比为2 的在线算法在本学位 论文中我们给出了一个竞争比是2 以一1 的在线算法 9 第2 章多台平行分批处理机在线排序 2 1引言 模型介绍：本章我们考虑的排序模型是多台平行分批处理机在线排序问题我们 有m 台批容量无界的平行批处理机和几个工件每个工件都有一个到达时间和一个加工 时间，并且工件的这些信息只有工件到达时决策者才被告知目标函数是最小化最大完 工时间，即，瓯戕根据l a m e r 等人【3 7 】提供的三参数表示法，本章的排序模型可以简记 为： p r o o n l i n e ，乃，p - b a t c h ，b = j “缸 相关文献：在在线情形下，有关平行分批处理机上的排序问题文献中已有大量的 研究对于排序模型l o n l i n e ，巧，p - b a t c h ，b = o 。i c m 娃，d e n g 等人 1 2 】和z h a n g 等人【7 0 】分 别给出了具有竞争比( 怕+ 1 ) 2 的最好可能的在线算法；p o o n 和y uf 5 3 】进一步给出 了一类含有参数的最好可能的在线算法( 包含文献f 1 2 1 和【7 0 】中的算法) 对于排序 模型1 o n l i n e ，巧，p - b a t c h ，b 扎i c m 8 x ，z h a n g 等人【7 0 】提供了两个竞争比为2 的在线算 法；p o o n 和y u1 5 4 i 正明了一类以f b l p t 算法为基础的在线算法( 包含文献【7 叫中的两 个算法) 的竞争比为2 ；同时，当批容量b = 2 时，p o o n 和y u 【5 3 1 还给出了一个竞争比 为7 4 的在线算法对于排序模型p m l o n l i n e , 巧，p - b a t c h ，b = i x ，z h a n g 等人【7 0 】证 明了所有在线算法竞争比的下界为”顿，并且提供了一个竞争比为1 + 风的在线算 法p 日( 风) ，其中，风是方程风= ( 1 一风) m 一1 介于0 和1 之间的根在同一篇文献中， z h a n g 等人还考虑了上述排序模型的稠密算法具体结果如下：作者证明了所有稠 密算法的下界为以，并且给出了一个竞争比为( 锯+ 1 ) 2 的稠密算法对于排序模 型p r o o n l i n e ，吩，乃= p ，p - b a t c h ，b l 瓯舣，z h a n g 等人【7 1 】在批容量b = o 。时给出了一个 竞争比为1 + 最好可能的在线算法，其中，是方程( 1 + ) 州_ 1 = + 2 的正根； 在批容量b 礼时提供了一个竞争比为( 锈+ 1 ) 2 最好可能的在线算法对于排序模 型p 2 o n l i n e ，乃，p - b a t c h ，b = i c m 娃，n o n g 等人【4 9 】给出了一个竞争比为以的在线算法； t i a n 等人 6 2 1 提供了另一个具有竞争比为以的在线算法，并且证明了此问题所有在线算 1 1 第2 章多台平行分批处理机在线排序 法的下界为以这就说明文献 4 9 1 和【6 2 1 中的算法都是最好可能的在线算法 本章结果：在本章中，对于排序模型p m l o n l l n e , 巧，p - b a t c h ，b = 。o i g 瞰，我们将证 明所有在线算法的下界为1 + a m ，并且，提供了一个竞争比为l + q m 的最好可能的在线算 法日( q m ) ，其中，o m 方程q 磊+ m 一1 = o 的正根同时，我们也考虑了此问题的稠密算 法具体地，我们证明了所有稠密算法的下界为3 2 ，并且给出一个竞争比为3 2 的最好可 能的稠密算法d a 这些结果改进了文献【7 0 】中为本章所研究的排序模型提供的竞争比 的下界和算法 本章的结构如下：在第2 2 节中将给出本章所研究排序模型所有在线算法竞争比的 下界；在第2 3 节中将提出一个在线算法日( a m ) 和一个稠密算法d a ；在第2 3 节中我们将 证明在线算法日( q m ) 和稠密算法d a 分别是一个最好可能的在线算法和一个最好可能的 稠密算法 在本章下面的讨论中，我们用r f 和肼分别表示工件以的到达时间和加工时间给定 一个实例互用盯和丌分别表示在线算法产生的排序和一个离线最优排序；用最和g 分别 表示工件以在排序仃和丌中的开工时间记g p ) 和c m 觚( 7 r ) 分别为排序口和7 r 中最大的完 工时间，即，时间表长 2 2 竞争比的下界 在本节中，对于排序模_ 型p m l o n l i n e ，乃，p - b a t c h ，b = o 。i g 懈，我们将证明所有在线 算法竞争比的下界为l + ，其中，0 o ，m 1 是方程。磊+ m a m 一1 = o 的根首先，我 们介绍文献【7 0 】中提到的有关稠密算法的定义 定义2 2 1 在任何时刻若空闲机器的数目大于1 ，在线算法a 就立即从已到的工件 中选择工件在空闲机器上加工，那么我们就称算法a 为一个稠密算法 定理2 2 1 对于排序模型_ p m o n l i n e ，吩，p - b a t c h ，b = o 。i 敝，( i ) 不存在竞争比小 于1 + o 的在线算法，其中，0 q m 1 是方程口毛+ m 口m 一1 = o 的根；( i i ) 不存在竞争 比小于3 2 的稠密算法 证明( i ) 任取一个在线算法a 令e 表示一个充分小的正数下面我们构造一个工 1 2 2 2 竞争比的下界 件数目至多为m + 1 的实例z ，其中，实例z 中工件篚j 1 j w - r 时间和到达时间分别定义如下： p l = 1 ，p 2 = 1 一岛，鼽= 1 一鼠一1 ，p m = 1 一曲一1 ，p m + l = 1 + 研一； 7 1 = 0 ，7 2 = & + e ，n = & 一1 十e ，7 m = s m 一1 + e ，+ l = & + e 记s o = 0 于是我们锄= 1 一s j 一1 ， 1 ，m ) 若岛 岛一1 + ，工 件乃+ l 在时刻巧+ l 到达；若s j s j 一1 + o t m ，实例z 中剩余的工件易+ l ，厶+ l 就不再出 现，其中1 歹m 我们用n 表示实例z 的基数，即，集韶中所含工件的数目根据n 和m + 1 2 间的大小 关系，下面我们将考虑两种情形 情形1n m + 1 依据实例z 的构造，我们可知鼠一1 + o t m 于是，g n 蚁( 仃) + & 一1 + 0 f m + 1 一& 一12 l + q m n 为c m a x ( 1 r ) 。1 m 。a x 。 r j + 聊) = m a x 岛+ p l ，2 m n a x n ( s j l + e + 1 一岛一1 ) = 1 + e ，所以 舔( 盯) a x ( 7 r ) 2 ( 1 + o l m ) ( 1 + e ) 一1 + 乜m ，当e 叫0 情形2 扎= m + 1 根据实例z 的构造，对于任莉 1 ，m ) ，我们可知岛一1 乃s j 毋一1 + o m 于是，我们有岛 j a 仇因此，对于任意z 1 ，m 一1 ) ， 我f 门可知| s ；f + 1 ( i + 1 ) 口m m c t m 1 = & 一l + ( 1 一& 一1 ) 最+ 鼽这就表明 在排序盯中集合 ，厶) 中的每个工件都各自独立地占用一台机器假设在排 序仃中工件如+ 1 和以被安排在同一台机器上加工，其中，1 七sm 于是，弧( 盯) 鼠+ m + p m + 1 = 瓯+ 1 一& 一1 + 1 + & 一s 毛因为存在这样一个可行排序7 r 7 ：工 件以和如同批安排在一台机器上，而剩余工件以，厶各自独立地占用一台机器，所以， 我们得到 瓯觚( 7 r ) 瓯缸( 丌7 ) = m a x 研+ e + p l ，粤梦 吩+ 鳓) ) j 、n = m a x s 1 + + 1 ，嬲 $ 一l + e + l 一岛一1 ) ，+ e + 1 + - 受一) = l + 吼+ e 因为s 1 q m ，瓯一1 ( 惫一1 ) q m 且s k 鼠+ ( m 一尼) q m ，所以，我们可得 娃( 伊) 一觚( 7 r ) 1 + 鼠一( 鼠一1 + ) 一e 一1 瑟娃。鬲) 一二一。再丽一 、1 + 。鼠一【( 忌一1 ) q m + & 一( m 一七) q m 】一e ， 一 一 1 + 乜m + e 13 第2 章多台平行分批处理机在线排序 ：上粤兰净二一生粤兰造：，当- - t e o = 一一一= f 亡叶， 1 + o t m + e 1 + 乜m 这就完成了( i ) 的证明 ( i i ) 为了证明( i i ) ，我们考虑任意一个稠密算法b 和下面的实例具有单位加工 时间的前m 个工件分别在下列时刻到达：0 ，( m 一1 ) e 根据稠密算法的定义，对 于任意的歹 1 ，仇一1 ，工件易将被算法b 安排在时刻吩开始加工，即，岛= 吩， 坳 1 ，m 一1 ) 下面我们考虑两种情形 情形1s 互1 工件序列终止于是，我们得到g 眦( 盯) s 矗+ p 。；且c k 缸( 丌) = r m + p m = 1 + ( m 一1 ) e 情形2s m i 且( 7 r ) = m a x t i n + 1 ，r m + l + + 1 ) = m a x 1 + o z m 乒j l 尬e j 二l 一 图2 1 ( 2 1 ) 对于任意n j 1 ，m ) ，我们用岛表示机器歹在时刻& 之前的最后一个被加 工的批我们将会在下文中证明实例z 中必然存在b 1 ，b m 这些批重新对机器 进行标号使得在新标号下有s l + 陬，所以我们得到 g 一( 盯) 一。( 7 r ) & 一鼠 ( 2 2 ) 不等式( 2 2 ) 将在下面的证明中反复被调用此外，依据算法日( q m ) ，我们还可以得到下面 两个不等式： 刀( & ) 一r x a m ( 1 m a x ( 7 r ) ，任取b 盯；( 2 3 ) 岛& + o l m p m 缸( 岛) ，任取岛，岛盯，且& 岛( 2 4 ) 因为在n n s