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