本研究探讨的主题为动态装箱问题,是一个经典的组合最佳化.PDFVIP

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