Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi

Öz

Bu makalede üretim ve kurulum süreleri stokastik olan kapasite kısıtlı çok ürünlü dinamik parti büyüklüğü belirleme problemi ele alınmıştır. Bu problemde tüm sürelerin stokastik olduğu durum göz önünde bulundurularak hem verimli hem de güvenilir üretim planları elde edilmektedir. Ele alınan problemin amacı klasik üretim maliyetleri ve ek mesai maliyetlerinden oluşan toplam maliyeti en küçüklemektir. Klasik maliyetler, üretim, kurulum ve envanter tutmaktan kaynaklanmaktadır. Ek mesai maliyetleri ise makinenin zaman kapasitesini aşacak şekilde kullanılmasından dolayı ortaya çıkmaktadır. Öncelikle, belirli bir üretim ve kurulum planı için beklenen ek mesai süresini kesin olarak hesaplayan bir prosedür önerilmiştir. Problemi etkin bir şekilde çözmek için tabu algoritmasına dayanan bir çözüm yaklaşımı geliştirilmiştir. Bu yaklaşım üç aşamadan oluşmaktadır: Başlangıç, iyileştirme ve planlama. Algoritmanın ilk aşamasında olurlu planlar üreten bir başlangıç metodu önerilmiştir. Bulunan planlar makalede önerilen tabu arama metoduyla iyileştirilmektedir. Planlama aşamasında, yerel arama metodunun bulduğu çözümleri iyileştirmek için bir doğrusal programlama modeli geliştirilmiştir. Çözüm yöntemimizin performansı literatürde yayınlanmış alt sınırlar kullanılarak onaylanmıştır.  Ayrıca, sonuçlar tabu arama yöntemimizin makul sürelerde çok iyi çözümler elde ederek iyi performans sergilediğini göstermektedir.

Anahtar Kelimeler

• Parti büyüklüğü belirleme,Stokastik üretim zamanları,Stokastik kurulum zamanları,Ek mesai maliyetleri

Capacitated Lot Sizing Problem with Stochastic Times

Öz

In this paper, we study a capacitated multi-item dynamic lot sizing problem with stochastic production and setup times. In this problem, we consider stochastic times to obtain production plans that are both efficient and reliable. The objective of the considered problem is to minimize the total cost including regular production costs and expected overtime costs. The regular costs result from production, setup and inventory holding. The expected overtime costs are incurred due to the excess usage of the machine capacity. First, a procedure that exactly computes the expected overtime for a given production and setup plan is developed. A solution procedure based on tabu search algorithm is proposed to effectively solve the problem. This procedure includes three main phases: initialization, improving, and scheduling. In the first phase of the algorithm, an initialization method is developed to construct feasible production plans. These plans are then improved by the proposed tabu search method. In the scheduling phase, a linear programming model is developed to further improve the solutions obtained by the local search method. The performance of our solution procedure is validated by the lower bounds reported in the literature. Moreover, results show that our tabu search method performs well by obtaining very good solutions in reasonable amount of times.

Anahtar Kelimeler

• Lot sizing problem,Stochastic production times,Stochastic setup times,Overtime costs

Kaynakça

1. Aloulou, M.A., Dolgui, A. ve Kovalyov, MY. (2014) A bibliography of nondeterministic lot-sizing models, International Journal of Production Research, 52, 2293-2310. doi: 10.1080/00207543.2013.855336
2. Barbarosoğlu, G. ve Özdamar, L. (2000) Analysis of solution space-dependent performance of simulated annealing: the case of the multi-level capacitated lot sizing problem, Computers and Operations Research, 27, 895–903. doi: 10.1016/S0305-0548(99)00064-7
3. Beraldi, P., Ghiani, G., Guerriero, E. ve Grieco, A. (2006) Scenario-based planning for lot-sizing and scheduling with uncertain processing times, International Journal of Production Economics, 101, 140-149. doi: 10.1016/j.ijpe.2005.05.018
4. Birge, J.R. ve Louveaux, F. (2011) Introduction to Stochastic Programming, Springer Series in Operations Research and Financial Engineering.
5. Bitran, G.R. ve Yanesse, H.H. (1982) Computational complexity of the capacitated lot size problem, Management Science, 28, 1174–1186. doi: 10.1287/mnsc.28.10.1174
6. Bookbinder, J.H. ve Tan, J.Y. (1988) Strategies for the probabilistic lot-sizing problem with service-level constraints, Management Science, 34, 1096-1108. doi: 10.1287/mnsc.34.9.1096
7. Brahimi, N., Dauzere-Peres, S., Najid ve N.M., Nordli, A. (2006) Single item lot sizing problems, European Journal of Operational Research, 168, 1–16. doi: 10.1016/j.ejor.2004.01.054
8. Brahimi, N., Absi, N., Dauzère-Pérès, S. ve Nordli, A. (2017) Single-item dynamic lot-sizing problems: An updated survey, European Journal of Operational Research, 263, 838-863. doi: 10.1016/j.ejor.2017.05.008

