Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

Reversibility of Rings with Respect to the Jacobson Radical

Let R be a ring with identity and J(R) denote the Jacobson radical of R. A ring R is called J-reversible if for any a, \(b \in R\), \(ab = 0\) implies \(ba \in J(R)\). In this paper, we give some properties of J-reversible rings. We prove that some results of reversible rings can be extended to J-reversible rings for this general setting. We show that J-quasipolar rings, local rings, semicommutative rings, central reversible rings and weakly reversible rings are J-reversible. As an application it is shown that every J-clean ring is directly finite.     

Adjoining batch Markov arrival processes of a Markov chain

A batch Markov arrival process (BMAP) X* = (N, J) is a 2-dimensional Markov process with two components, one is the counting process N and the other one is the phase process J. It is proved that the phase process is a time-homogeneous Markov chain with a finite state-space, or for short, Markov chain. In this paper, a new and inverse problem is proposed firstly: given a Markov chain J, can we deploy a process N such that the 2-dimensional process X* = (N, J) is a BMAP? The process X* = (N, J) is said to be an adjoining BMAP for the Markov chain J. For a given Markov chain the adjoining processes exist and they are not unique. Two kinds of adjoining BMAPs have been constructed. One is the BMAPs with fixed constant batches, the other one is the BMAPs with independent and identically distributed (i.i.d) random batches. The method we used in this paper is not the usual matrix-analytic method of studying BMAP, it is a path-analytic method. We constructed directly sample paths of adjoining BMAPs. The expressions of characteristic (D _k , k = 0, 1, 2 · · ·) and transition probabilities of the adjoining BMAP are obtained by the density matrix Q of the given Markov chain J. Moreover, we obtained two frontal Theorems. We present these expressions in the first time.     

Packing measure of super separated iterated function systems

Let J be the limit set of an iterated function system in \(\mathbb {R}^d\) satisfying the open set condition. It is well known that the h-dimensional packing measure of J is positive and finite when h is given by Hutchinson’s formula. However, it may be hard to find a formula for the h-dimensional packing measure of J. We introduce the super separation condition and use it to reduce the problem of computing the packing measure to checking densities of a finite number of balls around each point in the limit set. We then use this fact to find formulas for the packing measure of a class of Cantor sets in \(\mathbb {R}\), a class of fractals based on regular convex polygons in \(\mathbb {R}^2\), and a class of fractals based on regular simplexes in \(\mathbb {R}^d\) for \(d \ge 3\).     

Finite derivation type for large ideals

In this paper we give a partial answer to the following question: does a large subsemigroup of a semigroup S with the finite combinatorial property finite derivation type (FDT) also have the same property? A positive answer is given for large ideals. As a consequence of this statement we prove that, given a finitely presented Rees matrix semigroup M[S;I,J;P], the semigroup S has FDT if and only if so does M[S;I,J;P].     

Semigroup graded algebras and graded PI-exponent

Let S be a semigroup. We study the structure of graded-simple S-graded algebras A and the exponential rate PIexp ^S-gr(A):= lim_n→∞ \(\sqrt[n]{{c_n^{S - gr}\left( A \right)}}\) of growth of codimensions c _n ^S-gr (A) of their graded polynomial identities. This is of great interest since such algebras can have non-integer PIexp ^S-gr(A) despite being finite dimensional and associative. In addition, such algebras can have a non-trivial Jacobson radical J(A). All this is in strong contrast with the case when S is a group since in the group case J(A) is trivial, PIexp ^S-gr(A) is always integer and, if the base field is algebraically closed, then PIexp ^S-gr(A) equals dimA. Without any restrictions on the base field F, we classify graded-simple S-graded algebras A for a class of semigroups S which is complementary to the class of groups. We explicitly describe the structure of J(A) showing that J(A) is built up of pieces of a maximal S-graded semisimple subalgebra of A which turns out to be simple. When F is algebraically closed, we get an upper bound for \({\overline {\lim } _{n \to \infty }}\sqrt[n]{{c_n^{S - gr}\left( A \right)}}\). If A/J(A) ≈ M ₂(F) and S is a right zero band, we show that this upper bound is sharp and PIexp ^S-gr(A) indeed exists. In particular, we present an infinite family of graded-simple algebras A with arbitrarily large non-integer PIexp ^S-gr(A).     

Structure of Abelian rings

