《若干裝箱問題模型的研究》是依託大連理工大學,由韓鑫擔任醒目負責人的面上項目。
基本介紹
- 中文名：若干裝箱問題模型的研究
- 依託單位：大連理工大學
- 項目類別：面上項目
- 項目負責人：韓鑫
項目摘要,結題摘要,
項目摘要
裝箱是經典組合最佳化問題之一, 該問題的研究見證了近似算法和線上算法的發展歷程。.該問題有著廣泛的套用，比如計算機領域記憶體分配，雲平台上遊戲資源的分配等等。.而且近幾年關於裝箱問題的研究比較熱，新的結果層出不窮。圍繞新出現的結果和模型，.本項目從博弈，一維，多維，三個不同的角度探索裝箱問題的七個新模型。.對於一維，多維裝箱問題，本項目設計和分析相應的近似算法和線上算法。.對博弈裝箱問題，本項目考察最壞均衡的解和社會最優解比值的大小。
結題摘要
裝箱是經典組合最佳化問題之一, 該問題的研究見證了近似算法和線上算法的發展歷程。該問題有著廣泛的套用，比如計算機領域記憶體分配，雲平台上遊戲資源的分配等等。該項目重要結果如下：共發表11篇文章，其中CCF A 類期刊1篇 ，CCF B類期刊6篇等。具體如下：1：給出了一維裝箱問題和條形裝箱的對應關係，文章發表在CCF（計算機協 會）推薦的A類期刊中。2：研究了帶緩衝的線上裝箱問題，就是物品可以暫時放在一定容量的緩衝中，如果緩衝滿了，就必須放到一定規格的箱子中，目標是在輸入結束時，最小化箱子的個數。我們改進了前人的競爭比的上下界，文章發表在期刊： Journal of Combinatorial Optimization。3：研究了帶運輸時間的2台流水調度，就是工件先在2台流水機器上加工，然後被一台運輸車運輸到目的地。當每次最多只能運輸常數2個物品時，前人證明是一般的Np難。我們進一步證明該問題為強Np-hard問題，文章發表在期刊：Theoretical Computer Science CCF（計算機協 會）推薦的B類期刊中 。4：研究了博弈下的線上裝箱問題，就是物品是博弈的參與者，它可以選擇去哪個箱子，如果有空間的話。我們證明了當效用矩陣是對稱的話，該博弈一定存在納什均衡，並分析了幾種特定條件下的效用矩陣，給出常數的PoA. 文章發表在期刊： Algorithmica 80(5): 1534-1555 (2018)(CCF B類期刊) （算法方面國家頂級期刊）。5：研究了凹函式下線上背包問題，給出了該問題的上下界，文章發布在Theoretical Computer Science CCF推薦的B類期刊中。6： 研究了違約需要賠付的線上背包問題，違約賠付跟違約的個數成比例的前提下，當物品大小和價值成比例時，我們給了最優的線上算法，文章發布在Theory of Computing Systems CCF B 類期刊。
