Accession Number:

ADA028285

Title:

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

Descriptive Note:

Research rept.,

Corporate Author:

FLORIDA UNIV GAINESVILLE DEPT OF INDUSTRIAL AND SYSTEMS ENGINEERING

Report Date:

1976-05-01

Pagination or Media Count:

45.0

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.

Subject Categories:

  • Administration and Management
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE