Yıl 2019, Cilt , Sayı 16, Sayfalar 441 - 453 2019-08-31

Capacitated Lot Sizing Problem with Stochastic Times
Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi

Duygu Taş [1]


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.

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.

  • 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
Birincil Dil tr
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Orcid: 0000-0002-3579-4600
Yazar: Duygu Taş (Sorumlu Yazar)
Kurum: MEF ÜNİVERSİTESİ
Ülke: Turkey


Tarihler

Yayımlanma Tarihi : 31 Ağustos 2019

Bibtex @araştırma makalesi { ejosat559645, journal = {Avrupa Bilim ve Teknoloji Dergisi}, issn = {}, eissn = {2148-2683}, address = {}, publisher = {Osman SAĞDIÇ}, year = {2019}, volume = {}, pages = {441 - 453}, doi = {10.31590/ejosat.559645}, title = {Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi}, key = {cite}, author = {Taş, Duygu} }
APA Taş, D . (2019). Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi. Avrupa Bilim ve Teknoloji Dergisi , (16) , 441-453 . DOI: 10.31590/ejosat.559645
MLA Taş, D . "Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi". Avrupa Bilim ve Teknoloji Dergisi (2019 ): 441-453 <https://dergipark.org.tr/tr/pub/ejosat/issue/45333/559645>
Chicago Taş, D . "Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi". Avrupa Bilim ve Teknoloji Dergisi (2019 ): 441-453
RIS TY - JOUR T1 - Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi AU - Duygu Taş Y1 - 2019 PY - 2019 N1 - doi: 10.31590/ejosat.559645 DO - 10.31590/ejosat.559645 T2 - Avrupa Bilim ve Teknoloji Dergisi JF - Journal JO - JOR SP - 441 EP - 453 VL - IS - 16 SN - -2148-2683 M3 - doi: 10.31590/ejosat.559645 UR - https://doi.org/10.31590/ejosat.559645 Y2 - 2019 ER -
EndNote %0 Avrupa Bilim ve Teknoloji Dergisi Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi %A Duygu Taş %T Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi %D 2019 %J Avrupa Bilim ve Teknoloji Dergisi %P -2148-2683 %V %N 16 %R doi: 10.31590/ejosat.559645 %U 10.31590/ejosat.559645
ISNAD Taş, Duygu . "Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi". Avrupa Bilim ve Teknoloji Dergisi / 16 (Ağustos 2019): 441-453 . https://doi.org/10.31590/ejosat.559645
AMA Taş D . Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi. Avrupa Bilim ve Teknoloji Dergisi. 2019; (16): 441-453.
Vancouver Taş D . Stokastik Süreler İçeren Kapasite Kısıtlı Parti Büyüklüğü Belirleme Problemi. Avrupa Bilim ve Teknoloji Dergisi. 2019; (16): 453-441.