Single item lot-sizing problem for a warm/cold process with immediate lost sales

We consider the dynamic lot-sizing problem with finite capacity and possible lost sales for a process that could be kept warm at a unit variable cost for the next period t + 1 only if more than a threshold value Q_t has been produced and would be cold, otherwise. Production with a cold process incurs a fixed positive setup cost, K_t and setup time, S_t, which may be positive. Setup costs and times for a warm process are negligible. We develop a dynamic programming formulation of the problem, establish theoretical results on the structure of the optimal production plan in the presence of zero and positive setup times with Wagner–Whitin-type cost structures. We also show that the solution to the dynamic lot-sizing problem with lost sales are generated from the full commitment production series improved via lost sales decisions in the presence of a warm/cold process.     

A two-echelon inventory model with lost sales

This paper considers a single-item, two-echelon, continuous-review inventory model. A number of retailers have their stock replenished from a central warehouse. The warehouse in turn replenishes stock from an external supplier. The demand processes on the retailers are independent Poisson. Demand not met at a retailer is lost. The order quantity from each retailer on the warehouse and from the warehouse on the supplier takes the same fixed value Q, an exogenous variable determined by packaging and handling constraints. Retailer i follows a (Q, R_i) control policy. The warehouse operates an (SQ, (S − 1)Q) policy, with non-negative integer S. If the warehouse is in stock then the lead time for retailer i is the fixed transportation time L_i from the warehouse to that retailer. Otherwise retailer orders are met, after a delay, on a first-come first-served basis. The lead time on a warehouse order is fixed. Two further assumptions are made: that each retailer may only have one order outstanding at any time and that the transportation time from the warehouse to a retailer is not less than the warehouse lead time. The performance measures of interest are the average total stock in the system and the fraction of demand met in the retailers. Procedures for determining these performance measures and optimising the behaviour of the system are developed.     

Optimal and near-optimal policies for lost sales inventory models with at most one replenishment order outstanding

In this paper we use policy-iteration to explore the behaviour of optimal control policies for lost sales inventory models with the constraint that not more than one replenishment order may be outstanding at any time. Continuous and periodic review, fixed and variable lead times, replenishment order sizes which are constrained to be an integral multiple of some fixed unit of transfer and service level constraint models are all considered. Demand is discrete and, for continuous review, assumed to derive from a compound Poisson process. It is demonstrated that, in general, neither the best (s, S) nor the best (r, Q) policy is optimal but that the best policy from within those classes will have a cost which is generally close to that of the optimal policy obtained by policy iteration. Finally, near-optimal computationally-efficient control procedures for finding (s, S) and (r, Q) policies are proposed and their performance illustrated.     

The complexity of the fixed point property

It is NP-complete to determine whether a given ordered set has a fixed point free order-preserving self-map. On the way to this result, we establish the NP-completeness of a related problem: Given ordered sets P and Q with t-tuples (p ₁, ... , p _t) and (q ₁, ... , q _t) from P and Q respectively, is there an order-preserving map f: P→Q satisfying f(p _i)≥q _i for each i=1, ... , t?     

An economic production quantity model with a positive resetup point under random demand

In this paper, an extended economic production quantity (EPQ) model is investigated, where demand follows a random process. This study is motivated by an industrial case for precision machine assembly in the machinery industry. Both a positive resetup point s and a fixed lot size Q are implemented in this production control policy. To cope with random demand, a resetup point, i.e., the lowest inventory level to start the production, is adapted to minimize stock shortage during the replenishment cycle. The considered cost includes setup cost, inventory carrying cost, and shortage cost, where shortage may occur at the production stage and/or at the end of one replenishment cycle. Under some mild conditions, the expected cost per unit time can be shown to be convex with respect to decision parameters s and Q. Further computational study has demonstrated that the proposed model outperforms the classical EPQ when demand is random. In particular, a positive resetup point contributes to a significant portion of this cost savings when compared with that in the classical lot sizing policy.     

Some path properties of generalized Lévy sheet

Let X(t) be an N parameter generalized Lévy sheet taking values in ℝ^d with a lower index α, ℜ = {(s, t] = ∏ _i=1 ^N (s _i, t _i], s _i < t _i}, E(x, Q) = {t ∈ Q: X(t) = x}, Q ∈ ℜ be the level set of X at x and X(Q) = {x: ∃t ∈ Q such that X(t) = x} be the image of X on Q. In this paper, the problems of the existence and increment size of the local times for X(t) are studied. In addition, the Hausdorff dimension of E(x, Q) and the upper bound of a uniform dimension for X(Q) are also established.     

