The project scheduling problem with irregular starting time costs

We consider the problem of scheduling a set of activities satisfying preced ence 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 act ivity starting time cost functions are irregular functions. This problem ca n be solved in polynomial time either when the precedence graph has a speci al structure or when the starting time cost function of each activity is mo notonic. A (0-1) integer programming formulation of this problem is present ed and used to derive valid lower bounds to the optimal solution cost. An e xact branch-and-bound algorithm is described. Computational results show th e effectiveness of the proposed exact algorithm in solving problems up to 1 00 activities. (C) 1999 Elsevier Science B.V. All rights reserved.