Bounding and dominance approaches in improving the efficiency of branch and bound type solution to the `SCLS` problems

Abstract

ÖZET...<. TEK URUNLU VE KAPASİTE KISITLI YI?IN HACMİ BELİRLEME PROBLEMLERİNDE DAL-DU?ÜM YÖNTEMİNİN VERİMLİLİ?İNİ ARTTIRMAK İÇİN SINIR VE DOMİNANS YAKLAŞIMLARI DEMİRLİ, Kudret Yüksek Lisans Tezi, End. Müh. Bölümü Tez Yöneticisi: Y.Doc. Dr. Sinan Kayalıgil Şubat 1988, 85 sayfa Tek ürünlü ve kapasite kısıtlı sistemlerde sabit üretim ve tasıma maliyetini gözeten en iyi yığın hacimlerinin belirlenmesi problemi ele alınmıştır. Problemin NP-zor oluşu, çözüm yöntemlerinin verimliliğini arttırmak için birtakım ek yöntemler geliştirme zorunluluğunu getirmiştir. Bu çalışmada, Baker, Dixon, Magazine ve Silver [1978] tarafından Önerilen dal-düğüm teknigindeki dominans ve kısmi maliyet faktörleri yeniden düzenlenmiş ve yeni bir kavram olan derinlik sıkıştırması (depth compression) ortaya atılmıştır. Bazı faktörlerin problemin işlemsel zorlukları üzerindeki etkilerini belirlemek amacı ile 2* faktorsel tasarımı yapılmıştır. Anahtar kelimeler:Tek ûrunlü kapasite kısıtlı yığın hacmi belirleme, dal-duğum tekniği, dominans. iv

ABSTRACT BOUNDING AND DOMINANCE APPROACHES IN IMPROVING THE EFFICIENCY OF BRANCH AND BOUND TYPE SOLUTION TO THE `SCLS` PROBLEMS. DEMİRLİ, Kudret M.S. in Industrial Engineering Supervisor: Asst.Prof. Dr. Sinan Kayalıgil February 1988, 85 pages Single item capacitated lot sizing problem with constant production and inventory costs is studied. NP-hard characteristic of the problem warrants additional tools to increase the efficiency of the solution procedures. To increase the efficiency of the algorithm of Baker, Dixon, Magazine, and Silver [1978] proposed `Dominance` and `Partial Cost` properties are modified and a new concept, named as, `Depth Compression` is introduced in this study. A 21* experiment is designed to specify significance of certain factors on the computational difficulty of single item capacitated lot sizing problems. Key words: Single item capacitated lot sizing, branch and bound, dominance. m