RUTCOR Seminar -
Christian
Almeder
Combining ant
colony optimization and exact methods for multi-level capacitated lot-sizing
problems
Abstract: We developed 2 new solution
methods for multi-level capacitated lot-sizing (MLCLS) problems. This method is a
combination of a MAX-MIN ant system and an exact LP/MIP solver. The MLCLS is a part of the material requirements
planning (MRP) process and it describes the
problem of determining a production schedule for a set of products including
the preliminary products and raw materials. That
means to calculate the amounts of intermediate items and final products that should be produced in each period. There
are several constraints and objectives that should be considered while
developing a production schedule:
(i) The given demand of the final products has to be fulfilled, no backorders or shortages are allowed, but
unused products are stored for later use;
(ii) each production decision causes resource needs for setting
up production (independent of the amount produced) and for the production of
each item;
(iii) each production step needs a deterministic amount of time
(measured in periods);
(iv) costs occur for setup, production and holding.
This kind of
problem is NP-hard and usually real world applications are too large to be solved
exactly. But small mixed-integer problems or pure
linear problem without any binary decision
variables can be solved very efficiently.
For the first approach we use the ant system to optimize the decomposition
of the problem into smaller subproblems. These subproblems containing only a few items and periods are modelled as mixed-integer
programs and solved exactly using CPLEX. Then the overall solution is derived by consolidating the partial solutions. This
hybrid approach provides superior results with respect to solution quality in
comparison to the existing approaches in the literature.
For the second approach the solution method is split into two levels. On
the first level we use a MAX-MIN ant system, for
selecting the production periods for each item. Each ant starts with the end product and determines for each period, if there should
be production or not, but the amounts to be produced and the amounts to be
stored are still open. The calculation of these decision variables is done on the second level. This second level problem is a
rather simple linear problem without any binary or integer decision variables.
We use CPLEX for solving this problem exactly. To improve the solution further,
a local search method is applied in two steps.
We tested both
methods using available test instances and compared the
results with those of other methods published in literature. It turned out that
the first approach provides superior results with respect to solution quality
in comparison to the existing approaches. But for
medium-sized instances the second approach delivers even better results.
C. Almeder. A hybrid solution approach for
multi-level capacitated lot-sizing problems. Working
paper, 2007.
R.
Pitakaso, C. Almeder, K.F. Doerner, and R.F. Hartl. Combining
population-based and exact methods for multi-level capacitated lot-sizing
problems. International Journal of Production Research,
44(22):4755–4771, 2006