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.

[thumbnail of 030565289.pdf]


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)
Lieu de publication:Chicoutimi
Programme d'étude:Maîtrise en informatique
Nombre de pages:95
Sujets:Sciences naturelles et génie > Sciences mathématiques > Informatique
Sciences naturelles et génie > Sciences mathématiques > Mathématiques appliquées
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique
Directeur(s), Co-directeur(s) et responsable(s):Rebaïne, Djamal
Mots-clés: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
Dernière modification:20 mai 2016 15:48
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630