35-5 Parallel machine scheduling

In the parallel-machine-scheduling problem, we are given $n$ jobs, $J_1, J_2, \dots, J_n$, where each job $J_k$ has an associated nonnegative processing time of $p_k$. We are also given $m$ identical machines, $M_1, M_2, \dots, M_m$. Any job can run on any machine. A schedule specifies, for each job $J_k$, the machine on which it runs and the time period during which it runs. Each job $J_k$ must run on some machine $M_i$ for $p_k$ consecutive time units, and during that time period no other job may run on $M_i$. Let $C_k$ denote the completion time of job $J_k$, that is, the time at which job $J_k$ completes processing. Given a schedule, we define $C_{\max} = \max_{1 \le j \le n} C_j$ to be the makespan of the schedule. The goal is to find a schedule whose makespan is minimum.

For example, suppose that we have two machines $M_1$ and $M_2$ and that we have four jobs $J_1, J_2, J_3, J_4$, with $p_1 = 2$, $p_2 = 12$, $p_3 = 4$, and $p_4 = 5$. Then one possible schedule runs, on machine $M_1$, job $J_1$ followed by job $J_2$, and on machine $M_2$, it runs job $J_4$ followed by job $J_3$. For this schedule, $C_1 = 2$, $C_2 = 14$, $C_3 = 9$, $C_4 = 5$, and $C_{\max} = 14$. An optimal schedule runs $J_2$ on machine $M_1$, and it runs jobs $J_1$, $J_3$, and $J_4$ on machine $M_2$. For this schedule, $C_1 = 2$, $C_2 = 12$, $C_3 = 6$, $C_4 = 11$, and $C_{\max} = 12$.

Given a parallel-machine-scheduling problem, we let $C_{\max}^*$ denote the makespan of an optimal schedule.

a. Show that the optimal makespan is at least as large as the greatest processing time, that is,

$$C_{\max}^* \ge \max_{1 \le k \le n} p_k.$$

b. Show that the optimal makespan is at least as large as the average machine load, that is,

$$C_{\max}^* \ge \frac 1 m \sum_{1 \le k \le n} p_k.$$

Suppose that we use the following greedy algorithm for parallel machine scheduling: whenever a machine is idle, schedule any job that has not yet been scheduled.

c. Write pseudocode to implement this greedy algorithm. What is the running time of your algorithm?

d. For the schedule returned by the greedy algorithm, show that

$$C_{\max} \le \frac 1 m \sum_{1 \le k \le n} p_k + \max_{1 \le k \le n} p_k.$$

Conclude that this algorithm is a polynomial-time $2$-approximation algorithm.

(Omit!)