The single server queue in discrete time-numerical analysis IV

The nonlinear difference equation for the distribution of the busy period for an unbounded discrete time queue of M|G| 1 type is solved numerically by a monotone iterative procedure. A starting solution is found by computing a first passage time distribution in a truncated version of the queue.     

On the busy period of the M/G/1 retrial queue

The M/G/1 queue with repeated attempts is considered. A customer who finds the server busy, leaves the service area and joins a pool of unsatisfied customers. Each customer in the pool repeats his demand after a random amount of time until he finds the server free. We focus on the busy period L of the M/G/1$ retrial queue. The structure of the busy period and its analysis in terms of Laplace transforms have been discussed by several authors. However, this solution has serious limitations in practice. For instance, we cannot compute the first moments of L by direct differentiation. This paper complements the existing work and provides a direct method of calculation for the second moment of L. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 115–127, 2000     

The queue G/M/m/N: Busy period and cycle,waiting time under reverse and random order service

The busy period, busy cycle, and the numbers of customers served and lost therein, of the G/M/m queue with balking is studied via the embedded Markov chain approach. It is shown that the expectations of the two discrete variables give the loss probability. For the special case G/M/1/N a closed expression in terms of contour integrals is obtained for the Laplace transform of these four variables. This yields as a byproduct the LIFO waiting time distribution for the G/M/m/N queue. The waiting time under random order service for this queue is also studied.     

A queueing system with vacations after N services

This article is devoted to the study of an M/G/1 queue with a particular vacation discipline. The server is due to take a vacation as soon as it has served exactly N customers since the end of the previous vacation. N may be either a constant or a random variable. If the system becomes empty before the server has served N customers, then it stays idle until the next customer arrival. Such a vacation discipline arises, for example, in production systems and in order picking in warehouses. We determine the joint transform of the length of a visit period and the number of customers in the system at the end of that period. We also derive the generating function of the number of customers at a random instant, and the Laplace–Stieltjes transform of the delay of a customer. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 646–658, 2015     

A linear programming model for design of communications networks with time varying probabilistic demands

In this paper marginal investment costs are assumed known for two kinds of equipment stocks employed to supply telecommunications services: trunks and switching facilities. A network hierarchy is defined which includes important cases occurring in the field and also appearing in the literature. A different use of the classical concept of the marginal capacity of an additional trunk at prescribed blocking probability leads to a linear programming supply model which can be used to compute the sizes of all the high usage trunk groups. The sizes of the remaining trunk groups are approximated by the linear programming models, but can be determined more accurately by alternate methods once all high usage group sizes are computed. The approach applies to larger scale networks than previously reported in the literature and permits direct application of the duality theory of linear programming and its sensitivity analyses to the study and design of switched probabilistic communications networks with multiple busy hours during the day. Numerical results are presented for two examples based on field data, one of which having been designed by the multi-hour engineering method.     

Dual criteria preemptive open-shop problems with minimum makespan

In this article we present an algorithm for the minimum makespan preemptive open shop, which is superior to existing algorithms in both space and time requirements. We define the more complex generalized open shop and flexible open shop and address the minimum makespan problem on these shops. We show how we can use the algorithm for the minimum makespan open shop to achieve load balancing in simple and generalized open shops without increasing the complexity of the algorithm. Load balancing dictates that the number of busy machines in each period is as even as possible. We also consider preventive maintenance issues in the open shop, and makespan retains its minimum value. In particular we consider the scenario where a machine can be maintained during any period that it happens to be idle. Also we consider the case that a maintenance schedule is prespecified. We show that this problem can be solved via a linear programming formulation that can also take into account release times for the jobs and ready times for the machines. Faster algorithms are presented for open shops with three machines or less. © 1995 John Wiley & Sons, Inc.     

Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

An MX/G/1 queueing system with disasters and repairs under a multiple adapted vacation policy

We consider a queueing system with batch Poisson arrivals subject to disasters which occur independently according to a Poisson process but affect the system only when the server is busy, in which case the system is cleared of all customers. Following a disaster that affects the system, the server initiates a repair period during which arriving customers accumulate without receiving service. The server operates under a Multiple Adapted Vacation policy. The stationary regime of this process is analyzed using the supplementary variables method. We obtain the probability generating function of the number of customers in the system, the fraction of customers who complete service, and the Laplace transform of the system time of a typical customer in stationarity. The stability condition for the system and the Laplace transform of the time between two consecutive disasters affecting the system is obtained by analyzing an embedded Markov renewal process. The statistical characteristics of the batches that complete service without being affected by disasters and those of the partially served batches are also derived. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 171–189, 2015     

