Scheduling project activities in a distributed environment

We study the problem of distributing a set of activities, with precedence constraints in the form of an assembly tree, among a set of competing firms with the objective of minimizing total cost. Each firm bidding for an activity specifies a production cost, an activity duration for its achievement and a maintenance cost for the upkeep of this activity beyond its completion time. When activity durations are independent of firms, the problem reduces to a special case of project scheduling where the cost function for each activity is concave and piecewise linear. We give a mathematical programming model for the general problem and derive an O(n log n) algorithm for solving the special case. We discuss how this special case can be used to solve the general problem.