Accession Number : AD0710417

Title :   ENUMERATIVE ALGORITHMS FOR SOLVING A CLASS OF NETWORK SYNTHESIS PROBLEMS.

Descriptive Note : Research rept.,

Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s) : Sanderson,Robert D.

Report Date : APR 1970

Pagination or Media Count : 145

Abstract : A class of network flow problems having a combinatorial nature is defined. A network is synthesized by including exactly one directed arc from each of several disjoint subsets of possible arcs. All candidate arcs in a particular subset connect the same pair of nodes, and associated with each arc are five parameters: a cost of inclusion, unit cost of flow, lower and upper limits on flow, and direction of positive flow. When a network is synthesized, a least cost feasible flow is computed. The objective of the problem is to synthesize the network for which the total cost--costs of inclusion plus costs of flow--is least. In certain special cases the problem reduces to a linear minimum cost flow problem, but more frequently an enumerative technique is required. Branch-and-bound and implicit enumeration algorithms are formulated and compared. The algorithms are specialized for three applications: plant location problems, cost-time critical path scheduling with nonconvex costs, and critical path scheduling under disjunctive constraints. (Author)

Descriptors :   (*MANAGEMENT PLANNING AND CONTROL, FLOW CHARTING), ALGORITHMS, COST EFFECTIVENESS, COMBINATORIAL ANALYSIS, BOUNDARY VALUE PROBLEMS, INDUSTRIAL PLANTS, SITE SELECTION, COMPUTER PROGRAMS, SCHEDULING, THESES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE