带冲突装箱问题的高性能优化算法研究

项目名称： 带冲突装箱问题的高性能优化算法研究

项目编号： No.11201333

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 盖玲

作者单位： 上海大学

项目金额： 22万元

中文摘要： 装箱问题是经典的组合最优化问题之一，传统的装箱问题考虑的是对于给定的一组（序列）物品，如何安排装箱方式使得所用箱子数目最少。在设计装箱时，主要的难点是如何协调安排不同尺寸的物品，使箱子的容量限制得到满足并尽可能装满。1999年Klaus Jansen提出的"带冲突装箱问题"（Bin Packing with Conflicts）模型，更加贴近生活生产实际，考虑到物品之间可能存在"冲突"关系，如何避免冲突同时使用箱子数目尽可能少，是近年来装箱问题研究领域的重要分支之一。在带冲突装箱问题中，物品间的冲突关系一般由图给定，称为冲突图。到目前为止，文献中考虑的冲突图基本都限制在可以多项式时间求解色数的图上。本项目的研究重点，是把冲突图进行推广，主要考虑赋权图、有向图及在线情形下的带冲突装箱问题，对问题计算复杂性进行分析，并设计新算法，通过分析近似比（竞争比）来保证优化算法的高性能表现。

中文关键词： 带冲突装箱；排序；近似算法；在线算法；组合优化

英文摘要： Given a set of items of known sizes and a set of bins of fixed capacity, the bin packing problem seeks to find the minimum number of bins to pack all the items without exceeding the capacity of the bins. The problem is well known in the optimization literature where a number of algorithms, exact and approximate, have been proposed. It also has a number of extensions, including variable capacities and multiple dimensions. The problem treated in this project is one such extension that arises in scheduling and timetabling, where it often occurs that items have conflicts and cannot be packed in the same bin, giving rise to the bin packing problem with conflicts (BPC). Bin packing problem with conflicts was first introduced by Professor Klaus Jansen in 1999. Given a set of items V={1,…n} with sizes s1,…, sn∈(0, 1] and a conflict graph G=(V, E), they considered the problem to find a packing for the items into bins of size one such that adjacent items (i, j)∈E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem with E being an empty set. Furthermore, if ∑si<1 then the problem turns to be computing the chromatic number χ(G) of the conflict graph G. From the previous results of these two classical p

英文关键词： bin packing problem；conflict；approximation algorithms；online algorithms；combinatorial optimization