Variable neighborhood search based algorithms for the parallel machine capacitated lotsizing and scheduling problem
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
Bu çalışmada, farklı yetkinliklere sahip paralel makinelerde sıra bağımlı ayar zamanlı ve maliyetli, kapasiteli parti büyüklüğü belirleme ve çizelgeleme problemi ele alınmıştır. Çalışmanın amacı, belirlenen zaman süresi için talebi eksiksiz karşılayacak ve toplam üretim, ayar ve stok maliyetini en aza indirecek bir üretim planı oluşturmaktır. Problem NP-zor olduğu için, Değişken Komşuluk Arama (DKA) yöntemi ve onun türevleri olan Değişken Komşu İniş (DKİ) ve İndirgenmiş Değişken Komşuluk Arama (İDKA) yöntemleri kullanılarak her bir yöntemin performansları analiz edilmiştir. İlk başta, her periyodun talebini karşılamayı garanti eden, probleme özgü bir başlangıç çözüm yöntemi geliştirilmiştir. Komşuluk çözümlerini oluşturmak için, 3 farklı hareket tanımlanmıştır, bunlar sırasıyla, yerleştirme, ikili yer değiştirme ve kısmi yerleştirmedir. Her bir çözüm yaklaşımının etkinliğini ve verimliliğini değerlendirmek amacıyla, literatürdeki mevcut problemler kullanılarak analizler yapılmıştır. Analizlerin sonucunda, Değişken Komşuluk Arama (DKA) yönteminin küçük ölçekli problemlerde iyi sonuçlar verdiği görülmüştür. Değişken Komşu İniş (DKİ) metodunun literatürdeki mevcut çözüm teknikleriyle benzer sonuçlar verdiği saptanırken, İndirgenmiş Değişken Komşuluk Arama (İDKA) yönteminin ise yüksek çözüm sürelerine rağmen tüm test edilen problemlerde literatürdeki sonuçların hepsinden iyi sonuçlar bulduğu gözlemlenmiştir. In this paper, the capacitated lot-sizing and scheduling problem on parallel machines with eligibility constraints and sequence-dependent setup times and costs is addressed. The aim of this study is to find a production plan that minimizes production, setup and inventory holding costs while meeting the demands of products for each period without delay for a given planning horizon. Since this problem is NP-hard, various types of variable neighborhood search (VNS), variable neighborhood descent (VND) and reduced variable neighborhood search (RVNS) algorithms are used in order to analyse their performances on this problem. At first, a problem specific initial solution method is presented, which satisfies the demand of each period. In order to generate neighborhood solutions, three types of moves are defined which are respectively, insert move, swap move, and fractional insert move.. To evaluate the effectiveness and efficiency of each solution approach, a computational study is made using the benchmark problem instances which are taken from the literature. The results indicate that VNS algorithm performs well on small sized instances. The performance of VND approach is somehow similar when it is compared with the existing solution techniques in literature, and the solution times are relatively shorter. Additionally, although relatively high computation times, all instances are improved with RVNS algorithm.
Collections