Manufactural activity is the basis of every sound economy. The risk for today's industrial establishments in our let us say european conditions is to hold competitiveness in the terms of global economy. This diploma thesis is focusing on solving problems of manufacturing scheduling with the view of theory and practice. It is impeach of real-life production. Scheduling belongs to hard combinatorial problems and therefore are usually solved by various heuristic or metaheuristic methods. For application of mentioned metaheuristic methods is important to use suitable choice of representative data.

In this work, we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are present. In such a problem setting, after finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in a prespecified buffer. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. Besides a general buffer model,also specific configurations are considered.The key issue to develop fast heuristics for the job-shop problem with buffers is to find a compact representation of solutions. In contrast to the classical job-shop problem,where a solution may be given by the sequences of the jobs on the machines, now also the buffers have to be incorporated in the solution representation. In this work, we propose two solution representations for the job-shop problem with buffers. Furthermore, we investigate whether the given solution representations can be simplified for specific buffer configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation is necessary, whereas for specific buffer configurations possible simplifications are presented. Based on the given solution representations we develop local search heuristics in the second part of this work. Therefore, the well-known block approach for the classical job-shop problem is generalized to the job-shop problem with specific buffer configurations.

Nos travaux concernent l’étude d’une extension d’un problème d’ordonnancement bien connu sous l’appellation job shop. Nous appelons cette extension le General Flexible Job Shop Scheduling Problem (GFJSSP). Celui-ci se rencontre dans différents types d’ateliers ayant comme caractéristique commune d’être soumis à des contraintes dues à des ressources de transport. Le GFJSSP se caractérise par l’intégration de machines et robots flexibles. Le terme General induit par ailleurs la présence de robots dont la capacité est supposée unitaire dans notre étude, des temps opératoires bornés, et la possibilité de prise en compte d’emplacements de stockage spécifiques. Après avoir défini l’atelier et le problème correspondant à cette extension, nous avons proposé deux modélisations du GFJSSP ainsi défini : une première modélisation mathématique linéaire, et une modélisation graphique, qui correspond à une généralisation du graphe disjonctif couramment utilisé pour les problèmes de job shop. Nous avons ensuite abordé la résolution suivant deux étapes : tout d’abord en nous focalisant sur l’aspect séquencement des tâches de traitement et de transport, pour lequel nous avons élaboré deux méthodes heuristiques (de type Tabou et basée sur une procédure de shifting bottleneck améliorée) ; puis en intégrant dans un deuxième temps la problématique de l’affectation induite par la flexibilité de certaines ressources. Pour cette dernière étape, nous avons combiné les méthodes précédentes avec un algorithme génétique. L’algorithme hybride obtenu nous permet de résoudre des instances de la littérature correspondant à divers cas spécifiques, avec des résultats assez proches des meilleures méthodes dédiées. A termes, il pourrait être intégré dans un système d'aide à la décision général qui s’affranchirait de la phase d’identification préalable du type de job shop considéré, et serait adapté à la résolution de nombreux cas (avec ou sans problème d'affectation, temps de traitement fixes ou bornés, avec ou sans stockage, etc..). / Our work focuses on an extension of the well known job shop scheduling problem. We call this extension the General Flexible Job Shop Scheduling Problem (GFJSSP). It occurs in various kinds of workshops which are particularly constrained by one or several transportation resources (called robots). GFJSSP is characterized by the flexibility of both machines and robots. In the studied problem, the term General involves unitary capacity transportation resources, bounded processing times, and possible input/output buffers for machines. After defining the workshop and the corresponding problem, we proposed two kinds of model for the GFJSSP: a mathematical model, and a graphical one. This last one is a generalization of the disjunctive graph commonly used for job shop problems. We then addressed the resolution in two steps: firstly, by focusing on the sequencing of processing and transportation tasks. For this purpose we have developed two heuristics (Tabu search and an improved shifting bottleneck procedure). Secondly, we have considered the assignment problem involved by the flexibility of some resources. For this last step, we combined the above methods with a genetic algorithm. This hybrid algorithm allowed us to solve various specific cases of instances in the literature, with performance rather close to the best dedicated methods. In the future, it could be integrated within a general decision support system which could emancipate from the initial identification phase of the considered type of job shop, and which would be suitable for solving many cases (with or without assignment problem, fixed or bounded processing times, with or without storage, and so on).

Dans cette thèse nous nous sommes intéressés à l’extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l’existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu’un robot ne peut transporter qu’un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu’un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :• Une modélisation linéaire ;• Une modélisation sous forme de graphe disjonctif ;• Plusieurs heuristiques de construction de solutions ;• Plusieurs recherches locales qui améliorent les solutions obtenues ;• Utilisation des algorithmes génétiques / mémétiques comme schéma global d’optimisation ;• De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité. / In this thesis we are interested in the extension of the job-shop problem by adding the constraint of transport of jobs between different machines. In this study we used two types of robots, robots with unary loading capacity (capacity =1 means that each robot can carry only one job at a time,) and robots with non unary loading capacities (robot with capacity >1 can carry more than one job at time). Thus, the first step is devoted to the problem of job-shop with several robots with unary loading capacity. In the second step we extend the problem by adding the non-unary loading capacities to the robots. For both problems studied we have proposed :• A linear modeling ;• A Disjunctive graph Model ;• Several constructive heuristics ;• Several local searches methods that improve the obtained solutions ;• Use of genetic / memetic algorithms as a global optimization schema ;• New benchmarks, test results of our approaches on our benchmarks and those present in the literature and these results are commented and compared with those of literature. The results show the relevance of our model and its quality.