Optimally competitive list batching

Batching has been studied extensively in the offline case, but applications such as manufacturing or TCP acknowledgment often require online solutions. We consider online batching problems, where the order of jobs to be batched is fixed and where we seek to minimize the sum of the completion times of the jobs. We present optimally competitive online algorithms for both s -batch and p -batch problems, and we also derive results for certain naturally occurring special cases, such as the case of unit processing times.

Authors

• Wolfgang Bein
• Leah Epstein
• Lawrence L. Larmore
• John Noga

Keywords

• Design of algorithms
• Online algorithms
• Batching
• TCP acknowledgment