Blocking in a shared resource environment with batched Poisson arrival processes

We study a variant of the multi-dimensional Erlang blocking model in which customer arrivals require multiple servers and are modelled as batched Poisson processes with arbitrary batch size distribution. We show that the state distribution for the partial batch blocking discipline is a product form, and for the special case of the complete sharing policy, we obtain a one-dimensional recursion for the aggregate state distribution. When the batch size distribution is geometric, our recursion is identical to a recursion due to Delbrouck. This correspondence provides a new interpretation for Delbrouck's recursion, which was introduced to model peaked stream blocking. We show that this correspondence is due to an equivalence between a batched Poisson blocking model with geometrically distributed batches and a blocking model with a linear state dependent arrival process.     

Analytical modelling of networks in multicomputer systems under bursty and batch arrival traffic

The hypercube and torus are two important message-passing network architectures of high-performance multicomputers. Analytical models of multicomputer networks under the non-bursty Poisson traffic have been widely reported. Motivated by the convincing evidence of bursty and batch arrival nature of traffic generated by many real-world parallel applications in high-performance computing environments, we develop a new and concise analytical model in this paper for hypercube and torus networks in the presence of batch message arrivals modelled by the compound Poisson process with geometrically distributed batch sizes. The average degree of virtual channel multiplexing is derived by employing a Markov chain which can capture the batch arrival nature. An attractive advantage of the model is its constant computation complexity independent of the network size. The accuracy of the analytical performance results is validated against those obtained from simulation experiments of an actual system.     

随机供应中断和退货环境下库存的应急控制

随机供应中断和退货环境下库存变化, 失去传统上的单调性, 呈现复杂的随机波动状态, 从而, 极大地增加了控制难度. 为解决系统库存的短缺和超储问题, 本文提出一个应急控制(包括应急采购和应急处理)策略. 在库存水平的动态变化表示为Lévy过程条件下, 利用连续时间Markov链、更新过程和鞅理论, 构建了系统期望折扣总利润模型, 并设计了交叉熵法确定最优控制策略. 仿真结果表明, 中断强度和类型及退货批次和批量, 对最优应急处理水平和应急采购量均有较大影响. 而退货类型仅影响最优应急处理水平, 对最优应急采购量影响较小.     

极小化等待时间的热处理批调度模型与PSO解

机加车间的工件动态到达热处理车间后因受到批处理设备合批等的约束不能及时得到加工,基于工件动态到达的热处理车间,以最小化工件等待时间期望为目标,建立批调度模型,根据工件到达时间实现了粒子群算法微粒的编码以及对工件的分批,通过仿真实验得到结论:缩短工件的加工时间,则在热处理车间内,可以减小工件等待时间期望;降低工件数规模,工件会密集到达热处理环节,从而减短工件等待时间;工件的等待时间期望的大小与工件规模数量有关,工件数规模较小时,大尺寸工件的等待时间期望优于小尺寸工件,规模较大时,则相反。最后,对比分析了本文改进的粒子群算法的效果,发现改进的粒子群算法最优。     

Sample-path analysis of queues with batch arrivals

In this article we give a deterministic sample path general relationship that relates workload and batch delays, and use it to extend the Pollaczek–Khintchine formula for a batch arrival single-server queueing model. We also give a conservation law for the same system with multiple classes that leads to new versions of conservation laws for Poisson batch arrival models. Our results are completely rigorous and hold under weaker assumptions than those given in the literature. We do not make stochastic assumptions, so the results hold almost surely on every sample path of the stochastic process that describes the system evolution. The article is self contained in that it gives a brief review of necessary background material.     

Queueing analysis and optimal control of and systems

We first consider a finite-buffer single server queue where arrivals occur according to batch Markovian arrival process (BMAP). The server serves customers in batches of maximum size ‘b’ with a minimum threshold size ‘a’. The service time of each batch follows general distribution independent of each other as well as the arrival process. We obtain queue length distributions at various epochs such as, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue length, mean waiting time, probability of blocking, etc. have been obtained. Total expected cost function per unit time is also derived to determine the optimal value N^* of N at a minimum cost for given values of a and b. Secondly, we consider a finite-buffer single server queue where arrivals occur according to BMAP and service process in this case follows a non-renewal one, namely, Markovian service process (MSP). Server serves customers according to general bulk service rule as described above. We derive queue length distributions and important performance measures as above. Such queueing systems find applications in the performance analysis of communication, manufacturing and transportation systems.     

Optimal hedging point control for a failure-prone manufacturing system

This paper considers a manufacturing system with multiple operational modes producing one part type. The part processing time at each operational mode is exponentially distributed and its rate is controllable. The demand arrival is random and described by a Poisson process. By minimizing an infinite-horizon discounted expected cost function, the optimal service rate control is derived. It is proved that the optimal policy is of a hedging point structure by examining the properties of the optimal cost function such as convexity, monotonicity and asymptotic behaviours. The hedging points at different operational modes can be ordered according to their production capacities. The relationships of the hedging points with some system parameters are presented. These structural properties of the optimal control policy are helpful in finding simple and realistic suboptimal policies for practical manufacturing systems. A numerical example is given to demonstrate our results.     

Order picking systems: Batching and storage assignment strategies

We consider batching and storage allocation strategies in a manual order picking system of small parts which processes high volume of orders. The arrivals of orders are assumed to follow a Poisson process, and the quantity of items in an order is assumed to be independently and identically distributed negative binomial variates. The order picking system is modeled by a two-stage queueing system with batching and picking activities. Bounds and approximate estimates for the mean and variance of the turnover time (total service time) of a batch of orders are derived. The quality of the results is evaluated via simulation. A comparison between uniform and skewed item storage assignment is also presented. The effects of batching and the batch size on the service time are discussed.     

The interdeparture time distribution for each class in the ∑Mi/Gi/1 queue with set-up times and repeated server vacations

This paper studies the interdeparture time distribution of one class of customers who arrive at a single server queue where customers of several classes are served and where the server takes a vacation whenever the system becomes empty or is empty when the server returns from a vacation. Furthermore, the first customer in the busy period is allowed to have an exceptional service time (set-up time), depending on the class to which this customer belongs. Batches of customers of each class arrive according to independent Poisson processes and compete with each other on a FIFO basis. All customers who belong to the same class are served according to a common generally distributed service time. Service times, batch sizes and the arrival process are all assumed to be mutually independent. Successive vacation times of the server form independent and identically distributed sequences with a general distribution.For this queueing model we obtain the Laplace transform of the interdeparture time distribution for each class of customers whose batch size is geometrically distributed. No explicit assumptions of the batch size distributions of the other classes of customers are necessary to obtain the results.The paper ends by showing how the mathematical results can be used to evaluate a protocol that controls access to a shared medium of an ATM passive optical network. The numerical results presented in the last section of this paper show that the bundle spacing principle that is used by the permit distribution algorithm of this protocol introduces high delays and in many cases also more variable interdeparture times for the ATM cells of individual connections. An alternative algorithm is proposed that does not cope with these performance short comings and at the same time conserves the good properties of the protocol.     

A perishable system with modified base stock policy and random supply quantity

We analyse an inventory system with Poisson demands stocking perishable items having constant hazard rates. Orders are placed at every demand epoch so as to take the inventory position back to its maximum level. The replenishment rate depends on the amount on order and the supply quantity which is random. The assumption on demands during stock out periods cover complete lost sales, partial backordering, and full backlogging as special cases. A matrix recursive scheme is developed to determine the limiting distribution. The computational efficiency of this procedure in the determination of the optimal parameters that minimizes the long run expected cost rate is illustrated with examples.     

On the Invariance of Stationary State Probabilities of a Non-Product-Form Single-Line Queueing System

We consider a single-line queueing system (QS) with Poisson input flow of varying intensity, which depends on the number of demands in the system. The job size (length) distribution for a demand depends on the number of demands in the system at the arrival moment. The service rate also depends on the number of calls in the QS. If the job size for a new arrival is larger than the remaining job size for the currently processed demand, then the arrival is put at the beginning of the queue with a certain probability, which depends on the total number of demands in the system. Otherwise, it occupies the server and displaces the currently processed demand, which is put at the beginning of the queue. The probability distribution of stationary states of the QS is found and necessary and sufficient conditions for this distribution to be invariant with respect to the job size distribution with a fixed mean are obtained.     

