Large neighbourhood search based on mixed integer programming and ant colony optimisation for car sequencing

Dhananjay Thiruvady, Kerri Morgan, Amiza Amir, Andreas T. Ernst

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requiring the same options need to be distributed far enough apart. The desired separation is not always feasible, leading to an optimisation problem that minimises the violation of the ideal separation requirements. In order to solve the problem, we use a large neighbourhood search (LNS) based on mixed integer programming (MIP). The search is implemented as a sliding window, by selecting overlapping subsequences of manageable sizes, which can be solved efficiently. Our experiments show that, with LNS, substantial improvements in solution quality can be found.

Original languageEnglish
Pages (from-to)2696-2711
Number of pages16
JournalInternational Journal of Production Research
Volume58
Issue number9
DOIs
Publication statusPublished - 2 May 2020

Keywords

  • ant colony optimisation
  • car sequencing
  • large neighbourhood search
  • mixed integer programming
  • scheduling

Cite this