Let R be a ring with identity. We use J(R); G(R); and X(R) to denote the Jacobson radical, the group of all units, and the set of all nonzero nonunits in R; respectively. A ring is said to be Abelian if every idempotent is central. It is shown, for an Abelian ring R and an idempotent-lifting ideal N ? J(R) of R; that R has a complete set of primitive idempotents if and only if R/N has a complete set of primitive idempotents. The structure of an Abelian ring R is completely determined in relation with the local property when X(R) is a union of 2; 3; 4; and 5 orbits under the left regular action on X(R) by G(R): For a semiperfect ring R which is not local, it is shown that if G(R) is a cyclic group with 2 ∈ G(R); then R is finite. We lastly consider two sorts of conditions for G(R) to be an Abelian group.     

Continuous time random walks and the Cauchy problem for the heat equation

We deal with anomalous diffusions induced by continuous time random walks - CTRW in ?ⁿ. A particle moves in ?ⁿ in such a way that the probability density function u(·, t) of finding it in region Ω of ?ⁿ is given by ∫_Ωu(x, t)dx. The dynamics of the diffusion is provided by a space time probability density J(x, t) compactly supported in {t ≥ 0}. For t large enough, u satisfies the equation

$$u\left( {x,t} \right) = \left[ {\left( {J - \delta } \right)*u} \right]\left( {x,t} \right)$$

, where δ is the Dirac delta in space-time. We give a sense to a Cauchy type problem for a given initial density distribution f. We use Banach fixed point method to solve it and prove that under parabolic rescaling of J, the equation tends weakly to the heat equation and that for particular kernels J, the solutions tend to the corresponding temperatures when the scaling parameter approaches 0.

     

Optimal strategy in <Emphasis Type="Italic">N</Emphasis>-policy production system with early set-up

This paper considers a production system in which an early set-up is possible. The machine(server) is turned off when there are no units(customers) to process. When the accumulated number of units reaches m(<N), the operator starts a set-up that takes a random time. After the set-up, if there are N or more units waiting for processing, the machine begins to process the units immediately. Otherwise the machine remains dormant in the system until the accumulated number of units reaches N. We model this system by M/G/1 queue with early set-up and N-policy. We use the decomposition property of a vacation queue to derive the distribution of the number of units in the system. We, then, build a cost model and develop a procedure to find the optimal values of (m,N) that minimize a linear average cost.     

Solving the uncapacitated multi-facility Weber problem by vector quantization and self-organizing maps

The uncapacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane and allocating the demands of n customers to these facilities with the minimum total transportation cost. This is a non-convex optimization problem and difficult to solve exactly. As a consequence, efficient and accurate heuristic solution procedures are needed. The problem has different types based on the distance function used to model the distance between the facilities and customers. We concentrate on the rectilinear and Euclidean problems and propose new vector quantization and self-organizing map algorithms. They incorporate the properties of the distance function to their update rules, which makes them different from the existing two neural network methods that use rather ad hoc squared Euclidean metric in their updates even though the problem is originally stated in terms of the rectilinear and Euclidean distances. Computational results on benchmark instances indicate that the new methods are better than the existing ones, both in terms of the solution quality and computation time.     

A discrete queue with double thresholds policy and its application to SVC systems

A discrete time Geo/Geo/1 queue with (m, N)-policy is considered in this paper. There are three operation periods being considered: high speed, low speed service periods and idle periods. With double thresholds policy, the server begins to take a working vacation when the number of customers is below m after a service and there is one customer in the system at least. What’s more, if the system becomes empty after a service, the server will take an ordinary vacation. Otherwise, high speed service continues if the number of customers still exceeds m after a service. At the vacation completion instant, servers resume their service if the quantity of customers exceeds N. Vacations can also be interrupted when the system accumulate customers more than the prefixed threshold. Using the quasi birth-death process and matrix-geometric solution methods, we derive the stationary queue length distribution and some system characteristics of interest. Based on these, we apply the queue to a virtual channel switching system and present various numerical experiments for the system. Finally, numerical results are offered to illustrate the optimal (m, N)-policy to minimize cost function and obtain practical consequence on the operation of double thresholds policy.     

Convergent expansions of the Bessel functions in terms of elementary functions

We consider the Bessel functions J _ν (z) and Y _ν (z) for R ν > ?1/2 and R z ≥ 0. We derive a convergent expansion of J _ν (z) in terms of the derivatives of \((\sin z)/z\), and a convergent expansion of Y _ν (z) in terms of derivatives of \((1-\cos z)/z\), derivatives of (1 ? e ^?z )/z and Γ(2ν, z). Both expansions hold uniformly in z in any fixed horizontal strip and are accompanied by error bounds. The accuracy of the approximations is illustrated with some numerical experiments.     

Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm

The Multi-commodity Capacitated Multi-facility Weber Problem (MCMWP) is concerned with locating I-capacitated facilities in the plane in order to satisfy the demands of J customers for K commodities so that the total transportation cost is minimized. We propose a Lagrangean relaxation scheme and a subgradient-like algorithm based on the relaxation of the capacity and commodity bundle constraints. The resulting subproblem is a variant of the well-known Multi-facility Weber Problem and it can be solved by using column generation and branch-and-price on an equivalent set covering formulation, which is accurate but extremely inefficient. Therefore, we devise different strategies to increase the efficiency. They mainly benefit from the effective usage of the lower and upper bounds on the optimal value of the Lagrangean subproblem. On the basis of extensive computational tests, we can say that they increase the efficiency considerably and result in accurate Lagrangean heuristics.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

(<Emphasis Type="Italic">Q,r</Emphasis>) Inventory Model with a Mixture of Lost Sales and Time-Weighted Backorders

This paper presents a stochastic inventory model for situations in which, during a stockout period, a fraction β of the demand is backordered and the remaining fraction 1 – β is lost. The model is suggested by the customers' different reactions to a stockout condition: during the stockout period, some patient customers wait until their demand is satisfied, while other impatient or urgent customers cannot wait and have to fill their demand from another source. The cost of a backorder is assumed to be proportional to the length of time for which the backorder exists, and a fixed penalty cost is incurred per unit of lost demand. Based on a heuristic treatment of a lot-size reorder-point policy, a mathematical model representing the average annual cost of operating the inventory system is developed. The optimal operating policy variables minimizing the average annual cost can be calculated iteratively. At the extremes β = 1 and β = 0, the model presented reduces to the usual backorders and lost sales case, respectively.     

Analysis of queues in a random environment with impatient customers

We study M/M/c queues (c = 1, 1 < c < ∞ and c = ∞) in a Markovian environment with impatient customers. The arrivals and service rates are modulated by the underlying continuous-time Markov chain. When the external environment operates in phase 2, customers become impatient. We focus our attention on the explicit expressions of the performance measures. For each case of c, the corresponding probability generating function and mean queue size are obtained. Several special cases are studied and numerical experiments are presented.     

An <Emphasis Type="Italic">L</Emphasis>-approach for packing (<Emphasis Type="Italic">ℓ</Emphasis>, <Emphasis Type="Italic">w</Emphasis>)-rectangles into rectangular and <Emphasis Type="Italic">L</Emphasis>-shaped pieces

This paper presents an approach using a recursive algorithm for packing (?, w)-rectangles into larger rectangular and L-shaped pieces. Such a problem has actual applications for non-guillotine cutting and pallet/container loading. Our motivation for developing the L-approach is based on the fact that it can solve difficult pallet loading instances. Indeed, it is able to solve all testing problems (more than 20 000 representatives of infinite equivalence classes of the literature), including the 18 hard instances unresolved by other heuristics. We conjecture that the L-approach always finds optimum packings of (?, w)-rectangles into rectangular pieces. Moreover, the approach may also be useful when dealing with cutting and packing problems involving L-shaped pieces.     

Approximating the Distribution of Customers in <Emphasis Type="Italic">M/E</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript><Emphasis Type="Italic">/s</Emphasis> Queues

Approximation formulae are suggested for the mean and variance of customers in M/E _n /s queues. It is shown that the distributions can be approximated by using the mean and variance to fit Gamma functions. A brief comment on the more general E _m /E _n /s case is given.     

Characteristics of positive reciprocal matrices in the analytic hierarchy process

Positive reciprocal matrices (PRMs) are the basic elements used by the Analytic Hierarchy Process (AHP) for resolving an important class of multi-criteria decision problems. A PRM, A=(a _ij ), is square with all a _ij >0 and a _ji =1/a _ij . We discuss characteristics of such matrices based on an analysis of both real-world and randomly generated sets.