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

Year 2019, Issue: 16, 441 - 453, 31.08.2019

Duygu Taş

https://doi.org/10.31590/ejosat.559645

Abstract

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.

Keywords

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

Capacitated Lot Sizing Problem with Stochastic Times

Abstract

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.

Keywords

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

References

• 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
• 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
• 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
• Birge, J.R. ve Louveaux, F. (2011) Introduction to Stochastic Programming, Springer Series in Operations Research and Financial Engineering.
• 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
• 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
• 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
• 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
• Brandimarte, P. (2006) Multi-item capacitated lot-sizing with demand uncertainty, International Journal of Production Research, 44, 2997-3022. doi: 10.1080/00207540500435116
• 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
• 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
• 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
• 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
• 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
• 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
• Glover, F. (1989) Tabu search – Part I, ORSA Journal on Computing, 1, 190-206. doi: 10.1287/ijoc.1.3.190
• Glover, F. (1990) Tabu search – Part II, ORSA Journal on Computing, 2, 4-32. doi: 10.1287/ijoc.2.1.4
• Glover, F. ve Laguna, M. (1997) Tabu search. Kluwer Academic Publishers, Boston.
• Glover F, Kochenberger GA. Handbook of metaheuristics. Kluwer Academic Publishers, Boston, 2003.
• 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
• 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
• 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
• 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
• 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
• IBM, ILOG CPLEX Optimizer 12.5, http://www-01.ibm.com/ software/integration/optimization/cplex-optimizer, 2019.
• 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
• 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
• 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
• 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
• 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
• 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
• 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.
• 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
• 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
• Michalewicz, Z. ve Fogel, D.B. (2002) How to solve it: modern heuristics. Springer-Verlag, Berlin.
• 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
• Ö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.
• Ö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
• Pochet, Y. ve Wolsey, L.A. (2006) Production planning by mixed integer programming. Springer.
• Ribeiro, C. ve Hansen, P. (2001) Essays and surveys in metaheuristics. Kluwer Academic Publishers, Dordrecht, The Netherlands.
• 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
• 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
• 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
• 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.
• 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