An Analytic Approach for a Capacitated C.P.M. Problem.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1976
- Accession Number
- ADA028285
Entities
People
- C. Stafford Loveland
- Thom J. Hodgson
Organizations
- University of Florida