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

## Algorithms for two-stage flow-shop with a shared machine in stage one and two parallel machines in stage two

Yang Yang. (2013). Algorithms for two-stage flow-shop with a shared machine in stage one and two parallel machines in stage two. Mémoire de maîtrise, Université du Québec à Chicoutimi.

 Prévisualisation

4MB

## 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.

Type de document: Thèse ou mémoire de l'UQAC (Mémoire de maîtrise) 2013 Chicoutimi Maîtrise en informatique 95 9781412319294 Sciences naturelles et génie > Sciences mathématiques > InformatiqueSciences naturelles et génie > Sciences mathématiques > Mathématiques appliquées Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique Rebaïne, Djamal Heuristique, Métaheuristiques, Optimisation mathématique, Recherche opérationnelle, Résolution de problème, Heuristic, Mathematical optimization, Operations research, Problem solving
Déposé le: 17 avr. 2014 14:08 20 mai 2016 15:48