
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 costcosts of inclusion plus costs of flowis least. In certain special cases the problem reduces to a linear minimum cost flow problem, but more frequently an enumerative technique is required. Branchandbound and implicit enumeration algorithms are formulated and compared. The algorithms are specialized for three applications: plant location problems, costtime 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