To appear in Proceedings of International Network Optimization Conference (INOC 2007), Spa, Belgium, 2007.
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.
PDF file of full paper