Abstract




 
   

IJE TRANSACTIONS B: Applications Vol. 27, No. 8 (August 2014) 1223-1232   

downloaded Downloaded: 179   viewed Viewed: 2171

  THREE META-HEURISTIC ALGORITHMS FOR THE SINGLE-ITEM CAPACITATED LOT-SIZING PROBLEM (RESEARCH NOTE)
 
E. Mehdizadeh and A. Fatehi Kivi
 
( Received: October 04, 2013 – Accepted: March 06, 2014 )
 
 

Abstract    This paper proposes a mixed integer programming model for single-item capacitated lot-sizing problem with setup times, safety stock, demand shortages, outsourcing and inventory capacity. Due to the complexity of problem, three meta-heuristics algorithms named simulated annealing (SA), vibration damping optimization (VDO) and harmony search (HS) have been used to solve this model. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristics and select the optimal levels of the algorithmís performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the HS against VDO and SA.

 

Keywords    Lot-sizing, Safety stocks, Simulated annealing, Vibration¨ damping optimization, Harmony search

 

چکیده    در اين مقاله يک مدل عدد صحيح مختلط براي مسئله تعيين اندازه سفارش تک محصولي با در نظر گرفتن محدوديت ظرفيت، زمان≠هاي راه≠اندازي، موجودي اطمينان، کمبود، برونسپاري و فضاي انبار ارائه مي شود. با توجه به پيچيدگي مسئله سه الگوريتم فرا≠ابتکاري شبيه سازي تبريد، بهینه سازی ميرايي ارتعاش و جستجوي هارموني براي حل مدل ارائه شده به کار گرفته مي≠شوند. همچنين از روش تاگوچي به منظور تنظيم پارامترهاي الگوريتم≠هاي فرا≠ابتکاري و انتخاب سطوح بهينه آن≠ها استفاده مي≠شود. نتايج محاسباتي از حل مثال هاي عددي که به صورت تصادفي توليد شده≠اند، نشان≠ مي≠دهند که الگوريتم جستجوي هارموني در مقايسه با ميرايي ارتعاش و تبريد شبيه≠سازي شده عملکرد بهتري دارد.

References   

 

1.        Wagner, H.M. and Whitin, T.M., "Dynamic version of the economic lot size model", Management science,  Vol. 5, No. 1, (1958), 89-96.

2.        Stadtler, H., "Improved rolling schedules for the dynamic single-level lot-sizing problem", Management Science,  Vol. 46, No. 2, (2000), 318-326.

3.        Aksen, D., Altınkemer, K. and Chand, S., "The single-item lot-sizing problem with immediate lost sales", European Journal of Operational Research,  Vol. 147, No. 3, (2003), 558-566.

4.        Akbalik, A. and Rapine, C., "Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost", Operations Research Letters,  Vol. 40, No. 5, (2012), 390-397.

5.        Akbalik, A. and Rapine, C., "The single item uncapacitated lot-sizing problem with time-dependent batch sizes: Np-hard and polynomial cases", European Journal of Operational Research,  Vol. 229, No. 2, (2013), 353-363.

6.        Montgomery, D.C., Bazaraa, M. and Keswani, A.K., "Inventory models with a mixture of backorders and lost sales", Naval Research Logistics Quarterly,  Vol. 20, No. 2, (1973), 255-263.

7.        Abad, P.L., "Optimal price and order size for a reseller under partial backordering", Computers & Operations Research,  Vol. 28, No. 1, (2001), 53-65.

8.        Karimi, B., Fatemi Ghomi, S. and Wilson, J., "The capacitated lot sizing problem: A review of models and algorithms", Omega,  Vol. 31, No. 5, (2003), 365-378.

9.        Berretta, R. and Rodrigues, L.F., "A memetic algorithm for a multistage capacitated lot-sizing problem", International Journal of Production Economics,  Vol. 87, No. 1, (2004), 67-81.

10.     Brahimi, N., Dauzere-Peres, S., Najid, N.M. and Nordli, A., "Single item lot sizing problems", European Journal of Operational Research,  Vol. 168, No. 1, (2006), 1-16.

11.     Robinson, P., Narayanan, A. and Sahin, F., "Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms", Omega,  Vol. 37, No. 1, (2009), 3-15.

12.     Akbalik, A. and Penz, B., "Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs", International Journal of Production Economics,  Vol. 119, No. 2, (2009), 367-379.

13.     Akbalik, A. and Pochet, Y., "Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs", European Journal of Operational Research,  Vol. 198, No. 2, (2009), 412-434.

14.     Wang, N., He, Z., Sun, J., Xie, H. and Shi, W., "A single-item uncapacitated lot-sizing problem with remanufacturing and outsourcing", Procedia Engineering,  Vol. 15, No., (2011), 5170-5178.

15.     Kovalyov, M.Y. and Pesch, E., "An algorithm for a single-item capacitated lot-sizing problem with linear costs and no backlogging", International Journal of Production Research,  Vol., No. ahead-of-print, (2013) 4-1.

16.     Tang, O., "Simulated annealing in lot sizing problems", International Journal of Production Economics,  Vol. 88, No. 2, (2004), 173-181.

17.     Mokhtari, G. and Kianfar, F., "Simultaneous due date assignment and lot sizing with uncertain flow times", International Journal of Engineering Transactions A Basics,  Vol. 20, No. 3, (2007), 263.

18.     Jenabi, M., Ghomi, S.F. and Torabi, S., "Finite horizon economic lot and delivery scheduling problem: Flexible flow lines with unrelated parallel machines and sequence dependent setups", International Journal of Engineering,  Vol. 21, (2008), 143-158.

19.     Piperagkas, G.S., Konstantaras, I., Skouri, K. and Parsopoulos, K.E., "Solving the stochastic dynamic lot-sizing problem through nature-inspired heuristics", Computers & Operations Research,  Vol. 39, No. 7, (2012), 1555-1565.

20.     Chu, C., Chu, F., Zhong, J. and Yang, S., "A polynomial algorithm for a lot-sizing problem with backlogging, outsourcing and limited inventory", Computers & Industrial Engineering,  Vol. 64, No. 1, (2013), 200-210.

21.     Brooks, S. and Morgan, B., "Optimization using simulated annealing", The Statistician,  Vol., No., (1995), 241-257.

22.     Mehdizadeh, E. and Tavakkoli-Moghaddam, R., "Vibration damping optimization algorithm for an identical parallel machine scheduling problem", in Proceeding of the 2nd International Conference of Iranian Operations Research Society. (2009), 20-22.

23.     Geem, Z.W., Kim, J.H. and Loganathan, G., "A new heuristic optimization algorithm: Harmony search", Simulation,  Vol. 76, No. 2, (2001), 60-68.

24.     Yadav, P., Kumar, R., Panda, S.K. and Chang, C., "An intelligent tuned harmony search algorithm for optimisation", Information Sciences,  Vol. 196, No., (2012), 47-72.

25.     Taguchi, G., Chowdhury, S. and Taguchi, S., "Robust engineering, McGraw-Hill Professional,  (2000).    





International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir