带拒绝箱覆盖问题的局内算法

摘 要:作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题｡设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用｡物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱｡如果物品被放入箱中,则产生费用｡该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景｡给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果｡

关键词:箱覆盖问题;近似算法;最坏情况渐近性能比;因特网通信;信息管理

中图分类号:TP393文献标识码:A

1 引 言

面对内外众多客户对Web服务信息的高频率访问要求,如何有效地对内部网(Intranet) 的分布式信息系统进行管理,以达到低费用､高效率的目的,是非常重要的关键技术｡文献[1]首先提出这类问题,进行了一定深度的研究｡文献[2]对此问题进行了探讨｡一个企业为了有效地降低通信费用,往往将被访问频繁的外部Internet信息块下载至Intranet内部的网络服务器上,使之成为内部信息块｡但由于网络服务器本身内存的限制及访问该服务器上的信息的速度的要求,企业要有选择地下载Internet外部信息块｡企业要考虑的是如何使通信费用总和最小｡

本文将上述问题转化成如下定义的优化问题:如何合理地将互联网上的信息分布到所有Web服务器上,在至少达到各个服务器容量基本额度要求下,使这些信息因被访问而产生的通信费用最小?因为可以对每个有用的信息块定义两个参数:信息块容量,表示其内存大小;信息块费用值,表示放在服务器上产生的费用值｡从而目标变为达到放在服务器上的信息块费用值之和最少的服务器数最多｡该问题描述如下:

设有长为C的一维箱子,给定n个物品的序列Ln=,物品华i(1≤i≤n)的大小为ωi,费用值为pi(1≤i≤n)｡物品可以放入箱子也可被拒绝放入箱子｡每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少超过箱子容量,如果某物品被放入箱中,则产生费用pi,怎样安排物品使箱子中物品总费用之和最小同时容量达到要求的箱子数最多｡我们称此问题为带拒绝箱覆盖问题｡

注意到如果令每个物品的费用都充分大,大于购买服务器的费用,在最优解中该物品一定不会拒绝｡带拒绝箱覆盖问题就变成箱覆盖问题,它是强NP难的[3],因此带拒绝箱覆盖问题也是强NP难的｡

计算技术与自动化2007年6月第26卷第2期杨鼎强等:带拒绝箱覆盖问题的局内算法本文第2节给出相关知识;第3节提出一个求解带拒绝箱覆盖问题的局内近似算法C-FF算法,然后分析了该算法的性能;第4节给出了实验结果｡

2 相关知识

箱覆盖问题是:给定n个物品的序列Ln=,物品华i(1≤i≤n)的大小为ωi∈(0,1],要求将这些物品装入单位容量的箱子B1,B2,…,Bm中,使得每个箱子中的物品大小之和至少为1,并使所使用的箱子数目m最大｡

箱覆盖问题是组合优化领域的基本问题,已有很多好的结果[4-6],而对带拒绝装箱覆盖问题,尚未见文献研究｡由于目前NP完全问题不存在有效时间内求得精确解的算法,因此设计和分析其近似算法是重要的研究内容｡设A为一近似算法,A(L)表示算法A对输入物品序列L操作所使用的装箱数,OPT(L)表示最优值｡算法A的最坏情况渐近性能比定义为R∞A=┆limn∞┆infL{A(L)/OPT(L)|OPT(L)≥n}｡

Ц据对物品信息的依赖程度,近似算法分为局内(online)算法和局外(offline)算法｡如果在依序处理各输入物品时,不知道任何后续物品信息,并立即给出当前物品的装箱方案,则称为局内算法;而首先得到所有物品信息之后,统一处理所有物品的装箱方案,则称为局外算法｡

最早研究此类带拒绝的组合优化问题是可拒绝并行处理器调度问题,它与本文所讨论的问题有一定联系｡该问题可描述如下:设有m个同型并行处理器(identical multiprocessor),n类不同尺寸的工件,其罚值也不同,并行处理器可选择,也可拒绝,要求将最后一个工件的完工时间与被拒绝工件的总罚值之和最小｡这个问题最早由Bartal等人提出[7]｡他们对局外和局内算法的研究都得到了很好的结果｡Alex和Richar[8]将此问题推广同型并行处理器(uniform multiprocessor)上的调度问题,对局外算法的设计进行了探讨｡

3 C-FF算 法

