An Analytic Approach for a Capacitated C.P.M. Problem.

The capacitated C.P.M. problem with a single resource and jobs having unit duration and requiring a single unit of resource is formulated efficiently as a 0-1 linear integer program. Individual job precedences are combined into groups and modeled as multiple-precedence constraints. The problem of finding the optimal integer solution is one of finding a feasible basis to the linear program which contains the slack variables of the precedence constraints. The special case containing two multiple-precedence constraints is considered. It is shown that an optimal basis of a linear relaxation of the problem is at most two simplex pivots from the basis of an optimal integer solution.