Reliability of linear multistate multiple sliding window systems

This paper proposes a new model that generalizes the linear consecutive k‐out‐of‐r‐from‐n:F system to multistate case with multiple failure criteria. In this model (named linear multistate multiple sliding window system) the system consists of n linearly ordered multistate elements (MEs). Each ME can have different states: from complete failure up to perfect functioning. A performance rate is associated with each state. Several functions are defined for a set of integer numbers ρ in such a way that for each r ∈ ρ corresponding function f_r produces negative values if the combination of performance rates of r consecutive MEs corresponds to the unacceptable state of the system. The system fails if at least one of functions f_r for any r consecutive MEs for r ∈ ρ produces a negative value. An algorithm for system reliability evaluation is suggested which is based on an extended universal moment generating function. Examples of system reliability evaluation are presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Optimal state-dependent pricing policies for a class of stochastic multiunit service systems

This paper models a k-unit service system (e.g., a repair, maintenance, or rental facility) with Poisson arrivals, exponential service times, and no queue. If we denote the number of units that are busy as the state of the system, the state-dependent pricing model formalizes the intuitive notion that when most units are idle, the price (i.e., the service charge per unit time) should be low, and when most units are busy, the price should be higher than the average. A computationally efficient algorithm based on a nonlinear programming formulation of the problem is provided for determination of the optimal state-dependent prices. The procedure ultimately reduces to the search on a single variable in an interval to determine the unique intersection point of a concave increasing function and a linear decreasing function. The algorithm takes, on the average, only about 1/2 second per problem on the IBM 360/65 (FORTRAN G Compiler). A discrete optimal-control approach to the problem is shown to result in essentially the same procedure as the nonlinear-programming formulation. Several properties of the optimal state-dependent prices are given. Comparisons of the optimal values of the objective function for the state-dependent and state-independent pricing policies show that the former is on the average, only about 0.7% better than the latter, which may explain partly why state-dependent pricing is not prevalent in many service systems. Potential generalizations of the model are discussed.     

The analysis of some algorithms for generating random variates with a given hazard rate

We analyze the expected time performance of two versions of the thinning algorithm of Lewis and Shedler for generating random variates with a given hazard rate on [0,∞]. For thinning with fixed dominating hazard rate g(x) = c for example, it is shown that the expected number of iterations is cE(X) where X is the random variate that is produced. For DHR distributions, we can use dynamic thinning by adjusting the dominating hazard rate as we proceed. With the aid of some inequalities, we show that this improves the performance dramatically. For example, the expected number of iterations is bounded by a constant plus E(log₊(h(0)X)) (the logarithmic moment of X).     

Contractual agreements for coordination and vendor‐managed delivery under explicit transportation considerations

We consider the coordination problem between a vendor and a buyer operating under generalized replenishment costs that include fixed costs as well as stepwise freight costs. We study the stochastic demand, single‐period setting where the buyer must decide on the order quantity to satisfy random demand for a single item with a short product life cycle. The full order for the cycle is placed before the cycle begins and no additional orders are accepted by the vendor. Due to the nonrecurring nature of the problem, the vendor's replenishment quantity is determined by the buyer's order quantity. Consequently, by using an appropriate pricing schedule to influence the buyer's ordering behavior, there is an opportunity for the vendor to achieve substantial savings from transportation expenses, which are represented in the generalized replenishment cost function. For the problem of interest, we prove that the vendor's expected profit is not increasing in buyer's order quantity. Therefore, unlike the earlier work in the area, it is not necessarily profitable for the vendor to encourage larger order quantities. Using this nontraditional result, we demonstrate that the concept of economies of scale may or may not work by identifying the cases where the vendor can increase his/her profits either by increasing or decreasing the buyer's order quantity. We prove useful properties of the expected profit functions in the centralized and decentralized models of the problem, and we utilize these properties to develop alternative incentive schemes for win–win solutions. Our analysis allows us to quantify the value of coordination and, hence, to identify additional opportunities for the vendor to improve his/her profits by potentially turning a nonprofitable transaction into a profitable one through the use of an appropriate tariff schedule or a vendor‐managed delivery contract. We demonstrate that financial gain associated with these opportunities is truly tangible under a vendor‐managed delivery arrangement that potentially improves the centralized solution. Although we take the viewpoint of supply chain coordination and our goal is to provide insights about the effect of transportation considerations on the channel coordination objective and contractual agreements, the paper also contributes to the literature by analyzing and developing efficient approaches for solving the centralized problem with stepwise freight costs in the single‐period setting. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

