COMPARISON AMONG HEURISTIC METHODS TO PROVIDE AN INITIAL SOLUTION FOR A BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE MAKESPAN IN A FLOW SHOP WITH BLOCKING ENVIRONMENT

Felipe Borreiro Sanches¹; Mauricio Iwama Takano¹; Marcelo Seido Nagano²

¹ Universidade Tecnológica Federal do Paraná câmpus Cornélio Procópio; ² Universidade de São Paulo câmpus São Carlos

doi:10.20906/CPS/COB-2015-1297

Resumo

This paper has the objective to compare the use of different methods to obtain an initial solution for the Branch-and-Bound algorithm with the objective of minimizing the makespan in a flow shop with zero buffer environment. As the problem is known to be NP-Hard, the Branch-and-Bound algorithm may take great computational time to find the best solution. The use of an initial solution may reduce the computational time, by providing an initial upper bound. The efficiency of the use of an initial solution for the Branch-and-Bound algorithm is measured by comparing the traditional algorithm (without an initial solution) and four other algorithms which use different initial solutions provided by four different I phase constructive heuristics (according to Framinan et al., 2004 classification) each. The heuristic methods used to provide the initial solutions are: MM (Ronconi,2004); PF (McCormick et al., 1989); PW and wPF (Pan and Wang, 2012). The Branch-and-Bound algorithm used as well as the lower bound were proposed by Ronconi (2005). The five methods were tested using a 540 problems database. Results show that the use of an initial solution do reduce considerable computational time.

Palavras-chave: Branch-and-Bound; heuristics; flow shop; block; makespan; scheduling