Authors: Davidović, Tatjana 
Hansen, Pierre
Mladenović, Nenad 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Raspoređivanje metodom promenljivih okolina : eksperimentalna analiza
Other Titles: Scheduling by VNS: Experimental Analysis
First page: 319
Last page: 322
Conference: XXVIII Simpozijum o operacionim istraživanjima, SYMOPIS 2001
Issue Date: 2001
Rank: M60
URL: http://www.mi.sanu.ac.rs/~tanjad/SYMOPIS2001.pdf
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.
Keywords: graf zadataka | raspoređivanje | komunikaciono kašnjenje | metoda promenljivih okolina;task graph | scheduling | communication delay | variable neighborhood search
Publisher: Medija centar "odbrana"
Project: Mathematical Logic, Combinatorics and Information Processing: Foundations and Applications of Computer Science 
Methods and Models in Theoretical, Applied and Industrial Mathematics 

Show full item record

Page view(s)

20
checked on Sep 26, 2021

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.