多指标排序研究

Scheduling with multiple criteria (multi-criteria scheduling) is an important research direction in scheduling theory, which includes the following four forms of problems: (1) Hierarchical Optimization; (2) Constrained Optimization; (3) Positive Combination Optimization; (4) Pareto Optimization. These forms of scheduling have been widely applied in productions and managements. The research of this project includes the following aspects: (1) Open problems in multi-criteria scheduling (especially in multi-agent scheduling); (2) Multi-criteria scheduling on drop-line parallel-batch machines; (3) Rescheduling with flexible original jobs under global disruption and so on. These problems are also combined with various new scheduling models to form a broad research perceptions. Based on totally new theoretical tools, the goal of this project is to present complexity analysis, find efficient polynomial-time algorithms and design polynomial-time approximation algorithms with good performances. In the aspect of expression of achievements， we will solve several open problems in multi-criteria scheduling, and provide complete research results for multi-criteria scheduling on drop-line parallel-batch machines and rescheduling with flexible original jobs under global disruption.

多指标排序是排序领域的重要研究方向，其问题形式包括以下四种：(1) 分层优化；(2) 约束优化；(3) 正组合优化；(4) Pareto 优化。这四种形式的多指标排序广泛应用于生产与管理之中。本项目的研究内容包括：(1) 多指标排序(特别是多代理排序)中的历史遗留问题；(2) 可自由下线的平行批机器上的多指标排序；(3) 柔性原始工件整体错位下的重新排序等。这些问题也将与各种新兴排序模型结合起来形成广泛的研究内涵。本项目的目标是在全新的理论工具的基础上对需要研究的多指标排序问题进行计算复杂性分析、寻求有效的多项式时间算法、设计性能良好的近似算法。在成果表现方面，我们将解决多指标排序中若干历史遗留问题，并在可及时下线的平行批机器排序和柔性原始工件整体错位下的重新排序模型下对多指标排序给出完整的研究结果。

多指标排序是排序领域的重要研究方向并广泛地应用于生产和管理之中。发展新的研究方法并用来求解各种具有理论意义和应用前景的多指标排序问题是本项目的实施要点。本项目在分层指标排序、约束指标排序、正组合指标排序、折衷指标排序（Pareto-排序）等方面进行了深入的研究，并得到了较为系统的研究进展。我们对经典排序、多代理排序、分批排序、重新排序等模型中的多个多指标排序问题给出了计算复杂性分类和与之匹配的算法设计；解决了文献中的多个历史遗留问题；引入了GCT-排序模型并将其应用于一致机等长工件双指标排序的研究等。受本项目资助共发表学术论文43篇。代表性成果如下：（1）研究了ND-多代理最大延迟型瓶颈指标折衷排序。在代理数固定的情形，应用排序构型预测折衷点集合的轮廓的方法给出了多项式时间算法，改进或涵盖了文献中的多个结果。（2）研究了CO-双代理排序问题：在B代理的误工工件数有限制下最小化A代理工件的总完工时间。这是文献中2004年的遗留问题，文献中2010年给出了错误的NP-困难性证明。我们建立了一类新的NP-完全的“奇偶划分”问题并由此重新证明了：即使在A代理的工件等长的情形，该问题仍然是NP-困难的。（3）证明了单机工件具有截止期最小化总误工时间排序问题的一元NP-困难性，从而解决了文献中2001年和1993年提出的两个相关的遗留问题。（4）研究了IF-双代理排序中的四个历史遗留问题，其中，整体指标是误工工件数，代理指标是最大延迟和时间表长。我们证明了这四个问题均是二元NP-困难的，并对其中代理指标为时间表长的两个问题给出了拟多项式时间算法。（5）研究了多代理最小化代理的误工工件数和时间表长总和问题。当代理的数目固定时，该问题是文献中的遗留问题。我们给出了该问题的多项式时间算法。