Optimally competitive list batching

DOI10.1016/j.tcs.2009.04.011zbMath1171.68053OpenAlexW2032752940MaRDI QIDQ837154

Leah Epstein, John Noga, Lawrence L. Larmore, Wolfgang W. Bein

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.011

zbMATH Keywords

online algorithmsdesign of algorithmsbatchingTCP acknowledgment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Batch sizing and job sequencing on a single machine
• On the remote server problem or more about TCP acknowledgments
• Scheduling a batching machine
• Batch scheduling with deadlines on parallel machines
• On-line scheduling on a single machine: Minimizing the total completion time
• The complexity of one-machine batching problems
• Batching identical jobs
• Solving a chemical batch scheduling problem by local search
• A class of on-line scheduling algorithms to minimize total completion time
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
• Minimizing makespan on a single batch processing machine with nonidentical job sizes
• On Minimizing Total Tardiness in a Serial Batching Problem
• On-line analysis of the TCP acknowledgment delay problem
• Dynamic TCP acknowledgment in the LogP model
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Scheduling jobs that arrive over time