Author(s): Lopes, Manuel ; Alvelos, Filipe Pereira e ; Lopes, Henrique Daniel Oliveira
Date: 2014
Persistent ID: http://hdl.handle.net/1822/53257
Origin: RepositóriUM - Universidade do Minho
Project/scholarship: info:eu-repo/grantAgreement/FCT/5876-PPCDTI/100645/PT ; info:eu-repo/grantAgreement/FCT/5876/135968/PT;
Subject(s): Parallel machine scheduling; Sequence dependent setup times; Column generation; Branch-and-price; Science & Technology
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.
This work was financed by Fundacao para a Ciencia e a Tecnologia ( Portuguese Foundation for Science and Technology) within projects " SearchCol: Metaheuristic search by column generation" ( PTDC/ EIAEIA/100645/2008) and PEst-OE/EEI/UI0319/2014.
info:eu-repo/semantics/publishedVersion