A new family of Padé-type approximants in

This paper gives the definition and some properties of a new family of Padé-type approximants (PTA) for k-variate formal power series (FPS). These PTA have the form P(t)/Q(t) where Q(t) = Π^r_{i = 0}(1 ? x(i)·t), {x(i), 0 ? i ? r} being a given set of points in

, and x·t is the scalar product of x and t in

. Some results about the approximation order, the unicity and some invariance properties of these PTA are proved together with a convergence result when the FPS is defined by a Stieltjes integral.     

A distance-labelling problem for hypercubes

Let i₁≥i₂≥i₃≥1 be integers. An L(i₁,i₂,i₃)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…} such that |?(u)−?(v)|≥i_t for any u,v∈V with d(u,v)=t, t=1,2,3, where d(u,v) is the distance in G between u and v. The integer ?(v) is called the label assigned to v under ?, and the difference between the largest and the smallest labels is called the span of ?. The problem of finding the minimum span, λ_i1,i2,i3(G), over all L(i₁,i₂,i₃)-labellings of G arose from channel assignment in cellular communication systems, and the related problem of finding the minimum number of labels used in an L(i₁,i₂,i₃)-labelling was originated from recent studies on the scalability of optical networks. In this paper we study the L(i₁,i₂,i₃)-labelling problem for hypercubes Q_d (d≥3) and obtain upper and lower bounds on λ_i1,i2,i3(Q_d) for any (i₁,i₂,i₃).     

Parallel queuing systems with and without decentralized server reallocation — A simulation study

This paper describes the results of an initial exploratory research effort on the subject of the dynamic reallocation of servers in a group of parallel queuing systems under decentralized control. Each queuing system is described as being (M/E_k/c_i,t): (FCFS/∞/∞) where t = 1,.., ∞ and i = 1,..., I. Server reallocation is handled by a (G^(b)/G/C): (FCS/C/K) system — where C = Σ_t=1^∞Σ_i=1^Ic_i,t and K is an unknown constant — located at a higher level than the group members. The customers of the latter system are requests for servers independently generated by identical heuristic event-triggered operating policies at each of the lower level systems. These local policies are of the stochastic review, relative control number type. Performance is measured by means of a variety of criteria from the viewpoint of the group as a whole (global) as well as an individual queuing system (local). Results of experiments using a simulation model confirmed the null hypothesis that the customer service behaviour of a group that shared servers was significantly different from the behaviour of a control group that did not share servers.     

The minimum increment of f-divergences given total variation distances

Let (P _i , Q _i ), i = 0, 1, be two pairs of probability measures defined on measurable spaces (Ω _i ,F _i ) respectively. Assume that the pair (P₁, Q₁) is more informative than (P₀,Q₀) for testing problems. This amounts to say that If (P₁,Q₁) ≥ If (P₀,Q₀), where If (·, ·) is an arbitrary f-divergence. We find a precise lower bound for the increment of f-divergences I_f(P₁,Q₁) ? I_f(P₀,Q₀) provided that the total variation distances ||Q₁ ? P₁|| and ||Q₀ ? P₀|| are given. This optimization problem can be reduced to the case where P₁ and Q₁ are defined on the space consisting of four points, and P₀ and Q₀ are obtained from P₁ and Q₁ respectively by merging two of these four points. The result includes the well-known lower and upper bounds for I_f(P,Q) given ||Q ? P||.     

Value iteration in countable state average cost Markov decision processes with unbounded costs

We deal with countable state Markov decision processes with finite action sets and (possibly) unbounded costs. Assuming the existence of an expected average cost optimal stationary policyf, with expected average costg, when canf andg be found using undiscounted value iteration? We give assumptions guaranteeing the convergence of a quantity related tong?Ν _n (i), whereΝ _n (i) is the minimum expectedn-stage cost when the process starts in statei. The theory is applied to a queueing system with variable service rates and to a queueing system with variable arrival parameter.     

Optimal replacement policies with minimal repair and age-dependent costs

In this paper, we study a modified minimal repair/replacement problem that is formulated as a Markov decision process. The operating cost is assumed to be a nondecreasing function of the system's age. The specific maintenance actions for a manufacturing system to be considered are whether to have replacement, minimal repair or keep it operating. It is shown that a control limit policy, or in particular a (t, T) policy, is optimal over the space of all possible policies under the discounted cost criterion. A computational algorithm for the optimal (t, T) policy is suggested based on the total expected discounted cost.     