On the behavior of the batch arrival queue Mx/M/1 during a busy period

The queue size process (^t)⁰≤^t≤^t0 of the batch arrival queue M^X/M/1 is studied under the condition that the duration of its busy period is larger than t⁰. Explicit formulas for the transition probabilities are given and the limiting Markov process for t⁰ → ∞ is investigated. Several properties of this process are considered. Its transition probabilities and moments and the distribution of its minimum are derived and a functional limit theorem for the rescaled process is proved. © 1994 John Wiley & Sons, Inc.     

An integral equation for the second moment function of a geometric process and its numerical solution

In this article, an integral equation satisfied by the second moment function M₂(t) of a geometric process is obtained. The numerical method based on the trapezoidal integration rule proposed by Tang and Lam for the geometric function M(t) is adapted to solve this integral equation. To illustrate the numerical method, the first interarrival time is assumed to be one of four common lifetime distributions, namely, exponential, gamma, Weibull, and lognormal. In addition to this method, a power series expansion is derived using the integral equation for the second moment function M₂(t), when the first interarrival time has an exponential distribution.     

Analysis of production lines with Coxian service times and no intermediate buffers

This paper uses the holding time model (HTM) method to derive an approximate analytic formula for the calculation of the mean throughput of a K-station production line with no buffers between any two successive stations. Service times follow the two-stage Coxian (C²) distribution at all stations. The paper provides a formula that relates the third moment of the service completion (or virtual service) time with the respective parameters of the service time, the repair time and the time to breakdown (the latter is assumed to follow the exponential distribution). In this way, it concludes that under certain conditions the two-stage Coxian distribution can be used to approximate any general distribution matching the first three moments of the service completion time distribution. The mean holding times (consisting of the service and blocking periods) of all stations of the line are obtained in an analytical form. Numerical results are provided for the mean throughput of lines with up to 20 stations. These results are shown to have a good accuracy compared against results obtained from the Markovian state method (for short lines) and results from simulation (for longer lines). © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 669–685, 1998     

具有规范化的四元数递推计算的公式误差估计

对捷联式制导系统中目前常用的四元数递推公式进行误差估计,给出利用观测数据计算四元数的误差界的公式,还介绍了保持四元数范数不变的一类递推公式。     

A class of distributions generated from distributions of exponential type

A class of exponential type distributions with special exponential parameters is defined. It is assumed that the exponential parameters vary according to some (known) probability law. It has been shown in this paper that the compound distribution can be easily represented in form involving moment generating function of the mixing distribution. The results obtained in this paper provide an efficient and simple method of obtaining compound failure time distribution with known mixing distributions (uniform, exponential, gamma).     

Threshold optimization for weighted voting classifiers

Weighted voting classifiers considered in this paper consist of N units each providing individual classification decisions. The entire system output is based on tallying the weighted votes for each decision and choosing the one which has total support weight exceeding a certain threshold. Each individual unit may abstain from voting. The entire system may also abstain from voting if no decision support weight exceeds the threshold. Existing methods of evaluating the reliability of weighted voting systems can be applied to limited special cases of these systems and impose some restrictions on their parameters. In this paper a universal generating function method is suggested which allows the reliability of weighted voting classifiers to be exactly evaluated without imposing constraints on unit weights. Based on this method, the classifier reliability is determined as a function of a threshold factor, and a procedure is suggested for finding the threshold which minimizes the cost of damage caused by classifier failures (misclassification and abstention may have different price.) Dynamic and static threshold voting rules are considered and compared. A method of analyzing the influence of units' availability on the entire classifier reliability is suggested, and illustrative examples are presented. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 322–344, 2003.