平行机分组工件排序的多面体方法

项目名称： 平行机分组工件排序的多面体方法

项目编号： No.10971201

项目类型： 面上项目

立项/批准年度： 2010

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

项目作者： 原晋江

作者单位： 郑州大学

项目金额： 24万元

中文摘要： 为了突破国内排序研究中数学工具和理论深度不够而导致学科发展受阻的局面，我们建议通过研究可行解域（即排序多面体）来处理排序问题。目的是在全新的理论工具的基础上寻求有效的多项式时间算法、近似算法和在线算法。借助线性规划的对偶理论、整数规划的线性规划松弛、不等式系统的全对偶整性与整多面体的关系以及原设-对偶近似算法的原理，我们将对平行机分组工件系统的离线和在线排序进行系统的研究。我们构造完工时间向量的整线性约束，并以此为基础研究松弛线性约束所定义的多面体与整线性约束之间的内在联系。在成果表现方面，不仅要对平行机分组工件排序模型有完整的研究结果，还要对一般排序问题的多面体组合研究方法建立基本的理论构架。

中文关键词： 排序；分组工件；平行机；多面体方法；近似算法

英文摘要：

英文关键词： scheduling；family-jobs；parallel machines；polyhedral approach；approximation algorithms