The network programming method in project scheduling problems

The network programming method is applied to the discrete problem of minimizing the costs of a project with a given duration. Two basic algorithms for solving this problem in the cases of independent and sequential jobs are described. More complex cases of project scheduling on networks (tree network and aggregated network) are treated by the sequential application of the basic algorithms. For the case of a build-up assembly network, a new method based on the following idea is proposed: an appropriate set of jobs is determined and their durations are fixated so that the resulting network becomes either a tree or an aggregated network. All possible alternatives for fixating the durations of jobs from such a set are considered and, for each alternative, the problem is completely solved. The best alternative among all possible ones is selected. The case of project scheduling on an arbitrary network is also studied.