Modifikacije metode promenljivih okolina i njihove primene za rešavanje problema raspoređivanja prenosa datoteka

Abstract

Metoda promenljivih okolina se u praksi pokazala vrlo uspesnom za resavanje pro- blema diskretne i kontinualne optimizacije. Glavna ideja ove metode je sistematska promena okolina unutar prostora resenja u potrazi za boljim resenjem. Za opti- mizaciju funkcija vise promenljivih koriste se metode koje nalaze lokalni minimum polazeci od zadate pocetne tacke. U slucaju kada kontinualna funkcija ima mnostvo lokalnih minimuma, nalazenje globalnog minimuma obicno nije lak zadatak jer najcesce dostignuti lokalni minimumi nisu optimalni. Kod uobicajenih implementa- cija sa ogranicenim okolinama razlicitih dijametara iz proizvoljne tacke nije moguce dostici sve tacke prostora resenja. Zbog toga je strategija koriscenja konacnog broja ogranicenih okolina primenjiva na probleme kod kojih optimalno resenje pripada nekom unapred poznatom ogranicenom podskupu skupa IRn. U cilju prevazilazenja pomenutog ogranicenja predlozena je nova varijanta meto- de, Gausovska metoda promenljivih okolina. Umesto denisanja niza razlicitih okolina iz kojih ce se birati slucajna tacka, u ovoj metodi se sve okoline pokla- paju sa celim prostorom resenja, a slucajne tacke se generisu koriscenjem razlicitih slucajnih raspodela Gausovog tipa. Na ovaj nacin se i tacke na vecem rastojanju od tekuce tacke mogu teorijski dostici mada sa manjom verovatnocom. U osnovnoj verziji metode promenljivih okolina neophodno je unapred denisati sistem okolina, njihov ukupan broj i velicinu, kao i tip raspodele koja ce se koristiti za odabir slucajne tacke unutar tih okolina. Gausovska metoda promenljivih okolina za razliku od osnovne verzije ima manje parametara jer su sve okoline teorijski iste velicine (jednake celom prostoru pretrage) i imaju jedinstvenu jednoparametarsku familiju raspodela Gausovu raspodelu slucajnih brojeva sa promenljivom dispe- rzijom. Problem raspored-ivanja prenosa datoteka (File transfer scheduling problem - FTSP) je optimizacioni problem koji svoju primenu pronalazi u mnogim oblastima poput telekomunikacijama, LAN i WAN mrezama, raspored-ivanju u okviru MIMD (multiple instruction multiple data) racunarskih sistema i dr. Spada u klasu NP teskih problema za cije resavanje se uobicajeno koriste heuristicke metode. Za- datak optimizacije FTSP sastoji se u trazenju odgovarajuceg rasporeda pojedinacnih prenosa datoteka, tj. vremenskih trenutaka kada ce svaka datoteka zapoceti svoj prenos tako da duzina vremenskog intervala od trenutka kada prva datoteka zapocne prenos do trenutka u kom poslednja zavrsi bude sto manja...

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 dening the sequence of dierent neighborhoods from which the random point will be chosen, all neighborhoods coincide with the whole solution space, but with die- 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 dene 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- 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...