Combinatorial Benders cuts for assembly line balancing problems with setups

Sener Akpinar, Atabak Elmi, Tolga Bektaş

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems also suggest a natural decomposition of the problem. This paper adopts such an approach and describes an exact algorithm based on Benders decomposition to solve both simple and mixed-model assembly line balancing problems with setups. The algorithm is tested on a set of benchmark instances and numerically compared against a mixed-integer linear programming formulation of the problem solved using a commercial optimizer.

Original languageEnglish
Pages (from-to)527-537
Number of pages11
JournalEuropean Journal of Operational Research
Volume259
Issue number2
DOIs
Publication statusPublished - 1 Jun 2017
Externally publishedYes

Keywords

  • Benders decomposition
  • Combinatorial Benders cuts
  • Combinatorial optimization
  • Sequence-dependent setup times
  • Type-I assembly line balancing problem

Cite this

@article{af58cbe9f98241379536bc26302bd0c7,
title = "Combinatorial Benders cuts for assembly line balancing problems with setups",
abstract = "The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems also suggest a natural decomposition of the problem. This paper adopts such an approach and describes an exact algorithm based on Benders decomposition to solve both simple and mixed-model assembly line balancing problems with setups. The algorithm is tested on a set of benchmark instances and numerically compared against a mixed-integer linear programming formulation of the problem solved using a commercial optimizer.",
keywords = "Benders decomposition, Combinatorial Benders cuts, Combinatorial optimization, Sequence-dependent setup times, Type-I assembly line balancing problem",
author = "Sener Akpinar and Atabak Elmi and Tolga Bektaş",
year = "2017",
month = "6",
day = "1",
doi = "10.1016/j.ejor.2016.11.001",
language = "English",
volume = "259",
pages = "527--537",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

Combinatorial Benders cuts for assembly line balancing problems with setups. / Akpinar, Sener; Elmi, Atabak; Bektaş, Tolga.

In: European Journal of Operational Research, Vol. 259, No. 2, 01.06.2017, p. 527-537.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Combinatorial Benders cuts for assembly line balancing problems with setups

AU - Akpinar, Sener

AU - Elmi, Atabak

AU - Bektaş, Tolga

PY - 2017/6/1

Y1 - 2017/6/1

N2 - The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems also suggest a natural decomposition of the problem. This paper adopts such an approach and describes an exact algorithm based on Benders decomposition to solve both simple and mixed-model assembly line balancing problems with setups. The algorithm is tested on a set of benchmark instances and numerically compared against a mixed-integer linear programming formulation of the problem solved using a commercial optimizer.

AB - The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems also suggest a natural decomposition of the problem. This paper adopts such an approach and describes an exact algorithm based on Benders decomposition to solve both simple and mixed-model assembly line balancing problems with setups. The algorithm is tested on a set of benchmark instances and numerically compared against a mixed-integer linear programming formulation of the problem solved using a commercial optimizer.

KW - Benders decomposition

KW - Combinatorial Benders cuts

KW - Combinatorial optimization

KW - Sequence-dependent setup times

KW - Type-I assembly line balancing problem

UR - http://www.scopus.com/inward/record.url?scp=85008168841&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2016.11.001

DO - 10.1016/j.ejor.2016.11.001

M3 - Article

VL - 259

SP - 527

EP - 537

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -