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

DOI10.1023/A:1024858623282zbMath1154.90426OpenAlexW1491174955MaRDI QIDQ2464401

Yanyan Li

Publication date: 20 December 2007

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1024858623282

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (14)

Integrated production and multiple trips vehicle routing with time windows and uncertain travel times ⋮ The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard ⋮ Unary NP-hardness of minimizing the number of tardy jobs with deadlines ⋮ Machine scheduling with job class setup and delivery considerations ⋮ Single machine batch scheduling problem with family setup times and release dates to minimize makespan ⋮ Solving the serial batching problem in job shop manufacturing systems ⋮ A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness ⋮ A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines ⋮ A survey of scheduling problems with setup times or costs ⋮ A coordination mechanism for a scheduling game with parallel-batching machines ⋮ An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines ⋮ A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups ⋮ 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

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