平行机分组工件排序的多面体方法

排序论是运筹学和组合最优化领域极为活跃的研究分支。平行机分组工件排序则包含了丰富的经典及新兴排序模型，例如：在线排序、多目标排序、工件可拒绝可退化排序、集成送货排序、工期可指派排序等。本项目研究平行机分组工件排序问题的在线算法以及离线情形的计算复杂性与近似算法。研究成果分类如下：在线算法研究发表论文10篇、多目标排序研究发表论文4篇；工件可拒绝可退化排序研究论文5篇；集成送货排序研究论文2篇；工期可指派排序研究论文2篇。受本项目资助共发表学术论文23篇，其中22篇论文发表于SCI期刊上。本项目的代表性成果如下：（1）对无界平行批处理机最小化时间表长允许重启在线排序给出了竞争比为1.382的最好可能在线算法；（2）对无界平行批处理机最小化所有工件送货完成时间在线排序给出了一个竞争比为1.828的在线算法，改进了历史文献中竞争比为2的在线算法；（3）对无界平行批处理机上的两个竞争代理在相容与不相容两种情形分别给出了不同指标下的计算复杂性分类；（4）对分组工件无界平行批集成送货排序给出了NP-困难性证明和3/2-因子近似算法。