Show simple item record

dc.contributor.advisorAkgül, Mustafa
dc.contributor.authorKandiller, Levent
dc.date.accessioned2020-12-02T12:50:53Z
dc.date.available2020-12-02T12:50:53Z
dc.date.submitted1994
dc.date.issued2018-08-06
dc.identifier.urihttps://acikbilim.yok.gov.tr/handle/20.500.12812/37360
dc.description.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ıı
dc.description.abstractAbstract 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. VIen_US
dc.languageEnglish
dc.language.isoen
dc.rightsinfo:eu-repo/semantics/embargoedAccess
dc.rightsAttribution 4.0 United Statestr_TR
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectEndüstri ve Endüstri Mühendisliğitr_TR
dc.subjectIndustrial and Industrial Engineeringen_US
dc.titlePolyhedral approaches to hypergraph partitioning and cell formation
dc.title.alternativeHiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
dc.typedoctoralThesis
dc.date.updated2018-08-06
dc.contributor.departmentDiğer
dc.subject.ytmHypergraphs
dc.subject.ytmPolyhedral
dc.subject.ytmCellular manufacturing
dc.identifier.yokid36211
dc.publisher.instituteMühendislik ve Fen Bilimleri Enstitüsü
dc.publisher.universityİHSAN DOĞRAMACI BİLKENT ÜNİVERSİTESİ
dc.identifier.thesisid36211
dc.description.pages162
dc.publisher.disciplineDiğer


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

info:eu-repo/semantics/embargoedAccess
Except where otherwise noted, this item's license is described as info:eu-repo/semantics/embargoedAccess