A note on scheduling identical parallel machines with preemptions and setup times

Mourad Boudhar, Alexandre Dolgui, Amina Haned, Abida Kerdali, Sergey Kovalev and Mikhail Y. Kovalyov

International Journal of Production Research, 2025, vol. 63, issue 3, 1203-1208

Abstract: 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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2024.2362414 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:63:y:2025:i:3:p:1203-1208

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2024.2362414

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().