Chapter 35, Problem 5P

a.

Program Plan Intro

To show that optimal makespan is at least as large as the greatest processing time $C^{*}{}_{\max }$ i.e. $C^{*}{}_{\max }\ge \underset{1\le k\le n}{\max }{p}_k$ .

b.

Program Plan Intro

To show that optimal makespan is at least as large as the average machine load i.e. $C^{*}{}_{\max }\ge \frac{1}{m}{\displaystyle \sum _{1\le k\le n}^{}{p}_k}$ .

c.

Program Plan Intro

To write the pseudocode for the given greedy approach and provide its running time as well.

d.

Program Plan Intro

To show $C_{\max }\le \frac{1}{m}{\displaystyle \sum _{1\le k\le n}^{}{p}_k}+\underset{1\le k\le n}{\max }{p}_k$ for the schedule returned by the greedy algorithm and then conclude that this algorithm is a polynomial-time 2-approximation algorithm.