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

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

项目编号： No.11201121

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 何程

作者单位： 河南工业大学

项目金额： 23万元

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

中文关键词： 排序；多目标；分批；多代理；可解性

英文摘要： 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 schedulin

英文关键词： scheduling；multicriteria；batching；multi-agent；solvability