Modélisation et résolution de problèmes de distribution et ordonnancement
A major concern of many industrial enterprises is the irnprovement of their distribution system. ln the fust part of this thesis, we show how the use of tools from applied mathematics and computer science helps to reduce distribution costs significantly. For this purpose, we propose new methods for solving the vehicle routing problem. These methods are not only efficient but also flexible (they take into account a large variety of constraints) and robust (they can be applied to very different problems, without the need to determine precisely their control parameters). Combining a simple and fast heuristic procedure with a method based on Tabu search techniques makes it possible to solve complex real life problems. Another algorithm developed in this thesis is an evolutionary method at the crossroads of the Tabu meta-heuristic and genetic algorithms. In addition to the above advantages and as opposed to most of today's heuristics, an interesting feature of this new method is the fact that it can be easily codable on parallel CPU's. The number of processors can be chosen independently from the size of the problem. The second type of problem addressed in this thesis is the optirnization of sample processing in a robotized analytical system. Recent market studies have shown a growing interest in these complex scheduling problems, which, to our knowledge, cannot be solved with currently available methods. In the second part of this work, we describe both a fast constructive heuristic and a genetic algorithm to efficiently solve scheduling problems in a robotized environment. Our methods, which have already been used in practice, are flexible and can handle a large number of constraints. More precisely, we take into account the management of a non-static resource such as a robot, of resources able to sirnultaneously process several samples, of (possibly bounded) waiting tirnes between operations on a single sample, and of flexibility in the samples processing tirnes on the resources.
EPFL_TH1517.pdf
n/a
openaccess
Copyright
10.4 MB
Adobe PDF
a0ac359ac2f6f44414124f244d727d1b