论文部分内容阅读
批装箱问题是一类新的装箱问题,在实际生活中有着广泛的应用。与经典装箱问题不同,批装箱过程中,需装箱的物品按批到达,其中一批可以包含多个物品,且必须在下一批到达之前装好前一批。当只有一批时,就是已知的离线装箱问题;当每批只包含一个物品时,就是已知的在线装箱问题。GregoryGutin等人首先研究了批装箱问题,证明了2批装箱问题渐进竞争比R∞A,2的下界为1.3871,并对此下界的最优性做了猜想:存在2批装箱问题的一个算法A,使得R∞A,2=1.3871。文中还对2批装箱问题的一个特例,即第一批物品的长度都相同的情况给出了一个渐进竞争比为1.3871的近似算法。本文进一步研究了多批装箱问题的下界和近似算法。我们首先给出了批装箱问题及含参数的批装箱问题的相关定义,接下来证明了3批及4批装箱问题的下界分别为1.5和1.53521,又给出了含参数r的2批及3批装箱问题的下界,最后对于2批装箱问题的上述特例构造了BFFD算法,利用权函数法证明了其渐近竞争比为1.5,并举例说明了这个界是紧的。