装箱问题的理论与算法

装箱（Bin Packing）是组合优化的一个经典问题。以其为基本模型构成的装箱问题类有强烈的实际背景和深刻的算法理论意义。本项目研究若干具体装箱问题的算法结构和性质，通过对带个数限制的在线装箱、元素有区间约束的装箱、二维带状装箱、一般费用下的装箱以及传感器安置等问题的深入探讨，刻画相应问题的内在特性以及可行装箱的充分条件和必要条件。利用这些条件分析和估计算法的上下界，试图在算法设计与分析的思想上有所突破。在此基础上取得重要算法结果。

装箱问题一直是组合优化领域的热点研究问题。经典的遗留问题不断需要我们在算法设计与分析上创新，而各种组合优化模型大多与装箱问题相关，如平行机调度、背包以及树覆盖等问题。本项目的研究内容可以分成三个层面，一是装箱问题的各种变形，包括带容量限制的平行机调度、多带状装箱、在线背包、双层背包优化等；二是调度算法的研究，如多核处理器的调度问题、带加速资源的调度问题以及两个代理的流水作业问题；三是由算法设计过渡到机制设计，首次研究了厌恶性选址问题的算法机制。.在模型方面提出了双层背包优化和带加速资源的调度，前者刻画了博弈环境下的两阶段背包问题，后者描述了计算机信息处理环境下的资源分配模型，得到了相应的深刻算法结果。在算法理论和方法方面准确分析了带容量限制平行机调度和带资源扩展的在线背包问题的最优解结构，分别设计了EPTAS（有效的多项式时间近似方案）和最优的在线算法，丰富了近似方案的设计思想和在线算法的分析手段。在算法机制设计方面我们抓住了厌恶性选址问题诚实机制的核心，利用直径定位、就近分类的思想，从特殊到一般网络分别给出了相应的有效机制。项目所得到的所有算法成果是相应问题的最好结果。.依托本项目，我们培养了优秀的博士研究生和博士后研究人员，加强和拓展了广泛的国际学术交流，项目负责人近两年也先后受邀担任重要国际学术期刊《Omega-The International Journal of Management Science》和《Journal of Scheduling》的编委。