An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan

DOI10.1007/s10878-007-9128-7zbMath1159.90021OpenAlexW2798229098MaRDI QIDQ1016040

Zhigang Cao, Yu-Zhong Zhang

Publication date: 4 May 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9128-7

zbMATH Keywords

schedulingmakespanbatchingnon-identical job sizesasymptotic PTAS

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Solving a supply chain scheduling problem with non-identical job sizes and release times by applying a novel effective heuristic algorithm

Cites Work

• Bin packing can be solved within 1+epsilon in linear time
• Scheduling a batching machine
• Approximation algorithms in batch processing
• Minimizing mean completion time in a batch processing system
• Scheduling with batching: A review
• Minimizing makespan on a single batching machine with release times and non-identical job sizes
• Minimizing makespan on a single batch processing machine with nonidentical job sizes
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling a single batch processing machine with non-identical job sizes
• Scheduling a batch processing machine with non-identical job sizes
• Minimizing the makespan on a batch machine with non-identical job sizes: An exact procedure