Steiner tree network scheduling with opportunity cost of time

This paper points out the impact of opportunity cost of time (high discount rate or high rate of time preference, time-dependent profits, etc.) in designing real-world Steiner trees like electricity, gas, water, or telecommunications networks. We present the Steiner Tree Scheduling Problem which consists of finding a Steiner tree in an activity-on-arc graph that spans a set of mandatory vertices, and of scheduling each selected activity in a competition for scarce resources so as to optimize a given objective function. Project managers typically make the network design decisions and the activity scheduling decisions separately. The main contribution of this paper is in demonstrating the potential for a more efficient network planning in a context of high opportunity cost of time by making simultaneous design and scheduling decisions. Mixed integer programming formulations are also proposed, and a heuristic procedure is described.


Working paper, Universidad del Pacifico, Lima, Peru, January 2013



View Steiner tree network scheduling with opportunity cost of time