中文摘要：

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