Impact of information sharing and lead time on bullwhip effect and on-hand inventory

This work analyzes a two echelon (warehouse–retailer) serial supply chain to study the impact of information sharing (IS) and lead time on bullwhip effect and on-hand inventory. The customer demand at the retailer is assumed to be an autoregressive (AR(1)) process. Both the echelons use a minimum mean squared error (MMSE) model for forecasting lead time demand (LTD), and follow an adaptive base-stock inventory policy to determine their respective order quantities. For the cases of without IS and inter as well as intra echelon IS, expressions for the bullwhip effect and on-hand inventory for the warehouse are obtained, considering deterministic lead-time. The results are compared with the previous research work and an easy analysis of the various bullwhip effect expressions under different scenarios, is done to understand the impact of IS on the bullwhip effect phenomenon. It is shown that some part of bullwhip effect will always remain even after sharing both inter as well as intra echelon information. Further, with the help of a numerical example it is shown that the lead time reduction is more beneficial in comparison to the sharing of information in terms of reduction in the bullwhip effect phenomenon.     

An algorithmic approach to finding factorial designs with generalized minimum aberration

Factorial designs are arguably the most widely used designs in scientific investigations. Generalized minimum aberration (GMA) and uniformity are two important criteria for evaluating both regular and non-regular designs. The generation of GMA designs is a non-trivial problem due to the sequential optimization nature of the criterion. Based on an analytical expression between the generalized wordlength pattern and a uniformity measure, this paper converts the generation of GMA designs to a constrained optimization problem, and provides effective algorithms for solving this particular problem. Moreover, many new designs with GMA or near-GMA are reported, which are also (nearly) optimal under the uniformity measure.     

The rotor-router model on regular trees

The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible “escape sequences” for the ternary tree, that is, binary words a₁…an for which there exists a rotor configuration so that the kth chip escapes to infinity if and only if ak=1.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

Quasi-median hulls in Hamming space are Steiner hulls

A Hamming space Λⁿ consists of all sequences of length n over an alphabet Λ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u,v,w the sequence which in each coordinate attains either the majority coordinate from u,v,w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Λⁿ the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Λⁿ there exists a shortest realization within Λⁿ for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

The minimum speed for a blocking problem on the half plane

We consider a blocking problem: fire propagates on a half plane with unit speed in all directions. To block it, a barrier can be constructed in real time, at speed σ. We prove that the fire can be entirely blocked by the wall, in finite time, if and only if σ>1. The proof relies on a geometric lemma of independent interest. Namely, let K⊂R² be a compact, simply connected set with smooth boundary. We define dK(x,y) as the minimum length among all paths connecting x with y and remaining inside K. Then dK attains its maximum at a pair of points both on the boundary of K.     

Harmonious order of graphs

We consider the following generalization of the concept of harmonious graphs. Given a graph G=(V,E) and a positive integer t≥|E|, a function is called a t-harmonious labeling of G if is injective for t≥|V| or surjective for t<|V|, and for all distinct edges vw,xy∈E(G). Then the smallest possible t such that G has a t-harmonious labeling is named the harmonious order of G. We determine the harmonious order of some non-harmonious graphs, such as complete graphs K_n (n≥5), complete bipartite graphs K_m,n (m,n>1), even cycles C_n, some powers of paths , disjoint unions of triangles nK₃ (n even). We also present some general results concerning harmonious order of the Cartesian product of two given graphs or harmonious order of the disjoint union of copies of a given graph. Furthermore, we establish an upper bound for harmonious order of trees.     

Non-separating trees in connected graphs

Let T be any tree of order d≥1. We prove that every connected graph G with minimum degree d contains a subtree T^′ isomorphic to T such that G−V(T^′) is connected.     

一类非齐次树上的Shannon-McMillan定理

通过构造适当的辅助鞅差序列,利用鞅差序列的收敛定理给出了一类特殊非齐次树上具有a.e.收敛性质的Shannon-M cM illan定理.