GRASP with path-relinking for network migration scheduling
Diogo V. Andrade (dandraderutcor.rutgers.edu)
Abstract: Network migration scheduling is the problem where inter-nodal traffic from an outdated telecommunications network is to be migrated to a new network. Nodes are migrated, one at each time period, from the old to the new network. All traffic originating or terminating at given node in the old network is moved to a specific node in the new network. Routing is predetermined on both networks and therefore arc capacities are known. Traffic between nodes in the same network is routed in that network. When a node is migrated, one or more temporary arcs may need to be set up since the node migrated may be adjacent to more than one still active node in the old network. A temporary arc remains active until both nodes connected by the arc are migrated to the new network. In one version of the problem, one seeks an ordering of the migration of the nodes that minimizes the maximum sum of capacities of the temporary arcs. In another version, the objective is to minimize the sum of the total capacities of the temporary arcs over each period in the planning horizon. In this paper, we propose a hybrid heuristic which combines GRASP with path-relinking to find cost-efficient solutions to both versions of the network migration problem.
Keywords: Network optimization, node migration, minimum cut, linear arrangement, GRASP, path-relinking, local search, metaheuristic, heuristic
Category 1: Applications -- OR and Management Sciences (Telecommunications )
Category 2: Combinatorial Optimization (Meta Heuristics )
Category 3: Network Optimization
Citation: AT&T Labs Research Technical Report TD-6V4V9Z, Shannon Laboratory, Florham Park, NJ 07932, October 31, 2006.
Entry Submitted: 10/31/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|