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
Yazar: SEVİL ŞEN
Danışman: Y.DOÇ.DR. MUSTAFA EGE
Hacettepe Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2005
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Ö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.Anahtar Sözcükler: kenar aktif ağ oluşturma, en az yapay kenar problemi, polinomsal indirgemekuralları, yapay kenar büzme, düğüm örtüşmeDanışman: Yrd. Doç. Dr. Mustafa EGE, Hacettepe Üniversitesi, Bilgisayar MühendisliğiBölümü

Abstract:
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.Keywords: AoA network construction, minimum dummy arc problem, polynomial reductionrules, dummy arc contraction, node overlappingAdvisor: Asst. Prof. Dr. Mustafa EGE, Hacettepe University, Department of ComputerEngineering.