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

摘要

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.