9. Brandimarte, P. (2006) Multi-item capacitated lot-sizing with demand uncertainty, International Journal of Production Research, 44, 2997-3022. doi: 10.1080/00207540500435116
10. Buschkühl, L., Sahling, F., Helber, S. ve Tempelmeier, H. (2010) Dynamic capacitated lot-sizing problems: a classification and review of solution approaches, OR Spectrum, 32, 231–261. doi: 10.1007/s00291-008-0150-7
11. Dellaert, N.P. ve Melo, M.T. (1998) Make-to-order policies for a stochastic lot sizing problem using overtime, International Journal of Production Economics, 56-57, 79-97. doi: 10.1016/S0925-5273(98)00053-X
12. Dellaert, N, de Kok, A.G. ve Wei, W. (2000) Push and pull strategies in multistage assembly systems, Statistica Neerlandica, 54, 175-189. doi: 10.1111/1467-9574.00135
13. Denizel, M. ve Süral, H. (2006) On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times, Journal of the Operational Research Society, 57, 389-399. doi: 10.1057/palgrave.jors.2601996
14. Diaby, M., Bahl, H.C., Karwan, M.H. ve Zionts, S. (1992a) Capacitated lot-sizing and scheduling by lagrangean relaxation, European Journal of Operational Research 59, 444-458. doi: 10.1016/0377-2217(92)90201-J
15. Diaby, M., Bahl, H.C., Karwan, M.H. ve Zionts, S. (1992b) A lagrangean relaxation approach for very-large-scale capacitated lot-sizing, Management Science, 38, 1329-1340. doi: 10.1287/mnsc.38.9.1329
16. Glover, F. (1989) Tabu search – Part I, ORSA Journal on Computing, 1, 190-206. doi: 10.1287/ijoc.1.3.190
17. Glover, F. (1990) Tabu search – Part II, ORSA Journal on Computing, 2, 4-32. doi: 10.1287/ijoc.2.1.4
18. Glover, F. ve Laguna, M. (1997) Tabu search. Kluwer Academic Publishers, Boston.
19. Glover F, Kochenberger GA. Handbook of metaheuristics. Kluwer Academic Publishers, Boston, 2003.
20. Gopalakrishnan, M., Ding, K., Bourjolly, J.M. ve Mohan, S. (2001) A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover, Management Science, 47(6), 851-863. doi: 10.1287/mnsc.47.6.851.9813
21. Hindi, K.S. (1995) Solving the single-item, capacitated dynamic lot sizing problem with startup and reservation costs by tabu search, Computers & Industrial Engineering, 28, 701-707. doi: 10.1016/0360-8352(95)00027-X
22. Hindi, K.S. (1996) Solving the CLSP by a tabu search heuristic, Journal of the Operational Research Society, 47, 151-161. doi: 10.1057/jors.1996.13
23. Hindi, K.S., Fleszar, K. ve Charalambous, C. (2003) An effective heuristic for the CLSP with set-up times, Journal of the Operational Research Society, 54, 490-498. doi: 10.1057/palgrave.jors.2601525
24. Hung, Y.F., Chen, C.P., Shih C.C. ve Hung M.H. (2003) Using tabu search with ranking candidate list to solve production planning problems with setups, Computers & Industrial Engineering, 45, 615-634. doi: 10.1016/j.cie.2003.09.006
25. IBM, ILOG CPLEX Optimizer 12.5, http://www-01.ibm.com/ software/integration/optimization/cplex-optimizer, 2019.
26. Jans, R. ve Degraeve, Z. (2004) Improved lower bounds for the capacitated lot sizing problem, Operations Research Letters, 32, 185-195. doi: 10.1016/j.orl.2003.06.001
27. Jans, R. ve Degraeve, Z. (2007) Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches, European Journal of Operational Research, 177, 1855–1875. doi: 10.1016/j.ejor.2005.12.008
28. Jans, R. ve Degraeve, Z. (2008) Modeling industrial lot sizing problems: a review, International Journal of Production Research, 46, 1619–1643. doi: 10.1080/00207540600902262
29. Jeunet, J. ve Jonard, N. (2000) Measuring the performance of lot-sizing techniques in uncertain environments, International Journal of Production Economics, 64, 197-208. doi: 10.1016/S0925-5273(99)00058-4
30. Kimms, A. (1996) Competitive methods for multi-level lot sizing and scheduling: tabu search and randomized regrets, International Journal of Production Research, 34, 2279-2298. doi: 10.1080/00207549608905025
31. Koca, E., Yaman, H., Aktürk, M.S. (2015) Stochastic lot sizing problem with controllable processing times, Omega, 53, 1-10. doi: 10.1016/j.omega.2014.11.003
32. Krarup, J. ve Bilde, O. (1977) Plant location, set covering and economic lot sizes: an O(mn) algorithm for structured problems. Editors: Collatz L, Meinardus G, Wetterling W. Optimierung bei Graphentheoretischen und Ganzzahligen Probleme, Numerische Methoden bei Optimierungsverfahren, Band 3, 155-179, Birkhauser Verlag, Basel.
33. Kuhn, H. (1997) A dynamic lot sizing model with exponential machine breakdowns, European Journal of Operational Research, 100, 514-536. doi: 10.1016/S0377-2217(96)00136-1
34. Kuik, R., Salomon, M., Van Wassenhove, L.N. ve Maes, J. (1993) Linear programming, simulated annealing and tabu search heuristics for lotsizing in bottleneck assembly systems, IIE Transactions, 25, 62-72. doi: 10.1080/07408179308964266
35. Michalewicz, Z. ve Fogel, D.B. (2002) How to solve it: modern heuristics. Springer-Verlag, Berlin.
36. Nourelfath, M. (2011) Service level robustness in stochastic production planning under random machine breakdowns, European Journal of Operational Research, 212, 81-88. doi: 10.1016/j.ejor.2011.01.032
37. Özdamar, L. ve Barbarosoğlu, G. (1999) Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem, Journal of the Operational Research Society, 50, 810–825.
38. Özdamar, L. ve Birbil, Ş.İ. (1998) Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions, European Journal of Operational Research, 110, 525–547. doi: 10.1016/S0377-2217(97)00269-5
39. Pochet, Y. ve Wolsey, L.A. (2006) Production planning by mixed integer programming. Springer.
40. Ribeiro, C. ve Hansen, P. (2001) Essays and surveys in metaheuristics. Kluwer Academic Publishers, Dordrecht, The Netherlands.
41. Süral, H., Denizel, M., Van Wassenhove ve L.N. (2009) Lagrangean relaxation based heuristics for lot sizing with setup times, European Journal of Operational Research, 194, 51-63. doi: 10.1016/j.ejor.2007.11.052
42. Taş, D., Dellaert, N., Van Woensel, T. ve de Kok, T. (2013) Vehicle routing problem with stochastic travel times including soft time windows and service costs, Computers & Operations Research, 40, 214-224. doi: 10.1016/j.cor.2012.06.008
43. Taş, D., Gendreau, M., Jabali, O. ve Jans, R. (2019) A capacitated lot sizing problem with stochastic setup times and overtime, European Journal of Operational Research, 273(1), 146–159. doi: 10.1016/j.ejor.2018.07.032
44. Tempelmeier, H. (2013) Stochastic lot sizing problems. Editors: Smith JM, Tan B. Handbook of stochastic models and analysis of manufacturing system operations, International Series in Operations Research & Management Science, Volume 192, 313–344, New York, Springer.
45. Trigeiro, W., Thomas, L. ve McClain, J. (1989) Capacitated lot sizing with setup times, Management Science, 35, 353–366. doi: 10.1287/mnsc.35.3.353