Mostrar el registro sencillo del ítem

hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorFROGER, Aurélien
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorSADYKOV, Ruslan
dc.date2022
dc.date.accessioned2024-04-04T02:40:33Z
dc.date.available2024-04-04T02:40:33Z
dc.date.issued2022
dc.identifier.issn0377-2217
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191071
dc.description.abstractEnWe study the prize-collecting job sequencing problem with one common and multiple secondary resources. In this problem, a set of jobs is given, each with a profit, multiple time windows for its execution, and a duration during which it requires the main resource. Each job also requires a preassigned secondary resource before, during, and after its use of the main resource. The goal is to select and schedule the subset of jobs that maximize the total profit. We present a new mixed integer linear programming formulation of the problem and a branch-cut-and-price algorithm as an exact solution method. We also introduce a heuristic algorithm to tackle larger instances. Extensive numerical experiments show that our exact algorithm can solve to optimality literature instances with up to 500 jobs for a particular dataset and up to 250 jobs for another dataset with different characteristics. Our heuristic builds high-quality solutions in a small computational time. It computes new best-known solutions for most of the larger instances.
dc.language.isoen
dc.publisherElsevier
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enIterated local search
dc.subject.enBranch-cut-and-price
dc.subject.enLabeling algorithm
dc.subject.enSequencing
dc.subject.enScheduling
dc.title.enNew exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ejor.2022.07.012
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalEuropean Journal of Operational Research
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-03287769
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03287769v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2022&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=FROGER,%20Aur%C3%A9lien&SADYKOV,%20Ruslan&rft.genre=article


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