Genetic algorithm based hybrid approaches to solve the capacitated lot sizing problem with setup carryover and backordering

Abstract

Müşteri taleplerini zamanında karşılayacak ve toplam maliyeti en küçükleyecek şekilde üretimin olacağı dönemleri ve bu dönemlerde üretilecek ürün miktarlarını belirleme amacını taşıyan parti büyüklüğü problemleri, zor üretim planlama problemlerinden birisidir ve üretim ve stok sistemlerinin etkinliği üzerinde önemli bir etkiye sahiptir. Üretim planlamadaki uygulamalarından dolayı, farklı özellikleri taşıyan parti büyüklüğü problemleri uzun yıllardır çalışılmaktadır. Bu problemler arasında, Kapasite Kısıtlı Parti Büyüklüğü Problemi (KKPBP) araştırmacıların ilgisini en çok çeken problemlerden biridir. Bu doktora tezinin başlıca amacı hazırlık zamanları, hazırlık taşıma ve birikmiş sipariş özellikleri eklenen KKPBP'ni çözmek üzere özgün Genetik Algoritma (GA) tabanlı yaklaşımlar sunmaktır. Hazırlık taşımalı ve birikmiş siparişli KKPBP bu tez çalışmasında iki aşamada çözülmüştür. İlk aşamada, sadece hazırlık süreleri ve hazırlık taşımasının olduğu KKPBP (KKPBPC) için iki tane özgün melez yaklaşım önerilmiştir. Bu melez yaklaşımlar bir meta-sezgisel olan GA ve karışık tamsayı programlama (KTP) tabanlı bir sezgisel olan Sabitle-ve-Optimize Et sezgiselini iki farklı şekilde birleştirmektedir. İlk yaklaşımda, ardışık melezleme kullanılmış ve Sabitle-ve-Optimize Et sezgiseli GA'dan sonra uygulanmıştır. İkinci yaklaşım Sabitle-ve-Optimize Et sezgiselini GA'nin içerisine yerleştirerek farklı bir melezleme çeşidi içermektedir. Rastsal başlangıç popülasyonuna alternatif olmak üzere probleme özgü bilgileri ve rastsallık içeren özgün bir başlangıç popülasyonu oluşturma yöntemi önerilmiştir. Bunun yanı sıra, başlangıç popülasyonundaki probleme özgü ve rastsal kısımların oranlarını belirlemek için de bir deneysel çalışma yürütülmüştür. Ayrıca, GA'nın arama süresince olabilirliği sağlayabilmesi için çeşitli tamir operatörleri önerilmiştir. Son olarak da, önerilen yaklaşımların performansları literatürdeki mevcut problemler üzerinde test edilmiştir. İkinci aşamada, KKPBPC'ye birikmiş sipariş özelliği eklenmiş ve hazırlık taşımalı ve birikmiş siparişli KKPBP olarak adlandırılan bu problemi çözmek üzere sekiz farklı melez yaklaşım önerilmiştir. Bu melez yaklaşımlar, KKPBPC için önerilen melez yaklaşımları modifiye ederek geliştirilmiştir. İlk aşamada önerilen melez yaklaşımlardan farklı olarak, bu aşamada önerilen melez yaklaşımlarda Sabitle-ve-Optimize Et sezgiseli farklı şekillerde uygulanmış ve problemin ayrıştırılmasında çeşitli ölçütler kullanılmıştır. Farklı problem örnekleri üzerinde, önerilen yaklaşımların performansı GA ile karşılaştırılmıştır. Ayrıca, önerilen yaklaşımların performanslarının problem parametrelerindeki değişikliklere ne kadar duyarlı olduğu araştırılmıştır.

Lot sizing studies aim at determining the periods where production takes place and the quantities to be produced in order to satisfy the customer demand while minimizing the total cost. Having an important impact on the efficiency of production and inventory systems, lot sizing problem is one of the most challenging production planning problems. Due to their applications in production planning, lot sizing problems have been studied for many years with different features. Among these problems, The Capacitated Lot Sizing Problem (CLSP) has received a lot of attention from researchers. The primary aim of this Ph.D. study is to propose novel Genetic Algorithm (GA) based hybrid approaches for solving the CLSP with three extensions, i.e. setup times, setup carryover and backordering. In this thesis, the capacitated lot sizing problem with setup carryover and backordering is solved in two stages. In the first stage, two novel hybrid approaches are proposed for solving the capacitated lot sizing problem with setup times and setup carryover (CLSPC). These two hybrid approaches combine a meta-heuristic, i.e. GA, with a Mixed Integer Programming (MIP) based heuristic, i.e. the Fix-and-Optimize heuristic, in two different ways. In the first methodology, i.e. sequential hybridization, the Fix-and-Optimize heuristic is performed after the GA. The second methodology involves a different hybridization scheme where the Fix-and-Optimize heuristic is embedded into the GA. As an alternative to a random initial population, a novel initialization scheme which consists of problem specific information and randomness is proposed. Moreover, in order to sustain the feasibility during the search of GA, several repair operators are proposed. Lastly, the performances of proposed hybrid approaches are evaluated on various sets of problems from published literature. In the second stage, the CLSPC is extended to include the backorder option, called capacitated lot sizing problem with setup carryover and backordering. For solving the capacitated lot sizing problem with setup carryover and backordering, eight hybrid approaches are proposed. These approaches are modified versions of the hybrid approaches developed for solving the CLSPC. Unlike the hybrid approaches proposed in the first stage, in these hybrid approaches, the Fix-and-Optimize heuristic is implemented with different decomposition schemes. An extensive experimental analysis is carried out to compare the performances of the proposed hybrid approaches to the pure GAs using various problem instances. Moreover, the robustness of the performances of the proposed approaches under different parameter values is examined.