Bivariate Distributions of Maximum Remaining Service Times in Fork-Join Infinite-Server Queues

Problems of Information Transmission - We study the maximum remaining service time in M(2)∣G2∣∞ fork -join queueing systems where an incoming task forks on arrival for service...     

The Gated Infinite-Server Queue with Unbounded Service Times and Heavy Traffic

A queueing system with infinitely many servers is considered where access of customers to service is controlled by a gate. The gate is open only if all servers are free. Customers are served in stages. We study the asymptotic behavior of the number of customers served in a stage and of the stage duration in the heavy traffic regime in the case where the service time distribution belongs to the attraction domain of a double exponential law.     

Optimal Routing in Two Parallel Queues with Exponential Service Times

In this paper we investigate the problem of the effective computation of the optimal routing sequence in a queuing system made of two parallel queues with exponential service times. We first show that the optimal policy (minimizing the expected waiting time) is a Sturmian sequence and we establish several qualitative properties of this policy (monotonicity, continuity, convexity). Then, we propose an algorithm to compute the optimal routing sequence efficiently. We address the issues of time complexity as well as numerical stability of this algorithm. We then run an extensive set of experiments which show several interesting features of the optimal policy with apparent discontinuities and a fractal behavior and we provide several good approximations by using fast heuristics.     

Generalized Thermodynamics of Maximum Work in Finite Time

We consider thermodynamic behaviour of thermal machines founded on kinetic rather than static origins. Their models, which are formulated for finite time transitions, simplify to models of classical thermodynamics in the limiting case of an infinite duration. An extended exergy is derived as a finite-time extension of the classical thermodynamic work delivered from a system of a body and its environment. With this quantity enhanced bounds can be determined for active continuous and cascade processes, in which there is an indirect energy exchange between two sybsystems through the working fluid of an engine, a refrigerator or a heat pump. These bounds refer to systems with finite exchange area or with a finite contact time. An economic framework of this theory is outlined.For both continuous and discrete processes, nonlinear thermodynamic models are derived from a combination of the energy balance and transfer equations. These models serve as constraints in the problem of work optimization. Variational and optimal control approaches are developed which are analogous to those found in analytical mechanics. Variational calculus is used along with some aspect of the canonical transformation theory to maximize work and discuss the role of a finite process intensity and of a finite duration.The optimality of a definite irreversible process for a finite-time transition of a controlled fluid is pointed out as well as a connection between the process duration, optimal dissipation and the optimal process intensity measured in terms of a hamiltonian, a dissipative quantity. It is shown that limits of the classical availability theory should be replaced by stronger limits which are obtained for finite time processes, and which are closer to reality. A hysteretic property of the generalized exergy describes a decrease of the maximum work received from an engine system and an increase of work added to a heat pump system, the features which are particularly important in high-rate regions of thermodynamic processes. For an infinite sequence of infinitesimal thermal machines, an optimal temperature strategy is obtained in the form similar to that known in the theory of simulated annealing.     

Throughput in Processor-Sharing Queues

Processor-sharing queues are often used to model file transmission in networks. While sojourn time is a common performance metric in the queueing literature, average transmission rate is the more commonly discussed metric in the networking literature. Whereas much is known about sojourn times, there is little known about the average service rate experienced by jobs in processor-sharing queues. We first define the average rate as observed by users and by the queue. In an M/M/1 processor-sharing queue, we give closed-form expressions for these average rates, and prove a strict ordering amongst them. We prove that the queue service rate (in bps) is an increasing function of the minimum required average transmission rate, and give a closed-form expression for the marginal cost associated with such a performance requirement. We then consider the effect of using connection access control by modeling an M/M/1/K processor-sharing queue. We give closed-form expressions for average transmission rates, and discuss the relationship between the queue service rate (in bps), the queue limit, the average rate, and the blocking probability     

基于双层机器学习的业务流程剩余时间预测

