（运筹学与控制论专业论文）带服务等级的排序问题的若干研究.pdf

摘要 摘要 本文主要研究具有服务等级的平行机排序问题预先赋予每个任务和每台机 器一个服务等级标号，使得服务等级低的机器既能加工服务等级低的任务，又能 加工服务等级高的任务，而服务等级高的机器只能加工服务等级高的任务目标 函数是极小化最大机器完工时间这类问题最先是h w a n g 等提出来的本文给 出了求解这类问题的新算法从而大大改进了已知文献中的结果2 一未t 全文共 分为三章 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识 第一章主要研究了具有两个服务等级的m 台平行机排序问题目标函数是极 小化最大的机器完工时间( c k a x ) 给出了一个修正的m 矿l t ，f ，t 算法，其最坏情 况界为i 4 + ( ) ，其中是预先给定得迭代次数 第三章主要研究了一般情况下具有服务等级的m 台平行机排序问题目标 函数为极小化最大的机器完工时间给出了一个最坏情况界为 + ( ) 的算法 对m = 3 的情形给出了一个最坏情况界为i 十( ) 的算法，并证明了这个界是紧 的 关键词：、f 行机排序，服务等级，最坏情况界，f f d ，m u l t i f i t a b s t r a c t a b s t r a c t t h i st h e s i sm a i n l ys t u d i e sp a r a l l e lm a c h i n es c h e d u l i n gu n d e rag r a d eo fs e r v i c e p r o v i s i o n e a c hj o ba n dm a c h i n ea r el a b e l l e dw i t hp r e s p e c i f i e dg r a d eo fs e r v i c e ( o r g o s ) l e v e l s e a c hj o bi sa l l o w e dt ob ep r o c e s s e db yap a r t i c u l a rm a c h i n eo n l yw h e n t h eg o sl e v e lo ft h ej o bi sn ol e s st h a nt h eg o st e v e lo ft h em a c h i n e t h eg o a li st o m i n i m i z et h em a x i m u mm a c h i n ec o m p l e t i o nt i m e ，c a l l e dm a k e s p a n t h i sp r o b l e mi s p r o p o s e db yh w a n ge ta 1 r e c e n t l y f o rt h i sp r o b l e m ，w ep r e s e n tan e wa l g o r i t h m ， w h i c hi m p r o v e dt h ek n o w nr e s u l t2 一示b t h et h e s i sc o n s i s t so f t h r e ec h a p t e r s t h ef i r s tc h a p t e rg i v e ss o m ei n t r o d u c t i o na n dp r e l i m i l a r i e sf o rs c h e d u l i n gp r o b l e m s t h es e c o n dc h a p t e ri n v e s t i g a t e sp a r a l l e lm a c h i n es c h e d u l i n gp r o b l e mw i t ht w o g r a d e so fs e v i c ep r o v i s i o n w ep r e s e n ta l la l g o r i t h mm m f w h i c hi sm o d i f i e df r o m m u l t i f i t t h ew o r s t c a s er a t i oo f m m f i s ；+ ( ) ，w h e r ek i st h ed e s i r e dn n m h e ro fi t e r a t i o n t h et h i r dc h a p t e rc o n s i d e r st h eg e n e r a lc a s ef o rt h ep r o b l e mu n d e r c o n s i d e r a t i o n t h eg o a li st om i n i m i z et h em a k e s p a nu n d e rt h ec o n s t r a i n tt h a ta l lr e - q u e s t sa r es a t i s f i e d w ep r e s e n ta l la l g o r i t h mw i t haw o r s t c a s er a t i oo f ；+ ( ) 。w e f u r t h e rp r e s e n ta na l g o r i h t mw i t haw o r s t c a s er a t i oo f2 + ( j ) f o rm = 3a n ds h o w t h eb o u n di st i g h t k e yw o r d s ：p a r a l l e lm a c h i n es c h e d u l i n g ，g r a d eo fs e v i c e ，w o r s t - c a s er a t i o ，f f d m u l 0 i f i t i i 第一章绪论 1 1 排序问题 第一章绪论 排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问题由于 它在现实计算机系统中多方面的应用，排序问题早已成为理论计算机学界的研究 领域之一，并已拥有大量结果除了在计算机科学领域以外，排序问题还在管理科 学和工程技术等诸多方面具有大量的应用近几十年来，排序问题得到了运筹学 界、计算机科学界、工程学界和管理学界极大的关注，鉴于经典问题的研究日益 深入，而具有实际背景的新问题又不断涌现，可以说，对排序问题的研究正在进入 成熟期， 按照学术界多年来形成的惯例，一般用所谓的三参数表示法( t h r e e f i e l d r e p r e s e n t a t i o n 妞卢7 来表示一个具体的排序问题，三个参数，p 和，y 分别刻画了机 器状况，工件特征和目标函数，一卜- 面我们分别对每个参数所代表的含义作具体介 绍 q 域表示处理机的数量、类型和环境，它可以为 l ：单处理机 p m ：仇个同速机 q m ：m 个恒速机 f h ：仇个变速机 f m ：m 个处理机，流水作业 o m ：m 个处理机，开放作业 j r a ：m 个处理机，异顺序作业 f f s ：s 类处理机，柔性流水作业 其中同速机、恒速机和变速机这三种机器状况的具体含义如下：如果所有的 处理机都具有相同的速度，称之为同速机( i d e n t i c a lp r o c e s s o r s ) ；如果处理机的速 度不同，但是每个处理机的速度都是常数，不依赖被加工的任务，称它们为恒速 机( u n i f o r mp r o c e s s o r s ) ；如果处理机的速度依赖被加工的任务，它们被称为变速 机( u n r e l a t e dp r o c e s s o r s ) 流水作业、开放作业、异顺序作业和柔性流水作业的具 体含义分别为：如果每个作业需要在每个处理机上加工，而且每个作业的工序也 第一章绪论 相同，即在处理机上加工的顺序相同，把这种多类型机的环境称为流水作业川o w s h o p ) ；如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把 它称为开放作、i k ( o p e ns h o p ) ；如果个作业需要在每个处理机上加工，每个作业有 自己的加工顺序，称之为异顺序作业( o bs h o p ) ；在多处理机中，还有一种更为复杂 的情况，这就是柔性流水作业( f l e x i b l ef l o ws h o p ) ，它是流水作业和平行机的推广 在柔性流水作业中，有s 类处理机，第7 类有8 f 个平行机，每个作业有s 道工序，每道 工序需要在每类平行机中的一个处理机上加工，且每个作业的加工顺序相同 卢域表示任务或作业的性质、加工要求或限制，资源的种类、数量和对加工 的影响等约束条件它同时可以包含多项 排序问题的实质是寻找对所需完成的任务( 或作业) 以合理的安排以得到某 种意义下的最优结果，这就涉及到所谓的最优准则，通俗的讲也就是以什么为目 标函数如果记q 为在某个满足排序问题要求的可行排序下工件 的完工时间， 而在该排序下机器尬的完工时间为厶，则称c k 。= m a x e ，为该排序的最大完工 时i 司( m a k e s p a n ) ，c m 。= m ! n 厶为该排序的最小机器负载于是g 。和c k l 札就可 看成是某种最优准则下的目标函数对于前者，最优准则可叙述为找一个可行排 序，使得它的最大完工时间g k 。在所有的可行排序中取得最小的值，即这时是极 小化目标函数；对于后者，最优准则可叙述为找一个可行排序，使得它的最小机 器负载g 麓m 在所有的可行排序中取得最大的值，即这时是极大化目标函数当然， 除了上面的两个目标函数以外，排序问题中还有很多目标函数，较常见的有总完 工时间，最大延误时间，最大误工时间等，在此我们就不一一介绍了有关排序问 题的近期综述可参见7 ；2 2 第一章绪论 1 2 近 以算法、最坏情况界、离线和在线 鉴于7 0 年代建立起来的计算复杂性理论 1 0 1 ，以及几十年来人们在这方面的 各种工作，现今p p 的猜想己为绝大多数人所接受；而给出此猜想的证明， 也已成为对整个人类智慧的一大挑战，国际数学界将此问题列为二十一世纪最根 本的几个大问题中的一个如果我们接受p n p 的猜想，那么对于所谓的n p 一难 问题就不可能存在多项式时间内找到最优解的算法也就是说，随着问题实例的 规模的增大，对这种n p 难问题的每一个实例要用统一的算法找出最优解，从计算 时间上来看几乎是不可能的因此一个自然的想法就是放弃对最优解的寻找。而 代之以寻找具有某种性能保证的可行解( 称为近似解) ，从而换取计算时间，这也 就是所谓的近似算法( a p p r o x i m a t i o na l g o r i t h m ) 的思想可以证明，本论文讨论的排 序问题都是n p 难的，因此本论文主要给出它们的近似算法以及对给出的近似算 法的性能作一些分析 近似算法的好坏可以从两个方面来看，一是算法的计算时间，二是算法得到 的近似解的解值与最优解的解值的接近程度这里，接近程度常常用所谓的最坏 情况界( w o r s t c a s er a t i o ) 来刻画：假设a 是求解极小化居标排序问题的某一近似算 法，称 r ( a ) = s u p 萨c a ：对排序问题任意一个实例) 为算法4 的最坏情况界，其中a “和分别表示算法a 解实例，所得的目标函数值 和实例，的最优解值如果近似算法a 还是所谓的在线算法，则这时将算法a 的最 坏情况界特别地称为竞争b l ( c o m p e t i t i v er a t i o ) ，其中e 4 是指相应离线问题的最优 解值 下面介绍一f f 什么是离线算法，什么是在线算法对于具体的一个排序问题， 根据问题所涉及到的信息对排序者( s c h e d u l e r ) 开放的程度、可以将该问题大体上 分为离线和在线两种情况对于离线问题，这时排序者在排序之前知道工件的全 部信息，于是基于任务全部信息已知情形下设计的算法就称为离线算法但是，在 实际问题中，常常是在排序进行过程中后续任务的信息是未知的，这时排序者只 能就当前已有的任务进行排序，并且由于问题的实际背景，常常是排序者一旦对 某个任务作出安排就不允许改变，为与离线问题相区别，这种问题称为在线问题， 相应地解这种问题的算法称为在线算法本文主要讨论的是离线情况下具有服务 等级的排序问题最经典的离线算法和在线算法就是解平行机排序问题的l p t 算 第一章绪论 法 6 ；1 2 和l s 算法 1 3 l p t 算法先将工件从大到小排列后依次将它们安排在能 使其最早完工的机器上加工，而l s 算法只是按工件到达的顺序依次将它们安排 在能使其最早完工的机器上加工就l p t 算法，已证明它解p m g 。的最坏情况 界为i 4 一丽1 【1 2 ；就l s 算法，已证明它解p m g k 。的竞争比为2 1 3 1 对离线问题，如果不考虑时间要求，由于排序问题是组合优化问题，原则上用 枚举法总可以得到最优解也就是说，如果给你足够多的时间，原则上存在最坏情 况界为1 的离线算法但对在线问题，即便是给你足够多的时间，竞争比为l 的在线 算法在一般情况下也是不可能存在的 4 第二章具有两个服务等级的平行机排序问题 2 1 引言 第二章具有两个服务等级的平行机排序问题 在加工服务行业，服务的提供者经常会遇到一些特殊顾客他们要求得到比 一般顾客更好的服务因此，服务的提供者必须制定出相应的服务策略一种简单 的策略就是预先给每台机器和每项任务赋予一个服务等级( g r a d eo fs e v i e e ) 指标， 使得服务等级低的机器既能加工服务等级低的任务，又能加工服务等级高的任 务，而服务等级高的机器只能加工服务等级高的任务这样就可以将标号较高的 机器留下来加工标号较高的任务因此，对那些需要得到更好服务的顾客，我们只 要给他们的加工任务赋予一个较高的标号，就能保证为他们提供更好的服务 h w a n g 等f 1 4 提出了基于上述考虑的一个新的平行机排序问题：给定任务 集j = 乃：正，霸) 和机器集朋= ，尬， ，m 2 ，任务乃的加 工时间为z ( 乃) ，服务等级为9 ( 乃) 机器蚴的服务等级为9 ( 尬) 由于只有m 台 机器，不失一般性，设有至多m 个不同的服务等级，用整数1 ，m 标记并且仅 当g ( 尬) g ( 乃) 时，乃允许被尬加工一个排序是指将给定的，分成仇个不交 的子集p = ( p l ，岛，f k ) ，并且仅当9 ( 觚) 59 ( t j ) 时，乃允许属于只一个排 序p 的完工时间( m 。k e 印n 礼) 定义为m o 1 1 l s 。z ( p d ，其中f ( p f ) = r e rf ( t ) 目标 为寻找一个排序，使排序完工时间尽可能小 上述问题是强n p 一难的，文献 1 4 给出了该问题的一个近似算法l g l p t 并证明了当m = 2 时，该算法的最坏情况界为；，当m 3 时，最坏情况界为2 一鬲与 在许多应用中，总是将顾客分成两个等级，即p 顾客和一般顾客因此本章 讨论服务分为两个等级的情况，即9 嘎) 和g ( 马) 取i 或2 不失一般性，给定了和朋， 假设服务等级为2 的机器共有冶，1 t m l ，其余机器的服务等级为1 我们称 此问题为具有两个服务等级的平行机排序问题，并将它的实例简记为( 了，m ，t ) ， 用c + ( j ，朋，) 表示实例( 了，m ，t ) 的最优解值 对于任何机器集m ，在本文的以下章节中均假设m 中的箱子按服务等 级9 ( m 1 ) 29 ( m 2 ) 9 ( a d k ) 排列 第二章具有两个服务等级的平行机排序问题 2 2 算法描述 本节设计的算法，是以装箱问题的经典算法f f d 为基础的下面给出具有两 个服务等级的裴箱问题实例在某种意义上，这类似于极小化完工时间的经典平 行机排序问题与装箱问题之间的对偶关系 将排序问题实例( 了，川，t ) 的m 台机器看成m 个箱子，j 中n 个任务看成礼个有 长度的物品，物品长度为任务的加工时间，机器和任务的服务等级分别看成对 应的箱子和物品的服务等级，服务等级为2 的箱子只能装服务等级为2 的物品， 服务等级为l 的箱子可以装服务等级为l 和2 的物品给定一个上界c ，一个可行 装箱是指将了分成m 个不交的子集p = ( p 1 ，b ，p m ) ，只中物品放入第i 个箱 子中，使得e ( r ) 曼c ，1 曼i m ，并且仅当g ( a 磊) g ( 弓) ，码允许属于只装箱 问题的目标函数是最小化箱子的数目m 令o p t ( j ，c ，t ) 表示箱子容量为g 时， m 的最小可能值由前面c + ( j ，m ，t ) 的定义，针对具有两个服务等级的装箱问题， 有c 4 ( 了，m ，t ) = m i n c ：o p t ( f f ，c ，t ) m ) 显然要找到o p t ( j ，c ，t ) 也是 强n p 难的下面我们给出子程序m f f d ( 修正的f f d ) ，它能很快找出近似优装 箱 不失一般性，对任意给定的( 了，a 4 ，t ) ，假设，= j 1 u j 2 ，其中j 1 和j 2 分别为 服务等级为1 和2 的物品集，并且m 个箱子已按次序排好，前t 个箱子的服务等级 为2 。后m t 个箱子的服务等级为1 对任意给定的f j ，a 4 ，t ) ，假定箱子容量为a 下述子程序m f f d 先将中 的物品用f f d 装箱，假设在这一步中共用了n 个箱子若r l t ，则前t 个箱子 不再装物品。然后用f f d 分配，1 中的物品，假发在这一步中共用了r 2 一t 个箱 子若r ， t ，则前t 个箱子不再装任何物品，而其它箱子中物品全部取出重新装 箱；记l ，= j 2 【疋，r ，忽略j 1 和j 2 中物品的服务等级，然后将这些物品一起 用f f d 分配，假设在这一步中共用了”2 一个箱子子程序的具体描述如下： 子程荐m f f d 1 将沪中的物品按f f d 装到第1 ，2 ，r 1 个箱子中，若t 1 墨埠 2 ，否则转3 ； 2 将j 1 中的物品按f f d 装到第t 十1 ，t + 2 ，r 2 个箱子中； 3 将j 2 u 2 lp 牙i j j l 中的物品按f f d 装到第t + 1 ，t + 2 ，r 2 个箱子中 记子程序m f f d 中所需要的箱子个数：为m f f d ( f l ，g n 在接下来的各节 一6 一 第二章具有两个服务等级的平行机排序问题 中，我们主要讨论：给定j 和箱子数目m ，以及它们对应的服务等级，箱子容量g 为 多大时，m f f d ( f f ，c ，t ) m ? 为此定义 r 。= i n f r ：剥所有( 了，m ，t ) ，m f f d ( f f ，r c + ( j ，3 , t ，t ) ，t ) m ) 则r 。1 ，且r 。满足下面的引理 引理2 2 1 ：给定具有两个服务等级的装箱问题任意实例( z 朋，t ) ，对所有r r 。，有m f f d ( f f ，r c + ( j ，m ，t ) ，t ) m i , v n ：首先，我们用反证法证明对任意( ，m ，t ) ，m f f d ( j ，r 。c ( 了，州，t ) ，t ) 5 m 成立假设这个结论不成立，即存在一个( 了，3 , t ，t ) ，使 得m f f d ( f l ，r 。c + ( 歹，m ，t ) ，t ) m 对此( ，m ，) ，令c = r m c 4 ( 了，m ，f ) ，执 行子程序m f f d 在第一步中，f f d 每次将j 2 中的某个物品装到不是第1 个箱 子的某个箱子中时，是因为若将这个物品装到下标较小的箱子中，将会导致这 个箱子中所有物品的长度之和与g 之差为一正数令6 是这些正数中最小的 个同样，在第二步( 或第三步) 中，f f d 每次将j 1 ( 或l ，2 7 u j l ) 中的某个物品装到 第t + 1 个箱子以外的某个服务等级为1 的箱子中，也是因为若将这个物品装到 下标较小的箱子中，将会导致这个箱子中所有物品的长度之和与g 之差为一 正数令e 是这些正数中最小的一个若d 0 ，则令= m i n 6 ，) 若d = 0 ，则 令e = g - ，此时所有服务等级为2 的物品都装在服务等级为2 的第一个箱子中那 么，对任意满足大于等于g 且小于c + f 的c ，当箱子容量分别为g 和g 7 时，子 程序中所需要的箱子数是一样多的，因此m f f d ( j ，c 7 ，t ) m 然而由r 。的定 义，我们知道存在r ，当r 任意趋近r 。时，m f f d ( j ，r c + ( ，m ，t ) ，) m 选择这样一个r ，并且使得r ，m ，t ) 1 ，使 得m f f d ( z o z r 。c ( 了，m ，t ) ，) m ，则可以利用j 构造一个新物品 集歹7 ，使得m f f d ( f f ，r r n c + ( 了7 ，3 4 ，t ) ，t ) m ，从而与我们刚刚所证明的结 论矛盾由此可知引理2 2 1 结论成立下面我们来进行具体证明假设存在 这样的( 了，m ，t ) ，最优解值j , j c 4 ( 了，m ，t ) 将最优解中每个箱子的容量扩大 到驴( j ，a 4 ，t ) ，并通过以下四步增加一些新的物品到了中形成新物品集了7 1 新增加物品的长度小于了中任意一个物品的长度 一7 第二章具有两个服务等级的平行机排序问题 2 任意两个新增加的物品置，乃，若9 ) = 2 ，9 ( 乃) = 1 ，则有z ( 正) z ( 弓) 3 新增加的服务等级为2 的物品恰好使得扩大容量后的第1 ，2 ，t 个箱子被装 满 4 新增加的服务等级为l 的物品恰好使得扩大容量后的第t + 1 ，t + 2 ，m 个 箱子被装满 此时有( ，7 ，川，t ) = 眇( j ，m ，t ) 然而在m f f f d 对j 装箱时，在对新增加 的服务等级为1 的物品进行装箱之前，第m + 1 个箱子中已经装有物品了，所 以m f f d ( j ，血口( j ，m ，t ) ，t ) m & p m f f d ( j ，r 饥( ，川，t ) ，t ) ? t t 与先前我们所证明的结论矛盾 接下来我们开始介绍本文给出的算法m m f 对任意给定的( 了，m ，z ) ，先 确定上界g u 和下界c l ，令箱子的容量为盟等烈，然后用二分法迭代，判断子程 序m f f d 中所需要的箱子个数是否小于等于m 以调整箱子容量的上界和下界 迭代次后( 女为预先给定的迭代次数) ，以上界作为输出该算法中的初始上界 为2 岛，初始下界为函，其中岛= m a x ( t 。“) ，矬，警) ，2 ( p “) = m a x ( t ) l t 了) 算法m m f 1 c u o 】_ 2 c o ，c l i o 卜c o ，i = 1 2 若t 停止，否则c = c u i - l l + 2 c l i - 1 3 若m f f d ( j ，c ，t ) sm ，令e u = e ，i = i + 1 ，转2 4 若m f f d ( j ，c ，t ) m ，令c l i = c ，i = i + 1 ，转2 引理2 2 2 ：c + ( 了，m ，t ) c o 证明：若c o = l ( t “) ，则包含p “的箱子的长度不小于岛，此时显然 有g + ( 了，m ，) c o 若岛= 警，因为z ( 了) = 垩，f ( 耳) ，所以警 m a x ；2 ( 耳) ，即c + ( j ，m ，t ) c o 若岛= 坠m 盟- t ，因为j 1 中的物品只能装到m t 个 服务等级为l 的箱子中，所以z ( 一) 銎。+ 。f ( 芹) ，同理可得驴( ，m ，t ) 矬= c o _ 第二章具有两个服务等级的平行机排序问题 引理2 23 ：( 1 ) 对任意c m ( 2 ) 对任意c2 c u o 】= 2 c o ，m f f d ( j ，c ，t ) m 证明：因为c + ( ，m ，t ) 岛，所以结论( 1 ) 显然下证( 2 ) ，假设存在实例( 了，a 4 ，) ， 使得c c u o 且_ m f f d ( j ，c ，t ) m 不失一般性，令正是第一个装到第m + 1 个箱子中的物品，由q2l ( t “) 可知，c o f ( 乃) 根据9 ( 乃) 的值分两种情况讨 论 情况l ：9 ( 巧) = 2 ， 因为乃不能装入前m 个箱子故有f ( 最) + f ( 乃) c 2 c o ，1 冬i 冬m 即器。( r ) + m t ( t j ) 2 m c o 又因为 ( 乃) sc o ，故翟11 ( 只) + t ( t j ) ( m + 1 ) 岛，与兰17 ( 只) + t ( t j ) f ( ，) m 岛矛盾 情况2 ：夕( 乃) = 1 a ) 若在子程序m f f d 中是由第2 步分配物品到第t + 1 ，t + 2 ， 2 个箱子 中，n x c t + 1 is 也，只中的物品全部来自l ，1 由岛黔可知，罢抖l f ( 只) + 2 ( 乃) f ( j 1 ) ( t o , t ) c o 又因为乃不能放到最后m t 个箱予中，故有t ( 5 ) + f ( 弓) 2 c o ，t + l i m 从+ 1 到m 对这个不等式求和，可得当十1 f ( 只) + e ( 巧) ( m t + 1 ) 岛，矛盾 b ) 若在子程序m f f d 中是由第3 步分配物品到第t + 1 ，t + 2 ，r 2 个箱子中， 则l ，2 0 对任意n l ，因为死不能装到前t 个箱子中，故有f ( 只) + z ( 珏) 2 c o ， 从而l ( 只) c o ，1 ist 又因为乃不能装入第t 十1 ，- 一，m 个箱子中，所以同样 有f ( 只) 岛，t + 1s i5 m 因此兰1f ( 只) m c o ，矛盾 一 定理2 , 2 4 ：对任意m 2 及女1 ，有r ( m m f m ) r 。十( ；) 2 $ i e n ：假设存在m ，k ，使得r ( m m f k ) r 。+ ( ；) 根据r ( m m f ) 的定义 可知，存在实例( 了，m ，t ) ，运用算法m m f 迭代次，算法m m f 中最后输出 值大于( r 。+ ( j ) ) 9 ( d r ，m ，) 由丁这个值不能超过g u n ，因此c u k 1 ( ，m + ( ) ) c ”( ，朋，f ) 另方面，c u k 】一c l k j = ( ；) 。( c u o j c l o j ) s ( j ) c 4 ( 了，m ，t ) 因此可得a l 9 ( ，川，f ) 又因为对任意m 2 ， 有r 。 l ，所以g l 嘲 c l i o 也就是说在算法m m f 的执行过程中，子程序 会以箱子容量为c l k 】执行一次操作，并得到m f f d ( j ，c l k ，t ) m 然而 出e l 吲r 。c + ( 了，朋，t ) 及引理2 2 1 可知这是不可能的从而定理2 2 4 得证一 9 第二章具有两个服务等级的平行机排序问题 2 3 上界 本节用反证法证明对m m f 算法，4 3 为此先引入一些定义 对任意一对整数p q ，称实例( ，m ，t ) 为一个p g 一反例，如果 m f f d ( j ，p ，t ) m o p t ( j ，q ，t ) 1 , 叭p q 一反例的定义可知，尽管存在一种装箱方法，可以将j 中的物品装到m 个 容量为g 的箱子中，其中有t 个箱子的服务等级为2 ，且仅当9 ( 坛) 9 ( 乃) 时，只能 包含乃，但是即使当箱子容量为p g 时，子程序m f f d 也做不到显然如 果 p q ，则存在一个m = m 的p 向一反例 ( 了，川，t ) 构成最小p 加一反例，是指了，m 满足以下条件： 1 ( 了，m ，t ) 构成一个p q 一反例； 2 任意满足条件1 的( ，7 ，m ，t ) ，有l | fjf ； 3 对任意a 4 c 朋，其中m 7 中有m 个箱子，m 中有m 个箱子，且1sm * ，故m f f d ( j 1 ，4 ，t ) = o p t ( j 1 ，3 ，t ) = m t 而对够，m ，t ) 执行 予程序m f f d 时，中的物品全部装在前t 个箱子中，所以m f f d ( j ，4 ，t ) = o p t ( 了，3 ，t ) = m ，与( j ，m ，t ) 为最小反例矛盾 一 因此，下文对最小4 3 反例的讨论中，我们只考n j 2 d 的情况令 _ p = ( p 1 ，p 2 ，p m + 1 ) 为限定箱子容量n 4 ，对这个最小4 ，3 - 反例运用子程 y 芋m f f d n ，所得到的装箱，而矿= ( 矸，巧，焉) 为箱子容量为3 时所得 的最优装箱令x = u 2 。只及s = m i n l ( t ) l t j 2 ， 引理2 3 3 ：对任意弓x ：有2 ( 弓) 8 ，且s l 证明：先用反证法证明对任意蜀x ，f ( 乃) s 成立假设存在乃x 使 得f ( 巧) 4 ，lsi m ，并且竺1f ( 只) 十 f ( l ) = 2 ( 了) s3 m ，由这m + 1 个不等式可以推出2 ( 露) l ，即s 1 情况2 ：9 ( 兀) = 1 令f ( 乃) = a ，则同样有s a 假设s 1 n n l ( p 1 ) + s 4 ，1 茎j s t ，即e2 ( p i ) + t s 4 t 又因为8s 1 ，所以有 ( 2 1 ) 乳 r 。 第二章具有两个服务等级的平行机排序问题 ，中物品的长度满足下面这个不等式 tl f ( 只) + l ( p j ) + 口3 m ( 2 2 ) i = l j = t + l 出于r 不能装到第t + 1 ，m 个箱子中，所以有 l ( p j ) + a 4 ，t + 1 m ( 2 3 ) m ( 2 1 ) 一( 2 3 ) 式可得n 翮m - t 1 与假设矛盾 由日理2 3 3 矢口s = m i n ( t t ) i 正j 2 冀 引理2 3 4 ：f 碍i = 2 ，1si t 并且s 吾 z 证明：由引理2 3 3 5 j 知，对任意t j 2 ，有l ( r ) 1 故1 片1 s2 ，1 is 假 设存在某个i 耳f = l ，1 t 令耳= 。) ，则有f ( 。) l ( t 1 ) ，这里n 为服务 等级为2 的最大的物品由子程序的执行过程可知丑p 】利用j 构造新物品 集了7 = 了p l ，即= u 篓1p i 下面根据t 的取值讨论，得出与( j ，朋，t ) 为最 小反例相矛盾的结论由此可知引理2 34 结论成立 若t 1 ，令m7 = 朋 m ) 对( 了，m7 ，t 1 ) 执行子程序m f f d 得到一 个装箱p7 ，p 7 = ( p 2 ，f 打1 ) ，目o m f f d ( j ，4 ，t 一1 ) = m 考虑最优解p + ，交 换p + 中r t 和z 的位置构造新的装箱p ”，由于z ( 噩) 芝f ( 茁) ，因此z ( 爿7 ) 3 ，对所 有1 j m 成立，而且掣= ( 乃 因此从中删除p 1 中的所有物品就可以得 到了7 的一个装箱，且该装箱至多用m 一1 个容量为3 的箱子因此o p t ( 了，3 ，t 一 1 ) m 1 由于m 一1 1 首先用反证法证明c ( 噩) e ( 马) f ( 丑) 2 假设从某个正开始2 ( 正) 2 ，ist 对，a 4 ，t ) 运用子程序m f f d ，由于前面i 一1 个物品的长度都大于2 ， 故前面i 一1 个物品分别装在前i 一1 个箱子中接下来考虑互和正+ l 若正能放 入只，( i 1 i ) 中，则如图l ( a ) 所示若正不能放入前面i 一1 个箱子中，则正放在第i 个 箱子中接着考虑正+ 1 若五十l 能放八( i 2 1 ，所p a l ( x ) f ( 死) ，并 且z ( v ) z 十1 ) 对于( a ) 中的情况，构造新物品集了= j ( 丑。，t d 若t 1 ， 令朋7 = m 坛，) 对( ，m ，t 一1 ) 执行子程序m f f d 得到一个装箱，p 7 = ( p l ，- ，只，一l ，只，+ h ，p m + 1 ) ，目p m f f d ( j 7 ，4 ，t 一1 ) = m 考虑最优解p + ， 将p 中的噩。与5 7 ，五与y 交换得到新的装箱p ”由于z ( 正，) f ( 正) f ( z ) z ( ) ， r；b；e。； 一 z l) a 第二章具有两个服务等级的平行机排序问题 因此 ( p _ ? ) s3 ，对所有1 jsm ，j r 成立，并且群= 互。，互) 因此从p ”中 删除物品五，和正就可以得到，7 的一个装箱，且该装箱至多用m 一1 个容量为3 的 箱子因此o p t ( 了7 ，3 ，t 1 ) m 1 由于m l m ，与( 了，3 , l ，t ) 为最小 反例矛盾若t = 1 ，则耳= 矸= 伽，g ) ，即服务等级为2 的箱子仅有一个令 了7 中所有物品的服务等级都为1 ，贝u m f f d ( , 7 ，4 ，t ) = m + 1 考虑最优解_ p + ， 将p + 中的五，与x ，正与y 交换得到新的装箱p ”，则2 ( 掣) 3 ，对所有2 j m 成 立，而且爿7 = 五，正因此从尹”中删除物品互，和正就可以得到，的一个装 箱，且该装箱至多用m 1 个容量为3 的箱子加上第一个服务等级为2 的空箱 子，所以o p t ( j ，3 ，t ) m 由于j i 1 ，所以f ( z ) 1 r l ( t 1 ) 2 伍) 2 ，所以在最优解 1 4 一 寓 第二章具有两个服务等级的平行机排序问题 中乃，马，丑，掣分别装在服务等级为1 的不同的t + 1 4 箱子中不失一般性，假 设正昂，霹，略= 。，可) ，t + 1 j 1 ，如m ，1 j ost ，如图2 ( b ) 最后我们证明图2 中的情况也不可能出现，从而1 只i = 1 ，1 i t 成立首先 构造新物品集了= j 正，霉 若t l ，令m 7 = 川 舰) 对( 歹7 ，m ，t 1 ) 运用子程) 芋m f f d 得到一个装箱p 7 ，p 7 = ( p 1 ，只“最+ h t ，p m + 1 ) ， 目p m f f d ( , j 7 ，4 ，t 一1 ) = m 根据最优解构造一个新的装箱其中， 碟= 正，珊，= 壤，噬= p i t u 壤亿，掣 ，彤= 口，j 如，j t ，丘 又因为f ( 矗) 4 - z ( ) s6 ，f ( 互) + f ( 掣) 3 ，所以f ( 喂) 3 因此2 ( 弓7 ) 3 ，对所 有1