4. (a) A company wish to produce the optimal ordering of 5 jobs on two machines where each job has to be processed on Machine 1 and then on Machine 2. The times of processing each job on each machine are as follows:

Find the optimal ordering using Johnson’s Algorithm. Draw a Gantt chart of the jobs and state the corresponding makespan.

(b) A company that make generators must plan its production schedule for the next five months. They estimate the demand is as follows:

 Month 1: 4

Month 2: 3

Month 3: 7

Month 4: 5

Month 5: 2

They will start month 1 with 1 generator in stock. It costs £1,000 to store a generator for one month. Each generator costs £5,000 to manufacture though the company saves £1,000 if they make more than 3 generators in a month (so for example making 3 generators costs £15,000 whereas making 4 generators costs £19,000). They can make a maximum of 5 generators per month. They wish to end Month 5 with 0 generators in stock. Use dynamic programming to determine how many generators the company should manufacture each month. Include all definitions in your answer.