具有层次结构的多目标排序的可解性研究

Stimulated by information science and system science, combinatorial optimization keeps its flourishing development. As a branch of combinatorial optimization with regard to time and order, scheduling theory is always within an active frontier area. Associated with the advance of scheduling theory in depth and width, a trend of structuralization appears upon the set of jobs, such as the multi-batch (batching) scheduling, the multi-agent (multi-family) scheduling, and the multi-stage scheduling (re-scheduling), and meanwhile the objective function changes from single criterion to multiple criteria. So, a class of multicriteria scheduling problems with multi-level structure is proposed. This project intends to study the solvability systematically of this class of new models. Here "solvability" includes establishing polynomial-time algorithms (e.g., to construct all Pareto optimal solutions), proving the intractability of problems (e.g., NP-hardness for some constraint problems), and designing approximation algorithms. In the previous research work, the multicriteria scheduling and the scheduling with multi-level structure have obtained intensive results respectively. Further, the combination of these two directions suggests a series of remarkable topics and extends the research fields of the multicriteria scheduling. Especially the partition construction method for generating all Pareto optimal solutions is of significance in creativity.

受信息科学与系统科学的有力推动，组合最优化学科呈现蓬勃发展的态势。作为时序性组合最优化问题，排序理论始终处于活跃的前沿领域。随着排序理论向深度和广度推进，工件集表现出结构化的趋势，如出现多批次（分批）、多代理（分族）、多阶段（重新）排序等；同时，优化指标从单目标发展为多目标。这样就提出一类多层次的多目标排序问题。本项目针对这类新模型，系统地研究其可解性。这里"可解性"包括建立多项式时间算法（如构造同时最优化的全部Pareto最优解）、证明问题的难解性（如某种约束问题的NP-困难性）以及设计近似算法。在已有的研究工作中，多目标排序与多层次排序各自均有较深入的成果；而二者的结合将提出一系列富有特色的课题，拓广多目标排序的研究领域。特别对多层次问题寻求全部Pareto最优解的划分构造方法具有显著创新意义。

受信息科学与系统科学的有力推动，组合最优化学科呈现蓬勃发展的态势。作为时序性组合最优化问题，排序理论始终处于活跃的前沿领域。随着排序理论向深度和广度推进，工件集表现出结构化的趋势，如出现多批次（分批）、多代理（分族）、多阶段（重新）排序等；同时，优化指标从单目标发展为多目标。在已有的研究工作中，多目标排序与多层次排序各自均有较深入的成果。然而将这两个方面结合起来的研究却非常少见。因此二者的结合将提出一系列富有特色的课题，拓广多目标排序的研究领域。基于此种原因，我们对具有层次结构的多目标排序的可解性进行了一系列的研究。这里“可解性”包括建立多项式时间算法（如构造同时最优化的全部Pareto最优解）、证明问题的难解性（如某种约束问题的NP-困难性）以及设计近似算法。我们的研究得到了一系列的成果，得到了平行分批、序列分批的几个多项式时间算法，设计了几个多代理排序问题的近似算法以及与之相关的几个结果。这些问题的解决为后续进行更难的工作奠定了坚实的基础，提供了丰富的解决问题的经验，特别对多层次问题寻求全部Pareto最优解的划分构造方法具有显著创新意义。