A parallel heuristic algorithm for multi-stage lot-sizing in general production systems

This paper considers the uncapacitated multi-stage dynamic lot-sizing problem for general production structures, which are characterized by the fact that each stage of the production may have several preceding, and/or successive stages. A parallel heuristic algorithm, which attempts to optimize the total production costs over all stages simultaneously while building the production plans in a forward period-by-period manner, is proposed to tackle the problem. A levelling scheme, which assigns an index to each production stage to indicate its level in the product structure, is presented to make the proposed parallel heuristic algorithm work more efficiently. Numerical experiments reveal that the parallel heuristic algorithm proposed in this paper is efficient and effective for multi-stage lot-sizing in general production systems