Polinomially solvable cases of multifaciling distance canstraints on cyclic networks
Başlık çevirisi mevcut değil.
- Tez No: 28877
- Danışmanlar: DOÇ. DR. BARBAROS Ç. TANSEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Ağlar, Uzaklık, Distance Constraints, Network Location, Minimax Problem with Mutual Communication. / m, Networks, Distance
- Yıl: 1993
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Ö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
Özet (Çeviri)
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.
Benzer Tezler
- Polyhedral approaches to hypergraph partitioning and cell formation
Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
LEVENT KANDİLLER
Doktora
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiDOÇ.DR. MUSTAFA AKGÜL
- Distance constrains on cylic networks: A new polynomially solvable class
Genel serimlerde uzaklık kısıtları problemi polinom zamanda çözülebilir yeni bir sınıf
HÜLYA EMİR
Yüksek Lisans
İngilizce
1997
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. BARBAROS TANSEL
- Rescheduling under machine disraptions
Makine arızaları durumunda yeniden çizelgeleme
OĞUZHAN ALAGÖZ
Yüksek Lisans
İngilizce
2000
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MERAL AZİZOĞLU
- A Polynomially bounded dual simplex algorithm for capacitated minimum cost flow problem
Başlık çevirisi yok
AYŞEGÜL ALTABAN
Yüksek Lisans
İngilizce
1990
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CANAN A. SEPİL
- İki değişkenli fonksiyonların Bernstein polinomları
Bernstein polinomials of two variable founctions
İBRAHİM BÜYÜKYAZICI
