The Dynamic Bin Packing Problem Revisited

動態裝箱問題之探討

張綺芬(Chang, Chi Fen)

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2015年)

摘要

本研究探討的主題為動態裝箱問題，是一個經典的組合最佳化問題。此問題是依來到時間先後將尺寸不超過箱子容量的物件分配至容量相同的箱子，且物件會隨時間離開，須在每個箱子中的所有物件尺寸總和不可超過箱子容量的限制條件下，最小化過程中使用的最大箱子數量。從應用角度來看，裝箱問題經常用於探討電腦系統中的記憶體配置問題，在過去數十年中持續有許多研究探討其變形問題。本研究探討過去文獻中已提出之即時演算法的特性，並深入討論半即時動態裝箱問題。「半即時」特性為放寬部分即時演算法的限制，例如：允許部分物件在被裝入箱子後可以再被取出並放入其它箱子，或是事先得知部分未來資訊。我們提出一個在部分情況下，可以表現得比先前文獻結果好的半即時動態裝箱演算法。

關鍵字

半即時演算法 ； 動態裝箱問題 ； 近似演算法

並列摘要

This study investigates the dynamic bin packing problem which is one of the oldest classic NP-complete problems in the field of combinatorial optimization. The problem involves assigning a set of n items with size no more than the given bin capacity to equal-capacity bins so that the total size of items in each bin does not exceed the bin capacity, and items may depart from the packing at any time. The optimization objective is to minimize the maximum number of bins ever used over all time. In the perspective of practice, this problem has widely studied for the memory allocation problems. Therefore, many variants have been continually proposed over the past decades. In this study, we revisit the properties of some on-line algorithms in the dynamic bin packing problem and investigate a generalization model of the bin packing problem, called semi-online dynamic bin packing. The semi-online property provides some relaxations of on-line constraints, such as allowing to repack some items or knowing some information in advance. We develop a semi-online dynamic bin packing algorithm with a greater upper bound in some specific situations.

並列關鍵字

semi-online algorithm ； dynamic bin packing ； approximation algorithm

參考文獻

[1] J. Balogh, J. B`ek`esi, G. Galambos. New lower bounds for certain class of bin

packing algorithms. Theoretical Computer Science, 440-441:1-13, 2012.

[2] J. W.-T. Chan, T.-W. Lam, P. W. H. Wong. Dynamic bin packing of unit

fraction items. Theoretical Computer Science, 409(3):521–529, 2008.

An improved lower bound and resource augmentation analysis. Algorithmica,