Abstract: In online bin packing problem, for the online property of next fit(NF) algorithm, it is used widely. However, NF works according to the item arrival sequence, the resource utility ratio is low. This paper based on the computer communication network, adds repacking scheme to NF algorithm, and presents two new algorithms: the last item repacking and each item repacking. Because of being repacked, some items would be packed into the subsequent bin, hence they are called semi-online algorithms. By means of average-case analysis, the paper finds they perform much better than NF, and almost same to the smart next fit algorithm.

Key words: Semi-online, Bin-packing, Performance ratio, Repacking

摘要： 在装箱问题中，下次填充法（NF）由于其在线特性，而被广泛应用。然而这种算法由于按照物件到达先后顺序来填充，资源利用率比较低。该文根据计算机通信网络中的实际应用，在NF算法基础上添加了置换功能，提出两种新的算法：最后物件置换算法和每个物件置换算法。由于物件被置换后，可能会被填充到后续箱内，因此称之为准在线算法。通过平均分析发现，这两种算法性能比NF算法有较大提高，类似于智能NF算法的性能。

关键词: 准在线, 装箱, 性能比, 置换

CLC Number: 

• TP 301.6