带有固定工件的一个单机排序问题  

Single Machine Scheduling with Fixed Jobs

作　　者：石磊[1] 金世国[2] 

机构地区：[1]安阳师范学院数学科学学院,河南安阳455000 [2]河南广播电视大学,河南郑州450008

出　　处：《安阳师范学院学报》2008年第5期21-23,共3页Journal of Anyang Normal University

摘　　要：本文考虑带有固定工件的一个单机排序问题,证明了该问题是NP-困难的并给出了它的一个动态规划算法,证明该问题是拟多项式时间可解的。This paper considers a single machine scheduling with fixed jobs. It proves that this problem is NP- hard and presents a dynamic programming algorithm which is pseudo - polynomial.

关 键 词：固定工件 NP-困难 动态规划算法 

分 类 号：O223[理学—运筹学与控制论]