New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria

•We study preemptive parallel identical machine scheduling problems with release dates.•Solutions having a permutation flow shop structure are dominant.•Completion times of all jobs can be ordered in an optimal solution.•We provide new results on polynomially solvable problems.

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 PP and NPNP for these problems.