A note on scheduling identical parallel machines with preemptions and setup times
本文修正并改进了带抢占和设置时间的相同并行机调度问题的算法与复杂性结果，证明了任意机器数下问题的强NP困难性，并为两台机器情形给出了伪多项式算法和完全多项式时间近似方案。
We correct, extend and improve recent algorithmic and computational complexity results for the identical parallel machine scheduling problem with preemptions and setup times preceding uninterrupted job parts. The objective is to minimise the makespan. Our results include a proof of strong NP-hardness for an arbitrary number of machines, and a pseudo-polynomial algorithm and an FPTAS for the two machines case.