The project scheduling problem with irregular starting time costs

We consider the problem of scheduling a set of activities satisfying precedence constraints in order to minimize the sum of the costs associated with the starting times of the activities. We consider the case in which the activity starting time cost functions are irregular functions. This problem can be solved in polynomial time either when the precedence graph has a special structure or when the starting time cost function of each activity is monotonic. A (0–1) integer programming formulation of this problem is presented and used to derive valid lower bounds to the optimal solution cost. An exact branch-and-bound algorithm is described. Computational results show the effectiveness of the proposed exact algorithm in solving problems up to 100 activities.