Comparing single-server loss systems in random environment

Considers a single-server loss system in a random environment. The environment is determined by a finite-state Markov process. When the environment is in state i, the arrival process is Poisson with rate λ_i, and the service time is exponential with rate μ _i=1,···m. We show that the blocking probability of this system is bounded from below (above) by that of the same system with a more (less) regular arrival and service pattern. This result supports Ross's conjecture (1978) that the blocking probability is smaller when the arrival process is more regular and suggests its validity in scenarios with dependent arrival and service processes. Such structural properties are useful in obtaining bounds and approximations for system performance. We then fix the marginal service (arrival) process and search for an arrival (service) process with the same long-run rate that minimizes the blocking probability. It is shown that the optimal solution is the one such that the arrival and service rates are proportional. This result is in contrary with the case of independent arrival and service processes, where the system performance reaches its minimum when the arrival is replaced by Poisson, and it provides insight into the understanding of the effect of nonstationarity on system performance     

集卡分批到达模式下的进口箱场桥作业调度优化

在进口箱疏港过程中, 服务于相同客户的若干集卡组成集卡组, 具有相同的抵港时间, 因此, 外部集卡抵港提箱呈现分批到达的特点. 集卡组内作业指派的优劣直接影响场桥的作业效率, 存在较大的优化空间. 对此, 基于翻箱作业不能跨贝进行的现实约束, 将场桥作业调度解构为场桥作业路径优化问题和贝内翻箱作业优化问题两部分并分别建立动态优化模型. 针对场桥作业路径优化问题, 提出一种多项式时间的精确算法并给以证明; 针对贝内翻箱作业优化问题, 设计一种基于MSA的双层启发式算法进行求解. 一系列数值实验的结果显示了所提出优化模型及算法的有效性和鲁棒性.

     

Scalable, statistical storage allocation for extensible inverted file construction

An Inverted file is a commonly used index for both archival databases and free text where no updates are expected. Applications like information filtering and dynamic environments like the Internet require inverted files to be updated efficiently. Recently, extensible inverted files are proposed which can be used for fast online indexing. The effective storage allocation scheme for such inverted files uses the arrival rate to preallocate storage. In this article, this storage allocation scheme is improved by using information about both the arrival rates and their variability to predict the storage needed, as well as scaling the storage allocation by a logarithmic factor. The resultant, final storage utilization rate can be as high as 97-98% after indexing about 1.6 million documents. This compares favorably with the storage utilization rate of the original arrival rate storage allocation scheme. Our evaluation shows that the retrieval time for extensible inverted file on solid state disk is on average similar to the retrieval time for in-memory extensible inverted file. When file seek time is not an issue, our scalable storage allocation enables extensible inverted files to be used as the main index on disk. Our statistical storage allocation may be applicable to novel situations where the arrival of items follows a binomial, Poisson or normal distribution.     

Switched poisson process/g/1 queue with service interruptions

In this paper, we develop an expression for the expected waiting time in a single server queueing system subject to interruptions with alternately varying Poisson arrival and renewal service rates. This queueing system is useful to model situations in production, computer and telecommunication systems in which customer arrivals and service requirements differ depending on whether the server is working or not. We develop an expression for the expected waiting time by approximating the virtual delay process by a Brownian motion. Our approximation for the expected waiting time involves only the means and variances and does not depend on any assumptions regarding the interarrival, service or switching time distributions. We present simulation results to illustrate the quality of our approximations.     

非泊松工件流CSPS系统的Q学习算法适用性仿真研究

研究工件非泊松到达情况下, 传送带给料加工站(CSPS)系统无法建立成半马尔可夫决策过程(SMDP)模型 时, Q学习算法的适用性问题. 首先, 以马尔可夫调制泊松过程(MMPP)和半马尔可夫调制泊松过程(SMMPP)来模拟 非泊松工件流, 并在相同的平均到达率下, 仿真评估其Q学习算法性能, 并分别与泊松工件流情况下的Q学习算法性 能进行比较: 其次, 在非泊松工件流情况下, 观测以实时统计平均到达率作为工件标准泊松到达率的理论优化情况: 最后讨论在MMPP和SMMPP叠加混合非泊松工件流情况下CSPS 系统的Q学习算法性能. 实验表明, 在工件非泊松 到达情况下Q学习算法依然能学到较好的控制策略, 从而说明了CSPS系统中Q学习算法的适用性.     

On the Asymptotic Optimality of First-Fit Storage Allocation

Suppose requests to store files arrive at a storage facility in a Poisson stream at rate 1. Each file is allocated storage space on arrival and each remains independently for an exponential time with mean l/p. The lengths of the files are assumed to be independent with common distribution F. Each file is placed in the lowest addressed contiguous sequence of locations large enough to accommodate the fre at its arrival time. This is the so-called first-fit storage discipline. We conjecture that first-fit is asymptotically optimal in the sense that the ratio of expected empty space to expected occupied space tends to zero as p → 0, i.e., as the occupied space tends to ∞. This conjecture seems very hard to prove, but it has been proved for constant file lengths [1], i.e., when F degenerates. We are unable to prove the conjecture but give a graphic display of the results of a Monte Carlo simulation which makes it very convincing.     

EOQ model where a portion of the defectives can be used as perfect quality

The main purpose of this article is to investigate an economic order quantity model for products with imperfect quality, where the defective items are screened out by a 100% inspection process and then can be sold in a single batch by the end of the inspection process. However, differing from the previous studies on the topic, we assume, in this article, that a portion of the defectives (called the acceptable defective part) can be utilised as perfect quality and that the utilisation of the acceptable defective part will reduce the consumption of the remaining perfect quality items after the defectives are sold. In practice, there are a number of goods (e.g. clothes, sporting shoes, purses, porcelain dishes, fruits, vegetables, etc.) with such characteristic. First, we construct the model in terms of annual profit and find the optimal order quantity with a constant defective percentage. Next, we determine the optimal order quantity for the case that the defective percentage follows a uniform distribution by maximising the expected annual profit. For both cases, two properties of the optimal order quantity and the corresponding annual profit are also given. Finally, two numerical examples are provided to illustrate the proposed models.     

Simulation model of buffer behavior for data multiplexing with Erlang arrivals in analog speech

Due to great simplicity in mathematical analysis, data-arrival process is generally assumed to be a Poisson process but it does not fit in many practical situations. However, the arrival process can be better approximated by Erlang distribution having appropriate degree. This paper analyses buffer behavior in queueing system with finite waiting-room, Erlang arrivals, synchronous transmission and single server having interruptions through a first order Markov process. Erlang distribution for arrival process puts multiple dependence on buffer states. Also this interruption process gives two simultaneous linear matrix equations. Thus the solution of state equations is difficult. Therefore, computer simulation has been used to study the relationships among overflow probability, buffer size and expected queueing delay due to buffering as a function of traffic intensity and the degree of Erlang distribution (Erlang parameter). A voice-data system (shown in Fig. 1) has been considered as an application for this model. The results of this study are portrayed on graphs and may be used as guidelines in buffer design problems in similar situations. Although this problem arose in the study of multiplexing of data in speech, the queueing model developed is quite general and may be useful for other industrial applications.     

Sensitivity analysis of the optimal management policy for a queuing system with a removable and non-reliable server

The management policy of an M/G/1 queue with a single removable and non-reliable server is considered. The decision-maker can turn the single server on at any arrival epoch or off at any service completion. It is assumed that the server breaks down according to a Poisson process and the repair time has a general distribution. Arrivals form a Poisson process and service times are generally distributed. In this paper, we consider a practical problem applying such a model. We use the analytic results of the queueing model and apply an efficient Matlab program to calculate the optimal threshold of management policy and some system characteristics. Analytical results for sensitivity analysis are obtained. We carry out extensive numerical computations for illustration purposes. An application example is presented to display how the Matlab program could be used. The research is useful to the analyst for making reliable decisions to manage the referred queueing system.