Single-machine scheduling with release times and tails

We study the problem of scheduling jobs with release times and tails on a single machine with the objective to minimize the makespan. This problem is strongly NP-hard, however it is known to be polynomially solvable if all jobs have equal processing time P. We generalize this result and suggest an O(n²log n log P) algorithm for the case when the processing times of some jobs are restricted to either P or 2P.