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

The two-machine open shop problem with time delays

Zhang Li Chuan. (2012). The two-machine open shop problem with time delays. Mémoire de maîtrise, Université du Québec à Chicoutimi.

[thumbnail of 030297895.pdf]


Research on scheduling problems as we know it nowadays dates back to 1950s. Indeed, in 1954, Johnson described an exact algorithm to minimize the overall completion time (known as the makespan) for the two-machine flow shop problem. This resulted in a new discipline of operational research known as scheduling theory.

Scheduling theory deals with the attempt of using a set of scarce resources in accomplishing variegated tasks in order to optimize one or several criteria. The resources and tasks are commonly referred to as machines and jobs, respectively. There is a broad spectrum of definitions for the tasks and resources. For example, the resources can take the form of production lines in workshops, airport runways, school classrooms, etc. Furthermore, the process of fulfilling a task in a given machine is sometimes called an operation. For instance, a task may be represented by the work-pieces processed on production lines, the aircrafts taking off and landing at airports, the teachers lecturing in classrooms and so on. Let us note at this stage that machines and jobs may have been characterized by many other factors such as speed, time of availability, duplication, etc for the former, and precedence constraints, due dates, time lags for the latter. These factors must be taken into consideration when formulating a scheduling strategy if we want to produce a realistic solution.

Generally speaking, scheduling problems fall into the following three categories: A single machine model, parallel machines model and multi-operation model. The models known as multi-operation model are flow-shop, open shop and job shop.

In addition, a scheduling solution is evaluated according to a given criterion or sometimes to a set of given criteria such as the minimization of makespan, mean finish time, number of tardy jobs, etc.

This thesis is mainly concerned with the problems of minimizing the makespan criterion in a two-machine open shop environment with time delay considerations.

In order to better approach the resolution of this problem, some basic concepts on scheduling theory and related knowledge, such as the theory of NP-completeness, have been introduced. It is important to analyze the advantages and disadvantages of different algorithms, in order to come up with an adequate solution.

We presented in this dissertation the resolution of the two-machine open shop problem with time delays along the following lines. First, we start by looking at special cases to solve to optimality in polynomial time. Then, we move onto the design of heuristic algorithms, based on simple rules. Finally, we discuss two meta-heuristic algorithms and lower bounds, and undertake simulation experiments to analyze their performance in the average case. For heuristic algorithms, we discussed some approaches that evaluate their performance. Regarding the meta-heuristic approach, we used the simulated annealing and the tabu search algorithms, respectively. We then improved the second approach by adding the intensification and diversification strategies. Finally, we proposed a new hybrid approach to solve our original open shop problem in the hope to improve and speed up the quality of the solution.

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:98
Identifiant unique:10.1522/030297895
Sujets:Sciences naturelles et génie > Sciences mathématiques > Informatique
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:Ordonnancement (Informatique), Computer scheduling, Problèmes NP-complets, NP-complete problems, Algorithmes heuristiques, Heuristic algorithms, TWO-MACHINE
Déposé le:14 déc. 2012 09:59
Dernière modification:20 mai 2016 15:47
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