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

DOI10.1016/J.EJOR.2005.12.027MaRDI QIDQ856324zbMATH OpenOpenAlexFDO

Authors 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

maximum latenessschedulingbatchingdue-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)

Recommendations

• The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard
• A note on the complexity of family scheduling to minimize the number of late jobs
• Single machine batch scheduling problem with family setup times and release dates to minimize makespan
• Batch scheduling to minimize maximum lateness
• Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Batch scheduling to minimize maximum lateness
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• On the Complexity of Scheduling with Batch Setup Times
• 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

Cited in

(8)

• Single batch machine scheduling with dual setup times for autoclave molding manufacturing
• A note on the complexity of family scheduling to minimize the number of late jobs
• Minimizing L _max for the single machine scheduling problem with family set-ups
• A simulated annealing algorithm for single machine scheduling problems with family setups
• Hardware design of a new genetic based disk scheduling method
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard
• Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856324)