Strong NP-Hardness of Single Machine Scheduling Problems with Variable Processing Time  

作　　者：周贤伟 杜文 朱健梅 

出　　处：《Journal of Modern Transportation》1998年第2期78-88,共11页现代交通学报（英文版）

摘　　要：In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.

关 键 词：single machine scheduling problem variable processing time strong NP   hardness. 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]