有色装箱问题近似算法的研究

有色装箱问题近似算法的研究摘要有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景.论文提出了求解有色装箱问题的新算法-LSCP算法,它首先对输入物品按颜色进行分类,将相同颜色的物品分成一类,放置时按照物品个数最多的那一类首先放置的原则,将物品进行装箱.实验证明,该算法与文献[5]中的SCPF-A算法相比具有更好的装箱效果,使用的箱子数更少.并从理论上论证了该算法的性能比SCPF-A算法更好.关键词装箱问题组合优化近似算法多处理器调度1引言有色装箱问题是一种带约束的一维装箱问题,它最初在支持容错的多处理器实时计算机系统的任务调度问题中被提出[1].有色装箱问题在多处理器任务调度[2,3]、并行处理、资源分配和现实生活中的包装等问题中有着广泛的应用背景.下面简单介绍一个有色装箱问题的例子:在多处理器实时调度系统中,往往需要将一个任务分割成若干个子任务.为了支持容错,每个子任务都必须有若干个拷贝,这些拷贝在不同的处理器上运行,以保证处理结果的正确性.现在的问题是:如何分配这些子任务,使得整个任务在规定的时间内完成,同时使得运行该任务的处理器的数量尽可能少.因为同一个子任务的拷贝必须放在不同的处理器上运行,相当于对同一子任务的每份不同的拷贝赋予不同的颜色,要求装在箱子中的物品的颜色各不相同.这种带约束的一维装箱问题就是有色装箱问题.2相关知识2.1经典的一维装箱问题经典的一维装箱问题是这样描述的:给定n个物品的序列123{,,,,}nnLaaaa,物品(1)iain的大小()(0,1]isa,12,,BB为一个由单位容积的箱子组成的无限序列.我们要求:每一个物品ia只能装入到唯一的箱子里,每一个箱子中的数字和不超过1,如何用最少的单位容积的箱子,装下所有的物品?用线性规划的方式来描述一维装箱问题如下:min1niizy..st1(),njijijsaxy1,2,,in11,nijix1,2,,jn01iy或，1,2,,in01ijx或，,1,2,,ijn其中变量,xy的含义是：iy1,0i第个箱子被使用，否则，1,2,,in1,ijjx第个物品放入第i个箱子0，否则,,1,2,,ijn装箱问题是一个典型的NP完全问题[4],由于目前NP完全问题不存在有效时间内求得精确解的算法,因此陆续提出了各种求解装箱问题的近似算法.其中NF、FF、BF、FFD、BFD等是部分著名装箱问题的近似算法.定义1:如果近似装箱算法A依序处理各输入物品,装入新到来的物品ia时,仅仅根据已装物品(1)jaji的大小,而不考虑后面的物品的信息,并且不允许移动已经放好的物品,则称这样的近似装箱算法A为在线(online)装箱算法;而在进行装箱前,所有物品的信息都知道,因此,装入任何物品时,都要考虑其他所有物品的信息,使整体上达到最优,称这样的近似装箱算法A为离线(offline)装箱算法.对于装箱问题,采用性能比和时间复杂度来评价算法的性能.定义2:给定一个近似算法A,令()AL是该算法对输入物品序列L操作所使用的箱子数目,()OPTL是最少使用的箱子数目,并用()sL表示输入物品序列中所有物品的大小之和,则算法A对输入序列L的性能比为()()()AALRLOPTL;平均性能比为[()]lim[()]nnnEALREOPTL.2.2有色装箱问题有色问题是:给定n个物品的序列123{,,,,}nnLaaaa,(1)iain的大小()(0,1]isa,颜色为(1)iCiK,其中物品的颜色数不超过(,)KKNK是常数.12,,BB为一个由单位容积的箱子组成的无限序列.我们要求:每一个物品ia只能装入到唯一的箱子里,每一个箱子中的数字和不超过1,同一箱子中各物品颜色互不相同,如何用最少的单位容积的箱子,装下所有的物品?有色装箱问题也是NP完全问题,因为当K时,即物品的颜色数无穷大,每个物品颜色相同的机会就大大减少,就变成了经典的一维装箱问题了.2.3解决有色装箱问题的SCPF-A算法文献[5]提出了有色装箱问题的SCPF-A算法,首先对输入物品按颜色分类,将相同颜色的物品分成一类,放置时按照相同颜色的首先放置的原则,即颜色1C的所有先分别放在不同的箱子中,然后再处理颜色2C的所有物品,一直到所有颜色的物品都放置完毕.在放置物品的过程中,相同颜色的物品必须放在不同的箱子中.在放置颜色(2)iCi的所有物品时,物品的放置采用经典装箱问题的近似算法A.如当算法A选取的是FF算法,则得到SCPF-FF算法.例1:给定物品序列L={5(A),8(B),3(B),2(A),6(C),7(B),1(C),9(A),2(C),4(A),2(C),3(C)，4（C）},括号中的字母表示颜色值,A表示颜色A,B表示颜色B,C表示颜色C,箱子的长度为10.根据SCPF-A算法,首先将物品按颜色分类,分类结果如下所示:5(A)2(A)9(A)4(A)8(B)3(B)7(B)6(C)1(C)2(C)2(C)3(C)4(C)类I类II类III下面分别考察SCPF-FF算法和SCPF-FFD算法在该实例下的装箱情况．12345678图1SCPF-FF算法首先将类I的物品分别放入前4个箱子,在按照首次适应的原则放置类II的物品,如果放不下,就新开一个箱子,这样的放置结果是需要8个箱子.SCPF-FFD算法需要将物品按长度从大到小排序.9(A)5(A)4(A)2(A)8(B)7(B)3(B)6(C)4(C)3(C)2(C)2(C)1(C)类I类II类III装箱后的结果如图2.1234567图2SCPF-FFD算法SCPF-FFD算法需要7箱子.3LSCPF-A算法在SCPF-A算法中,是按颜色分类,将相同颜色的物品分成一类,放置时按照相同颜色的物品首先放置的原则.在放置过程中,对于先放置哪种颜色的物品没有限制或者说是按照颜色出现的先后顺序进行放置.在放置最后一种颜色的物品时,放置每个物品时,如果前面的箱子已无法放置就必须新开一个箱子,如果这种颜色的物品个数比较多,势必导致最后的一些箱子,每个箱子中只放有一个物品,并且这些物品都是最后一种颜色.而事实上,这些物品中可能有的物品可以与前面其他颜色的物品交换一下放置位置,被交换出来的那个物品可能可以与最后这种颜色的其他物品放在一个箱子中,这样就节省了箱子.按照这个思路,我们对SCPF-A算8B2A1C3B5A9A6C4A2C7B2C3C4C1C9A2C3B5A6C4A8B2A3C7B4C2C法进行了改进,提出了一种新的装箱算法LSCPF-A算法（LongSameColorPackedFirst）.LSCPF-A算法:首先对输入物品按颜色分类,将相同颜色的物品分成一类,然后比较每一类中物品个数的多少,把物品个数最多的那一类作为第I类,以此类推,物品个数最少的那一类作为最后一类.最后放置物品,首先放置第I类,再放置第II类,……,一直到所有类的物品都放置完毕.在放置物品的过程中,同一类的物品必须放在不同的箱子中.LSCPF-FF算法和LSCPF-FFD算法是我们考察的主要对象.3.1实例例2:再以例1作为例子来观察LSCPF-FF和LSCPF-FFD算法的放置效果.首先将物品按颜色分类(分类情况见例1),再按每类中物品个数的多少重新给每类编号.6(C)1(C)2(C)2(C)3(C)4(C)5(A)2(A)9(A)4(A)8(B)3(B)7(B)类I类II类III1234567图3LSCPF-FF算法首先将类I的物品分别放入前6个箱子,再按照首次适应的原则放置类II的物品,如果放不下,就新开一个箱子,这样的放置结果是需要7个箱子,比SCPF-FF算法少用一个箱子.LSCPF-FFD算法需要将物品按长度从大到小排序,再按每类中的物品个数的多少重新编号.6(C)4(C)3(C)2(C)2(C)1(C)9(A)5(A)4(A)2(A)8(B)7(B)3(B)类I类II类III放置效果如图4.123456图4LSCPF-FFD算法LSCPF-FFD算法需要6个箱子,比SCPF-FFD少用一个箱子.从这个例子看到,LSCPF-FF算法使用的箱子数比SCPF-FF少,LSCPF-FFD算法使用的箱子数也比SCPF-FFD少.这是因为在SCPF-A算法中是按照颜色出现的先后顺序进行放置的,先放置最先出现的那种颜色,在放置最后一种颜色的物品时,如果前面的箱子已无法放置就必须新开一个箱子,如果这种颜色的物品个数比较多,就会导致最后的一些箱子,每一个箱子中只放有一个物品,并且这些物品都是最后一种颜色的.而事实上,这些物品中可能有的物品可以与前面其他颜色的物品交换一下放置位置,被交换出来的那个物品可能可以与最后这种颜色的其他物品放在一个箱子中.而LSCPF-A算法,先放置物品个数最多的那种颜色的物品,尽可能少的避免上面情况的发生.这种算法仅仅改变了箱子的放置次序,而这个次序的改变并不影响最2A6C3B5A1C4A2C8B2C7B3C4C9A4A6C5A4C3B2A3C8B2C7B2C9A1C后放置的结果.从LSCPF-A算法的定义知它不具有在线性，是一种离线近似算法.定理:若A是经典一维装箱问题的近似算法,},{FFDFFA,SCPF-A是以A为基础的算法[5]，LSCPF-A是以A为基础的算法，则)()(LASCPFLALSCPF.证明:在SCPF-A算法中,首先对物品分类,将相同颜色的物品分成一类,放置时按相同颜色的物品首先放置的原则,将物品进行装箱.在放置物品的过程中,相同颜色的物品必须放在不同的箱子中.下面证明使用SCPF-A算法装箱后的结果如何使用LSCPF-A算法可以节省箱子,从而使得箱子数减少.采用SCPF-A算法进行装箱时,对于先放置哪种颜色的物品没有限制或者说是按照颜色出现的先后顺序进行装箱.先放置最先出现的那种颜色,在放置最后一种颜色的物品时,如果前面的箱子已无法放置就必须新开一个箱子,如果这种颜色物品个数比较多,势必导致最后的一些箱子,每个箱子中只放有一个物品,并且这些物品都是最后一种颜色的.假设采用SCPF-A算法进行装箱后,一共使用了l)1(l个箱子,最后的)(lmm个箱子都放了一个物品,并且这些物品都是同一种颜色的,设他们的颜色是KC,设最后的m个箱子中有一个物品长度是a,不妨设是倒数第m个箱子,即第1ml个箱子.则在前面ml个箱子中寻找满足下面条件的箱子(设箱子的总长度是L):(i)箱子中没有装颜色是KC的物品;(ii)设箱子中已装物品为)(11kkCa,)(22kkCa,…,)(kikiCa,其中1kC,2kC,…,kiC是不同的颜色,并且都不是KC这种颜色,aaLipjjkj,1;(iii)最后1m个箱子中有一个箱子中装的物品是)(KCb,并且Lbakp.若存在这样的物品kpa,不妨假设第一个箱子满足上述三个条件,则将)(KCa与)(kpkpCa交换一下位置,这样第一个箱子中既没有相同颜色的物品,同时物品的总长度和不超过箱子的长度L,符合装箱的要求.而第1ml个箱子装有物品)(kpkpCa,最后1m个箱子中有一个箱子中装的物品是)(KCb,KC与kpC不是一种颜色,并且长度和Lbakp,则可以将物品)(kpkpCa与)(KCb放在一个箱子中,符合装箱的要求.根据LSCPF-A算法,这样的装箱是允许的.继续重复上面的步骤,这样就节省了箱子,减少了箱子的使用数目.使用LSCPF-A算法,最后放置的是物品个数最少的那种颜色的物品,从而尽可能的避免上面情况的发生.如果不存在这样的物品kpa,那么可能对于该实例是无法优化的.如图1,第2个箱子中的2A与第6个箱子中的2C交换一下位置，并将2A放入第7个或第8个箱子中，可以减少一个箱子.由于LSCPF-A算法是先放置物品个数最多的那种颜色的物品,从而不会比SCPF-A算法使用的箱子数目多,即)()(LASCPFLALS