In this paper, a heuristic procedure is proposed for the facility location problem with general Bernoulli demands. This is a discrete facility location problem with stochastic demands that can be formulated as a two-stage stochastic program with recourse. In particular, facility locations and customer assignments must be decided here and now, i.e., before knowing the customers who will actually require to be served. In a second stage, service decisions are made according to the actual requests. The heuristic proposed consists of a greedy randomized adaptive search procedure followed by a path relinking. The heterogeneous Bernoulli demands make prohibitive the computational effort for evaluating feasible solutions. Thus the expected cost of a feasible solution is simulated when necessary. The results of extensive computational tests performed for evaluating the quality of the heuristic are reported, showing that high-quality feasible solutions can be obtained for the problem in fairly small computational times.
We develop a new randomization-based general-purpose method for the computation of the interval availability
distribution of systems modeled by continuous-time Markov chains (CTMCs). The basic idea of
the new method is the use of a randomization construct with different randomization rates for up and down
states. The new method is numerically stable and computes the measure with well-controlled truncation error.
In addition, for large CTMC models, when the maximum output rates from up and down states are significantly
different, and when the interval availability has to be guaranteed to have a level close to one, the new
method is significantly or moderately less costly in terms of CPU time than a previous randomization-based
state-of-the-art method, depending on whether the maximum output rate from down states is larger than the
maximum output rate from up states, or vice versa. Otherwise, the new method can be more costly, but a relatively
inexpensive for large models switch of reasonable quality can be easily developed to choose the fastest
method. Along the way, we show the correctness of a generalized randomization construct, in which arbitrarily
different randomization rates can be associated with different states, for both finite CTMCs with infinitesimal
generator and uniformizable CTMCs with denumerable state space.
This paper is concerned with the computation of the interval availability (proportion of time in a time interval in which the system is up) distribution of a fault-tolerant system modeled by a finite (homogeneous) continuous-time Markov chain (CTMC). General-purpose methods for performing that computation tend to be very expensive when the CTMC and the time interval are large. Based on a previously available method
(regenerative transformation) for computing the interval availability complementary distribution, we develop a method called bounding regenerative transformation for the computation of bounds for that measure. Similar to regenerative transformation, bounding regenerative transformation requires the selection of a regenerative state. The method is targeted at a certain class of models, including both exact and bounding failure/repair models of fault-tolerant systems with increasing structure function, with exponential failure and repair time distributions and repair in every state with failed components having failure rates much smaller than repair rates (F/R models), with a “natural” selection for the regenerative state. The method is numerically stable and computes the bounds with well-controlled error. For models in the targeted class and the natural selection for the regenerative state, computational cost should be traded off with bounds tightness through a control parameter. For large models in the class, the version of the method that should have the smallest computational cost should have small computational cost relative to the model size if the value above which the interval availability
has to be guaranteed to be is close to 1. In addition, under additional conditions satisfied by F/R models, the bounds obtained with the natural selection for the regenerative state by the version that should have the smallest computational cost seem to be tight for all time intervals or not small time intervals, depending on whether the initial probability distribution of the CTMC is concentrated in the regenerative state or not.