A metaheuristic approach for multiple-item economic lot sizing problem with inventory dependent demand

Abstract

In this study, we consider a multiple-item Economic Lot Sizing problem where the demands for items depend on their stock quantities. The objective is to find a production plan such that the resulting stock levels (and hence demands) maximize total profit over a finite planning horizon. The single-item version of this problem has been studied in the literature, and a polynomial time algorithm has been proposed when there are no bounds on production. It has also been proven that the single-item version is NP-hard even when there are constant (i.e, time-invariant) finite capacities on production. We extend this capacitated single-item model by considering multiple-item. Since the single-item capacitated version is NP-hard, the multiple-item capacitated version is NP-hard as well. In the context of this research, we propose a Lagrangian Relaxation method to find an initial solution to the problem, and a Tabu Search algorithm to find better solutions. The performance of the proposed metaheuristic model is compared with the performance of a standard commercial software that works on a mixed integer programming formulation of the problem. We show that our metaheuristic algorithm finds better solutions within a predetermined time limit.

Bu projede talebin stoğa bağlı olduğu çok ürünlü ekonomik öbek büyüklüğü belirleme problemini ele alıyoruz. Bu problemde amacımız stok seviyelerinin ve dolayısıyla taleplerin sınırlı bir planlama ufku boyunca toplam geliri maksimize edeceği bir üretim planı oluşturmaktır. Bu problemin tek ürünlü versiyonu literatürde yer almaktır ve üretimde kapasite kısıtı olmadığı durumlarda, polinom zamanlı çözülebilmektedir. Eğer modele kapasite dahil edilirse ve bu kapasitelerin zamanla sabit kaldığı durumlarda, tek ürünlü problemin NP-zor olduğu gösterilmiştir. Biz bu modeli ürün sayısını arttıracak şekilde genişletiyoruz. Eğer tek ürünlü model NP-zor ise çok ürünlü model de NP-zor'dur. Bu araştırma içinde, başlangıç çözümü bulmak için Lagranj gevşetme yöntemini, ve daha iyi sonuçlar bulmak için Tabu Arama algoritmasını öneriyoruz. Önerilen metasezgisel modelin performansı, problemin karma tamsayılı programlama formülasyonu üzerinde çalışan ticari yazılımın performansı ile karşılaştırılır. Metasezgisel algoritmamızın belirlenmiş bir zaman sınırı içinde daha iyi çözümler bulduğunu gösteriyoruz.