Parts P1--P7 are machined first on a milling machine and then polished at a separate machine. Using the information in the following table, the minimum total completion time required for carrying out both the operations for all 7 parts is ____________________ hours.
Show Hint
For two-machine scheduling, Johnson's Rule guarantees the minimum total completion time by placing short milling jobs early and short polishing jobs late.
This is a classic two-machine scheduling problem solved using Johnson's Rule. The rule states: (1) If the milling time<polishing time, schedule early. (2) If the polishing time<milling time, schedule late. We now classify the parts: Early group (Milling<Polishing): P3 (3<4), P4 (4<6), P5 (5<7), P7 (2<1? No), P2 (3<2? No), P6 (6<4? No), P1 (8<6? No). Late group (Polishing<Milling): P1, P2, P6, P7. Ordering early group in increasing milling time gives: P3 (3), P4 (4), P5 (5). Ordering late group in decreasing polishing time gives: P1 (6), P6 (4), P3 (4), P2 (2), P7 (1). But P3 is already used, so late group = P1, P6, P2, P7. Thus final Johnson order: \[ P3,\, P4,\, P5,\, P1,\, P6,\, P2,\, P7. \] Now compute the makespan: Milling (Machine 1) times accumulate: 3, 7, 12, 20, 26, 29, 31. Polishing (Machine 2) starts only after both Milling and its own completion allow it: Starts at 3 (finishes 7), then 11, 18, 26, 30, 32, and last finishing time is 33 hours. Final Answer: 33 hours
