In this paper, we present an integer programming model and a parallel genetic algorithm for solving certain type of cellular manufacturing system design problems. The parallel implementation of the genetic algorithm has significantly improved our computational capabilities comparing to those when the algorithm was run sequentially in solving the same model.

We present a framework for a guided parallel cooperative search that combines common meta-heuristics to solve combinatorial problem with more robustness and efficiency. Based on the central memory concept, the proposed identification pattern mechanism sends information to individual meta-heuristics about promising and unpromising patterns of the solution space. By fixing or prohibiting specific solution attribute values in particular search methods, we can focus the search to desired regions. This mechanism may thus be applied to enforce a better coordination between the individual methods and control the diversification and intensification of the global search. We apply this mechanism to the Vehicle Routing Problem with Time Windows. Experimental results on an extended set of benchmark problem sets illustrate the benefits of the proposed methodology. Keywords : Parallel computation, Cooperative Search, Vehicle Routing Problem

Les avions sans pilotes, UAV (Unmanned Aerial Vehicle), sont utilisés par la défense nationale canadienne dans des contextes divers et dans des missions à haut risques telles la reconnaissance ou la surveillance d’un territoire ennemi. La problématique qu’on se propose d’étudier est celle de la coordination et du contrôle d’une flotte d’UAVs lors d’une mission de surveillance, ou de reconnaissance, dans un contexte réel et dynamique. Ce dit contexte est défini par des contraintes réelles tels les obstacles géographiques, les pannes, les menaces ennemies, la cinématique des avions et la position variable des cibles à visiter. En outre il est dynamique car toutes ces dernières contraintes ne sont pas statiques mais plutôt sujet à des variations durant la mission. Le problème est modélisé comme un problème de tournées de véhicules, VRP (Vehicle Routing Problem), où les UAVs représentent les véhicules et les cibles les clients. L’une des particularités de notre sujet est que le plus court chemin entre deux positions - définies par les coordonnées et l’orientation de l’avion – n’est pas une ligne droite mais une courbe dite chemin non holonome, c’est à dire qui tient compte des contraintes cinématique de l’avion. Pour la résolution, nous commençons par le calcul des plus cours chemins non holonomes, reliant des paires de configurations données, sans collision avec les obstacles de l'environnement. Ensuite nous résolvons un problème de VRP pour déterminer la stratégie de déploiement des avions. La quantité accrue de calcul et les besoins du temps réel nous ont astreints à utiliser des méthodes de calcul parallèle.

Generic programming is a very powerfull paradigm to build flexible yet efficient libraries. We present in this talk a programming environment for local search called Metalab which is based on this paradigm. The environment proposes to design local search programs in three independant parts : representations, variables and controls. The set of representations modelize the search space, the set of variables takes some desired measures over the trajectory, and the set of controls proceeds the search in function of the variables received. The composition of variables between each other in turn allows to build complex information related to the search. This programming environment, which has been implemented with the static polymorphism features of the C++, may streamline the programming of local search methods as it allows to divide the computing tasks, to create reusable software components and to compose programs in different ways.