Refining the boundary between P and NP for identical machine scheduling
problems with preemption and release dates 

Damien Prot (IRCCYN, Nantes)

In this paper, we are interested in parallel identical machine 
scheduling problems with preemption and release dates in case 
of a regular criterion to be minimized. We show that solutions 
having a permutation flow shop structure are dominant if there 
exists an optimal solution with completion times scheduled in 
the same order as the release dates, or if there is no release date. 
We also prove that, for a subclass of these problems, the completion 
times of all jobs can be ordered in an optimal solution.
Using these two results, we provide new results on polynomially-solvable
problems and hence refine the boundary between P and NP for these problems.