To appear in Proceedings of International Network Optimization Conference (INOC 2007), Spa, Belgium, 2007.
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.
PDF file of full paper
Mauricio G.C. Resende's Home PageLast modified: 19 January 2007