A note on the performance of limited entry queuing systems

This note compares the performance of a queuing system in which customers can enter service only at multiples of the service time to the ordinary counterpart for both G/D/1 and M/D/1 systems. We show that the two modes of operation differ by at most one customer at any point in time. We give motivation for the use of a limited entry queuing system as a model for use in material handling analysis.     

A recursive method for the F-policy G/M/1/K queueing system with an exponential startup time

This paper deals with the optimal control of a finite capacity G/M/1 queueing system combined the F-policy and an exponential startup time before start allowing customers in the system. The F-policy queueing problem investigates the most common issue of controlling arrival to a queueing system. We provide a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining interarrival time, to develop the steady-state probability distribution of the number of customers in the system. We illustrate a recursive method by presenting three simple examples for exponential, 3-stage Erlang, and deterministic interarrival time distributions, respectively. A cost model is developed to determine the optimal management F-policy at minimum cost. We use an efficient Maple computer program to determine the optimal operating F-policy and some system performance measures. Sensitivity analysis is also studied.     

Concerning the regularity of the anisotropic porous medium equation

We show that a locally bounded nonnegative weak solution of the anisotropic porous media equation is locally continuous. The proof is based on DiBenedetto's technique called intrinsic scaling; by choosing an appropriate geometry one can deduce energy and logarithmic estimates from which one can implement an iterative method to obtain the regularity result.     

Dynamic lot-sizing in sequential online retail auctions

Retailers often conduct non-overlapping sequential online auctions as a revenue generation and inventory clearing tool. We build a stochastic dynamic programming model for the seller’s lot-size decision problem in these auctions. The model incorporates a random number of participating bidders in each auction, allows for any bid distribution, and is not restricted to any specific price-determination mechanism. Using stochastic monotonicity/stochastic concavity and supermodularity arguments, we present a complete structural characterization of optimal lot-sizing policies under a second order condition on the single-auction expected revenue function. We show that a monotone staircase with unit jumps policy is optimal and provide a simple inequality to determine the locations of these staircase jumps. Our analytical examples demonstrate that the second order condition is met in common online auction mechanisms. We also present numerical experiments and sensitivity analyses using real online auction data.     

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.     

Limit-point type solutions of nonlinear differential equations

We are concerned with the nonexistence of L²-solutions of a nonlinear differential equation x″=a(t)x+f(t,x). By applying technique similar to that exploited by Hallam [SIAM J. Appl. Math. 19 (1970) 430-439] for the study of asymptotic behavior of solutions of this equation, we establish nonexistence of solutions from the class L²(t₀,∞) under milder conditions on the function a(t) which, as the examples show, can be even square integrable. Therefore, the equation under consideration can be classified as of limit-point type at infinity in the sense of the definition introduced by Graef and Spikes [Nonlinear Anal. 7 (1983) 851-871]. We compare our results to those reported in the literature and show how they can be extended to third order nonlinear differential equations.     

Optimal control of the N policy M/G/1 queueing system with server breakdowns and general startup times

This paper deals with an N policy M/G/1 queueing system with a single removable and unreliable server whose arrivals form a Poisson process. Service times, repair times, and startup times are assumed to be generally distributed. When the queue length reaches N(N ? 1), the server is immediately turned on but is temporarily unavailable to serve the waiting customers. The server needs a startup time before providing service until there are no customers in the system. We analyze various system performance measures and investigate some designated known expected cost function per unit time to determine the optimal threshold N at a minimum cost. Sensitivity analysis is also studied.     

On the probability of abandonment in queues with limited sojourn and waiting times

Consider the Geo/Geo/1 queue with impatient customers and let X reflect the patience distribution. We show that systems with a smaller patience distribution X in the convex-ordering sense give rise to fewer abandonments (due to impatience), irrespective of whether customers become patient when entering the service facility.     

Dynamics of 2-worker bucket brigade assembly line with blocking and instantaneous walk-back

We analyze the dynamics of 2-worker m-stations bucket brigade assembly lines where the velocities of the workers on the stations are arbitrary, albeit fixed constants over each station. We provide a complete characterization of the dynamics under blocking and instantaneous walk-back.     

On bidding for a fixed number of items in a sequence of auctions

We consider the problem of a firm (“the buyer”) that must acquire a fixed number (L) of items. The buyer can acquire these items either at a fixed buy-it-now price in the open market or by participating in a sequence of N > L auctions. The objective of the buyer is to minimize his expected total cost for acquiring all L items. We model this problem as a Markov Decision Process and establish monotonicity properties for the optimal value function and the optimal bidding strategies.     

Block sparse recovery via mixed l 2/l 1 minimization

We consider efficient methods for the recovery of block sparse signals from underdetermined system of linear equations. We show that if the measurement matrix satisfies the block RIP with δ2s 0.4931, then every block s-sparse signal can be recovered through the proposed mixed l2 /l1 -minimization approach in the noiseless case and is stably recovered in the presence of noise and mismodeling error. This improves the result of Eldar and Mishali (in IEEE Trans. Inform. Theory 55: 5302-5316, 2009). We also give another sufficient condition on block RIP for such recovery method: δs 0.307.     

A tight colored Tverberg theorem for maps to manifolds

We prove that any continuous map of an N-dimensional simplex ΔN with colored vertices to a d-dimensional manifold M must map r points from disjoint rainbow faces of ΔN to the same point in M: For this we have to assume that N?(r−1)(d+1), no r vertices of ΔN get the same color, and our proof needs that r is a prime. A face of ΔN is a rainbow face if all vertices have different colors.This result is an extension of our recent “new colored Tverberg theorem”, the special case of M=Rd. It is also a generalization of Volovikov?s 1996 topological Tverberg theorem for maps to manifolds, which arises when all color classes have size 1 (i.e., without color constraints); for this special case Volovikov?s proof, as well as ours, works when r is a prime power.     

On the stretch factor of Delaunay triangulations of points in convex position

