Utilize este identificador para referenciar este registo: https://hdl.handle.net/1822/53257

TítuloImproving branch-and-price for parallel machine scheduling
Autor(es)Lopes, Manuel
Alvelos, Filipe Pereira e
Lopes, Henrique Daniel Oliveira
Palavras-chaveParallel machine scheduling
Sequence dependent setup times
Column generation
Branch-and-price
Data2014
EditoraSpringer International Publishing AG
RevistaLecture Notes in Computer Science
Resumo(s)In this paper we present a hybrid exact-heuristic method to improve a branch-and-price algorithm to solve the unrelated parallel machines with sequence-dependent setup times scheduling problem. As most of the computational time in the column generation (CG) process is spent in subproblems, two new heuristics to solve the subproblems are embedded in the branch-and-price (BP) framework with the aim to improve the efficiency of the process in obtaining optimal solutions. Computational results show that the proposed method improves a state-of-the-art BP algorithm from the literature, providing optimal solutions for large instances (e. g. 50 machines and 180 jobs) of the parallel machine scheduling problem with sequence dependent setup times, in significantly less time. One of the proposed approaches reduces, in average, to a half the time spent in the root of the branch-and-price tree and to a quarter the time spent in the full branch-and-price algorithm.
TipoArtigo em ata de conferência
URIhttps://hdl.handle.net/1822/53257
ISBN978-3-319-09128-0
DOI10.1007/978-3-319-09129-7_22
ISSN0302-9743
Versão da editorahttps://link.springer.com/chapter/10.1007/978-3-319-09129-7_22
Arbitragem científicayes
AcessoAcesso restrito UMinho
Aparece nas coleções:CAlg - Artigos em livros de atas/Papers in proceedings

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Improving Branch-and-Price for Parallel Machine Scheduling .pdf
Acesso restrito!
285,02 kBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID