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ıı, Hiperçizgeler, Hücresel üretim, Polihedral, Combinatorial Optimization, Polyhedral Combinatorics, Hyper graph Partitioning, Cellular Manufacturing Systems. VI, Hypergraphs, Cellular manufacturing, Polyhedral
- 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ı: Belirtilmemiş.
Ö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
- Hücresel imalatın başlangıç aşamaları için uzman sistem yaklaşımı
An Expert systems approach to the early stages of cellular manufacturing systems design
UFUK CEBECİ
- A Polyhedral approach to quadratic assignment problem
Karesel atama problemine polyhedral bir yaklaşım
AHMET SERTAÇ MURAT KÖKSALDI
Yüksek Lisans
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA AKGÜL
- Mekanik manipülatörlerde optimal yörünge planlaması
Optimum path planning for mechanical manipulators
A.YÜCEL YAZICI
- Görünmez çizgi ve görünmez yüzey algoritmalarının incelenmesi
Hidden line and hidden surface algorithms
TANSEL BOLAT
Yüksek Lisans
Türkçe
1997
Makine Mühendisliğiİstanbul Teknik ÜniversitesiKonstrüksiyon Ana Bilim Dalı
YRD. DOÇ. DR. HİKMET KOCABAŞ