Optimal batching of heterogeneous jobs under service speedup

May 28, 2019 – ,

In many communication and computing systems, the incoming stream of jobs may be served in batches. This leads to resource optimization in some cases justifying the additional step in the sequence of operations. For example, database systems are known to benefit from batching operations, i.e., collecting incoming queries in a batch to reduce the single operation overhead. This can be described as speedup in terms of the mean service time per job which depends on the job type, the batch size, and also the composition of the batch. In this work, we aim to formulate a cost metric in a batching system that accumulates the benefits from batching speedup at the cost of the waiting time for batch formation. Thereafter, we explore two types of batching: one that batches jobs by type and the other one that allows putting multiple job types in a single batch. We seek to find optimality in terms of size and composition of the batch for the metric we formulate.

download corresponding tendering

Keywords: Batching, Speedup, Queueing

Research Area(s):

Tutor: Kar,

Open Theses