Sequence-dependent time- and cost-oriented assembly line balancing problems: a combinatorial Benders' decomposition approach

Furugi A.

ENGINEERING OPTIMIZATION, vol.54, no.1, pp.170-184, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 54 Issue: 1
  • Publication Date: 2022
  • Doi Number: 10.1080/0305215x.2021.1953003
  • Journal Name: ENGINEERING OPTIMIZATION
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Communication Abstracts, Compendex, Metadex, zbMATH, Civil Engineering Abstracts
  • Page Numbers: pp.170-184
  • Keywords: Sequence-dependent set-up time, assembly line balancing problem, Benders' decomposition, combinatorial Benders' cut, HEURISTIC METHODS, SETUP TIMES, ALGORITHM, DESIGN, TASKS, CUTS
  • Ondokuz Mayıs University Affiliated: Yes

Abstract

This article deals with the cost-oriented assembly line balancing problem with sequence-dependent set-up times. To this end, a mixed-integer linear programming (MILP) model is proposed for time- and cost-oriented assembly line balancing problems with sequence-dependent set-up times between tasks. The problem is computationally intractable; therefore, a Benders' decomposition algorithm is developed to solve it. The proposed decomposition yields a master problem that addresses the issue of assigning assembly tasks to workstations, as well as a set of subproblems that deal with sequencing tasks within each workstation owing to sequence-dependent set-up times. The algorithm is tested on a set of randomly generated test problems and numerically compared with a MILP formulation of the problem solved using a commercial optimizer. The computational results demonstrate that the proposed Benders' decomposition approach outperforms the MILP model. The contribution of this article lies in the new models proposed and the decomposition-based exact algorithm developed.