Preemption Can Make Parallel Machine Scheduling Problems Hard

It is shown that problem P j p j = p; pmtn j P w j U j is binary NP -hard although the corresponding nonpreemptive problem can be solved in O(n log n) time where n is the number of jobs. This contrasts the fact that usually preemptive problems are not harder than their nonpreemptive counterparts. Keywords: parallel machine scheduling, jobs with equal processing times, preemption, NP -hardness, polynomial algorithm. It has been shown in Brucker et al. [1999] that problem J2 j n = 3; pmtn j C max is polynomial solvable although the nonpreemptive counterpart J2 j n = 3 j C max can be solved in O(r 4 ) time where r is the number of operations of the job shop problem. This result disproved a common belief that by preemption a scheduling problem becomes easier to solve. In this short note we prove that problem P j p j = p; pmtn j P w j U j is NP - hard where as an O(n log n)-algorithm is presented for problem P j p j = p j P w j U j . This shows that preemption can complicate ev..