A MAX-MIN ant system for unconstrained multi-level lot-sizing problems

Rapeepan Pitakaso, Christian Almeder, Karl Dörner, Richard Hartl

Publications: Contribution to journalArticlePeer Reviewed

Abstract

In this paper, we present an ant-based algorithm for solving unconstrained multi-level lot-sizing problems called ant system for multi-level lot-sizing algorithm (ASMLLS). We apply a hybrid approach where we use ant colony optimization in order to find a good lot-sizing sequence, i.e. a sequence of the different items in the product structure in which we apply a modified Wagner-Whitin algorithm for each item separately. Based on the setup costs each ant generates a sequence of items. Afterwards a simple single-stage lot-sizing rule is applied with modified setup costs. This modification of the setup costs depends on the position of the item in the lot-sizing sequence, on the items which have been lot-sized before, and on two further parameters, which are tried to be improved by a systematic search. For small-sized problems ASMLLS is among the best algorithms, but for most medium- and large-sized problems it outperforms all other approaches regarding solution quality as well as computational time. © 2005 Elsevier Ltd. All rights reserved.
Original languageEnglish
Pages (from-to)2533-2552
Number of pages20
JournalComputers & Operations Research
Volume34
Issue number9
DOIs
Publication statusPublished - 2007

Austrian Fields of Science 2012

  • 5020 Economics

Cite this