An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

Vilà, Mariona; Pereira, Jordi

Keywords: branch and bound, manufacturing, assembly line balancing

Abstract

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem. The algorithm has been tested with a series of computational experiments on a well-known set of problem instances. The tests show that the proposed algorithm outperforms the best existing exact algorithm for solving SALBP-1, verifying optimality for 264 of the 269 benchmark instances.

Más información

Título de la Revista: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 229
Número: 1
Editorial: Elsevier
Fecha de publicación: 2013
Página de inicio: 106
Página final: 113
Idioma: English
DOI:

10.1016/j.ejor.2013.03.003

Notas: WOS Core Collection ISI SCOPUS