带服务等级的排序问题的若干研究.pdf

y7 3 8 2 3 l带服务等级的排序问题的若干研究(申请浙江大学理学硕士学位论文)培养单位学科研究生指导教师浙江大学数学系运筹学与控制论周萍何勇教授二0 0 六年三月摘要摘要本文主要研究具有服务等级的平行机排序问题预先赋予每个任务和每台机器一个服务等级标号，使得服务等级低的机器既能加工服务等级低的任务，又能加工服务等级高的任务，而服务等级高的机器只能加工服务等级高的任务目标函数是极小化最大机器完工时间这类问题最先是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 TA b s t r a c tA b s t r a c tT 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 ep 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 rG 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 nt 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 om 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 sp 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 og 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 Fw h i c hi sm o d i f i e df r o mM 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 Fi s；+()，w h e r eki 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 rc 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 ef 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 wt h eb o u n di St i g h tK 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 DM U l 0 I F I TI I第一章绪论1 1 排序问题第一章绪论排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问题由于它在现实计算机系统中多方面的应用，排序问题早已成为理论计算机学界的研究领域之一，并已拥有大量结果除了在计算机科学领域以外，排序问题还在管理科学和工程技术等诸多方面具有大量的应用近几十年来，排序问题得到了运筹学界、计算机科学界、工程学界和管理学界极大的关注，鉴于经典问题的研究日益深入，而具有实际背景的新问题又不断涌现，可以说，对排序问题的研究正在进入成熟期，按照学术界多年来形成的惯例，一般用所谓的三参数表示法(t h r e e f i e l dr 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 Ws 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 D1 将沪中的物品按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)5m 成立假设这个结论不成立，即存在一个(了，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)lT 了)算法M M F1 c u o】_ 2 C o，C L I O 卜C o，i=12 若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，转24 若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)对任意C2c 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+1si5m 因此兰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有r。p q 因此，最小能J p q 一反例是指：(1)不存在lJ I p 口，则一定存在一个M=m 的塌+p q-反例为了用反证法证明r。的上界：勾4 3，我们假设存在一个最小的p g 一反例(了，M，t)，这里p=4，q=3 由最d、4 3-反例的定义直接可得引理2 3 1 引理2 3 1：J 必须满足以下条件：(1)M F F D(，4，t)=m+1，O P T(J，3，t)=m；(2)除咒外，J 中所有物品都由子程序M F F D 装到了前m 个箱子中引理2 3 2：在最小反例中，J 2 0 证明：对任意给定的了，如果J=0，$U J 2 中物品全部放入前t 个箱子中由于t，1 中物品只能放在后m t 个箱子中，所以我们讨论的最小反例等价于物品集为J 1，箱子数目为m t 时，M M F 不能将J 1 中物品全部装到这m t 个箱1 0 一第二章具有两个服务等级的平行机排序问题子中本文所设计的算法M M F 及子程序M F F D，在这种情况下就相当于经典平行机排序问题的M U L T I F I T 算法和经典装箱问题的F F D 算法 1 6；1 7 1 在文 1 7 o O 已经证明了，当子程序中所用箱子的容量不小于最优解中箱子容量的暑倍时，算法M M F 所用的箱子个数同最优解所需箱子个数一致又因为：*，故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(巧)s：则令了=，v j ，且M 不变由子程序M F F D 的执行过程可知，对J 和了7 中的物品装箱时，服务等级为2 且不能装到前t 个箱子中的物品是一致的，所以M F F D(，4，t)=M F F D(，7，4，t)=m+1 而在最优解中，去掉一个物品乃之后，所需要的箱子个数不会增加，即有O P T(J 7，3，t)m 又因为1J 1 1 由引理2 3 1(2)知咒装入第m+1 个箱子根据矗的服务等级分两种情况讨论情况1：9()=2 由于J 2 中物品长度从大到小排列，因此有f()=s 因N T 不能装到前m 个箱子中，故有f(R)+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。第二章具有两个服务等级的平行机排序问题，中物品的长度满足下面这个不等式tlf(只)+l(P j)+口3 m(2 2)i=lj=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 m，与(了，M，t)为最小反例矛盾若t=1，则碍=日=)，即服务等级为2 的箱子仅有个令5 r 7 中所有物品的服务等级都为1，N M F F D(J 7，4，t)=m+1 考虑最优解P 4，交换_ P+中马和。的位置构造新的装箱P”由于f(五)i(z)，因此(只)3，对所有1 Js7 7 1 成立，而且爿=乃 因此从P“中删除日的所有物品，就可以得到了7 的一个装箱，且该装箱至多用m 1 个容量为3 的箱子加上一个服务等级为2 的不能装J 7 中物品的箱子，所以o P T(J 7，3，t)m 由于IJ 7I 2 证明：不失一般性，假设J 2=正，T 2，最)，f(乃)t(T k)由引理2 3 3 可知l(T k l=8 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 i)中，则如图l(b)所示若丑十1 也不能放入前i 1 个箱子中，则互+1 一定放在第i 个箱子中，如图1(c)所示到此为止，已经讨论完了正与正+1 在M F F D 中可能出现的所有情况由引理2 3 4 可知最优解中前t 个箱子，每个箱子中恰好装有两个物品，不失一般性，令碍=z，y 如g qt(d)所示，1 r t，并假设2(z)f()(c)1S i t(b)i 2 2 成立因为f(z)+t(V)3 J|1(y)8 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。；一Zl)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)2 t，即霹也只能装在某个服务等级为l 的箱子中又因为2(霉)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 J m，J 如成立，并且J 7 一U 墨1 嚣尸：，故O P T(y 7，3，t 一1)sm 一1 由于1 T b 一1 m，与(，M，f)为最小反例矛盾若t=1，则令J 7 中所有物品的服务等级为1，此时M F F D(J ，4，t)=m+1 通过最优解P+构造一个和t 1 时一样的装箱P“，此时2(P，7)3，对l J m，J 如也成立，并且了=U 凳1 彤碟，因此O P T(J 7，3，t)m 又因为IJ 7I 2 定理2 3 6：对任意m 2，r。证明：假设存在最小4 3 一反例(，朋，o)不失一般性，记f()=并令丁为服务等级为2 的最小物品由引理2 3 5 知R=互)，1s t 由O I N 2 3 _ 3 知服务等级为2 的最小物品一定在，2 中，并且其长度大于1 故丁j 2 且c(T)=s 1，所以丁不能装入前个箱子中，即f 呱)+8 4，1 iS t，也即(2 4)因为咒不能装到第t4-1，t+2，m 个箱子中，故f(弓)+O t 4，t+1 J m将这m t 个不等式相加可得又因为mf(弓)+(m 一)口 4 沏一)