The problem of assigning computer program modules to functionally similar processors in a distributed computer network is investigated. The modules of a program must be assigned among processors in such a way as to minimize interprocessor communication while taking advantage of affinities of certain modules to particular processors. This problem is formulated as a zero-one quadratic programming problem, but is more conveniently modeled as a directed acyclic search graph. The model is developed and a backward shortest path labeling algorithm is given that produces an assignment of program modules to processors. A non-backtracking branch-and-bound algorithm is described that uses a local neighborhood search at each stage of the search graph. 相似文献
Position finding has historically been carried out by calculating the coordinates of the mean position via a least-squares procedure based on the distance of the position from several direction lines. It has been suggested that the least-squares procedure assigns too much weight to outliers among the set of direction lines, outliers which may actually be associated with objects other than the one being located. In this paper, a method of using least-absolute deviations, which yields a more outlier-resistant median estimate of the position instead of the least-squares mean estimate, is presented. 相似文献
A general class of continuous time nonlinear problems is considered. Necessary and sufficient conditions for the existence of solutions are established and optimal solutions are characterized in terms of a duality theorem. The theory is illustrated by means of an example. 相似文献
We consider the problem of searching for a target that moves in discrete time and space according to some Markovian process. At each time, a searcher attempts to detect the target. If the searcher's action at each time is such as to maximize his chances of immediate detection, we call his strategy “myopic.” We provide a computationally useful necessary condition for optimality, and use it to provide an example wherein the myopic strategy is not optimal. 相似文献
This paper gives characterization of optimal Solutions for convex semiinfinite programming problems. These characterizations are free of a constraint qualification assumption. Thus they overcome the deficiencies of the semiinfinite versions of the Fritz John and the Kuhn-Tucker theories, which give only necessary or sufficient conditions for optimality, but not both. 相似文献
In this paper we consider a major assembly composed of two or more subassemblies. The failure of any subassembly causes the major assembly to not function. Every failed subassembly is repaired or replaced. A total investment in stocks of spare components is to be distributed among the various subassemblies and the major assembly so as to provide the best possible customer service. This is a complicated problem: relevant factors are the failure rates, unit costs, and repair times of the various components. For the case of Poisson failures, a heuristic solution is developed which is a compromise between theoretical optimality and practical usefulness. 相似文献
This paper considers a problem of locating new facilities in the plane with respect to existing facilities, the locations of which are known. The problem consists of finding locations of new facilities which will minimize a total cost function which consists of a sum of costs directly proportional to the Euclidian distances among the new facilities, and costs directly proportional to the Euclidian distances between new and existing facilities. It is established that the total cost function has a minimum; necessary conditions for a mimumum are obtained; necessary and sufficient conditions are obtained for the function to be strictly convex (it is always convex); when the problem is “well structured,” it is established that for a minimum cost solution the locations of the new facilities will lie in the convex hull of the locations of the existing facilities. Also, a dual to the problem is obtained and interpreted; necessary and sufficient conditions for optimum solutions to the problem, and to its dual, are developed, as well as complementary slackness conditions. Many of the properties to be presented are motivated by, based on, and extend the results of Kuhn's study of the location problem known as the General Fermat Problem. 相似文献
A discrete time Collection Model is formulated, involving the completion of a touring objective on a network with stochastic node states. Heuristic touring strategies are constructed, there being as yet inadequate analytic results for its optimal solution. Effectiveness of the heuristics is assessed by comparing expected tour times under the heuristics with expected tour times given perfect information. A branch and bound algorithm is presented for computing the perfect information tour times. 相似文献