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.
No takes yet. Share an insight, caveat, or question.
Boudhar et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: