Mostrar el registro sencillo del ítem

dc.contributor.advisorFrançois Clautiaux
dc.contributor.advisorRuslan Sadykov
dc.contributor.advisorFrançois Vanderbeck
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorVIAUD, Quentin
dc.contributor.otherOlivier Beaumont [Président]
dc.contributor.otherManuel Iori [Rapporteur]
dc.contributor.otherIvana Ljubić [Rapporteur]
dc.contributor.otherSandra Ulrich Ngueveu
dc.contributor.otherEric Pinson
dc.date.accessioned2024-04-04T02:47:37Z
dc.date.available2024-04-04T02:47:37Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191662
dc.identifier.nnt2018BORD0350
dc.description.abstractCette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes.
dc.description.abstractEnThis thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.
dc.language.isoen
dc.subjectDécomposition
dc.subjectGénération de colonnes
dc.subjectHypergraphe
dc.subjectAlgorithme de labelling
dc.subjectHeuristique de diving
dc.subjectDécoupe
dc.subject.enDecomposition
dc.subject.enColumn generation
dc.subject.enHypergraph
dc.subject.enLabelling algorithm
dc.subject.enDiving heuristic
dc.subject.enCutting
dc.titleMéthodes de programmation mathématiques pour des problèmes complexes de découpe
dc.title.enMathematical programming methods for complex cutting problems
dc.typeThèses de doctorat
dc.subject.halMathématiques [math]/Combinatoire [math.CO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionUniversité de Bordeaux
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde ; 1991-....)
hal.identifiertel-03116523
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//tel-03116523v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=M%C3%A9thodes%20de%20programmation%20math%C3%A9matiques%20pour%20des%20probl%C3%A8mes%20complexes%20de%20d%C3%A9coupe&rft.atitle=M%C3%A9thodes%20de%20programmation%20math%C3%A9matiques%20pour%20des%20probl%C3%A8mes%20complexes%20de%20d%C3%A9coupe&rft.au=VIAUD,%20Quentin&rft.genre=unknown


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem