单机排序问题的数学规划表示

被引：10

作者：

罗守成

张峰

唐国春

机构：

[1] 上海第二工业大学工商管理学院!上海,,上海第二工业大学工商管理学院!上海,,上海第二工业大学工商管理学院!上海,

来源：

应用数学与计算数学学报 | 2000年 / 02期

关键词：

排序; 数学规划; 指派问题;

D O I：

暂无

中图分类号：

O223 [统筹方法]; O221 [规划论（数学规划）];

学科分类号：

070105 ; 1201 ;

摘要：

本文把单机排序问题１‖∑ｗｊＣｊ表述成一个二次规划，并把不带权的问题１‖∑Ｃｊ进一步转化成指派问题，从而用指派问题的匈牙利算法证明ＳＰＴ序是问题１‖∑Ｃｊ的最优解．这个结论似乎很平凡，但对于用数学规划来研究排序问题是一个很有意义的进展．这为我们用二次规划和半定规划来研究ＮＰ困难的排序问题的近似算法打下基础．

引用

页码：77 / 82

页数：6

共 3 条

[1] Improved bounds on relaxations of a parallel machine scheduling problem [J].