tailieunhanh - Gaussian variable neighborhood search for the file transfer scheduling problem

This paper presents new modifications of Variable Neighborhood Search approach for solving the file transfer scheduling problem. To obtain better solutions in a small neighborhood of a current solution, we implement two new local search procedures. | Yugoslav Journal of Operations Research 26 (2016), Number 2, 173–188 DOI: GAUSSIAN VARIABLE NEIGHBORHOOD SEARCH FOR THE FILE TRANSFER SCHEDULING PROBLEM ˇ C ´ Zorica DRAZI Faculty of Mathematics, University of Belgrade, Serbia zdrazic@ Received: January 2015 / Accepted: March 2015 Abstract: This paper presents new modifications of Variable Neighborhood Search approach for solving the file transfer scheduling problem. To obtain better solutions in a small neighborhood of a current solution, we implement two new local search procedures. As Gaussian Variable Neighborhood Search showed promising results when solving continuous optimization problems, its implementation in solving the discrete file transfer scheduling problem is also presented. In order to apply this continuous optimization method to solve the discrete problem, mapping of uncountable set of feasible solutions into a finite set is performed. Both local search modifications gave better results for the large size instances, as well as better average performance for medium and large size instances. One local search modification achieved significant acceleration of the algorithm. The numerical experiments showed that the results obtained by Gaussian modifications are comparable with the results obtained by standard VNS based algorithms, developed for combinatorial optimization. In some cases Gaussian modifications gave even better results. Keywords: Combinatorial Optimization, Variable Neighborhood Search, Gaussian Variable Neighborhood Search, File Transfer Scheduling Problem. MSC: 90C59, 68T20, 05C90. 174 Z. Draˇzi´c / Gauss-VNS for FTSP 1. INTRODUCTION The standard form of the optimization problem is given with: min{ f (x) | x ∈ X, X ⊆ S} (1) where S is a solution space, X is a set of feasible solutions, x is a feasible solution, and f is an objective function. In the case when S is a finite or countable infinite set, this is a problem of combinatorial (discrete)