装配型排序理论- - 计算复杂性、近似算法和随机算法-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

装配型排序理论- - 计算复杂性、近似算法和随机算法

项目名称：装配型排序理论- - 计算复杂性、近似算法和随机算法
项目类别：面上项目
批准号：10371112
申请代码：A011202
项目来源：国家自然科学基金
研究期限：2004-01-01-2006-12-31

项目负责人：原晋江
负责人职称：教授
依托单位：郑州大学
批准年度：2003

中文摘要：

排序论是运筹学和组合最优化领域极为活跃的研究分支,而装配型排序则包含了丰富的经典及新兴排序模型.排序问题的计算复杂性研究,即确定一个排序问题是多项式时间可解还是NP-困难的,向来是排序论的主要研究方向.NP-困难问题的近似算法和随机算法则是近年来国际上流行的研究方向.本项目以研究装配型排序的计算复杂性,近似算法和随机算法为主要研究内容.通过探讨可行排序或最优排序的局部及整体结构性质和数量关系,建立系统有效的计算方法和基本理论,在计算复杂性分析,近似算法和随机算法设计上做出创新性的研究成果.

中文主题词：装配型排序; 计算复杂性; 近似算法

英文摘要：

assembly scheduling; computati

英文主题词： assembly scheduling; computati

结论摘要：

排序论是运筹学和组合最优化领域极为活跃的研究分支，而装配型排序则包含了丰富的经典及新兴排序模型。排序问题的计算复杂性研究，即确定一个排序问题是多项式时间可解还是NP-困难的,向来是排序论的主要研究方向。NP-困难问题的近似算法则是近年来国际上蓬勃发展的研究方向。本项目以研究装配型排序的计算复杂性和近似算法为主要研究内容。通过探讨可行排序或最优排序的局部及整体结构性质和数量关系，建立了系统有效的计算方法和基本理论，在计算复杂性分析和近似算法设计上做出了一系列的研究成果。三年共发表学术论文34 篇，其中有19篇学术论文发表在国际SCI学术期刊上。

成果综合统计