Abstract

At the onset of this thesis we aimed for a simple problem but with wide
practical applications. The initial objective was to reach more general problems
and wider applications after adaptations. For this reason, we focus on
parallel machines scheduling problems, and within them, in unrelated parallel
machine problems as they are a generalization of the identical and uniform parallel
related machines cases. We chose to minimize the maximum completion
time or Cmax, one of the most commonly studied objectives in the literature.
This problem, despite its theoretical nature, has many practical applications, as
in the case of sequencing the work of ceramic kilns. Furthermore, the problem
has been expanded in thesis for some not studied extensions like the case in
which not all machines have to be used or in the case where not all jobs must
be processed.
The goals of this thesis are to present simple and powerful algorithms for
solving the R//Cmax problem, capable of constituting the new state-of-theart
in the literature. Modern computers are built with multi-core CPUs and
modern algorithms are starting to take this into account. Therefore, we also
set a goal to make parallel computing adaptations of our presented algorithms.
Finally, we set the goal of finding effective and simple methods for solving
problems where not all machines have to be used and problems where not all
jobs must be processed.
In the present thesis we have conducted and extensive study of existing literature
for the unrelated parallel machines scheduling problem and extracted the
state-of-the-art. We also study the possible types of instances to be used, since
the literature was lacking a common benchmark.
We present four simple initial algorithms that improve the performance of
existing state-of-the-art methods in some cases and better results, on average,
in the entire set of instances treated. These algorithms are based on iterative
methods. An iterative application to local optimality of an insertion local
search followed by a interchange local search has proven beneficial. This,
together with various methods of partial modification of the solution are the
main core of the proposed algorithms.
We introduce procedures to reduce the degree of randomness of the initially
proposed algorithms, where we develop three new methods that improve the
previous algorithms and give better results than the state-of-the-art in virtually
all cases. A new hybrid algorithm which combines all the features of the methods
developed so far leads us to a significant improvement in the benchmark
results.
Despite the excellent performance, we further propose new methods based on
a reduction in the number of variables to consider when solving the mathematical
assignment problem. This results in five new algorithms that further
improve the solutions obtained by all previously proposed methods. It is worth
noting that the proposed algorithms not only achieve good results, but they do
so with an inherent simplicity.
Some changes are made to the best algorithms in order to parallelize them.
This allows us to compare with the state-of-the-art in parallel computing environments.
The results show again the superiority of the proposed methods also
in parallel environments.
Finally, we study the problem where not all machines have to be used and problems
where not all jobs must be processed. Their mathematical formulations
are studied first. Later, we present some algorithmic approaches for solving the
first problem, as the second is shown to be readily solvable by mathematical
programming.
The thesis closes with an assessment of all the achievements, publications and
statements for future research lines.