An exact solution algorithm for the coordinated capacitated lot-sizing problem

Abstract

In this thesis we study large-scale coordinated capacitated lot sizing problems (CCLSP). CCLSP is the most general type of lot sizing problems, where (1) multiple items are involved in the production; (2) each item requires an individual (minor) setup cost in addition to a production cost; (3) items are grouped into families that share an additional joint (major) setup cost; (4) demand for an item in a period can be satisfied by production in any period; however, early and late productions add inventory holding and backlogging costs, respectively, and (5) production capacity in each period is limited. The problem is to determine the production schedule over a time horizon consisting of a number of fixed-length production periods that minimizes the total production cost while satisfying a given demand under the capacity constraints. CCLSP is essentially a mixed integer programming problem. It is known to be NP-hard, and therefore, most of the existing solution procedures are heuristics. CCLSPs considered in the literature include a single product family. In this thesis, we extend CCLSP by considering multiple product families. The goal of this study is to develop an exact solution algorithm for a large-scale multi-family CCLSP. The algorithm is based on Benders decomposition method, and it provides an alternative to existing approaches to solve mixed integer programming problems. The decomposition is based on a natural partitioning of the decision variables into continuous (production variables) and binary (major and minor setup variables) sets. The main contribution of this thesis will be the consideration of multiple product families, their effect on solution times and an exact algorithm to solve multi-family CCLSPs. The performance of the algorithm is tested with respect to solution times by comparing the results with those obtained by solving the standard mixed integer programming problem without decomposition. Data sets used in comparison are generated to comply with the benchmark examples available in the literature.Bu tezde büyük ölçekli koordineli kapasiteli öbek büyüklüğü belirleme problemleri (KKÖBP) incelenmiştir. KKÖBP (1) birden çok ürün ailesini içeren; (2) her ürünün üretim maliyetine ek olarak küçük kurulum maliyeti gerektirdiği; (3) ürünlerin büyük kurulum maliyetini paylaştıkları ürün ailelerine gruplandıkları; (4) ürünlerin dönemlik taleplerinin herhangi bir dönemde karşılanabildiği; ancak daha önceki ya da sonraki üretim dönemleriyle karşılanan taleplerin sırasıyla envanter tutma maliyeti ve geriye dönük tedarik maliyeti eklediği; ve (5) dönemlik üretim kapasitesinin sınırlı olduğu en genel öbek büyüklüğü belirleme problemidir. Problem sabit-süreli üretim dönemlerinden oluşan bir zaman dilimi boyunca kapasite kısıtlarını aşmadan ve bilinen talepleri karşılayacak şekilde bütün üretim maliyetlerini en aza indirgeyen üretim planını belirlemektir. Esasen KKÖBP karma tamsayılı programlama problemidir. Bu problemler NP-Zor olduklarından mevcut çözüm yöntemlerinin çoğu sezgiseldir. Literatürde dikkate alınmış KKÖBP tek bir ürün ailesini kapsar. Bu tezde KKÖBP’nin kapsamı birden çok ürün ailesini dikkate alarak genişletilmiştir. Bu tezin amacı büyük ölçekli, birden çok ürün ailesini içeren KKÖBP için kesin sonuçlu bir çözüm algoritması geliştirmektir. Önerilen çözüm algoritması Benders ayrıştırma yöntemine dayanmaktadır ve karma tamsayılı programlama problemlerini çözmede kullanılan mevcut yöntemlere alternatif oluşturmaktadır. Ayrıştırma, karar değişkenlerinin doğal olarak sürekli (üretim, envanter tutma ve geriye dönük tedarik maliyetleri) ve ikili (küçük ve büyük kurulum maliyetleri) setlere paylaştırılması temeline dayanmaktadır. Bu tezin başlıca katkısı, birden çok ürün ailesini içeren KKÖBP için kesin sonuçlu bir çözüm algoritması geliştirilmesi ve ürün ailelerinin çözüm sürelerine etkilerinin araştırılmasıdır. Algoritmanın performansı çözüm sürelerinin ayrıştırılma yapılmamış karma tamsayılı programlama problemlerinin sonuçlarıyla karşılaştırılmasıyla test edilmiştir. Kullanılan veri setleri literatürde mevcut örneklere uygun olarak oluşturulmuştur.