In some applications a minimum cost transportation model arises where supplies are fixed while demands may simultaneously vary. In this paper we analyse the structure of such a model and propose several techniques to ...
详细信息
In some applications a minimum cost transportation model arises where supplies are fixed while demands may simultaneously vary. In this paper we analyse the structure of such a model and propose several techniques to describe its behaviour. Our approach is founded on the concept of optimal region, i.e., the subset of demand vectors where a given basic tree is optimal. The proposed algorithm consists in different pivoting strategies designed to: 1. build up a minimal list of basic trees such that the associated optimal regions cover the set of feasible demand vectors;2. analyse the effects of either opening a new supplier or closing an existing one;3. suitably treat the dual degenerate case by building up a minimal representation of every maximal region where the optimal value is linear in the demand vector. Computational complexity is discussed and numerical examples are given. (C) 2002 Elsevier Science B.V. All rights reserved.
The K shortest paths problem has been extensively studied for many years. Efficient methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several proble...
详细信息
The K shortest paths problem has been extensively studied for many years. Efficient methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several problems in different areas, for example in relation with routing in dynamic networks. However. the K shortest hyperpaths problem has not yet been investigated. In this paper we present procedures for finding the K shortest hyperpaths in a directed hypergraph. This is done by extending existing algorithms for K shortest loopless paths. Computational experiments on the proposed procedures are performed, and applications in transportation. planning and combinatorial optimization are discussed. (C) 2003 Elsevier Ltd. All rights reserved.
In this paper, we study the single commodity flow problem, optimizing two objectives simultaneously. We propose a method that finds all the efficient extreme points in the objective space. This method is based on the ...
详细信息
In this paper, we study the single commodity flow problem, optimizing two objectives simultaneously. We propose a method that finds all the efficient extreme points in the objective space. This method is based on the well known method of Lee and Pulat, which also computes some efficient points of the objective space that are not extreme points. Our alternative method corrects this particularity by using the idea of adjacency among efficient extreme points in the objective space and introduces computational improvements that are shown in an experimental study. (C) 2000 Elsevier Science B.V. All rights reserved.
We consider the multiple bottleneck assignment problem which subsumes the well known min-sum and bottleneck assignment problems. The problem arises in the context of flexible manufacturing systems, where the objective...
详细信息
We consider the multiple bottleneck assignment problem which subsumes the well known min-sum and bottleneck assignment problems. The problem arises in the context of flexible manufacturing systems, where the objective is to maximize the throughput of a production system with several how shops, running in parallel, to produce a product. The problem is known to be strongly NP-hard. We propose a new algorithm for obtaining sharp lower bounds to the optimal objective value. Computational experiments are conducted to show the improvement over existing methods. (C) 1999 Elsevier Science B.V. All rights reserved.
In this paper, we present an alternative multi-stage generalized upper bounds (GUB) based approach for detecting an embedded pure network structure in an LP problem. In order to identify a GUB structure, we use two di...
详细信息
In this paper, we present an alternative multi-stage generalized upper bounds (GUB) based approach for detecting an embedded pure network structure in an LP problem. In order to identify a GUB structure, we use two different approaches;the first is based on the notion of Markowitz merit count and the second exploits independent sets in the corresponding graphs. Our computational experiments show that the multi-stage GUB algorithm based on these approaches performs favourably when compared with other well known algorithms.
We propose a neu method based on minimum mean cycle cancelling for multicommodity flow problems with separable convex cost ruling out saturated capacities. This method is inspired by the cycle cancelling method first ...
详细信息
We propose a neu method based on minimum mean cycle cancelling for multicommodity flow problems with separable convex cost ruling out saturated capacities. This method is inspired by the cycle cancelling method first worked out by Goldberg and Tarjan for minimum cost circulations (A.V. Goldberg, R.E. Tarjan, Finding minimum-cost circulation by cancelling negative cycles, JACM 36 (4), 1989, pp. 873-886). Convergence of the method is formally proved and a variant with a more flexible selection of cycles is proposed. Also. we report some computational experience on the message routing problem in telecommunication networks using actual and randomly generated networks. (C) 2000 Elsevier Science B.V. All rights reserved.
The trade-off between false sharing elimination and aggregation in distributed shared memory (DSM) systems has a major effect on their performance. Some studies in this area show that fine grain access is advantageous...
详细信息
The trade-off between false sharing elimination and aggregation in distributed shared memory (DSM) systems has a major effect on their performance. Some studies in this area show that fine grain access is advantageous, while others advocate the use of large coherency units. One way to resolve the trade-off is to dynamically adapt the granularity to the application memory access pattern. In this paper, we propose a novel technique for implementing multiple sharing granularities over page-based DSMS. We present protocols for efficient switching between small and large sharing units during runtime. We show that applications may benefit from adapting the memory sharing to the memory access pattern, using both coarse grain sharing and fine grain sharing interchangeably in different stages of the computation. Our experiments show a substantial improvement in the performance using adapted granularity level over using a fixed granularity level. (C) 2000 Elsevier Science Inc. All rights reserved.
In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with ...
详细信息
In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The;disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.
Skid-trail locations directly influence the economics and environmental impacts of harvesting operations. Typically, field managers design skid-trail networks manually based on field observations of vegetation and ter...
详细信息
Skid-trail locations directly influence the economics and environmental impacts of harvesting operations. Typically, field managers design skid-trail networks manually based on field observations of vegetation and terrain conditions. We designed a model to automatically design skid-trail networks to reduce skidding costs and soil disturbances. The model simulates tree-bunch locations, creates a feasible skid-trail network across the harvest unit, estimates skidding cost and soil recovery cost for each feasible skid-trail segment, and finds the network design that connects each tree bunch to landings while reducing skidding and soil recovery costs. The model was applied to a 24-ha hypothetical harvest unit to test its ability to design optimal networks under different scenarios representing conditions commonly found in timber harvesting operations (e.g., skidding pattern, uneven volume distribution, skidding obstacles, and different weights given to skidding and soil recovery costs). It was also applied to an actual 124-ha harvest unit to evaluate its ability to design skid-trail networks considering more realistic conditions with multiple design factors. The model successfully created optimized skid-trail networks for all scenarios considered, and results suggest that it provides a useful tool to help forest engineers and field managers design economically efficient and environmentally sound ground-based timber harvesting operations.
The explosive growth of the Web, the increasing popularity of PCs and the advances in high-speed network access have brought distributed computing into the mainstream. To simplify network programming and to realize co...
详细信息
The explosive growth of the Web, the increasing popularity of PCs and the advances in high-speed network access have brought distributed computing into the mainstream. To simplify network programming and to realize component-based software architecture, distributed object models have emerged as standards. One of those models is distributed component object model (DCOM) which is a protocol that enables software components to communicate directly over a network in a reliable, and efficient manner. In this paper, we investigate an aspect of DCOM concerning software architecture and security mechanism. Also, we describe the concept of role-based access control (RBAC) which began with multi-user and multi-application on-line systems pioneered in the 1970s. And we investigate how we can enforce the role-based access control as a security provider within DCOM, specially in access security policy. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论