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

PDF
2MB 
Résumé
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 twomachine 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 workpieces 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 multioperation model. The models known as multioperation model are flowshop, 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 twomachine 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 NPcompleteness, 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 twomachine 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 metaheuristic 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 metaheuristic 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) 

Date:  2012 
Lieu de publication:  Chicoutimi 
Programme d'étude:  Maîtrise en informatique 
Nombre de pages:  98 
ISBN:  9781412318044 
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), Codirecteur(s) et responsable(s):  Rebaïne, Djamal 
Motsclés:  Ordonnancement (Informatique), Computer scheduling, Problèmes NPcomplets, NPcomplete problems, Algorithmes heuristiques, Heuristic algorithms, TWOMACHINE 
Déposé le:  14 déc. 2012 09:59 

Dernière modification:  20 mai 2016 15:47 
Éditer le document (administrateurs uniquement)