Solving the capacitated dynamic lot sizing problem

Abstract

ÖZET Sığalı Devinimsel Parti Büyüklüğü Saptama problemi (CDLS), belli bir planlama dönemi boyunca bilinen fakat değişen talepleri karşılayabilmek amacıyla, üretim üzerindeki sığaları da göz önüne alarak, en düşük maliyetli üretim planının bulunmasını içerir. Bu problemi çözebilmek için bu çalışma sırasında dört adet sezgisel çözüm yöntemi geliştirilmiştir. Artmayan hazırlık maliyetleri ve azalmayan sığa değerlerini içeren durumlar için Kesin çözüm bulan ve süre karmaşası 0(T2) olan bir algoritma önerilmiştir. Aynı durum için kesin olan ve süre karmaşası 0(7^) olan bir başka algoritma daha geliştirilmiştir. Her zaman düzeyinde bir çok düğümün elimine edileceğinin garanti edildiği bir dallandırıp-smırlandırma yöntemi geliştirilmiş olup, sığa sınırlarının geniş olduğu durumlarda, yaratılan düğüm sayısının T2 ile sınırlı olduğu gösterilmiştir. 0(T2) algoritması ve dallandırıp-smırlandırma yöntemi birleştirilerek bir başka algoritma daha türetilmiştir. Yaratılan algoritmaların değişik durumlardaki hızları ve davranışlarının ölçülmesi için testler uygulanmış olup, bu alandaki önerilen algoritmalar ile karşılaştırılmaları yapılmıştır.

iv ABSTRACT The Capacitated Dynamic Lot Sizing Problem which in general is known to be NP-hard, can be described as the determination of an optimal production plan at minimum cost that satisfies Known but varying demands over a finite planning horizon in the presence of capacity bounds on production facilities. Four algorithms are developed for solving the Capacitated Dynamic Lot Sizing Problem. A heuristic algorithm with time complexity of 0(T2) is suggested which is exact for instances with nonincreasing set-up costs and nondecreasing capacities. Another heuristic with time complexity of OfT*) is also provided and it is also exact for the same instances with 0(T2) algorithm. A branch and bound algorithm is developed in which, at every level, many nodes are guaranteed to be eliminated. It is shown that if the capacity bounds are large enough, then the number of nodes generated is bounded by T2. Using the branch and bound and the 0(T2) algorithms, another algorithm is developed. Computational tests are performed to test the behaviour of the algorithms under different conditions and to compare the speed and accuracy with algorithms that are suggested in the literature.