近年来,流程挖掘技术不再局限于对事件日志的线下分析以实现对流程模型的改进,而更加关注如何为业务流程的优化提供在线支持.其中业务流程剩余执行时间的预测监控是流程挖掘中的关键研究问题,它能为相关者提供及时的预测信息,进而采取有效措施以减少流程执行风险(例如超过时间限制).当前剩余时间预测的研究仅考虑单个流程实例的内部属性,而忽略了多个实例共同执行对剩余执行时间所产生的竞争影响.为此,本文考虑多实例间的资源竞争,并将其作为预测的主要输入属性之一.此外,本文还通过分析历史事件日志选择出一些对当前流程实例执行时间有重大影响的关键活动,并将其也作为预测的输入属性之一.同时,为提高预测模型的精度和在复杂应用场景中的适应性,本文利用堆叠技术将XGBoost模型和LightGBM模型进行融合,构建出双层混合预测模型来完成对业务流程剩余时间的预测.在四个真实数据集上的实验表明,考虑了实例间属性以及关键活动属性的混合预测模型在平均绝对误差上比LSTM和XGBoost方法分别降低了11.6％和15.8％.     

基于轨迹聚类的业务流程剩余时间预测方法

现有的剩余时间预测方法仅关注对剩余时间预测任务起决定性作用的时间特征信息,并未考虑空间特征信息以及异质事件日志对预测任务的影响,导致预测准确度降低。提出基于轨迹聚类的剩余时间预测方法。将不同轨迹间的相似度作为距离度量,通过对事件日志中不同长度的轨迹进行聚类,以降低事件日志复杂度并细化结构。针对业务流程剩余时间预测任务,结合卷积神经网络与准循环神经网络,同时引入双向机制与注意力机制,设计基于注意力机制的卷积准循环神经网络模型,充分地捕获和增强对剩余时间预测任务有决定性影响的时间和空间特征信息,以提高业务流程中上下文事件之间的关联性,从而识别不同事件对业务流程剩余时间预测任务的重要程度。在BPIC_2012_A、BPIC_2012_O、BPIC_2012_W等事件日志数据集上的实验验证了该方法的有效性和可行性,结果表明,相比传统剩余时间预测方法,该方法的预测准确度平均提高约20%,有助于提升业务流程剩余时间的预测质量。     

最大边染色的指数时间算法

最近,凤旺森,张立昂,曲婉玲,王捍贫对源于无线Mesh网络中的一个新的计算问题--最大边染色问题--提出了常数比近似算法.最大边染色问题要求对图的所有边染色,满足对任一顶点v,与其相关联的所有边所染的颜色种数不超过正整数q(q≥2),求使用颜色种数最多的染色方案.然而,他们并没有给出该问题的任何精确算法.提出了几个指数时间的精确算法并分析了它们的复杂度.对完全图可以在多项式时间内找到精确解.     

Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

双时间尺度下的设备随机退化建模与剩余寿命预测方法

基于退化建模的剩余寿命预测（Remaining useful life,RUL）是当前可靠性领域研究的热点.现有的退化模型都是针对单个时间尺度下的退化设备,缺少对设备性能变化与多个时间尺度相关的退化建模与剩余寿命预测方法.鉴于此,本文基于Wiener过程提出了一种双时间尺度随机退化建模与剩余寿命预测方法,用随机比例系数描述不同时间尺度之间的不确定关系,推导出丫首达时间意义下设备的双时间尺度剩余寿命分布,讨论了其与基于单时间尺度退化模型得到的剩余寿命分布之间的关系,并给出了基于历史退化数据的未知参数极大似然估计方法.最后,将所提方法应用到惯性平台关键器件陀螺仪的退化建模与剩余寿命预测中,验证了方法的有效性.     

Heavy-traffic analysis of mean response time under Shortest Remaining Processing Time

Shortest Remaining Processing time (SRPT) has long been known to optimize the queue length distribution and the mean response time (a.k.a. flow time, sojourn time). As such, it has been the focus of a wide body of analysis. However, results about the heavy-traffic behavior of SRPT have only recently started to emerge. In this work, we characterize the growth rate of the mean response time under SRPT in the M/GI/1 system under general job size distributions. Our results illustrate the relationship between the job size tail and the heavy traffic growth rate of mean response time. Further, we show that the heavy traffic growth rate can be used to provide an accurate approximation for mean response time outside of heavy traffic regime.     

Violation Probability in Processor-Sharing Queues

Processor-sharing queues are often used to model file transmission in networks. While sojourn time is a common performance metric in the queueing literature, average transmission rate is the more commonly discussed metric in the networking literature. Whereas much is known about sojourn times, there is little known about the average service rate experienced by jobs in processor-sharing queues. We focus here upon performance requirements in the form of an upper bound on the probability of failing to achieve a specified minimum transmission rate or a specified minimum average rate. For an M/G/l processor-sharing queue, we give a closed-form expression for this violation probability. We derive closed-form expressions for the marginal service rate with respect to the violation probability and to the minimum transmission rate, and characterize when each is binding. We then consider the effect of using connection access control by modeling an M/G/l/K processor-sharing queue, and discuss the relationship between queue service rate, queue limit, violation probability, and blocking probability. Finally, we consider a two-class discriminatory processor-sharing queue, and discuss what combinations of class weighting and service rate can be used to achieve specified minimum rate violation probabilities for both classes.     

