Deakin University
Browse

File(s) under permanent embargo

Minimising Cycle Time in Assembly Lines: A Novel Ant Colony Optimisation Approach

conference contribution
posted on 2020-01-01, 00:00 authored by Dhananjay ThiruvadyDhananjay Thiruvady, Atabak ElmiAtabak Elmi, Asef NazariAsef Nazari, Jean-Guy Schneider
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.

History

Event

Joint artificial intelligence and advances in artificial intelligence. Conference (33rd : 2020 : Online from Canberra, A.C.T.)

Volume

12576

Series

Lecture Notes in Computer Science

Pagination

125 - 137

Publisher

Springer

Location

Online from Canberra, A.C.T.

Place of publication

Cham, Switzerland

Start date

2020-11-29

End date

2020-11-30

ISBN-13

9783030649845

Language

eng

Publication classification

E1 Full written paper - refereed

Editor/Contributor(s)

Marcus Gallagher, Nour Moustafa, Erandi Lakshika

Title of proceedings

AI 2020 : Proceeding of the 33rd Australasian Joint Conference on Artificial Intelligence and Advances in Artificial Intelligence 2020

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC