Product-forms in batch networks: Approximation and asymptotics

It is shown that a Markovian queue, with bulk arrivals and departures having any probability mass functions for their batch sizes, has geometrically distributed queue length at equilibrium (when this exists) provided there is an additional special bulk arrival stream, with particular rate and batch size distribution, when the server is idle. It is shown that the time-averaged input rate of the special arrivals tends to zero as the queue becomes saturated, and a heavy-traffic limit for the queue without special arrivals is derived by martingale methods. This is shown to give the same asymptotic queue length probabilities as the geometric model. The product form is then extended to tandem networks of batch queues using the reversed compound agent theorem (RCAT). In order to obtain the product form in this case, it is required that, in addition to special arrival streams, so-called ‘partial batches’ are discarded immediately from the network when there are not enough customers in the queue to fill an entire departing batch. Somewhat surprisingly it turns out that, in heavy traffic, the product-form network does not always agree with the regulated Brownian motion (RBM) diffusion limit for the standard network without special arrivals and where partial batches are not discarded, but forwarded to the next node. Indeed, we show that the two models agree in heavy traffic if and only if the skew-symmetry condition for the RBM to have a product form is satisfied. When the condition does hold, our theoretical and numerical results thus validate the use of the product-form batch networks as moderate-traffic approximations to the analogous standard queueing network model without special arrivals and where partial batches may be forwarded to the next node instead of being lost. In the case that the condition does not hold, we obtain a new product-form stationary distribution for the associated non-RBM diffusion limit.     

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.     

G-Networks: Development of the Theory of Multiplicative Networks

This is a review on G-networks, which are the generalization of the Jackson and BCMP networks, for which the multi-dimensional stationary distribution of the network state probabilities is also represented in product form. The G-networks primarily differ from the Jackson and BCMP networks in that they additionally contain a flow of the so-called negative customers and/or triggers. Negative customers and triggers are not served. When a negative customer arrives at a network node, one or a batch of positive (ordinary) customers is killed (annihilated, displaced), whereas a trigger displaces a positive customer from the node to some other node. For applied mathematicians, G-networks are of great interest for extending the multiplicative theory of queueing networks and for practical specialists in modeling computing systems and networks and biophysical neural networks for solving pattern recognition and other problems.     

Some Equivalence Results for Load-Independent Exponential Queueing Networks

In this paper we derive a number of results concerning the behavior of closed load-independent exponential queueing networks. It is shown that if the service rate of any station is increased (decreased), then the throughput of the network itself also increases (decreases). This is not true for product form networks in general. In addition, if the service rate at server i is increased then both the mean queue length and mean waiting time at server i decrease while both these quantities increase at all stations j ? i. The opposite effect is observed if the senrvice rate at station i is decreased. The main result of the paper is a proof of the conjective that corresponding to any general closed queueing network consisting of M stations and in which N customers circulate according to the elements of an irreducible stochastic routing matrix Q, there exists a closed load-independent exponential queueing network with the same M, N, and Q such that the mean number of customers at each station in the exponential network is equal to that in the general network. If the network throughput is specified, it is shown that this exponential network iS unique.     

A Constrained Multiple Raw Materials Manufacturing Batch Sizing Problem

The purpose of this research is to determine an optimal batch size for a product, and the purchasing policy of associated raw materials, for a manufacturing firm. Like any other practical situation, this manufacturing firm has a limited storage space, and transportation fleet of known capacity. The mathematical formulation of the problem indicates that the model is a constrained nonlinear integer program. Considering the complexity of solving such a model, we investigate the use of genetic algorithms (GAs) for solving this model. We develop both binary and real coded genetic algorithms with six different penalty functions. In addition, we develop a new procedure to solve constrained optimization models using penalty function based GAs. The real coded genetic algorithms work well for the batch sizing problems. The detailed computational experiences are presented.     

事件日志的批量迹与过程模型的多视角对齐方法

在业务过程发现的一致性检测中,现有事件日志与过程模型的多视角对齐方法一次只能获得一条迹与过程模型的最优对齐;并且最优对齐求解中的启发函数计算复杂,以致最优对齐的计算效率较低。为此,提出一种基于迹最小编辑距离的、事件日志的批量迹与过程模型的多视角对齐方法。首先选取事件日志中的多条迹组成批量迹,使用过程挖掘算法得到批量迹的日志模型;进而获取日志模型与过程模型的乘积模型及其变迁系统,即为批量迹的搜索空间;然后设计基于Petri网变迁序列集合与剩余迹的最小编辑距离的启发函数来加快A*算法;最后设计可调节数据和资源视角所占权重的多视角代价函数,在乘积模型的变迁系统上提出批量迹中每条迹与过程模型的多视角最优对齐方法。仿真实验结果表明,相比已有工作,在计算批量迹与过程模型间的多视角对齐时,所提方法占用更少的内存空间和使用更少的运行时间。该方法提高了最优对齐的启发函数计算速度,可以一次获得批量迹的所有最优对齐,进而提高了事件日志与过程模型的多视角对齐效率。     

An initiative for a classified bibliography on G-networks

In the last two decades, researchers have really been embracing the idea of G-networks with negative arrivals and the relevant product form solution including nonlinear traffic equations, which is the unified model for queueing networks and neural networks. This paper reports the initiative to collect and classify a bibliography on G-networks.     

Characterization of the stationary distribution of the batch-transfer networks as a product of biased geometric distributions

Consideration was given to the class of exponential queuing networks with batch arrivals and batch servicing. The messages arriving to the network nodes form random-size batches of customers associated with these nodes. Upon completion of servicing a current batch, it discharges the network and sends a message, if any, to the rest of the nodes according to some routing matrix. The necessary and sufficient conditions under which the stationary distribution of the network states is multiplicative were established in terms of the isolated nodes placed in a dummy random medium. These conditions underlie characterization of the stationary distribution in the form of biased geometric distributions.     

A diffusion approximation for batch queues of type GX/G(b,b)/1

Queues with bulk arrivals and batch service arise in a variety of application areas, in particular in the performance analysis of manufacturing lines, like semiconductor fabrications. In the course of this paper, a diffusion approximation for queueing systems with bulk arrivals and batch service for general and independent interarrival time distributions, as well as general service time distributions, is presented. The approximation uses a modified absorbing barrier and instantaneous return approach. The accuracy of the gained approximation is shown by a subsequent comparison with the corresponding discrete event simulation results.     

巧用DOS批处理命令,实现教师轻松批改作业

网络化教学是必然趋势,教师通过网络可以检查、批改学生作业,但教师在日常应用中,经常发现有些学生根本不做作业,只是复制其他同学的作业而蒙骗老师,基于这种情况,可以借助DOS批处理命令,建立批处理文件,来避免类似现象发生,使教师可以更好地了解每一个学生作业完成情况,真正达到在网络教室里进行网络化批改作业。     

A batch arrival queue under randomised multi-vacation policy with unreliable server and repair

This article examines an M^[x]/G/1 queueing system with an unreliable server and a repair, in which the server operates a randomised vacation policy with multiple available vacations. Upon the system being found to be empty, the server immediately takes a vacation. If there is at least one customer found waiting in the queue upon returning from a vacation, the server will be activated for service. Otherwise, if no customers are waiting for service at the end of a vacation, the server either remains idle with probability p or leaves for another vacation with probability 1???p. When one or more customers arrive when the server is idle, the server immediately starts providing service for the arrivals. It is possible that an unpredictable breakdown may occur in the server, in which case a repair time is requested. For such a system, we derive the distributions of several important system characteristics, such as the system size distribution at a random epoch and at a departure epoch, the system size distribution at the busy period initiation epoch, and the distribution of the idle and busy periods. We perform a numerical analysis for changes in the system characteristics, along with changes in specific values of the system parameters. A cost effectiveness maximisation model is constructed to show the benefits of such a queueing system.     

利用批处理和VBS实现目录定时清理

批处理以其易用、功能丰富的特点,在计算机日常管理中发挥着重要作用。本文介绍了利用批处理命令和VBS实现按目录定时清理数据的方法。先利用DOS命令和VBS编写处理代码,形成批处理程序,然后通过Windows计划任务定时自动清理数据。实践表明,该方法有效提高了工作效率,减少了维护人员的工作量。     

The <Emphasis Type="Italic">MAP/M/N</Emphasis> retrial queueing system with time-phased batch arrivals

We consider a retrial queueing system with batch arrival of customers. Unlike standard batch arrival, where a whole batch enters the system simultaneously, we assume that customers of a batch (session) arrive one by one in exponentially distributed time intervals. Service time is exponentially distributed. The batch arrival flow is MAP. The number of customers in a session is geometrically distributed. The number of sessions that can enter the system simultaneously is a control parameter. We analyze the joint probability distribution of the number of sessions and customers in the system using the techniques of multidimensional asymptotically quasi-Toeplitz Markov chains.     

基于Petri网的批处理调度研究

批处理过程存在于复杂的动态环境中,来自主客观的干扰及问题固有的易变性,会导致各种过程参数的变化,因此,需要研究对意外事件作出快速反应的动态调度方法,以捕捉生产环境的实时变化。该文针对批处理过程中最常出现的操作处理时间波动,提出了基于Petri网仿真技术的批处理过程动态调度方法。仿真结果表明,该方法能有效地改善调度性能,为批处理过程动态调度的研究提供了新思路。     

Tail probabilities of the delay in a batch-service queueing model with batch-size dependent service times and a timer mechanism

We deduce approximations for the tail probabilities of the customer delay in a discrete-time queueing model with batch arrivals and batch service. As in telecommunications systems transmission times are dependent on packet sizes, we consider a general dependency between the service time of a batch and the number of customers within it. The model also incorporates a timer mechanism to avoid excessive delays stemming from the requirement that a service can only be initiated when the number of present customers reaches or exceeds a service threshold. The service discipline is first-come, first-served (FCFS). We demonstrate in detail that our approximations are very useful for the purpose of assessing the order of magnitude of the tail probabilities of the customer delay, except in some special cases that we discuss extensively. We also illustrate that neglecting batch-size dependent service times or a timer mechanism can lead to a devastating assessment of the tail probabilities of the customer delay, which highlights the necessity to include these features in the model. The results from this paper can, for instance, be applied to assess the quality of service (QoS) of Voice over IP (VoIP) conversations, which is typically expressed in terms of the order of magnitude of the probability of packet loss due to excessive delays.     

多目的批量过程的受影响批次再调度算法

为解决多目的批量过程调度受延迟扰动的问题,提出了综合考虑新调度质量和稳定性的受影响批次再调度ABR算法,根据状态任务网STN所定义的工艺过程将受到延迟影响的所有批次向后移动最小可能值。仿真算例表明,ARB再调度算法在完成时间指标和开始时间总延迟指标上均优于现有的右移再调度法RSR。     

A discrete-time on–off source queueing system with negative customers

This paper studies a discrete-time single-server infinite-capacity queueing system with correlated arrivals, geometrically distributed service times and negative customers. Positive customers are generated by a Bernoulli bursty source, with geometrically distributed lengths of the on-periods and off-periods. Negative customers arrive to the system according to a geometrical arrival process which is independent of the positive arrival process. A negative customer removes a positive customer in service if any, but has no effect on the system if it finds the system empty. We analyze the Markov chain underlying the queueing system and evaluate the performance of the system based on generating functions technique. Closed-form expressions of some performance measures of the system are obtained, such as stationary probability generating functions of queue length, unfinished work, sojourn time distribution and so on. Finally, the effect of several parameters on the system is shown numerically.     

Higher-order distributional properties in closed queueing networks

In many real-life computer and networking applications, the distributions of service times, or times between arrivals of requests, or both, can deviate significantly from the memoryless negative exponential distribution that underpins the product-form solution for queueing networks. Frequently, the coefficient of variation of the distributions encountered is well in excess of one, which would be its value for the exponential. For closed queueing networks with non-exponential servers there is no known general exact solution, and most, if not all, approximation methods attempt to account for the general service time distributions through their first two moments.We consider two simple closed queueing networks which we solve exactly using semi-numerical methods. These networks depart from the structure leading to a product-form solution only to the extent that the service time at a single node is non-exponential. We show that not only the coefficients of variation but also higher-order distributional properties can have an important effect on such customary steady-state performance measures as the mean number of customers at a resource or the resource utilization level in a closed network.Additionally, we examine the state that a request finds upon its arrival at a server, which is directly tied to the resulting quality of service. Although the well-known Arrival Theorem holds exactly only for product-form networks of queues, some approximation methods assume that it can be applied to a reasonable degree also in other closed queueing networks. We investigate the validity of this assumption in the two closed queueing models considered. Our results show that, even in the case when there is a single non-exponential server in the network, the state found upon arrival may be highly sensitive to higher-order properties of the service time distribution, beyond its mean and coefficient of variation.This dependence of mean numbers of customers at a server on higher-order distributional properties is in stark contrast with the situation in the familiar open M/G/1 queue. Thus, our results put into question virtually all traditional approximate solutions, which concentrate on the first two moments of service time distributions.     

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

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

Benefits and Drawbacks of Redundant Batch Requests

Most parallel computing platforms are controlled by batch schedulers that place requests for computation in a queue until access to compute nodes is granted. Queue waiting times are notoriously hard to predict, making it difficult for users not only to estimate when their applications may start, but also to pick among multiple batch-scheduled platforms the one that will produce the shortest turnaround time. As a result, an increasing number of users resort to “redundant requests”: several requests are simultaneously submitted to multiple batch schedulers on behalf of a single job; once one of these requests is granted access to compute nodes, the others are canceled. Using simulation as well as experiments with a production batch scheduler we evaluate the impact of redundant requests on (1) average job performance, (2) schedule fairness, (3) system load, and (4) system predictability. We find that some of the popularly held beliefs about the harmfulness of redundant batch requests are unfounded. We also find that the two most critical issues with redundant requests are the additional load on current middleware infrastructures and unfairness towards users who do not use redundant requests. Using our experimental results we quantify both impacts in terms of the number of users who use redundant requests and of the amount of request redundancy these users employ. This work was supported by the NSF under Award 0546688.