Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

Scheduling problems may be encountered in many situations in everyday life. Organizing daily activities and planning a travel itinerary are both examples of small optimization problems that we try to solve every day without realizing it. However, when these problems take on larger instances, their resolution becomes a difficult task to handle due to prohibitive computations that generated.

This dissertation deals with the Two-Stage Flow-shop problem that consists of three machines and in which we have two sets of jobs. The first set has to be processed, in this order, by machine M± and then by machine M2. Whereas, the second set of jobs has to be processed, in this order, by machine M± and then by machine M3. As we can see, machine M1 is a shared machine, and the other two machines are dedicated to each of the two subsets of jobs.

This problem is known to be strongly NP-Hard. This means there is a little hope that it can be solved by an exact method in polynomial time. So, special cases, heuristic, and meta-heuristic methods are well justified for its resolution.

We thus started in this thesis to present special cases of the considered problem and showed their resolution in polynomial time.

In the approximation front, we solved the considered problem with heuristic and meta-heuristic algorithms.

In the former approach, we designed two heuristic algorithms. The first one is based on Johnson's rule, whereas the second one is based on Nawez, Enscore, and Ham algorithm. The experimental study we have undertaken shows that the efficiency and the quality of the solutions produced by these two heuristic algorithms are high.

In the latter approach, we designed a Particle Swarm Optimization algorithm. This method is known to be popular because of its easy implementation. However, this algorithm has many natural shortcomings. We thus combined it with the tabu search algorithm to compensate the negative effects. The experimental study shows that the new hybrid algorithm outperforms by far not only the standard Particle Swarm Optimization, but also the tabu search method we also designed for this problem.