工件可预处理的单台机排序问题  

Single-machine scheduling with job can be processed in advance

作　　者：魏麒[1] 何勇[2] 

机构地区：[1]浙江大学宁波理工学院基础部,浙江宁波315100 [2]浙江大学数学系,浙江杭州310027

出　　处：《浙江大学学报（理学版）》2006年第4期383-388,共6页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(10271110);高等学校青年教师教学科研奖励计算资助项目

摘　　要：考虑一个工件可预处理的单机排序问题.要求在所有工件能够按时完工的前提下,使得预处理工件的费用最小.证明了对于一般情况,该问题是NP-难的,并给出了动态规划算法.进一步,得到当每个工件的预处理费用都相同时该问题是多项式可解的,并给出了强多项式时间算法.A single machine scheduling where jobs can be preprocessed before they are scheduled to the machine is considered. The objective is to minimize the cost for preprocessing under the constraint that no job is tardy. The problem is showed to be NP-hard and a pesudo-polynomial time algorithm is presented. For the case that the costs for preprocessing jobs are the same, a strongly polynomial time algorithm is presented.

关 键 词：单机排序 最优算法 计算复杂性 

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