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

Mariona Vilà, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

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.

Original languageEnglish
Pages (from-to)106-113
Number of pages8
JournalEuropean Journal of Operational Research
Volume229
Issue number1
DOIs
StatePublished - 16 Aug 2013
Externally publishedYes

Keywords

  • Assembly line balancing
  • Branch and bound
  • Manufacturing

Fingerprint

Dive into the research topics of 'An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time'. Together they form a unique fingerprint.

Cite this