IE 375 - Production Planning Homework Assignment 5 - December 27 1. (20 points) Suppose that vi jobs must be processed through three machines (A. B, and C) in the sequence A - B - C. Also, suppose that min A > max B, or min C max B. Recall from Lecture 6 that Johnson's algorithm can be used to find the optimal sequence that minimizes the makespan in this three machine problem by treating A = A+ B, and B-B + C as the processing times in a two-machine problem. Explain how this approach yields the optimal sequence when n = 2. 2. (40 points) Eight jobs are to be processed through a single machine. The processing times and due dates are as follows. Job 1 2 3 4 5 6 7 8 Processing time 3 6 4 9 7 5 2 8 Due date 4 8 13 12 10 25 20 24 (a) Determine the sequence of the jobs in order to minimize the mean lateness. Find the mean lateness and the mean flow time for this sequence. (b) Determine the sequence of the jobs in order to minimize the maximum lateness. Find the maximum lateness and the mean flow time for this sequence (c) Determine the sequence of the jobs in order to minimize the number of tardy jobs. If there are multiple optimal sequences, report the one minimizing the mean flow time. Find the number of tardy jobs and the mean flow time for this sequence (d) Determine the sequence of the jobs in order to minimize the maximum lateness subject to the following precedence relationships: 1 + 2 + 4,1 + 3 + 4, 35+ 7. and 6 =8. Find the maximum lateness and the mean flow time for this sequence. 3. (40 points) Two jobs (1 and 2) are to be processed through six machines (A, B, C, D. E, and F). Job 1 must be processed in the order A, B, C, D, E, and F. Job 2 must be processed in the order D, B, C, E, A, and F. The times required for the six operations on the two jobs are as follows. Job 1 Job 2 Required sequence Time Required sequence Time A B D 2 1 3 2 7 5 3 2 7 5 5 2 E A Determine how the two jobs should be scheduled in order to minimize the makespan. Draw the Gantt chart that indicates the optimal schedule 1