两阶段物流排序和工件可拒绝排序理论研究

机器排序理论是运筹学与组合最优化方向极为活跃的研究领域之一。然而，在大多数经典排序文献中，只考虑工件（或者产品）如何加工，而不考虑工件如何运输给顾客；并且所有工件都必须安排加工，不允许拒绝任何工件。但是，在实际中却并非总是如此。随着市场经济的日益全球化，市场竞争也越来越激烈。为了提高企业的市场竞争性，有效的控制成本已经成为企业之间竞争的关键因素。为了降低产品成本（包括生产费用、储存费用和运输费用等等），企业决策者不得不考虑加工阶段和运输阶段之间的协调性，并且拒绝一些比较耗费资源且利润较低的工件。两阶段物流排序和工件可拒绝排序为近年来出现的两种新型排序问题，关于这个主题的研究有着深刻的实际背景和广泛的应用前景。目前，该领域尚有大量的未解问题有待解决。为了解决这些富有挑战性的问题，我们必须提出一些新的研究方法并设计出一些创新性的最优算法、近似算法和在线算法。

本项目主要研究两阶段物流排序和工件可拒绝排序文献中遗留的未解问题，并且也提出了一些新的问题模型和解决方案。到目前为止，共有18篇论文受本项目资助发表在国际SCI期刊或者国内核心期刊上。特别的是，其中有17篇论文发表在一些国际知名的SCI期刊上，包括《European Journal of Operational Research》﹑《International Journal of Production Economics》、《Journal of Scheduling》、《Journal of Operational Research Society》、《Theoretical Computer Science》、《Information Processing Letters》等等。本项目的代表性成果如下：（1）对按时间在线最小化最大运输完工时间的两阶段物流排序问题，我们给出了一个竞争比为1.618的最好可能在线算法，该结果发表在《Journal of Scheduling》上；（2）对按时间在线最小化最大完工时间的单机工件可拒绝排序问题，我们给出了一个竞争比为2的最好可能在线算法，该结果发表在《International Journal of Production Economics》上；（3）对具有展望区间最小化最大完工时间的多台平行批机器排序问题，我们给出了最好可能的在线算法，该结果发表在《Information Processing Letters》上。（4）对具有两个竞争性代理的无界平行批排序问题，我们给出了系统的复杂性分类和对应的最优算法，该结果发表在《Journal of Scheduling》上。