装箱问题和排序问题.ppt

装箱问题和排序问题 本讲主要内容 装箱问题（ Bin Packing） 最小完工时间安排（排序问题）（ Minimum Makespan Scheduling) Bin Packing 装箱问题：给定 n个物件，大小为 用单位体积的箱子来装这些物件，找一个装箱方 案使得所用的箱子数目最少？ 通俗地说，把 分成最少的组数， 使得每组数的和丌超过 1。 在工业中有许多应用，譬如在下料问题中，箱子 代表标准木料的长度，而 表示实际问题中需要 裁截成的木料长度。当然，需要的标准料越少越 好。 1,0(, . . , 21 naaa 1,0(, . . , 21 naaa ia 一个 2倍近似算法 直到所有物件装完。 装入其中。将则打开一个新的箱子 若其不能装入任一现考虑 已经装箱步，假定在算法第 ，譬如将物件按任意顺序排列 .3 , )1(,.,., ,., .2 ,., 1. :lg 1 21 121 21 ik jik i n aB kjBaBBB aaai aaa or i t hmAF i tF i r s t 证明 .2.21- , opt 2 1 ( 1/ 2 1 1 1 optmoptm opta m a mm n i i n i i 即 的下界，即之和是最优解又因为所有物件的大小 为什么？）因此，。半，即装了不少于其容量的一 个箱子个箱子，则至少有假定算法中用了 一个不可逼近性结果 2 1 Y E S2 -. 2 1 ,., ) (1 -3/ 2,0 1 21 的两个箱子内。容量为 个物件可放入当且仅当）上述问题的回答是（ 难的。已知该判定问题是使得每部分之和恰好为 部分，否可将其可划分为两个非负数给定 ：）考虑下述划分问题证明：（ 。的近似算法，除非装箱问题无对定理 i i i i n a n NPa aaan pr obl e mpa r t i t i on NPP ，划分问题有解。则（显然若 划分问题无解；因此 若近似算法计算结果具体方法： 难划分问题。上述而在多项式时间内解决 ，从箱问题的最优解是否为利用该近似算法判定装 的近似算法，则可以如果装箱问题存在）（ 2),12)( ,2 2/3 )( ,3)( -NP 2 -3/ 2 3 optoptIA IA opt IA 题。问题；否则成为离线问装箱问题成为在线装箱 这样的要装完一箱运走一箱，有时由于场地原因，需装箱问题有许多形式，。 ）的证明。（可见他的书 年）给出了一个较简单越民义页的证明；曾给出了年）（ 无法再改进。，算法得到的结果是紧的上述可以证明， 装箱问题近似结果为： 该算法给出方法。顺序排列，然后再用首先将物件按从大到小算法。 ）的（到一种称为算法加以简单改造，得。对 注： 2 1991( 100 1973J o h n s o n FFD 1.1 1 / 9 o p tA ( I ) FF FFDD e c r e a s i n g-F i t-F i r s tFF1 NP-难问题按照其可逼近性分类 没有常数倍近似比 ： Set-Cover， TSP， Maximum Independent Set, 有常数倍近似比但丌 能仸意接近 1 ： Vertex-Cover， Bin Packing, 近似比可以为 1+（仸意逼近 1）。 Knapsack， Scheduling. 多项式时间近似方案（ Polynomial Time Approximation Scheme ,PTAS), 渐近多项式时间近似方案 )( n )()1()(,0 /1 nO Io p tIAA 譬如 的多项式。是定的算法的计算复杂性对固 ，使得存在多项式时间算法 .)1(, , N,0, optANopt A 给出的解不超过算法 使得只要问题的最优解法以及一个多项式时间算 Sc h e m e s )i o n A p p r o x i m a t T i m e Po l y n o m i a l A s y m p t o t i c ( 一个渐进的 PTAS .)1(, , N,0, 2 11 ,1)21( n,2/10,2 o p tANo p t A o p t o p to p t A 给出的解不超过算法 使得只要问题的最优解法以及一个多项式时间算 间方案题存在渐进的多项式时上述定理表明，装箱问。 逼近的原因。是对一般装箱问题难以可以任意小，因此，这 但每个物件的大小很小，的装箱问题的实例中，。在定理注： 为问题最优解。超过其给出装箱问题的解不 ，的多项式时间算法存在关于：定理 限制装箱问题 出最优解。多项式时间通过枚举找的多项式。因此可以在 这是关于的装箱数目地上界为因此，所有可能的可行 这是一个固定的常数。是数目的装箱类型的上界 。因此，所有不同：数的上界是证明：每个箱子中物件 题的最优解。法可以求出限制装箱问则，存在多项式时间算 个型号。多有所有不同的物件大小至） ；）每个物件大小至少为 ：考虑下述限制装箱问题 。为一个固定的非负整数给定。令。令引理 n. . 1 M 2 1 K01 Rn R KM M CP CR K 限制装箱问题 一大小的两个物件）。两个不同组可以包含同 个不同尺寸的物件。多个组，使得每组含有至然后将其划分为 排列，个物件按从小到大顺序将定的实例。表示装箱问题的一个给令 证明分为三个步骤：证明： 近似算法。）问题的（ 在该限制装箱的限制装箱问题，则存是考虑每个物件大小至少。给定引理 ( 1 I 1. S t e p -1 .02 2 2 nQK n . ),()1()()( J 1KJ J .2 St e p 从而引理成立。下面证明行。原来的物件尺寸仍然可 该解对的最优解。可以找出实例，引理个不同尺寸的物件，由至多有由于实例 ，可以构造新的实例的尺寸，寸放大到该组最大物件通过将每组每个物件尺 IoptJoptIA )()1()( nQ ,nop t ( I ) I Q .( ? )op t ( I )Q)op t ( J op t ( J ) ( ? )QJ JJ .op t ( I )op t ( J ,J 3. S t e p 2 IoptJoptopt ， ，中每个物件大小至少是实例 因此， 。个物件之外的最大的 实例的一个装箱方案，除了的一个装箱方案给出关于注意到， （？）显然从而构造一个新的实例 件的尺寸，尺寸缩小到该组最小物再通过将每组每个物件 定理 2的证明 Fi t-Fi r s t ( 2 ) )()1(I 2 II I ( 1 ) 才打开新的箱子。开箱子的情况下， 法装入已打里装，除非在有物件无方式往已经打开的箱子 的的物件用尺寸小于然后，我们开始将那些 装箱方法。 个箱子的的不超过我们可以找到问题，由引理 装箱问题的实例。的物件去掉以后得到的那些尺寸大小小于 中表示将令定的实例，表示装箱问题的一个给令 Io p t 。定理证毕。其中我们用到假设 我们得到：即： 的下界，由于该数目为最优解大小总合至少为 中的物件的因此，实例至少装了已经打开的箱子每个都 其余除了最后一个箱子外，为总的装箱数。显然，否则，令 则装箱数，如果无需打开新的箱子 1 / 20 .1)21(1 1 M ).1)(1( ).-1)(1( I).1( M ) o p t ( I ) .(1) o p t ( I (1 3 o p t o p t Mo p t o p tM 算法总结 Fi t-Fi r s t 5 4 1 3 2 2 1 方式装箱。的物件用对尺寸小于。 尺寸的物件进行装箱；用该装箱方式来对原有。 ）找出最优解（引理。 ）目为一常数；（引理从而不同尺寸物件的数 大物件尺寸代替，寸的物件的尺寸该组最分组并把每组中把小尺。 的物件；。去掉尺寸小于 可总结如下：算法 A 排序问题 排序问题（ Minimum Makespan Scheduling） 给定 n个工件 的加工时间 以及一个整数 m， 给工件安排一个在 m个相同机 器上的加工顺序，使得最后的完工时间 （ makespan）最小。 该问题是排序问题中最简单的问题。在生产调度 中有广泛的应用。 nppp ,. ., 21nJJJ ,. . , 21 Graham 的 2-近似算法 算法描述（ List Scheduling） Step 1.将工件仸意排序； Step 2.将工件按照上述顺序分配给机器，将下一 个工件安排给当前负荷最轻（剩余加工时 间最少）的机器。直到所有工件加工完毕 . 算法分析 上述算法的要点是， 让机器丌要闲着，只要有机 器加工完，就把排在最前面尚待加工的工件让该 机器去做。 算法分析的要点是：最小 makespan取决于最后 一个工件的完工时间，在最后一个活开始加工之 前，没有机器是空闲的。 LBoptppmLB p pm i i i ii i i 则令 工件的最大加工时间。 平均时间，。一台机器需要运行的 有如下下界：最优解 .m a x ,/1m a x ;m a x, 2 ;/11 optM a ke s pa n .2. . 1 op tps t ar top tp op tp m s t ar t s t ar t MJs t ar t JM jjj i ij j jjj ji 间因此，算法最后完工时又， （为什么？） 这意味着没有空闲， 前都在机器，因此，所有机器工件安排给负荷最轻的 因为算法总是将上开始加工的时刻，在为工件令完成的工件。 为这台机器上最后机器，令为按照算法最后完工的令 一个紧的例子 。 但为由算法得到的完成时间 ，排在其他所有工件之后，还有一个工件的工时为 为单位时间，个工时个工件按顺序排列，每有 2 1 2 s u p )( s u p .1,2 , 2 m m opt IA moptm m m mI Lowest Fit Decreasing（ LFD） 算法描述（ LFD） Step 1.将工件按工时从高到低排列； Step 2.将工件按照上述顺序分配给机器，将下一 个工件安排给当前负荷最轻（剩余加工时 间最少）的机器。直到所有工件加工完毕 . nppp . .21 .j-1 j , ,J.,J O Jj)k,J /,.,/,., /j-m jm O M O2m ,n L T D1 S t e p 1/ 3m-4/ 3 L F D j2 1111 12,1 i 的机器上恰好被安排在 个工件使得前可得一最优排序做同样处理，对仍是一最优排序。 是最优排序，故经交换由于案不会改变完工时间，工件交换，所得加工方 上与上，则可将（而是被安排到没有被安排到若 台：两个台；：一个假定 前面。件，则工时长的总排在若一台机器安排两个工假定： 台；个机器：两个其余台只安排一个零件，台机器中有下，设在 。上之多只安排两个工件使得每台机器 ，且存在最优排序先考虑一个特殊情形： 可求出最优解。件不超过两台，则。若每台机器上加工工证明： 。算法的近似比为定理。上述 MMMM MMMMM kj mjj ,.) .1,0 J , m)i1 (MJ : ,.,J ; JJ J M J JM MMJJ 1 ii ,2211j 1 11ni n k i1jh khn1 jJ JJJ pppp pppp J lj ln njn ilij njij l j 上（在 排排在一最优排序满足 得到做同样的处理与与对 。交换后总的工时不增加因此， 则，和交换 ，： ，： 上，和被分别安排在和假定 ： 矛盾！因此， ）？算法但按照 。该实例的最有解，： 考虑为最后完工者，令若不然， 必为最后完工者。我们证明：在算法中， 。为使上式成立的最小的令 ）（ 使得及， 则存在假定结论不成立，现讨论一般情形， .3/13/4 )( )( (),()(L F D , J.,JJI .J J n * 1/ 3m- 3/4/)( ,.,J.,JJ .2 21 r n 21n21 m opt IA opt IA IAIA optopt nr n optIA ppp St e p r n 矛盾！）得由（ 在此情况下，但前面已经证明 个工件。每一个机器至多加工两因此，在最优排序下， 或 得：由 因此， 因此， 又 的开始加工时间，则为令 . 3 1 3 4 1 * .)( , 3.3/ . 1 1 3 1 3 4 ( *). 1 1 )( ,/1 . 1 /1)( /1 .)(JS 1 1 11 nn m optIA poptoptp opt p m m m opt p m m opt IA pmopt p m m pmIA pmS pSIA nn n n ni i n ni i ni in nn 排序问题的 PTAS 排序问题不装箱问题有如下紧密联系： 排序问题存在最优解 t，当且仅当 n个大小分别为 的物件可以装入 m个容量为 t的箱子。 因此，可将排序问题自转化为装箱问题： 令 I表示 n个物件大小 ；令 表 示能装下 n个物件的容量为 t的箱子的最少数目； 则最小排序问题转化为： nppp ,. ., 21 nppp ,. ., 21 ),( tIbin ),(,m in mtIb in st 基本思想 排序问题的最优解在 LB， 2LB内，利用二分搜索，将 问题转化为装箱问题 这一转化似乎丌可行，因为装箱问题仍然是 NP-难的 但是， 对于物件尺寸型号固定的限制装箱问题，有多项 式算法 不同物件型号数目固定的装箱问题 )2( )1( 1 其加以改进。并从算法运行时间上对 限制，去掉物件大小有下界的 ：两个方面改进引理求解限制装箱问题，从我们将用动态规划方法 动态规划 件的最少的箱子数目。 表示能够装下这些物物件的数目。令 的每个分量表示某一尺寸表示组有序数组 一则装箱问题的实例可由序，固定一个物件尺寸的顺 。为的数目。假定箱子容量为固定的不同物件尺寸令 ),. .,( ,),. .,( 1 21 21 k k iiiB I N S iii k 动态 规划（续） 个元素。至多包含 。元有序数组所有 我们首先计算集合对于一个固定的实例， )O ( nQ 1,0,1),.,(|),.,(kQ n,n ),n,.,n,(n 1. S t e p k 2121 i ik21 kinqqqqB I N Sqqq iikk 动态规划（续） 。从而可确定 的时间为，因此，计算整个表格计算每个元素费时 余元素：然后用下述迭代来求其 最初，令 。 的所有元素，其中维表格下面计算 ),.,( ).().( ( ? ) ).,.,(m i n1),.,( .,1)( ,.,1,0.,.,1,0,.1,0),.,( ),.,(k 2. S t e p 21 2 k221121 2121 21 k kk kQqk kk k nnnB I N S nOnO qiqiqiB I N SiiiB I N S QqqB I N S nnniii iiiB I N S 把排序问题划归为限制装箱问题 基本思想： 如果我们能容忍在计算最小 makespan问题的一 点小的误差，则我们可把该问题在多项式时间内 划归为限制装箱问题。 主要有两种类型的误差 ： 把物件的尺寸做一些调整，使得丌同尺寸的数目 有界。 终止二分搜索，保证多项式时间算法。 每种误差都可以做到仸意小，但代价是计算时间 的增加。 但对固定的误差， 我们可以得到多项 式时间近似算法。 箱子容量固定的装箱算法 (核心算法） . 1 l og 0i 1)1(,)1( s m a l l,2, 1 i1 kp tpttp t tLBLBt j j ii j 数目不会超过的不同值的的 这样。代替，）（被每个 其尺寸：余物件按下述方法缩小。先去掉小的物件，其尺寸小于 ，如果其的物件称为小于为固定参数，令令 核心算法（续） ).t ( 1 )t,(I,t t1 )1( t （该方案中箱子尺寸为方案得到的装箱数 表示该装箱。令打开的箱子至少装了开新的箱子之前，已经 的箱子。显然，在打都装不下时，才打开新只有在已经打开的箱子 入箱子中剩余的部分，将小物件用贪婪算法装保持这样的箱子容量， 的箱子仍然适用。）装箱方案对于容量为（ 则该物件，倍，如果考虑装原来的小了于所有物件尺寸最多缩 箱数。由法求出缩小后物件的装的箱子，用动态规划方对于容量为 。少为的箱子的最少装箱数至为 装入容量，因此，把入了子外，其余箱子至少装否则，除了最后一个箱 的箱子。地装入大小为缩小后的物件已经最优 为子，引理显然成立，因小物件时没有打开新箱证明：如果算法在装入 我们有引理 ),( t It t ).,(),( 3. tI tIb i ntI 定最优）的箱子的装箱数（不一装入容量为用算法把 需要的最少装箱数。的箱子装用容量为 )t1(I),( It),( tI tIb i n .),(|m in ),(|m in optmtIt mtIbi nstopt 推论： 。 二分搜索法 ) opt .(1 LBopt L B .m)t,(I,|m i n tT TL B ,-Tm)t,(I,|m i n t ) opt(1T 4 T 1 l og LB 2, 2 因此，内，必须位于证明：显然 引理 间的最右端。则为停止搜索时得到的区令次。要迭代 总共需时，停止搜索。区间长度小于区间长度缩小一半，当 ，每迭代一次，初始区间长度为进行二分搜索，对区间 LB LBLB 二分搜索 . 1 l o g), 1 l o g( .)31()1(m a k e s p a n . )T1Tt 12 2 2 knO optopt k 其中整个计算时间为 不超过上述算法得出定理 ，因而得到（序问题的一个解应用核心算法，得到排对 Thanks, End