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

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 problems, we know that the bin packing problem with conflicts (BPC) is NP-complete, and is generally hard to approximate within a fixed number unless P=NP. ..Due to its computational hardness, most literature focus on the special conflict graphs whose chromatic number could be computed in polynomial time, such as the trees, planar graphs, grid graphs etc. They first separate the items set to some subsets by computing the graph coloring problem, such that in each subset there are no conflicting items, then apply the classical bin packing algorithms to finish the packing stage. By this kind of technique, several approximation algorithms are proposed and the performance ratios are proved. ..In this project, we extend the conflict graph to general graphs, give the definition of BPC under weighted graphs and directed graphs, and the online version of bin packing problem with onflicts will also be considered. We will study the computational complexity of these new problems, and design the high performance optimization algorithms by investigating new techniques combining heuristic, graph theory and continuous optimization methods. The criteria we apply to evaluate the algorithms are approximation ratio (competitive ratio) analysis.

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

带冲突装箱问题是近年来组合优化领域重要的研究方向之一，并有了越来越广泛的实际应用。传统情形下，冲突主要体现在物品、网络等非生命体的优化安排中，“人”的调度和安排中应用比较少。我们在项目研究的进展过程中注意到，带冲突装箱问题在医疗管理中的应用十分关键，这也给本项目的研究带来了新的生命力。.我们从以下三类问题出发对带冲突装箱问题展开研究：.（1）赋权图下的带冲突装箱问题。在最初提出的带冲突装箱问题模型中，不允许相互冲突的物品放到一个箱子里去。但实际生活中可能会出现不得不“容忍”的情况，比如运输问题中车辆数量有限，不得不把冲突物品放到一个车辆里，但可能需要额外附加防护措施。这里就出现了费用的增加或者容忍限度的问题。主要考虑了如下两个模型：.模型Ⅰ：每个箱子除了容量限制之外，还有一定的冲突容忍度。物品间的冲突关系及冲突“严重程度”可以通过赋权的冲突图表现。图中的每个顶点仍然代表物品，两点之间若有边相连，则表示两物品间存在冲突，边上的权重代表这两个物品间的冲突值。只要放入一个箱子内物品的冲突值之和不超过该箱子的容忍度即为合理装箱。目标是最小化使用箱子的个数。.模型Ⅱ：从费用的角度对带冲突装箱问题进行考虑。假设物品之间的冲突费用介于0，1 之间，这个费用仍由冲突图中相应两点之间边的权重确定。箱子的使用费用为1，冲突容忍度也是1。目标是寻找一种合理装箱方式，使得产生的总费用最小，即箱子费用和冲突费用之和最小。.（2）有向图下的带冲突装箱问题。实际生活中很多问题的冲突关系是单向的，比如病人做多项检查治疗，验血需要空腹，而吊水则需要饮食后，所以验血可以安排在吊水之前，而吊水之后短时间内是不能进行验血的。类似更常见的例子还有很多，比如快递箱打包时也会把坚固耐压的物品放在下面，柔软易碎的物品放在上面等。.（3）在线情形下的带冲突装箱问题。当需要装箱的物品信息事先并不能完全得知，就需要考虑在线情形下的优化问题：物品按时间（或按序）到达，其尺寸及与其他物品的冲突关系均在到达后方能得知，要求物品到达后立即安排装箱，并且不可悔改，目标是使用的箱子个数尽可能少。.在本项目的研究中，我们针对以上四类带冲突装箱问题进行算法设计与分析，研究问题的计算复杂性，并通过数值计算协助分析算法的性能。