Heuristic Fss Methods Notes

Lecture 9: Heuristic FSS Methods / Heuristic TSP Methods Topics * * * * * Reading Heuristic Approaches to Flow Shop Scheduling Johnson's "Standard" 3 Machines Algorithm Johnson's 3-Machine "Difference" Algorithm 3 Machines Flow Shops: "Sequencing on the Two Dominant Machines" Heuristic Solutions to Traveling Salesman Problems (TSPs) Key Points * Why use heuristic approach to FSS * Johnson's standard 3 machine algorithm * Makespan * Johnson's 3 machine difference algorithm * Sequencing on the two dominant machines * Travelling salesman problems Heuristic Approaches to Flow Shop Scheduling * If none of the 3 conditions of the Johnson's 3-machines algorithm are satisfied, we need an heuristic approach * Use any approach that may throw up a good schedule * One heuristic approach may be to use Johnson's 3MC method even though the optimality test fails Johnson's "Standard" 3 Machines Algorithm * One step ahead TSP algorithm Definitions * Makespan = A lower bound on the final project completion time * Traveling Salesman Problem = Starting from O, you must travel to each of N places. You can travel to each place only once in any sequence and on leaving the Nth destination you must return to O for the first time. Example of Johnson's Standard 3 Machines Algorithm Formulae * * Makespan * Makespan = A lower bound on the final project completion time * In the best possible theoretical case: * No hold-ups occur * Consider each machine in turn to be a potential bottleneck * Leads us to three lower bounds on the makespan* [?] In the example above, the lower bound on the makespan will be:? This tells us that it is impossible for the project to be completed in less that 75 days ? This does not mean that there is or isn't a better schedule than our 78 day one Our conclusion based on the makespan ? "either our project completion time of 78 days is optimal, or, if it is not, it is at most 3 days non-optimal" ? It is very important to clearly conclude this Johnson's 3-Machine "Difference" Algorithm A variation on the "standard" algorithm Course Notes Page 15 

Buy the full version of these notes or essay plans and more in our Operational Research Techniques Notes.