A hybrid ant colony optimization algorithm to optimize capacitated lot-sizing problem

Document Type : Research Paper


Industrial Engineering Department, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran


The economical determination of lot size with capacity constraints is a frequently complex, problem in the real world. In this paper, a multi-level problem of lotsizing with capacity constraints in a finite planning horizon is investigated. A combination of ant colony algorithm and a heuristic method called shifting technique is proposed for solving the problem. The parameters, including the costs, demands and capacity of resources vary during the time. The goal is to determine the economical lot size value of each product in each period, so that besides fulfilling all the needs of customers, the total cost of the system is minimized. To evaluate the performance of the proposed algorithm, an example is used and the results are compared other algorithms such as: Tabu search (TS), simulated annealing (SA), and genetic algorithm (GA). The results are also compared with the exact solution obtained from the Lagrangian relaxation method. The computational results indicate that the efficiency of the proposed method in comparison to other meta-heuristics.


Absi N., Detienne B., Dauzere S. (2013), Heuristics for the multi-item capacitated
lot-sizing problem with lost sales; Computers & Operations Research 40; 264-272.
Absi N., Kedad-Sidhoum S. (2008), The multi-item capacitated lot-sizing problem
with setup times and shortage costs; European Journal of Operational Research
185; 1351-1374.
Afentakis P., Gavish B., Karmarkar V. (1984), Optimal solutions to the lot-sizing
problem in multi-stage assembly systems; Management Science 30; 222-239.
Afentakis P., Gavish B. (1986), Optimal lot-sizing algorithms for complex product
structures; Operations Research 34; 237-249.
Aggarwal A., Park J.K. (1993), Improved algorithms for economic lot size
problems; Operations Research, 41; 549-571.
Aksen D., Altınkemer K., Chand S. (2003), The single-item lot-sizing problem with
immediate lost sales; European Journal of Operational Research 147(3); 558-566.
Almeder C. (2010), A hybrid optimization approach for multi-level capacitated lotsizing
problems; European Journal of Operational Research 200; 599-606.
Barang I., VanRoy T.J., Wolsey L.A. (1984), Strong formulations for multi item
capacitated lot-sizing; Management Science 30; 1255-1261.
Belvaux G., Wolsey L.A. (2000), A specialized branch-and-cut system for lotsizing
problems; Management Science 46 (5); 724-738.
Billington P.J., McClain J.O., Thomas L.J. (1986), Heuristic for multi-level lotsizing
with a bottleneck; Management Science 32; 989-1006.
Brahimi N., Dauzere S. (2006), Review Single item lot-sizing problems; European
Journal of Operational Research 168; 1-16.
Choi S., Enns S.T. (2004), Multi-product capacity-constrained lot sizing with
economic objectives; International Journal of Production Economics 91(1); 47-62.
Dellaert N., Jeunet J., Jonard N. (2000), A genetic algorithm to solve the general
multi-level lot-sizing problem with time varying costs; International Journal of
Production Economics 68; 241-257.
Friedman M., Winter J.L. (1978), A Study of the infinite horizon ‘solution’ of
inventory lot size models with a linear demand function; Computers & Operations Research 5(2); 157-160.
Gallego G., Shaw D.X. (1997), Complexity of the ELSP with general cyclic
schedules; IEEE Transactions 29; 109–13.
Ganas I., Papachristos S. (2005), The single-product lot-sizing problem with
constant parameters and backlogging; Exact results, a new solution, and all
parameter stability regions; Operations Research 53 (1); 170–176.
Guan Y., Ahmed S., Miller AJ, Nemhauser G.L. (2006), On formulations of the
stochastic uncapacitated lot-sizing problem; Operations Research Letters 34(3);
Gupta Y.P., Keung Y. (1990), A review of multi-stage lot-sizing models;
International Journal of Operations and Production Management 10; 57-73.
Gupta D., Magnusson T. (2005), The capacitated lot-sizing and scheduling problem
with sequence-dependent setup costs and setup times; Computers & Operations
Research 32 (4); 727-747.
Huang K., Küçükyavuz S. (2008), On stochastic lot-sizing problems with random
lead times; Operations Research Letters 36(3); 303-308
Jans R., Degraeve Z. (2004), Improved lower bounds for the capacitated lot-sizing
problem with setup times; Operations Research Letters 32; 185-195.
Jans R., Degraeve Z. (2007), Meta-heuristics for dynamic lot-sizing; A review and
comparison of solution approaches; European Journal of Operational Research
177; 1855-1875.
Karimi B., Fatemi Ghomi S.M.T., Wilson JM. (2003), The capacitated lot-sizing
problem; a review of models and algorithms; Omega 31; 365-378.
Kovacs A., Brown K.N., Tarim S.A. (2009), An efficient MIP model for the
capacitated lot-sizing and scheduling problem with sequence-dependent setups;
International Journal of Production Economics 118(1); 282-291.
Kuik R., Salomon M., Van Wassenhove L.N., Maes J. (1993), Linear programming,
simulated annealing and tabu search heuristic for lot-sizing in bottleneck Assembly
systems; IIE Transactions 25; 62-72.
Lambrecht M.R., VanderEchen J., VanderVeken H. (1981), Review of optimal and
heuristic models for a class of facilities in series dynamic lot size problems, In
Multi-Level Production-Inventory Control Systems; Theory and Practice, North-
Holland, Amsterdam, 69-94.
Maes J., McClain J., VanWassenhove N .( 1991), Multilevel capacitated lot-sizing
complexity and LP-based heuristics; European Journal of Operational Research 53
(2); 131-148.
MATLAB Version (R2010a). The MathWorks, Inc. Protected by U.S.
and international patents, 2010.
Ozdamar L., Barbarosoglu G. (2000), An integrated Lagrangian relaxationsimulated
annealing approach to the multilevel multi-item capacitated lot-sizing
problem; International Journal of Production Economics 68 (3); 319-331.
Pitakaso R., Almeder C., Doerner K., Hartl R. (2006), Combining population-based
and exact methods for multi-level capacitated lot-sizing problems; International
Journal of Production Research 44 (22); 4755-4771.
Pitakaso R., Almederb C., Doernerb K.F., Hartlb R.F. (2007), A MAX-MIN ant
system for unconstrained multi-level lot-sizing problems; Computers & Operations
Research 34; 2533-2552.
Rezaei J., Davoodi M. (2011), Multi-objective models for lot-sizing with supplier
selection, International Journal of Production Economics 130(1); 77-86.
Robinson P., Narayanan A., Sahin F. (2009), Coordinated deterministic dynamic
demand lot-sizing problem; A review of models and algorithms; Omega 37(1); 3-
Senyigit E., Düğenci M., Aydin M.E., Zeydan M. (2013), Heuristic-based neural
networks for stochastic dynamic lot sizing problem; Applied Soft Computing 13( 3);
Shim I.S., Kim H.C., Doh H.H., Lee D.H. (2011), A two-stage heuristic for single
machine capacitated lot-sizing and scheduling with sequence-dependent setup costs;
Computers & Industrial Engineering 61(4); 920-929.
Tempelmeier H., Derstroff M. (1996), A Lagrangean-based heuristic for dynamic
multilevel multi item constrained lotsizing with setup times; Management Science
42 (5); 738-757.
Teng J.T., Chern M.S., Yang H.L., Wang Y.J. (1999), Deterministic lot-size
inventory models with shortages and deterioration for fluctuating demand;
Operations Research Letters 24; 65-72.
Toledo C.F.M., Ribeirode Oliveira R.R.R., Franca P.M. (2013), A hybrid multipopulation
genetic algorithm applied to solve the multi-level capacitated lot-sizing
problem with backlogging; Computers & Operations Research 40; 910-919.
Ustun O., Demırtas E.A. (2008), An integrated multi-objective decision-making
process for multi-period lot-sizing with supplier selection; Omega, 36(4); 509-521.
Wolsey L.A. (1995), Progress with single-item lot-sizing; European Journal of
Operational Research 86; 395-401.
Wua T., Shi L., Geunes J., Akartunalı K. (2011), An optimization framework for
solving capacitated multi-level lot-sizing problems with backlogging; European Journal of Operational Research 214; 428-441.
Xiao Y., Kaku I., Zhao Q., Zhang R. (2011), A reduced variable neighborhood
search algorithm for uncapacitated multilevel lot-sizing problems; European
Journal of Operational Research 214; 223-231.
Xie J., Dong J. (2002), Heuristic Genetic Algorithms for General Capacitated Lot-
Sizing; An International journal computers & mathematics 44; 263-276.
Zhou Y.W., Lau H.S., Yang S.L. (2004), A finite horizon lot-sizing problem with
time-varying deterministic demand and waiting-time-dependent partial
backlogging; International Journal of Production Economics 91(2); 109-119.