Kenar aktif ağ oluşturmada yapay kenar sayısını azaltmak için etkili bir algoritmanın tasarım ve gerçekleştirimi: Algoritmanın literatürdeki diğer algoritmalar ile karşılaştırılması
Design and implementation of an efficient algorithm to decrease the number of dummy arcs in AOA network: Its comparison with algorithms in the literature
- Tez No: 197136
- Danışmanlar: Y.DOÇ.DR. MUSTAFA EGE
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: kenar aktif ağ oluşturma, en az yapay kenar problemi, polinomsal indirgemekuralları, yapay kenar büzme, düğüm örtüşme, AoA network construction, minimum dummy arc problem, polynomial reductionrules, dummy arc contraction, node overlapping
- Yıl: 2005
- Dil: Türkçe
- Üniversite: Hacettepe Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
KENAR AKT F AĞ OLUŞTURMADA YAPAY KENAR SAYISINI AZALTMAKÇ N ETK L B R ALGOR TMANIN TASARIM VE GERÇEKLEŞT R M :ALGOR TMANIN L TERATÜRDEK D ĞER ALGOR TMALAR LEKARŞILAŞTIRILMASISevil ŞENÖZAğ tabanlı proje yönetiminde kullanılan Kenar Aktif Ağda(KAA) aktiviteler arası öncellikilişkilerini ifade etmek için yapay kenarlar kullanılır. Az yapay kenar ile KAA'ın kurulmasıaraştırıcıların ilgilendiği bir konu olmuştur. Literatürde bu problem, En Az Yapay KenarProblemi olarak bilinmektedir. Problemin, NP'de tamamlanır problemler sınıfına girmesi nedeniile, optimal çözüm için izlenebilir bir algoritma geliştirmek olası değildir, dolayısıyla,araştırmalar, olabildiğince az yapay kenarlı KAA'ı bulmaya yönelmiştir.Bu tez çalışmasında, olabildiğince az sayıda yapay aktivite içeren kenar aktif ağın kurulması içinetkili bir yaklaşım tasarlanmış ve gerçekleştirimi verilmiştir. Herhangi bir KAA üzerinde,aktiviteler arası öncellik ilişkilerini bozmadan yapay kenarların sayısını azaltacak bir indirgemekurallar kümesi geliştirilmiştir. En kötü durumda polinomsal süreden daha fazla zamangereksinimi duymayan ve küme kapsama problemi çözümünü de içermeyen indirgeme kuralları,dört ayrı sınıf altında incelenmiştir: Yapay kenar büzme, Yapay kenar ekleme, Düğüm örtüşme,Düğüm Ekleme. Geliştirilen indirgeme kurallarının işletim sırasının nasıl olması gerektiğinedeğinilmiş, indirgeme kurallarının farklı işleniş sırasının, hem işletim performansına hem deKAA oluşturmadaki etkisi araştırılmıştır. Ayrıca, önerilen yaklaşımın bilgisayar ortamında etkiligerçekleştirimi için kullanılması gereken veri yapıları açıklanmıştır.Bu konuda son yıllarda yapılan çalışmalar incelenmiş ve tezdeki çalışma, söz konusu çalışmalarile değişik kriterlere göre karşılaştırılmış ve karşılaştırma sonuçları tezde verilmiştir.
Özet (Çeviri)
DESIGN AND IMPLEMENTATION OF AN EFFICIENT ALGORITHM TO DECREASETHE NUMBER OF DUMMY ARCS IN AOA NETWORK : ITS COMPARISON WITHALGORITHMS IN THE LITERATURESevil ŞENABSTRACTIn activity-on-arc(AoA) network which is just another diagram used in network-based projectscheduling, dummy arcs are used to represent the immediate precedence relations betweenactivities. AoA network construction with less number of dummy arcs is a research subject onwhich many researchers have studied. This problem is known as Minimum Dummy-Arc Problem.As it is classified as NP-complete, there doesn?t exist a polynomial time algorithm, in otherwords, a tractable algorithm for the optimal solution can?t be developed; therefore, researcherstend to handle the AoA network with the number of dummy arcs as minimum as possible.In this thesis, an effective approach for constructing an AoA network including the number ofdummy arcs as minimum as possible is designed and its implementation is given. We revise andimprove the set of reduction rules described in order to decrease the number of dummy arcswithout violating the precedence relations given in an AoA network. The improved reductionrules, whose worst case running time is polynomial, don?t contain a solution for set coverproblem and are examined under four different classifications: Dummy arc contraction, Dummyarc insertion, Node overlapping, Node insertion. We underline the importance of the processingorder of the improved reduction rules and evaluate the effects of a different order of processing ofthe improved reduction rules on both the running time and AoA network construction. Thenecessary data structures for the effective implementation of our approach are also explained.Recent studies given in literature are examined in view of various criteria, and our approach iscompared to these studies and comparison results are also given.
Benzer Tezler
- Kenar aktif ağ oluşturmada yapay kenarların büzülmesi
Dummy arcs constriciton in AOA network construction
KURTULUŞ GÜNGÖR
Yüksek Lisans
Türkçe
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. MUSTAFA EGE
- Kenar aktif ağ oluşturmak için yeni bir yaklaşım
A New approach for constructing activity-on-arc network
AYŞEN ÜNLÜ COŞAR
Yüksek Lisans
Türkçe
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. MUSTAFA EGE
- Passive control of wake from a circular cylinder with a splitter plate: viscous VIC simulation
Dairesel silindirden iz akışının ayırıcı levha ile pasif kontrolu: viskoz VIC benzeşimi
AYDIN MISIRLIOĞLU
- Mobil telefon kullanımına bağlı oluşan 900-1800 mhz radyo frekans dalgalarının meydana getirdiği elektromanyetik alanın iliak kanat kemik mineral yoğunluğuna etkisi
The effect of electromagnetic fields on bone mineral density of iliac bone produced by 900-1800 mhz radio frequency waves dependent on cellular phone usage
BEŞİR ANDAÇ AKSOY
Tıpta Uzmanlık
Türkçe
2006
Ortopedi ve TravmatolojiSüleyman Demirel ÜniversitesiOrtopedi ve Travmatoloji Ana Bilim Dalı
PROF.DR. NEVRES HÜRRİYET AYDOĞAN
