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

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