Optimization Online


GRASP with path-relinking for network migration scheduling

Diogo V. Andrade (dandrade***at***rutcor.rutgers.edu)
Mauricio G. C. Resende (mgcr***at***research.att.com)

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.

Download: [PDF]

Entry Submitted: 10/31/2006
Entry Accepted: 11/01/2006
Entry Last Modified: 10/31/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society