Let S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the plane whose point set is S. The stretch factor of G is the maximum ratio, among all points p and q in S, of the length of the shortest path from p to q in G over the Euclidean distance |pq|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2π/(3cos(π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33.     

Some families of combinatorial and other series identities and their applications

The main object of this presentation is to show how some simple combinatorial identities can lead to several general families of combinatorial and other series identities as well as summation formulas associated with the Fox-Wright function _pΨ_q and various related generalized hypergeometric functions. At least one of the hypergeometric summation formulas, which is derived here in this manner, has already found a remarkable application in producing several interesting generalizations of the Karlsson-Minton summation formula. We also consider a number of other combinatorial series identities and rational sums which were proven, in recent works, by using different methods and techniques. We show that much more general results can be derived by means of certain summation theorems for hypergeometric series. Relevant connections of the results presented here with those in the aforementioned investigations are also considered.     

Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

Global dynamics of a mathematical model for HTLV-I infection of CD4 T cells with delayed CTL response

Human T-cell leukaemia virus type I (HTLV-I) preferentially infects the CD4⁺ T cells. The HTLV-I infection causes a strong HTLV-I specific immune response from CD8⁺ cytotoxic T cells (CTLs). The persistent cytotoxicity of the CTL is believed to contribute to the development of a progressive neurologic disease, HTLV-I associated myelopathy/tropical spastic paraparesis (HAM/TSP). We investigate the global dynamics of a mathematical model for the CTL response to HTLV-I infection in vivo. To account for a series of immunological events leading to the CTL response, we incorporate a time delay in the response term. Our mathematical analysis establishes that the global dynamics are determined by two threshold parameters R₀ and R₁, basic reproduction numbers for viral infection and for CTL response, respectively. If R₀≤1, the infection-free equilibrium P₀ is globally asymptotically stable, and the HTLV-I viruses are cleared. If R₁≤1<R₀, the asymptomatic-carrier equilibrium P₁ is globally asymptotically stable, and the HTLV-I infection becomes chronic but with no persistent CTL response. If R₁>1, a unique HAM/TSP equilibrium P₂ exists, at which the HTLV-I infection is chronic with a persistent CTL response. We show that the time delay can destabilize the HAM/TSP equilibrium, leading to Hopf bifurcations and stable periodic oscillations. Implications of our results to the pathogenesis of HTLV-I infection and HAM/TSP development are discussed.     

Exact algorithms for procurement problems under a total quantity discount structure

In this paper, we study the procurement problem faced by a buyer who needs to purchase a variety of goods from suppliers applying a so-called total quantity discount policy. This policy implies that every supplier announces a number of volume intervals and that the volume interval in which the total amount ordered lies determines the discount. Moreover, the discounted prices apply to all goods bought from the supplier, not only to those goods exceeding the volume threshold. We refer to this cost-minimization problem as the total quantity discount (TQD) problem. We give a mathematical formulation for this problem and argue that not only it is NP-hard, but also that there exists no polynomial-time approximation algorithm with a constant ratio (unless P = NP). Apart from the basic form of the TQD problem, we describe four variants. In a first variant, the market share that one or more suppliers can obtain is constrained. Another variant allows the buyer to procure more goods than strictly needed, in order to reach a lower total cost. We also consider a setting where the buyer needs to pay a disposal cost for the extra goods bought. In a third variant, the number of winning suppliers is limited, both in general and per product. Finally, we investigate a multi-period variant, where the buyer not only needs to decide what goods to buy from what supplier, but also when to do this, while considering the inventory costs. We show that the TQD problem and its variants can be solved by solving a series of min-cost flow problems. Finally, we investigate the performance of three exact algorithms (min-cost flow based branch-and-bound, linear programming based branch-and-bound, and branch-and-cut) on randomly generated instances involving 50 suppliers and 100 goods. It turns out that even the large instances of the basic problem are solved to optimality within a limited amount of time. However, we find that different algorithms perform best in terms of computation time for different variants.     

A global attractivity criterion for nonlinear non-autonomous difference equations

We establish a discrete version of the celebrated Yorke and Wright 3/2-stability criterion for a family of strongly nonlinear non-autonomous difference equations of the form xn+1=xn+anfn(xn,…,xn−k).     

Quantifying the value of buyer–vendor coordination: Analytical and numerical results under different replenishment cost structures

Despite a growing interest in channel coordination, no detailed analytical or numerical results measuring its impact on system performance have been reported in the literature. Hence, this paper aims to develop analytical and numerical results documenting the system-wide cost improvement rates that are due to coordination. To this end, we revisit the classical buyer–vendor coordination problem introduced by Goyal [S.K. Goyal, An integrated inventory model for a single-supplier single-customer problem. International Journal of Production Research 15 (1976) 107–111] and extended by Toptal et al. [A. Toptal, S. Çetinkaya, C.-Y. Lee, The buyer–vendor coordination problem: modeling inbound and outbound cargo capacity and costs, IIE Transactions on Logistics and Scheduling 35 (2003) 987–1002] to consider generalized replenishment costs under centralized decision making. We analyze (i) how the counterpart centralized and decentralized solutions differ from each other, (ii) under what circumstances their implications are similar, and (iii) the effect of generalized replenishment costs on the system-wide cost improvement rates that are due to coordination. First, considering Goyal’s basic setting, we show that the improvement rate depends on cost parameters. We characterize this dependency analytically, develop analytical bounds on the improvement rate, and identify the problem instances in which considerable savings can be achieved through coordination. Next, we analyze Toptal et al.’s [A. Toptal, S. Çetinkaya, C.-Y. Lee, The buyer–vendor coordination problem: modeling inbound and outbound cargo capacity and costs, IIE Transactions on Logistics and Scheduling 35 (2003) 987–1002] extended setting that considers generalized replenishment costs representing inbound and outbound transportation considerations, and we present detailed numerical results quantifying the value of coordination. We report significant improvement rates with and without explicit transportation considerations, and we present numerical evidence which suggests that larger rates are more likely in the former case.