The strong Markov property for canonical Wiener processes

A noncommutative analog of the concept of Markov time is formulated, in association with a canonical Wiener process (P, Q) [4]. For such a Markov time T, the quantities P_T(t) = P(t + T) ? P(T), Q_T(t) = Q(t + T) ? Q(T) can be defined using spectral integrals with operator-valued integrands, and constitute a new canonical Wiener process (P_T, Q_T), which is independent of the analog of the σ-field of events generated by the process up to the Markov time.     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

Simple heuristics for push and pull remanufacturing policies

Inventory policies for joint remanufacturing and manufacturing have recently received much attention. Most efforts, though, were related to (optimal) policy structures and numerical optimization, rather than closed form expressions for calculating near optimal policy parameters. The focus of this paper is on the latter. We analyze an inventory system with unit product returns and demands where remanufacturing is the cheaper alternative for manufacturing. Manufacturing is also needed, however, since there are less returns than demands. The cost structure consists of setup costs, holding costs, and backorder costs. Manufacturing and remanufacturing orders have non-zero lead times. To control the system we use certain extensions of the familiar (s, Q) policy, called push and pull remanufacturing policies. For all policies we present simple, closed form formulae for approximating the optimal policy parameters under a cost minimization objective. In an extensive numerical study we show that the proposed formulae lead to near-optimal policy parameters.     

Paths and edge-connectivity in graphs III. Six-terminalk paths

Suppose thatk ≥ 1 is an odd integer, (s ₁,t ₁),..., (s _k> ,t _k ) are pairs of vertices of a graphG andλ(s _i ,t _i ) is the maximal number of edge-disjoint paths betweens _i andt _i . We prove that ifλ(s _i ,t _i )≥ k (1≤ i ≤ k) and |{s ₁,...s _k ,t ₁,...,t _k }| ≤ 6, then there exist edge-disjoint pathsP ₁,...,P _k such thatP _i has endss _i andt _i (1≤ i ≤ k).     

A sufficient condition for a graph to be weakly k-linked

For a pair (s, t) of vertices of a graph G, let λ_G(s, t) denote the maximal number of edge-disjoint paths between s and t. Let (s₁, t₁), (s₂, t₂), (s₃, t₃) be pairs of vertices of G and k > 2. It is shown that if λ_G(s_i, t_i) ≥ 2k + 1 for each i = 1, 2, 3, then there exist 2k + 1 edge-disjoint paths such that one joins s₁ and t₁, another joins s₂ and t₂ and the others join s₃ and t₃. As a corollary, every (2k + 1)-edge-connected graph is weakly (k + 2)-linked for k ≥ 2, where a graph is weakly k-linked if for any k vertex pairs (s_i, t_i), 1 ≤ i ≤ k, there exist k edge-disjoint paths P₁, P₂,…, P_k such that P_i joins s_i and t_i for i = 1, 2,…, k.     

Resolvable perfect cyclic designs

Let k, λ, and υ be positive integers. A perfect cyclic design in the class PD(υ, k, λ) consists of a pair (Q, B) where Q is a set with |Q| = υ and B is a collection of cyclically ordered k-subsets of Q such that every ordered pair of elements of Q are t apart in exactly λ of the blocks for t = 1, 2, 3,…, k?1. To clarify matters the block [a₁, a₂, …, a_k] has cyclic order a₁ < a₂ < a₃ … < a_k < a₁ and a_i and a_i+1 are said to be t apart in the block where i + t is taken mod k. In this paper we are interested only in the cases where λ = 1 and υ ≡ 1 mod k. Such a design has $\text{υ(υ ? 1)}\text{k}$ blocks. If the blocks can be partitioned into υ sets containing $\text{(υ ? 1)}\text{k}$ pairwise disjoint blocks the design is said to be resolvable, and any such partitioning of the blocks is said to be a resolution. Any set of $\text{υ ? 1)}\text{k}$ pairwise disjoint blocks together with a singleton consisting of the only element not in one of the blocks is called a parallel class. Any resolution of a design yields υ parallel classes. We denote by RPD(υ, k, 1) the class of all resolvable perfect cyclic designs with parameters υ, k, and 1. Associated with any resolvable perfect cyclic design is an orthogonal array with k + 1 columns and υ rows with an interesting conjugacy property. Also a design in the class RPD(υ, k, 1) is constructed for all sufficiently large υ with υ ≡ 1 mod k.