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

DOI10.1016/J.EJOR.2005.12.027zbMATH Open1109.90043OpenAlexW2032041770MaRDI QIDQ856324FDOQ856324

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• On the Complexity of Scheduling with Batch Setup Times
• 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

Cited In (7)

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

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)