Minimising cycle time in assembly lines: a novel ant colony optimisation approach

Dhananjay Thiruvady, Atabak Elmi, Asef Nazari, Jean-Guy Schneider

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

We investigate the problem of mixed model assembly line balancing with sequence dependent setup times. The problem requires that a set of operations be executed at workstations, in a cyclic fashion, and operations may have precedences between them. The aim is to minimise the maximum cycle time incurred across all workstations. The simple assembly line balancing problem (with precedence constraints) is proven to be NP-hard and is consequently computationally challenging. In addition, we consider setup times and mixed model product types, thereby further complicating the problem. In this study, we propose a novel ant colony optimisation (ACO) based heuristic, which unlike previous approaches for the problem, focuses on learning permutations of operations. These permutations are then mapped to workstations using an efficient assignment heuristic, thereby creating feasible allocations. Moreover, we develop a mixed integer programming formulation, which provides a basis for comparing the quality of solutions found by ACO. Our numerical results demonstrate the efficacy of ACO across a number of problems. We find that ACO often finds optimal solutions for small problems, and high quality solutions for medium-large problem instances where mixed integer programming is unable to find any solutions.

Original languageEnglish
Title of host publicationAI 2020: Advances in Artificial Intelligence
Subtitle of host publication33rd Australasian Joint Conference, AI 2020 Canberra, ACT, Australia, November 29–30, 2020 Proceedings
EditorsMarcus Gallagher, Nour Moustafa, Erandi Lakshika
Place of PublicationCham Switzerland
PublisherSpringer
Pages125-137
Number of pages13
ISBN (Electronic)9783030649845
ISBN (Print)9783030649838
DOIs
Publication statusPublished - 2020
Externally publishedYes
EventAustralasian Joint Conference on Artificial Intelligence 2020 - Canberra, Australia
Duration: 29 Nov 202030 Nov 2020
Conference number: 33rd
https://link.springer.com/book/10.1007/978-3-030-64984-5 (Proceedings)
http://ajcai2020.net/ (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12576
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAustralasian Joint Conference on Artificial Intelligence 2020
Abbreviated titleAI 2020
Country/TerritoryAustralia
CityCanberra
Period29/11/2030/11/20
Internet address

Keywords

  • Ant colony optimisation
  • Assembly line balancing
  • Minimise cycle times
  • Mixed integer programming
  • Sequence dependent setup times

Cite this