Rule-based modeling and constraint programming based solution of the assembly line balancing problem

Topaloglu Ş. A., SALUM L., Supciller A. A.

EXPERT SYSTEMS WITH APPLICATIONS, vol.39, no.3, pp.3484-3493, 2012 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 39 Issue: 3
  • Publication Date: 2012
  • Doi Number: 10.1016/j.eswa.2011.09.038
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.3484-3493
  • Keywords: Assembly line balancing, Precedence graphs, Rule-based modeling, Constraint programming, ANT COLONY OPTIMIZATION, GENETIC ALGORITHM, SATISFACTION PROBLEMS, FORMULATIONS, SEARCH, GRAPH, TIME
  • Dokuz Eylül University Affiliated: Yes


The assembly line balancing problem employs traditional precedence graphs to model precedence relations among assembly tasks. Yet they cannot address alternative ways of assembling a product. That is, they only model conjunctions, not disjunctions. Moreover, some additional constraints need also to be considered, but these constraints cannot be modeled effectively through precedence graphs, e.g., constraints indicating certain tasks cannot be assigned into the same station. To address these issues, this paper proposes to model assembly constraints through the well known If-then rules, and to solve the rule-based model through constraint programming (CP), as CP naturally models logical assertions. The paper also shows how to map a rule-based model to a CP or an integer programming (IP) model. Finally, a computational experiment is carried out to analyze the performances of CP and IP models with respect to modeling capability, solution quality and time. The results reveal that CP is more effective and efficient than IP. (C) 2011 Elsevier Ltd. All rights reserved.