Optimally competitive list batching

DOI10.1016/j.tcs.2009.04.011zbMath1171.68053MaRDI 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 algorithms; design of algorithms; batching; TCP acknowledgment

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B35: Deterministic scheduling theory in operations research

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