带拒绝箱覆盖问题中,要求每个箱子中的物品费用总和最小,同时物品尺寸之和尽可能大,因此,可以考虑将达到要求的费用/尺寸比值的物品装入箱子｡一种自然的策略是首先判断物品是否满足装箱的条件,然后在满足条件的物品使用经典装箱算法｡基于此思想,我们提出C-FF(classified-first fit)算法｡

为方便计,将所有信息块的费用除以购买新服务器的费用后作为新的费用｡

Ц据物品华i的费用密度Cpi/ωi,算法中的物品分成两大类:

C-FF算法主要过程:

1)物品华1到达,如果p1

2)物品华i到达,设已到达物品的总费用值为P,如果P+pi

3)自当前物品华i开始,如果该物品属于M1,则按FF算法将该物品装入箱子中,当箱子中的物品大小至少为C时则关闭当前箱子;如果该物品属于M2,则拒绝该物品｡

引理1[2] 对任意带拒绝装箱问题实例I,L=∑i∈M1ωiC+P(M2)是其最优解值OPT(I)的下界,即有OPT(I)≥L;且成立L≥12(OPT(I)-1)｡这里P(M2)=∑i∈M2pi为M2中物品的总罚值｡

定理2 对于带拒绝箱覆盖问题的所有实例L,成立2C-FF(L)≥OPT(L)-1;C-FF算法的最坏情况渐近性能比RC-FF∞=1/2｡

证明 如果所有物品的总罚值小于1,则显然算法C-FF得到问题最优解｡故以下假定所有物品的总罚值至少为1｡令L1为算法C-FF按步骤3安排的物品集组成的实例｡由于算法C-FF步骤1～步骤2中被拒绝物品的总罚值不超过1,且未将任何物品装箱,所以C-FF(L\L1)≤1｡下面就L1中物品总长度分两种情况考虑:

(1) 如果L1中物品总长度小于C,按M2的定义知,L1中被拒绝物品的总罚值不超过它们的总长度除以C｡因此总罚值也不超过1,且未被拒绝的物品总长度仍小于C,所以C-FF(L1)=0,因此

C-FF(L)=C-FF(L1)+C-FF(L\L1)≤C-FF(L1)+1=1｡

由于OPT(L)≥1,显然成立C-FF(L)≤OPT(L),2C-FF(L)≥OPT(L)-1｡

(2) 如果L1中物品总长度至少为C,因为C-FF算法中每个箱子的物品大小之和超过C但小于2C,我们有2C-FF(L1)+1≥OPT(L1),因此有2C-FF(L)+1=2C-FF(L1)+2C-FF(L\L1)+1≥2C-FF(L1)+2≥OPT(L1)+1又据引理1知OPT(L)≤OPT(L1)+1,因此有2C-FF(L)≥OPT(L)-1｡

令ε=12m,用(,c)表示大小为､费用为c的物品,{华1,华2,…,华n}表示把物品序列{华1,华2,…,华n}重复k次所得的物品序列,考虑输入物品序列:

L={(1-ε,1),(1-ε2m,1)}2m

则所有物品均属于M1｡使用算法时每两个大小为1-ε的物品占用一个箱子,所以C-FF(L)=m;而若使用最佳策略,所有大小为(1-ε)/2m的物品恰好可以放入一个箱子中,每个大小为1-ε的物品也恰好占用一个箱子,故OPT(L)=2m+1,所以综上所述,C-FF算法的最坏情况渐近性能比RC-FF∞=1/2｡

证毕｡

4 实验结果

实验中分别取物品个数n=20,30,50,100,箱子长度C=100｡物品长度为区间[1,C]中随机产生的整数,费用为区间[0,2]中随机И产生的实数｡对每一种组合,随机产生50个实例,对50个的性能比取平均值｡实验环境是CPU1.6G,512M内存｡

求C-FF算法的平均性能比时,我们用第2节给出的最优解定界,采用分枝定界法(深探法)求出最优解｡实验结果如图1所示｡

从实验结果可以看出,随着问题规模的扩大,近似算法C-FF平均性能比逐步下降｡

5 结 论

П疚拇踊チ网的信息管理问题中提出了一个新的组合优化问题――极小化箱子中物品费用的带拒绝箱覆盖问题｡本文进一步给出了求解带拒绝装箱覆盖问题的局内近似算法C-FF,证明了该算法最坏情况渐近性能比R∞C-FF为1/2,实验显示在平均意义下C-FF的效果相当好｡设计出带拒绝箱覆盖问题最坏情况渐近性能比更好的局内算法,是我们进一步研究的课题｡

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。