|
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. |