Polyhedral approaches to hypergraph partitioning and cell formation
Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
- Tez No: 36211
- Danışmanlar: DOÇ.DR. MUSTAFA AKGÜL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Kombinatoryal Optimizasyon, Polihedral Kombinatoriks, Hiperçizge Parçalama, Hücre Tipi İmalat Sistemleri. vıı, Combinatorial Optimization, Polyhedral Combinatorics, Hyper graph Partitioning, Cellular Manufacturing Systems. VI
- Yıl: 1994
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 162
Özet
Özet HİPERÇİZGE PARÇALAMA PROBLEMİNE POLYHEDRAL YAKLAŞIMLAR VE HÜCRE BELİRLENMESİ Levent Kandiller Endüstri Mühendisliği Doktora Tez Yöneticisi: Doç. Dr. Mustafa Akgül Aralık 1994 Hiperçizgeler, çizgelerin ayrıtların birleştirdiği düğümlerin sayılarının ikiden fazla olabildiği daha genel durumlarıdır. Hiperçizgeler imalat sistemlerinin ve elektrik devrelerinin ifade edilmesinde kullanılırlar. Hücre Tipi İmalat sistemlerinde hiperçizge parçalaması hücre belirleme problemine dönüşür. Hiperçizge parçalama entegre devre tasarımında yerleşim problemini kolaylaştırmak için gereklidir. Literatürde çeşitli optimal olmayan çözümler veren sezgisel yöntemler vardır. Bu doktora çalışmasında hiperçizge parçalama problemi için tasarlanmış optimali arayan polihedral kombinatoriks temelli yaklaşımlar tanıtılmıştır. Hiperçizgeleri ikiye ayırma problemini incelemek için r-düzenli hiperçizgeler üzerinde iki politop tanımlanmıştır. R-düzenli hiperçizgelerde her ayrıt r düğümü bağlar. Bu politoplarm boyutları, geçerli eşitsizlik aileleri ve yüzey tanımlayan eşitsizlikleri araştırılmış ve bu eşitsizliklerin etkinlikleri rastsal problemler yardımıyla denenmişlerdir. Hücre belirleme aşaması Hücre Tipi İmalat sistemlerinin tasarımındaki ilk aşamadır. Yeni iki kombinatoryal optimizasyon temelli hücre belirleme tekniği geliştirilmiştir. Birinci teknik bir çizge ile hiperçizgeye yakınlaşmayı, maximum akış problemlerini arka arkaya çözme yoluyle elde edilen akış eşdeğer ağacı yaratmayı ve bir tarama yordamını kullanmaktadır. İkinci teknik ise daha önce bahsedilen politopun polinom zamanda çözülebilen özel halini kullanmaktadır. Bu iki yeni teknik tanınan altı hücre belirleme algoritması ile değişik ölçüler bazında rassal problemlerde karşılaştırılmıştır. Bulgular istatistiksel analizlerle yorumlanmıştır.
Özet (Çeviri)
Abstract POLYHEDRAL APPROACHES TO HYPERGRAPH PARTITIONING AND CELL FORMATION Levent Kandiller Ph.D. in Industrial Engineering Supervisor: Mustafa Akgül, Associate Professor December 1994 Hypergraphs are generalizations of graphs in the sense that each hyperedge can connect more than two vertices. Hypergraphs are used to describe manu facturing environments and electrical circuits. Hypergraph partitioning in man ufacturing models cell formation in Cellular Manufacturing systems. Moreover, hypergraph partitioning in VLSI design case is necessary to simplify the layout problem. There are various heuristic techniques for obtaining non-optimal hy pergraph partitionings reported in the literature. In this dissertation research, optimal seeking hypergraph partitioning approaches are attacked from polyhedral combinatorics viewpoint. There are two polytopes defined on r-uniform hypergraphs in which every hyperedge has exactly r end points, in order to analyze partitioning related prob lems. Their dimensions, valid inequality families, facet defining inequalities are investigated, and experimented via random test problems. Cell formation is the first stage in designing Cellular Manufacturing systems. There are two new cell formation techniques based on combinatorial optimization principles. One uses graph approximation, creation of a flow equivalent tree by successively solving maximum flow problems and a search routine. The other uses the polynomially solvable special case of the one of the previously discussed polytopes. These new techniques are compared to six well-known cell formation algorithms in terms of different efficiency measures according to randomly gen erated problems. The results are analyzed statistically.
Benzer Tezler
- A polyhedral approach to delivery man problem
Başlık çevirisi yok
PINAR KESKİNOCAK
Yüksek Lisans
İngilizce
1992
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiDOÇ. DR. MUSTAFA AKGÜL
- Büyük boyutlu sınıflandırma problemlerinin çözümü için yeni bir matematiksel yaklaşım
A new mathematical approaches to large scale classification problems
MEHMET TAHİR ÇİFTÇİ
Yüksek Lisans
Türkçe
2011
Endüstri ve Endüstri MühendisliğiAnadolu ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. GÜRKAN ÖZTÜRK
- Optimization based polyhedral region approach for multi-class data classification problem
Çok gruplu veri sınıflandırması problemi için eniyileme tabanlı çokyüzlü bölge yaklaşımı
FATİH RAHİM
Doktora
İngilizce
2019
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği ve İşletme Yönetimi Bilim Dalı
PROF. DR. METİN TÜRKAY
- Sınıflandırma problemleri için matematiksel programlama temelli çözüm yaklaşımları
Mathematical programming based solution approaches for classification problems
MÜGE ACAR
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri MühendisliğiAnadolu ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. REFAİL KASIMBEYLİ
- Çok yüzlü konik sınıflandırıcılar için marj enbüyüklenmesi
Margin maximization for polyhedral conic classifiers
GÜRHAN CEYLAN
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiAnadolu ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜRKAN ÖZTÜRK