Les problèmes de placement : étude et résolution de quelques problèmes réels

The purpose of this thesis is to characterize real life cutting stock( or packing) problems and to provide efficient methods for a large spectrum of industrial problems. Usually, the packing problem consists in assigning a subset of out put bars to a subset of input bars to minimize the number of input bars used. Since our concern is to solve industrial problems, we have been obliged to take into account a large number of contraints and criteria. To face this complex situation, two types of approaches have been introduced, that is : building methods, used in the case of criteria which are not precisely defined ; in this case, we propose some parameters which can influence the characteristics of the solutions. These methods are close to the way of thinking of the users. The dynamic programming oriented methods (DPO), which are put at work when the various criterion values can be combined into a unique cost. The developed methods are set up successfully in the factories of our industrial partner. The DPO methods are particularly efficient (8% saving on ours examples) for solving problems with several real-life criteriaL'objectif de cette thèse consiste à caractériser les problèmes de découpe tels qu'ils se présentent dans l'industrie et d'apporter des méthodes efficaces pour résoudre ces problèmes. Tel qu'ils se présentent dans la littérature, ces problèmes consistent à positionner un sous-ensemble de barres filles sur un sous-ensemble de barres mères de plus grandes tailles de façon à minimiser le nombre de barres mères utilisées. Cependant, pour résoudre les problèmes de notre partenaire industriel, nous avons dû prendre en compte un large éventail de contraintes et de critères. Afin de les satisfaire, nous avons développé deux groupes de méthodes: (I) les méthodes par construction, applicables lorsque les couts ne sont pas mesurables. Elles réalisent le placement pas à pas en fonction des paramètres de contrôle du système fournis par les utilisateurs. Elles s'apparentent aux méthodes de traitement des problèmes avec critères qualitatifs souvent utilisées par les industriels ; (II) les méthodes inspirées de la programmation dynamique (dynamic programming oriented methods - dpo) sont utilisées lorsque des couts peuvent être associes aux solutions. Elles sont utilisées lorsque l'ensemble des critères à optimiser peuvent s'exprimer à l'aide d'un cout unique. Les algorithmes développés ont été implantes avec succès chez notre partenaire industriel. Les méthodes dpo sont particulièrement efficaces (gain de 8% sur nos exemples) pour résoudre des problèmes comportant de nombreux critère