Raspoređivanje metodom promenljivih okolina : eksperimentalna analiza

Abstract

U ranijim radovima razvijali smo i uporedjivali razne heuristike za rasporedjivanje zadataka u prisustvu komunikacija i zaključili da metoda promenljivih okolina u proseku daje najbolje rezultate za sve tipove slučajno generisanih grafova zadataka. Međutim, pronašli smo klasu grafova sa poznatim optimalnim rešenjem za koju se heuristička raspodela dobijena metodom promenljivih okolina (iako je još uvek bolja od drugih) razlikuje od optimalne za više od 50%. U ovom radu opisaćemo analize koje smo izvršili sa ciljem razumevanja dobijenog odstupanja heurističkih rešenja od optimalnog. Kao rezultat dobili smo odstupanje samo 6%.

In our previous papers we developed and compared different scheduling heuristics and concluded that VNS performs best in average for all types of random task graphs we generated. Yet, there is a class of task graphs with known optimal solutions such that VNS obtained schedule (although still the best one) differs from the optimal one for more than 50%. In this paper we describe the analysis we performed in order to explain the deviation of the heuristic solution from the optimal one. As a result, we are able to reduce the error to 6% above the optimal solution.