Scheduling two types of jobs with minimum makespan

Abstract

We consider scheduling two types of jobs (A-job and B-job) to $p$ machines and minimizing their makespan. A group of same type of jobs processed consecutively by a machine is called a batch. For machine $v$, processing $x$ A-jobs in a batch takes $k_v^A{x}^2$ time units for a given speed $k_v^A$, and processing $x$ B-jobs in a batch takes $k_v^B{x}^2$ time units for a given speed $k_v^B$. We give an $O(n^{2}p\log (n))$ algorithm based on dynamic programming and binary search for solving this problem, where $n$ denotes the maximal number of A-jobs and B-jobs to be distributed to the machines. Our algorithm also fits the easier linear case where each batch of length $x$ of $A$-jobs takes $k_v^{A}x$ time units and each batch of length $x$ of $B$-jobs takes $k_v^{B}x$ time units. The running time is the same as the above case.