- A wide range of practical real-world problems deal with determining the optimal assignment of objects to maximally efficient subsets or clusters. One example of such "network partitioning" problems involves determining an optimal assignment of nodes (e.g., hardware components, data bases) to partitions (e.g., processors, memory) within distributed computing networks exhibiting static behavior., The primary objectives of this effort are: (1) the formulation of a flexible model to reflect the multiple conflicting goals and specification constraints considered in the evaluation of different configurations for distributed computing networks, and (2) the development, implementation and evaluation of a non-naive heuristic solution methodology. The model comprises a set of submodules including intracommunication, reliability, cost and similarity. Upper and lower bounds are also estimated for the submodules., The network partitioning problem is NP-complete and cannot be solved by exact methods. We propose a new 2-stage methodology combining generalized goal programming, a penalty heuristic and an exchange algorithm. The penalty heuristic is applied to the imbedded quadratic assignment problem and, starting from this "baseline solution," a 1/1 exchange search is employed to incorporate all other design goals. The exchange algorithm may be used to determine a lexicographically minimal solution for any given set of ranked objectives or, alternately, to generate a set of nondominated solutions. In order to evaluate the solution methodology, some test problems with known "baseline solutions" are developed., and The solution algorithms were coded in FORTRAN and applied to 48 test problems. Each problem contained 7 objectives and up to 200 nodes, 257 rows, and 1,680 variables. The average computation time for the penalty heuristic was observed to be proportional to the square of the number of nodes in the network, and the worst case time complexity for the exchange heuristic was a second order polynomial.
- Dissertation Note:
- Ph.D. The Pennsylvania State University 1982.
- Source: Dissertation Abstracts International, Volume: 43-07, Section: B, page: 2293.
View MARC record | catkey: 13611725