Scheduling the hybrid flowshop : branch and bound algorithms /

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the "Preflow Push" algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.