Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/53257
Título: | Improving branch-and-price for parallel machine scheduling |
Autor(es): | Lopes, Manuel Alvelos, Filipe Pereira e Lopes, Henrique Daniel Oliveira |
Palavras-chave: | Parallel machine scheduling Sequence dependent setup times Column generation Branch-and-price |
Data: | 2014 |
Editora: | Springer International Publishing AG |
Revista: | Lecture 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. |
Tipo: | Artigo em ata de conferência |
URI: | https://hdl.handle.net/1822/53257 |
ISBN: | 978-3-319-09128-0 |
DOI: | 10.1007/978-3-319-09129-7_22 |
ISSN: | 0302-9743 |
Versão da editora: | https://link.springer.com/chapter/10.1007/978-3-319-09129-7_22 |
Arbitragem científica: | yes |
Acesso: | Acesso restrito UMinho |
Aparece nas coleções: |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Improving Branch-and-Price for Parallel Machine Scheduling .pdf Acesso restrito! | 285,02 kB | Adobe PDF | Ver/Abrir |