The traditional supply chain network planning problem is stated as a multi-period resource allocation model involving 0-1 discrete strategic decision variables. The MIP structure of this problem makes it fairly intrac...
详细信息
The traditional supply chain network planning problem is stated as a multi-period resource allocation model involving 0-1 discrete strategic decision variables. The MIP structure of this problem makes it fairly intractable for practical applications, which involve multiple products, factories, warehouses and distribution centres (DCs). The same problem formulated and studied under uncertainty makes it even more intractable. In this paper we consider two related modelling approaches and solution techniques addressing this issue. The first involves scenario analysis of solutions to "wait and see" models and the second involves a two-stage integer stochastic programming (ISP) representation and solution;of the same problem. We show how the results from the former can be used in the solution of the latter model. We also give some computational results based on serial and parallel implementations of the algorithms. (C) 2000 Elsevier Science B.V. All rights reserved.
Conventional methods for state space exploration are limited to the analysis of small systems because they suffer from excessive memory and computational requirements. We have developed a new dynamic probabilistic sta...
详细信息
Conventional methods for state space exploration are limited to the analysis of small systems because they suffer from excessive memory and computational requirements. We have developed a new dynamic probabilistic state exploration algorithm which addresses this problem for general, structurally unrestricted state spaces. Our method has a low state omission probability and low memory usage that is independent of the length of the state vector. In addition, the algorithm can be easily parallelised. This combination of probability and parallelism enables us to rapidly explore state spaces that are an order of magnitude larger than those obtainable using conventional exhaustive techniques. We derive a performance model of this new algorithm in order to quantify its benefits in terms of distributed run-time, speedup and efficiency. We implement our technique on a distributed-memory parallel computer acid demonstrate results which compare favourably with the performance model. Finally, we discuss suitable choices for the three hash functions upon which our algorithm is based. (C)2000 Elsevier Science B.V. All rights reserved.
List ranking finds for each cell in a linked list the number of cells that precede it in the list. This paper presents a work-efficient list-ranking algorithm for fine-grained processor arrays. This algorithm runs on ...
详细信息
List ranking finds for each cell in a linked list the number of cells that precede it in the list. This paper presents a work-efficient list-ranking algorithm for fine-grained processor arrays. This algorithm runs on an array of n/ log(2) n processors with the expected run-time of O(log(2) n). As list ranking is highly communication intensive, the proposed algorithm is able to reduce communication cost among processors by assigning sublists, instead of arbitrary cells, of a linked list to each processor. The proposed algorithm is also capable of keeping all processors busy during the whole list-ranking process in order to utilize all processors efficiently. (C) 2000 Elsevier Science Inc. All rights reserved.
We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many archite...
详细信息
We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many architectures and has optimal cost for the RAM and EREW PRAM. (C) 2000 Academic Press.
In this paper, we present an efficient parallel algorithm for finding a set of maximal elements on the xy-plane, which is based on a Two-Dimensional array of processors with Optical Pipelined Bus System (2DMPBS). Our ...
详细信息
ISBN:
(纸本)1880843323
In this paper, we present an efficient parallel algorithm for finding a set of maximal elements on the xy-plane, which is based on a Two-Dimensional array of processors with Optical Pipelined Bus System (2DMPBS). Our parallel algorithm for solving the two dimensional maximal elements problem on the 2DMPBS model runs in O (log n) time, where n is the number of elements on the xy-plane.
We first propose for digital surfaces a notion analogous to the notion of strong homotopy which exists in 3D [1]. We present an associated parallel thinning algorithm. The surface of an object composed of voxels is a ...
详细信息
ISBN:
(纸本)3540413960
We first propose for digital surfaces a notion analogous to the notion of strong homotopy which exists in 3D [1]. We present an associated parallel thinning algorithm. The surface of an object composed of voxels is a set of surfels (faces of voxels) which is the boundary between this object and its complementary. But this representation is not the classical one to visualize and to work on 3D objects, in frameworks like Computer Assisted Geometric Design (CAGD). For this reason we propose a method for passing efficiently from a representation to the other. More precisely, we present a three-step algorithm to polyhedrize the boundary of a voxel object which uses the parallel thinning algorithm presented above. This method is specifically adapted to digital objects and is much more efficient than such existing methods [12]. Some examples are shown, and a method to make the reverse operation (discretization) is briefly presented.
The temperature profile and infrared exitance of a terrain object were calculated by combining domain decomposition method with monte carlo method. The object with 3-D complex shape can be divided into several regular...
详细信息
The temperature profile and infrared exitance of a terrain object were calculated by combining domain decomposition method with monte carlo method. The object with 3-D complex shape can be divided into several regular sub-zones, which are described by corresponding coordinate systems. The heat transfer within every sub-zone was calculated by control volume method and the heat transfer among sub-zones calculated by thermal mesh method. When the radiative transfer coefficient (RTC) was calculated by means of monte carlo method,the complication of surface radiative characteristic could be taken into account. By application of the RTC, a complicated calculation can be divided into several relatively easy sub-calculations, and the calculation in several different wavelength bands can be solved parallelly. Tn space-zone (computing zone),the object was divided into a number of domains, then several processors were used simultaneously.
In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m＋hlog ...
详细信息
In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m＋hlog h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p ＋ hlogp) for the general parallel best-first B&B algorithm in PRAM CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p＋H＋ (H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one az p ＝ max{he,r}, where ε ＝ 1/logh, and r is the largest branch number of the nodes in the state-space tree.
We study efficient parallel solutions to the problem of selectingrelements at specified ranks from a set of n arbitrary elements, known asmultiselection, in a hypercube withp<nprocessors. We propose two parallel al...
详细信息
We study efficient parallel solutions to the problem of selectingrelements at specified ranks from a set of n arbitrary elements, known asmultiselection, in a hypercube withpparallel algorithms based on different approaches, where one requires processors to operate in the SIMD mode, and the other in the MIMD mode. Our SIMD algorithm runs inO(nϵmin{r, logp}) time whenp=n1−rfor any 0<ϵ<1, which is cost-optimal whenr≥p. With the same number of processors, our MIMD algorithm runs inO(nϵlogr) time and is cost-optimal for any values ofr. Both algorithms are more efficient than straightforward solutions and that of direct simulation of the optimal EREW algorithm.
暂无评论