From Constrained to Unconstrained Maximum Agreement Subtree in Linear Time

We propose and study the Maximum Constrained Agreement Subtree (MCAST) problem, which is a variant of the classical Maximum Agreement Subtree (MAST) problem. Our problem allows users to apply their domain knowledge to control the construction of the agreement subtrees in order to get better results. We show that the MCAST problem can be reduced to the MAST problem in linear time and thus we have algorithms for MCAST with running times matching the fastest known algorithms for MAST. A preliminary version of this paper appears in the Proceedings of the Fifth Workshop on Algorithms in Bioinformatics (WABI 2005). Research of H.F. Ting is supported in part by Hong Kong RGC Grant HKU-7172/06E.     

Analysis of Queues under Batch Service in an M/G/1 System in a Random Environment

A queue system with batch service is investigated. The batch size depends on the state both of the system and the state of some random environment. The server state changes under the action of the random environment. When the system is empty, a birth-death process acts as the random environment, whereas when the system is busy the random environment is disregarded and affects only the initial service probabilistic characteristics (in this sense, the random environment in the busy state can be regarded as arbitrary). An analytical model of the system is constructed and studied in terms Laplace (Laplace–Stieltjes) images. The generating function of the queue length is derived.     

Queues in DOCSIS cable modem networks

In this paper we determine the optimal fraction c^*$c^{*}$ of the uplink channel capacity that should be dedicated to the contention channel in a DOCSIS cable network in order to minimize its mean response time. For this purpose, we have developed an open queueing network with a non-standard form of blocking consisting of tens to hundreds of nodes. The network contains several types of customers that enter the network at various points according to a Markovian arrival process with marked customers. One of the main building blocks of the model exists in capturing the behavior of the conflict resolution algorithm by means of a single processor sharing queue. To assess the performance characteristics of this open queueing network we rely on an advanced decomposition technique that is specifically designed to deal with the Markovian nature of the arrival pattern. Several simulations are run to confirm the accuracy of the decomposition technique. We also explore the impact of a variety of systems parameters, e.g., the number of cable modems, the initial backoff window size, the correlation structure of the arrival process, the mean packet sizes, etc., on the optimal fraction c^*$c^{*}$.     

一种基于进程剩余运行时间总和的集群动态负载平衡算法

负载的评价是集群负载平衡策略研究中的首要问题。本文总结和比较了当前使用的三类负载向量并分析了它们的优点与不足，提出了一种新的负载评价指标一进程剩余运行时间总和。测试结果表明，使用新的负载向量提高了系统的性能，缩短了任务的执行时间，取得了更好的效果。     

A Note on Linear Time Algorithms for Maximum Error Histograms

Histograms and Wavelet synopses provide useful tools in query optimization and approximate query answering. Traditional histogram construction algorithms, e.g., V-Optimal, use error measures which are the sums of a suitable function, e.g., square, of the error at each point. Although the best-known algorithms for solving these problems run in quadratic time, a sequence of results have given us a linear time approximation scheme for these algorithms. In recent years, there have been many emerging applications where we are interested in measuring the maximum (absolute or relative) error at a point. We show that this problem is fundamentally different from the other traditional {rm{non}}{hbox{-}}ell_infty error measures and provide an optimal algorithm that runs in linear time for a small number of buckets. We also present results which work for arbitrary weighted maximum error measures.     

一种基于极大团的关键时间段挖掘方法

针对带有时间属性的海量事务处理问题,提出了一种求最大相关性的最小时间区间(关键时间段KTI)的算法。通过利用极大团把海量的数据项进行有效的划分,降低了后续数据挖掘和决策选择的复杂度。针对特定的含有时间参量的极大团,通过寻找关键时间段(KTI),提高了决策的准确度,同时可以减小分析数据的规模,降低对计算资源的需求。假设事务中各项出现的事件具有相同的概率分布,得到了一种寻找关键时间段(KTI)的算法。从理论上证明了算法的正确性,并对其进行了复杂度分析,通过实际数据验证了算法的可行性。