Explore BrainMass

Johnson's Algorithm for Optimal Scheduling: Production Line

A production line consists of two main workstations: an assembly workstation and a packaging workstation. The processing times for 11 jobs (in minutes) that must be processed on these two workstations are given below. There is plenty of space in between the workstations such that blocking does not occur. Find the optimal job sequence for this serial system with the minimum makespan. Make sure you show the steps you take to find an optimal solution. Draw a Gantt chart that shows completion time values.

Job J1 J2 J3 J4 J5 J6 J7 J8 J9 J10 J11
Workstation 1 30 18 28 22 46 16 20 5 15 25 34
Workstation 2 10 20 12 14 24 26 32 6 20 10 25.

Solution Preview

See the attached file.

Johnson's Algorithm for Optimal Scheduling
A = {1,2,3,4,5,6,7,8,9,10,11}; L1 = {}, L2 = {}

Step 1
Shortest job is J8,1
Remove part 8 from list A and Add 8 to end of list L1
A = {1,2,3,4,5,6,7,9,10,11}
L1 = {8}, L2 = {}

Step 2
Of remaining parts shortest operations are J1,2 and J10,2
Since both are on workstation 2, pick one with longer duration on workstation 1, i.e. J1,2
Remove 1 from list A and ...

Solution Summary

The solution discusses Johnson's Algorithm for optimal scheduling regarding a production line.