Sujet de th
Forum 'Emplois' - Sujet créé le 2004-06-14
Optimisation de placement et de découpe en deux dimensions
Sujet de thèse de doctorat proposé par
I. Kacem & C. Chu
Laboratoire : ISTIT (Institut des Sciences et des Techniques de l’Information de Troyes)
Equipe: OSI (Optimisation des Systèmes Industriels)
Profil: Recherche opérationnelle, optimisation combinatoire
E-mail: {kacem, chu}@utt.fr
Le travail de recherche envisagé concerne le domaine de placement et de découpe en deux dimensions avec prise en compte de contraintes pratiques comme la contrainte guillotine et les contraintes de changement d’outils. La problématique de placement se pose dans de nombreux secteurs industriels comme le textile, la confection, la métallurgie, l’industrie papetière, l’industrie de bois, etc. D’où l’intérêt pratique d’aborder un tel problème.
D’un point de vue théorique, le développement d’une méthodologie efficace pour maîtriser les aspects combinatoires est certes d’une importance capitale. En effet, peu de travaux ont été réalisés dans ce domaine et notamment dans le cas où les contraintes précitées sont prises en compte. En outre, et depuis quelques années notre équipe s’est penchée sur l’étude de ce type de problème à une dimension et à deux dimensions, un axe de recherche récent et particulièrement privilégié dans notre laboratoire.
Notre étude va être donc une suite logique des travaux déjà réalisés et qui ont donné lieu à des prestigieuses publications dans le domaine comme la revue Operations Research. Parmi les résultats antérieurs de l’équipe, les travaux réalisés dans le cadre de la thèse de S. Ben Messaoud ont porté une contribution particulièrement intéressante dans le domaine de placement à deux dimensions. Une telle contribution consiste en l’élaboration d’une caractérisation formelle permettant d’identifier une configuration guillotine et la construction des approches heuristiques efficaces (10% d’écart par rapport à l’optimum). Ces résultats sont encourageants et prometteurs et représentent une bonne base pour démarrer l’étude intégrant les coûts de l’opération de la découpe.
D’un point de vue méthodologique, nous envisageons l’étude des méthodes exactes dont l’équipe a acquis l’expertise et la reconnaissance à l’échelle nationale et internationale comme l’atteste les nombreuses publications dans des revues prisées. En particulier, la méthode de séparation et d’évaluation a montré son efficacité sur un certain nombre de problèmes. Nous envisageons également l’élaboration d’approches heuristiques et de bornes inférieures pour le problème étudié. Une évaluation de performance au pire des cas permettra de prouver l’efficacité de ces approches en se basant sur des fondements scientifiques.
Contact
Imed KACEM
E-mail: kacem@utt.fr
Tél: 03 25 71 58 54
Compétences souhaitées
Bonnes connaissances en recherche opérationnelle,
Bonnes connaissances en algorithmique et programmation.
Références
[1] S. Ben Messaoud, C. Chu, M-L. Espinouse, SHF : une nouvelle heuristique pour le problème de découpe guillotine en 2D, MOSIM'03, 23-25 avril 2003, Toulouse, France.
[2] S. Ben Messaoud, C. Chu, M-L. Espinouse, New concept of the classic shelf algorithm, IEPM’03, 26-28 mai 2003, Porto, Portugal.
[3] C. Chu, J. Antonio. Approximation algorithms to solve real life multi-criteria cutting stock problems. Operations Research. Vol. 47, pp 495-508, N°4, 1999.
[4] C. Chu, R. La. Variable-sized bin packing: tight absulate worst-case performance ratios for four approximation algorithms, SIAM. J. COMPUT. Vol 30, N°6, pp 2069-2083.
[5] K.A. Dowsland, W.B. Dowsland, Packing problems, European Journal of Operational Reserach 56 (1992) 2-14.
[6] H. Dyckhoff, U. Finke. Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992.
[6] M. Hifi, R.'M’Hallah. Approximate algorithms for constrained circular cutting problems, Computers & Operations Research, Volume 31, Issue 5, April 2004, Pages 675-694
[7] A. Lodi, S. Martello, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11 (1999) 345-357.
[8] A. Lodi, S. Martello, M. Monaci, Two-dimensional packing problems:a survey, European Journal of Operational Research 141 (2002) 241-252.[b][/b]
Sujet de thèse de doctorat proposé par
I. Kacem & C. Chu
Laboratoire : ISTIT (Institut des Sciences et des Techniques de l’Information de Troyes)
Equipe: OSI (Optimisation des Systèmes Industriels)
Profil: Recherche opérationnelle, optimisation combinatoire
E-mail: {kacem, chu}@utt.fr
Le travail de recherche envisagé concerne le domaine de placement et de découpe en deux dimensions avec prise en compte de contraintes pratiques comme la contrainte guillotine et les contraintes de changement d’outils. La problématique de placement se pose dans de nombreux secteurs industriels comme le textile, la confection, la métallurgie, l’industrie papetière, l’industrie de bois, etc. D’où l’intérêt pratique d’aborder un tel problème.
D’un point de vue théorique, le développement d’une méthodologie efficace pour maîtriser les aspects combinatoires est certes d’une importance capitale. En effet, peu de travaux ont été réalisés dans ce domaine et notamment dans le cas où les contraintes précitées sont prises en compte. En outre, et depuis quelques années notre équipe s’est penchée sur l’étude de ce type de problème à une dimension et à deux dimensions, un axe de recherche récent et particulièrement privilégié dans notre laboratoire.
Notre étude va être donc une suite logique des travaux déjà réalisés et qui ont donné lieu à des prestigieuses publications dans le domaine comme la revue Operations Research. Parmi les résultats antérieurs de l’équipe, les travaux réalisés dans le cadre de la thèse de S. Ben Messaoud ont porté une contribution particulièrement intéressante dans le domaine de placement à deux dimensions. Une telle contribution consiste en l’élaboration d’une caractérisation formelle permettant d’identifier une configuration guillotine et la construction des approches heuristiques efficaces (10% d’écart par rapport à l’optimum). Ces résultats sont encourageants et prometteurs et représentent une bonne base pour démarrer l’étude intégrant les coûts de l’opération de la découpe.
D’un point de vue méthodologique, nous envisageons l’étude des méthodes exactes dont l’équipe a acquis l’expertise et la reconnaissance à l’échelle nationale et internationale comme l’atteste les nombreuses publications dans des revues prisées. En particulier, la méthode de séparation et d’évaluation a montré son efficacité sur un certain nombre de problèmes. Nous envisageons également l’élaboration d’approches heuristiques et de bornes inférieures pour le problème étudié. Une évaluation de performance au pire des cas permettra de prouver l’efficacité de ces approches en se basant sur des fondements scientifiques.
Contact
Imed KACEM
E-mail: kacem@utt.fr
Tél: 03 25 71 58 54
Compétences souhaitées
Bonnes connaissances en recherche opérationnelle,
Bonnes connaissances en algorithmique et programmation.
Références
[1] S. Ben Messaoud, C. Chu, M-L. Espinouse, SHF : une nouvelle heuristique pour le problème de découpe guillotine en 2D, MOSIM'03, 23-25 avril 2003, Toulouse, France.
[2] S. Ben Messaoud, C. Chu, M-L. Espinouse, New concept of the classic shelf algorithm, IEPM’03, 26-28 mai 2003, Porto, Portugal.
[3] C. Chu, J. Antonio. Approximation algorithms to solve real life multi-criteria cutting stock problems. Operations Research. Vol. 47, pp 495-508, N°4, 1999.
[4] C. Chu, R. La. Variable-sized bin packing: tight absulate worst-case performance ratios for four approximation algorithms, SIAM. J. COMPUT. Vol 30, N°6, pp 2069-2083.
[5] K.A. Dowsland, W.B. Dowsland, Packing problems, European Journal of Operational Reserach 56 (1992) 2-14.
[6] H. Dyckhoff, U. Finke. Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992.
[6] M. Hifi, R.'M’Hallah. Approximate algorithms for constrained circular cutting problems, Computers & Operations Research, Volume 31, Issue 5, April 2004, Pages 675-694
[7] A. Lodi, S. Martello, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11 (1999) 345-357.
[8] A. Lodi, S. Martello, M. Monaci, Two-dimensional packing problems:a survey, European Journal of Operational Research 141 (2002) 241-252.[b][/b]