Polyhedral approaches to hypergraph partitioning and cell formation

Abstract

Ö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. Anahtar kelimeler: Kombinatoryal Optimizasyon, Polihedral Kombinatoriks, Hiperçizge Parçalama, Hücre Tipi İmalat Sistemleri. vıı

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. Keywords: Combinatorial Optimization, Polyhedral Combinatorics, Hyper graph Partitioning, Cellular Manufacturing Systems. VI