A heuristic procedure for solving the Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP)

Abstract

The Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP) is a new assembly-line balancing problem recently defined in the literature. The LB-ALBP hierarchically minimises the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation, followed by the workload of the third most heavily loaded workstation, and so on. The original study presents two mixed-integer linear programming (MILP) models designed to solve the LB-ALBP optimally, together with three heuristic procedures based on these MILPs. In this paper, we propose and test new algorithms that combine a heuristic procedure for obtaining an initial solution and several local search procedures, which are an improvement upon the heuristic procedures published to date.

Keywords:

• assembly-line balancing
• production
• sequencing
• heuristic

Acknowledgements

Supported by the Spanish Ministry of Education and Science, project DPI2007-61905, co-financed by FEDER.