On Batching Task Scheduling

We investigate the following batching task scheduling problem. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. The scheduler needs to find a schedule giving optimum system utility. We develop an algorithmic framework for this batching task scheduling by investigating four formulations of the problem, the bounded and unbounded batching, depending on whether the number of simultaneously executable tasks is bounded, the synchronous and asynchronous batching, depending on whether the batched tasks need to start synchronously. For each formulation, we develop our approximation algorithm whose approximation ratio outperforms the best existing result. We further perform numerical simulations in a wide variety of system settings to complement our theoretical analysis and demonstrate the effectiveness of our scheduling algorithms.