大规模的NP困难排序问题松弛策略的研究-东篱科研大数据发现系统（DRDS）

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

大规模的NP困难排序问题松弛策略的研究

项目名称：大规模的NP困难排序问题松弛策略的研究
项目类别：面上项目
批准号：10371071
申请代码：A011202
项目来源：国家自然科学基金
研究期限：2004-01-01-2006-12-31

项目负责人：唐国春
负责人职称：教授
依托单位：上海第二工业大学
批准年度：2003

中文摘要：

本项目突破传统的纯组合（即离散）的研究框架，基于数学规划的松弛策略，对大规模的NP困难排序问题以及其他的组合最优化问题，从随机化算法、列生成技术、凸性及其最优性条件等三个方面进行理论研究和应用研究。这是"离散"和"连续"的相互融合，"确定"和"随机"的相互交叉，经典方法（六十年代初提出Dantzig-Wolfe分解方法）和数学规划最新理论的相互渗透。解决这些问题，必将产生许多新的思想、方法和理论，必将产生许多创新点。所有这些不但对排序论、对组合最优化理论的发展有促进作用，而且，反过来对数学规划本身的发展也有促进作用。本项目的研究属于运筹学学科的前沿研究，代表学科的发展方向；其研究方法具有可行性和前瞻性。项目的完成对推动近似算法的研究，促进组合最优化学科和数学规划学科的发展具有重要的科学意义；预期获得的研究成果有着很强的应用背景，对促进国民经济以及社会的发展具有重要的实际意义。

中文主题词：排序；松弛策略；随机化算法；列生成；供应链排序

英文摘要：

scheduling; relaxation techniq

英文主题词： scheduling; relaxation techniq

结论摘要：

本项目突破传统的纯组合（即离散）的研究框架，基于数学规划的松弛策略，对大规模的NP困难排序问题，从随机化算法和列生成技术两个方面进行理论研究和应用研究。我们研究加工时间可控排序问题，用凸二次规划松弛方法，设计界为3的多项式时间近似算法，被美国引文索引数据库（SCI）收录；用凸二次规划松弛方法研究工件具有不同就绪时间的工件可拒绝排序问题，得到界为2的多项式时间近似算法，被美国工程索引数据库（EI）收录。我们研究工件的安装时间与加工次序有关的平行机排序问题，给出整数规划模型，结合动态规划和分支定界方法，用列生成技术求解。我们项目组指导的博士学位论文研究成组加工排序问题，分别讨论单台机器和多台平行机环境下大规模的NP-困难问题的列生成算法，通过试验计算可以解决10台机器和60个工件的排序问题。我们项目组的海外成员研究供应链排序，4篇论文被SCI期刊收录。我们研究与交货期有关的多个供应商的排序问题，研究供应商是多台平行机的排序问题，研究机器加工能力不能超过给定的量的供应链排序。三年来我们完成论文22篇，其中SCI收录5篇，EI收录1篇。我们还培养博士生3人，其中已经获得学位2人，在读1人。

成果综合统计