Combinatorial auction based resource co-allocation model for grids

Abstract

ÖZET ŞEBEKELER İÇİN BIRLEŞIMSEL MÜZAYEDE TABANLI KAYNAK TAHSİS MODELLERİ Kaynak tahsis problemi, bilişim şebekelerinin etkin olarak çözülememiş prob lemlerinden biridir. Bu problemin modellenmesi doğrultusunda bilişim şebekeleri için yeni bir birleşimsel müzayede tabanlı kaynak tahsis (BMTKT) yaklaşımı önerilmiştir. Bu ekonomi tabanlı model müşterilere ayrım yapmaksızın, istedikleri kaynak tiplerine birleşimsel teklif vermelerine imkan vererek, bilişim şebeklerine ait kaynakların etkili ve ekonomik açıdan verimli tahsisine olanak sağlamaktadır. Bu modeli çözmek için öncelikle BMTKT problemi tanımlanmış ve problem tamsayı programlama metodu kullanılarak formüle edilmiştir. Bu problem NP-hard sınıfına ait bir problem olduğun dan dolayı optimum çözümü bulmak çok fazla zaman alabileceğinden, birim fiyat kri teri tabanlı iki yaklaşık sonuç algoritması önerilmiştir. BMTKT modeli için, içinde suni test üreticisi, optimum çözücüsü, bir üst sınır hesaplayıcısı ve üç adet yaklaşık sonuç çözücüsü bulunduran bir yazılım paketi hazırlanmıştır. Elimizde bu modele ait gerçek hayat verileri olmadığından, algoritmaların performansları test üreticisi tarafından oluşturulan kapsamlı testler ile sınanmıştır. Önerilmiş olan iki polinom zamanlı yaklaşık sonuç algoritması optimum sonuçlara göre yüzde 97,3 ve yüzde 99,2'lik ortalama sonuç larla ümit verici performans değerleri vermiştir.

IV ABSTRACT COMBINATORIAL AUCTION BASED RESOURCE CO- ALLOCATION MODEL FOR GRIDS Resource co-allocation problem is one of the challenging problems in grids. In order to model this problem, a new combinatorial auction based resource co-allocation (CABRC) approach is proposed. This economy based model provides efficient allo cation of resources in a grid environment by allowing bidders to submit bids on the combinations of different resource types. In order to solve the model, CABRC problem is defined and formulated using integer programming. It is proved that CABRC prob lem is NP-hard and since optimum solutions may take tremendous amount of time to be found,- two new greedy heuristics based on price per unit criteria are proposed. A software package that consists of an artificial test case generator, an optimum solver, an upper bound estimator and three greedy heuristic solvers for CABRC problem is coded. Since there is no real world data for testing the solvers, performance of algo rithms are compared using a comprehensive test suite which is produced by the test case generator. Proposed two polynomial time heuristic solvers produce promising re sults of 97.3 per cent and 99.2 per cent average performance relative to the optimum solution respectively.