摘要
本文把单机排序问题 １‖∑ｗｊＣｊ表述成一个二次规划，并把不带权的问题１‖∑Ｃｊ进一步转化成指派问题，从而用指派问题的匈牙利算法证明 ＳＰＴ序是问题１‖∑Ｃｊ的最优解．这个结论似乎很平凡，但对于用数学规划来研究排序问题是一个很有意义的进展．这为我们用二次规划和半定规划来研究ＮＰ困难的排序问题的近似算法打下基础．
In this paper we formulate the single machine scheduling problem １‖∑wjCｊas a quadratic program, and its special case 1‖∑Cj an assignment problem. Therefore it is proved by Hungary algorithm of the assignment problem that SPT sequence is an optimum for 1‖∑Cj.
出处
《应用数学与计算数学学报》
2000年第2期77-82,共6页
Communication on Applied Mathematics and Computation
基金
国家自然科学基金资助项目!(项目编号19771057).
