The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard

DOI10.1016/j.ejor.2005.12.027zbMath1109.90043OpenAlexW2032041770MaRDI QIDQ856324

N. E. Zubov

Publication date: 7 December 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2005.12.027

zbMATH Keywords

schedulingbatchingmaximum latenessdue-datesmulti-operation jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (5)

Unary NP-hardness of minimizing the number of tardy jobs with deadlines ⋮ Single batch machine scheduling with dual setup times for autoclave molding manufacturing ⋮ Hardware design of a new genetic based disk scheduling method ⋮ A simulated annealing algorithm for single machine scheduling problems with family setups ⋮ Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

Cites Work

• Unnamed Item
• Batch scheduling to minimize maximum lateness
• Scheduling multi-operation jobs on a single machine
• The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• On the Complexity of Scheduling with Batch Setup Times

This page was built for publication: The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard