MODIFIKACIJE METODE PROMENLJIVIH OKOLINA I NJIHOVE PRIMENE ZA REŠAVANJE PROBLEMA RASPOREĐIVANJA PRENOSA DATOTEKA

eLibrary

 
 

MODIFIKACIJE METODE PROMENLJIVIH OKOLINA I NJIHOVE PRIMENE ZA REŠAVANJE PROBLEMA RASPOREĐIVANJA PRENOSA DATOTEKA

Show simple item record

dc.contributor.advisor Filipović, Vladimir
dc.contributor.author Dražić, Zorica
dc.date.accessioned 2016-07-29T07:50:54Z
dc.date.available 2016-07-29T07:50:54Z
dc.date.issued 2014
dc.identifier.uri http://hdl.handle.net/123456789/4246
dc.description.abstract The Variable neighborhood search method proved to be very successful for solving discrete and continuous optimization problems. The basic idea is a systematic change of neighborhood structures in search for the better solution. For optimiza- tion of multiple variable functions, methods for obtaining the local minimum starting from certain initial point are used. In case when the continuous function has many local minima, nding the global minimum is usually not an easy task since the obta- ined local minima in most cases are not optimal. In typical implementations with bounded neighborhoods of various diameters it is not possible, from arbitrary point, to reach all points in solution space. Consequently, the strategy of using the nite number of neighborhoods is suitable for problems with solutions belonging to some known bounded subset of IRn. In order to overcome the previously mentioned limitation the new variant of the method is proposed, Gaussian Variable neighborhood search method. Instead of de ning the sequence of di erent neighborhoods from which the random point will be chosen, all neighborhoods coincide with the whole solution space, but with di e- rent probability distributions of Gaussian type. With this approach, from arbitrary point another more distant point is theoretically reachable, although with smaller probability. In basic version of Variable neighborhood search method one must de ne in advance the neighborhood structure system, their number and size, as well as the type of random distribution to be used for obtaining the random point from it. Gaussian Variable neighborhood search method has less parameters since all the neighborhoods are theoretically the same (equal to the solution space), and uses only one distribution family - Gaussian multivariate distribution with variable dispersion. File transfer scheduling problem (FTSP) is an optimization problem widely appli- cable to many areas such as Wide Area computer Networks (WAN), Local Area Ne- v tworks (LAN), telecommunications, multiprocessor scheduling in a MIMD machines, task assignments in companies, etc. As it belongs to the NP-hard class of problems, heuristic methods are usually used for solving this kind of problems. The problem is to minimize the overall time needed to transfer all les to their destinations for a given collection of various sized les in a computer network, i.e. to nd the le transfer schedule with minimal length. In order to obtain the exact solution of the FTS problem, integer linear pro- gramming formulations are proposed and their correctness is proved. In this way optimal solutions can be found for small and medium size test instances. For large test instances, the Variable neighborhood search method is proposed using the "permutation" representation and typical neighborhood structures. More- over, the same method is used for obtaining the upper bounds of the solutions which are used in proposed integer linear programming formulations. For obtaining be- tter solutions in the small neighborhood of the current solution, three di erent local search procedures are implemented: 2-swap, 2-swap adjacent and variable neighbo- rhood descent. In order to apply the continuous optimization methods for solving FTSP, the weighted solution representation is developed. Such representation enables the co- ntinuous optimization methods to be used, which do not require the di erentiability of objective function. Since Gauss Variable neighborhood search method proved to be successful in continuous optimization problems, it was applied to FTSP. Pre- viously described local search procedures can also be used with weighted solution representation. Using the proposed methods optimal solutions for all small and medium size test instances are found. For large size instances, which are beyond the reach of exact methods, metaheuristic methods obtained good solutions in reasonable time. en_US
dc.description.provenance Submitted by Slavisha Milisavljevic (slavisha) on 2016-07-29T07:50:54Z No. of bitstreams: 1 phdDrazic_Zorica.pdf: 4739629 bytes, checksum: 16238b4fc1e6f93b24461117aa391e94 (MD5) en
dc.description.provenance Made available in DSpace on 2016-07-29T07:50:54Z (GMT). No. of bitstreams: 1 phdDrazic_Zorica.pdf: 4739629 bytes, checksum: 16238b4fc1e6f93b24461117aa391e94 (MD5) Previous issue date: 2014 en
dc.language.iso sr en_US
dc.publisher Beograd en_US
dc.title MODIFIKACIJE METODE PROMENLJIVIH OKOLINA I NJIHOVE PRIMENE ZA REŠAVANJE PROBLEMA RASPOREĐIVANJA PRENOSA DATOTEKA en_US
mf.author.birth-date 1983-08-28
mf.author.birth-place Beograd en_US
mf.author.birth-country Srbija en_US
mf.author.residence-state Srbija en_US
mf.author.citizenship Srpsko en_US
mf.author.nationality Srpkinja en_US
mf.subject.area Računarstvo en_US
mf.subject.keywords Kontinualna optimizacija, kombinatorna optimizacija, metoda promenljivih okolina, celobrojno linearno programiranje, metaheuristike. en_US
mf.subject.subarea Optimizacija en_US
mf.contributor.committee Tošić, Dušan
mf.contributor.committee Živković, Miodrag
mf.contributor.committee Urošević, Dragan
mf.contributor.committee Savić, Aleksandar
mf.university.faculty Mathematical Faculty en_US
mf.document.references 95 en_US
mf.document.pages 106 en_US
mf.document.location Beograd en_US
mf.document.genealogy-project No en_US
mf.university Belgrade University en_US

Files in this item

Files Size Format View
phdDrazic_Zorica.pdf 4.739Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record