PREEMPTIVE SCHEDULING WITH DEADLINES ON PARALLEL MACHINES

This paper discusses the problem that n jobs with their own deadlines have to be processed on identical machines considering the idle insert.The objective is to find a preemptive job sequence so as to minimize the total earliness.The complexity is considered firstly,and the problem is proved strongly NP-hard through the induction of 3-partition problem.Then, the special case of common deadline is discussed.Since tardy jobs are prohibited,it's possible that there is no feasible sequence for the problem.The feasibility is considered primarily.If the problem is feasible,a polynomial time algorithm is developed to achieve optimality.