Scheduling a batching machine with convex resource consumption functions

In various industries jobs undergo a batching, or burn in, process where different tasks are grouped into batches and processed simultaneously. The processing time of each batch is equal to the longest processing time among all jobs contained in the batch. All to date studies dealing with batching machines have considered fixed job processing times. However, in many real life applications job processing times are controllable through the allocation of a limited resource. The most common and realistic model assumes that there exists a non-linear and convex relationship between the amount of resource allocated to a job and its processing time. The schedulerʼs task when dealing with controllable processing times is twofold. In addition to solving the sequencing problem, one must establish an optimal resource allocation policy. We combine these two widespread models on a single machine setting, showing that both the makespan and total completion time criteria can be solved in polynomial time. We then show that our proposed approach can be applied to general bi-criteria objective comprising of the makespan and the total completion time.

► First paper to assume parallel batching and controllable job processing times. ► Development of optimal polynomial time algorithms for minimizing makespan and total completion time.