Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem

Abstract

The goal of this work is to develop an improved procedure for the solution of the lexicographic bottleneck variant of the assembly line balancing problem (LB-ALBP). The objective of the LB-ALBP is to minimize the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation and so on. This problem—recently introduced to the literature (Pastor, 2011)—has practical relevance to manufacturing facilities. We design, implement and fine-tune GRASP, tabu search (TS) and scatter search (SS) heuristics for the LB-ALBP and show that our procedures are able to obtain solutions of a quality that outperforms previous approaches. We rely on both semi-greedy and memory-based designs that our experiments show to be effective. Experimental results verify the advantages of embedding such designs to improve the solution existing in the literature of this complex problem. Additionally, the extensive experimentation with 48 variants of GRASP, 12 of TS and 1 of SS establishes the benefits of adding enhanced search strategies to basic procedures.

Keywords:

• assembly line balancing
• lexicographic bottleneck
• metaheuristics

Acknowledgements

This research has been partially supported by the Ministerio de Educación Cultura y Deporte of Spain (Grant Ref. PRX12/00016) and by the Ministerio de Economía y Competitividad of Spain (Grant Ref. TIN2012-35632). We would like to thank the reviewers for their valuable comments and suggestions that improved the quality of the paper.