Mostrar el registro sencillo del ítem

Models and algorithms for configuring and testing prototype cars

hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorCLAUTIAUX, François
hal.structure.identifierRENAULT
dc.contributor.authorESSODAIGUI, Siham
hal.structure.identifierRENAULT
dc.contributor.authorNGUYEN, Alain
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierRENAULT
dc.contributor.authorYOUNES, Nawel
dc.date.accessioned2024-04-04T02:29:51Z
dc.date.available2024-04-04T02:29:51Z
dc.date.created2024
dc.date.issued2023-08-22
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190213
dc.description.abstractEnIn this paper, we consider a new scheduling problem, which occurs in the context of the automobile industry. Given a set of machines, and a set of jobs, we seek a fixed configuration for each machine (i.e. a set of values for different parameters), and an assignment of jobs to machines along the time horizon that respects compatibility constraints between jobs and machine configurations. Two objectives are optimized lexicographically: the number of late jobs, and the number of machines used. First we prove that even finding a feasible solution for the problem is NP-hard, and characterize the cases where compatibility constraints amount to ensuring that only pairwise compatible jobs are assigned to each machine. Then we propose a mathematical model for this problem, and a reformulation into a path-flow formulation. We use a refined labelling algorithm embedded in a column-and-row generation algorithm to produce primal and dual bounds from this formulation. We conducted computational experiments with industrial data from Renault, and compared our results with those obtained by solving a constraint programming model provided by the company. Our approach finds better solutions than those obtained by the company, and proves the optimality for all instances of our benchmark for the first objective function. We also obtain small optimality gaps for the second objective function.
dc.language.isoen
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enScheduling
dc.subject.enMixed integer linear programming
dc.subject.enColumn and row generation
dc.subject.enDiving heuristic
dc.subject.enAutomobile industry
dc.title.enModels and algorithms for configuring and testing prototype cars
dc.typeDocument de travail - Pré-publication
dc.subject.halMathématiques [math]/Optimisation et contrôle [math.OC]
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-04185248
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-04185248v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2023-08-22&rft.au=CLAUTIAUX,%20Fran%C3%A7ois&ESSODAIGUI,%20Siham&NGUYEN,%20Alain&SADYKOV,%20Ruslan&YOUNES,%20Nawel&rft.genre=preprint


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