【摘要】 Ｊ．Ｃｓｉｒｉｋ与Ｄ．Ｓ．Ｊｏｈｎｓｏｎ针对带ｋ－箱限制的在线装箱问题提出了四种装入和关闭法则，并利用这些法则给出了四种相应的算法．其中ＢＢＦｋ，ＮｋＦ和ＡＢＦｋ算法的紧界在文［１－３］中分别进行了很好的研究．但对算法ＡＦＢｋ来讲，其紧界仍是一个公开问题．本文给出了ＡＦＢｋ算法性能比的一个上界，即．同时，本文提出了一个新的关闭法则，对ＡＦＢｋ算法进行了修改，使修改后的算法ＡＦＢｋ的性能比不超过１．７（ｋ３）更多还原

【Abstract】 J.Csirik and D.S. Johnson[1] proposed four packing and closing rules for thek-bounded space on-line bin packing problems and based on these rules they designed fouralgorithms in dealing with these problems. The tight bounds for BBFk,NkF and ABFk weregiven in papers[1-3],respectively, but it remains open for AFBk.In this paper,we give anupper bound of the asymptotic worst-case ratio for the algorithm AFBk,i.e.R∞[AFBk]We also propose a new closing rule. Based on this new rule, theasymptotic worst-case ratio of the revised AFBk(denoted by AFB) is not greater than 1.7for k 3.更多还原