Polinomially solvable cases of multifaciling distance canstraints on cyclic networks

Abstract

ÖZET GENEL SERİMLERDE ÇOKTESİSLİ UZAKLIK KISITLARI PROBLEMİNİN POLİNOM ZAMANDA ÇÖZÜLEBİLİR DURUMLARI Naile Gülcan Yeşilkökçen Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Dr. Barbaros Ç. Tansel Temmuz, 1993 Uzakhk Kısıtları Problemi, bir serim üzerinde bir yada daha fazla yeni tesisi, yeni tesislerle varolan tesisler arasındaki ve yeni tesis çiftleri arasındaki uzaklıklar belli üst değerleri geçmeyecek biçimde yerleştirme problemidir. Problemin genel sexivoler&e NV -Zorluğu ağaç serimlerde ise polinom zamanda çözülebilirliği bilinmektedir. Ağaç serimler için geliştirilmiş temel kuramlar olmasına karşın, genel serimlerde geliştirilmiş hiçbir kuram ve algoritma bulunmamaktadır. Bu tez çalışmasında, biz uzaklık kısıtlarının yeni tesisler arasındaki ilişkilerin ağaç serimi biçiminde olduğu özel bir sınıfını çözen ve yerleşim uzayı olarak alman herhangi bir metrik uzaya uygulanabilen bir yöntem sunuyoruz. Yöntem, yerleşim uzayının alt kümelerinde tanımlanmış GENİŞ LETME ve KESİŞTİRME işlemlerini temel almaktadır. Bu yöntemin genel seçimlerde uygulaması polinom zamanlı algoritmalar verir. Son olarak, ilgili bir enküçük-enbüyük problemine e-eniyi çözüm üreten bir algoritma veriyoruz. Anahtar Kelimeleri Uzaklık Kısıtları, Serim Yerleşimi, Enküçük-enbüyük Problemi. iv

ABSTRACT POLYNOMIALLY SOLVABLE CASES OF MULTIFACILITY DISTANCE CONSTRAINTS ON CYCLIC NETWORKS Naile Gülcan Yeşilkökçen M.S. in Industrial Engineering Supervisor: Assoc. Prof. Barbaros Ç. Tansel July, 1993 Distance Constraints Problem is to locate one or more new facilities on a network so that the distances between new and existing facilities as well as between pairs of new facilities do not exceed given upper bounds. The prob lem is MV -Complete on cyclic networks and polynomially solvable on trees. Although theory for tree networks is well- developed, there is virtually no the ory for cyclic networks. In this thesis, we identify a special class of instances for which we develop theory and algorithms that are applicable to any metric space defining the location space. We require that the interaction between new facilities has a tree structure. The method is based on successive appli cations of EXPANSION and INTERSECTION operations defined on subsets of the location space. Application of this method to general networks yields strongly polynomial algorithms. Finally, we give an algorithm that constructs an e-optimal solution to a related minimax problem. Key words: Distance Constraints, Network Location, Minimax Problem with Mutual Communication. / m