Résolution séquentielles et parallèles des problèmes de découpe / placement

Several real life industrial applications require the allocation of a set of rectangular items (or pieces) to a larger rectangular standardized stock unit. For instance, in the glass, plastic or metal industries, rectangular components have to be cut from a large sheet of material. Similarly, when filling the pages of a newspaper, the editor has to arrange articles and advertisements, presented as rectangular areas, on pages of xed dimensions. Generally, industrial applications require cutting or packing the largest number of items/pieces into a rectangular unit as to minimize the waste of the rectangular stock unit. In this thesis, we propose exact, approximate and parallel algorithms for the Two-Dimensional Cutting stock Problem.; Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.