The Capacitaded lot sizing problem

Abstract

ÖZET Kapasite kısıtlı parti büyüklüğü belirleme ve yükleme problemi; ürün ailelerinin/son ürünlerin parti büyüklüğünün belirlenmesi ve bu partilerin, belirli bir planlama zamanı aralığında dinamik talebi karşılayacak şekilde, paralel makineler üzerine yüklenmesi işlemidir. Kapasite kısıtlı parti büyüklüğü belirleme ve yükleme probleminde karşılaşılan kapasite kısıtları, farklı sınıflardan oluşan paralel makineler yoluyla probleme uygulanmaktadır. Herhangi bir periyodda parti büyüklüğünün pozitif bir değer alması, o partinin normal çalışma ve vardiya çalışma zamanı toplam kapasitesini aşmadan bir makineye yüklenmesi anlamına gelmektedir. Her ürün ailesinin, her bir makine üzerindeki üretim/işlem zamanlan farklı olabilmektedir. Ayrıca, teknolojik olarak bir ürün ailesi, var olan makinelerin bir alt kümesini oluşturan makinelerde üretilebilmektedir. Bir ürün ailesi, bir makineye yüklendiği andan itibaren hazırlık zamanı nedeniyle kapasiteden yemektedir. Amaç fonksiyonunda, envanter tutma ve vardiya maliyetleri en küçüklenmektedir. Hazırlık maliyetleri, hazırlık zamanının kapasiteden yemesi haricinde bir maliyet getiriyorsa, amaç fonksiyonuna eklenebilir. Burada açıklanan kapasite kısıtlı parti büyüklüğü belirleme ve yükleme problemi ile, pek çok endüstriyel uygulamada karşılaşılmaktadır ve bu problem çok aşamalı üretim planlama ve yükleme modellerini de içerecek biçimde genelleştirebilir. Kapasite kısıtlı parti büyüklüğü belirleme ve yükleme problemi, üç ayrı planlama ve yükleme probleminin sentezidir, bunlar; Kapasite kısıtlı parti büyüklüğü belirleme (vardiya kararlan ve hazırlık zamanlan içeren), farklı işlemciler üzerinde toplam gecikmeyi en küçükleme ve sınıf çizelgeleme problemleridir. Bu problemlerin her biri olurluluk ve optimumu bulmada polinom zamanda çözülemeyen problemlerdir. Bununla birlikte, kapasite kısıtlı parti büyüklüğü belirleme ve yükleme probleminin çözümünde benzetimli tavlama, tabu arama ve genetik algoritmalar gibi güçlü arama tekniklerini içeren melez sezgisel metodlar geliştirilmiştir. Elde edilen sonuçlar rassal olarak üretilen 108 problem üzerinde optimal sonuçlar ile karşılaştırılarak değerlendirilmiştir. Ayrıca tüm prosedürler, kapasite kısıtlı parti büyüklüğü belirleme ve yükleme probleminin özel bir hali üzerinde, yine optimal sonuçlar ile karşılaştırılarak test edilmiştir.

ABSTRACT The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP may be imposed by unrelated parallel facilities of different classes. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP described here is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the Capacitated Lot Sizing Problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, hybrid heuristics involving powerful search techniques such as simulated annealing, tabu search and genetic algorithms are developed to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures are also compared with the optimal results of test problems consisting of a special case of CLSLP.