Estimation methods for passage times using one-dependent cycles

The lengths of certain passage-time intervals (random time intervals) in discrete-event stochastic systems correspond to delays in computer, communication, manufacturing, and transportation systems. Simulation is often the only available means for analyzing a sequence of such lengths. It is sometimes possible to obtain meaningful estimates for the limiting average delay indirectly, that is, without measuring lengths of individual passage-time intervals. For general time-average limits of a sequence of delays, however, it is necessary to measure individual lengths and combine them to form point and interval estimates. We consider sequences of delays determined by state transitions of a generalized semi-Markov process and introduce a recursively-generated sequence of realvalued random vectors, called start vectors, to provide the link between the starts and terminations of passage-time intervals. This method of start vectors for measuring delays avoids the need to tag entities in the system. We show that if the generalized semi-Markov process has a recurrent single-state, then the sample paths of any sequence of delays can be decomposed into one-dependent, identically distributed cycles. We then show that an extension of the regenerative method for analysis of simulation output can be used to obtain meaningful point estimates and confidence intervals for time-average limits. This estimation procedure is valid not only when there are no ongoing passage times at any regeneration point but, unlike previous methods, also when the sequence of delays does not inherit regenerative structure. Application of these methods to a manufacturing cell with robots is discussed.     

Regenerative stochastic Petri nets

The stochastic Petri net (SPN) model is well suited to formal representation of concurrency, synchronization, and communication. We define the marking process of an SPN in terms of a general state space Markov chain which describes the net at successive transition firing times. Using structural properties of the SPN and recurrence theory for generalized semi-Markov processes, we establish conditions which ensure that the marking process of an SPN is a regenerative process and that the expected time between regeneration points is finite. This leads to a theory of regenerative simulation in the SPN setting.     

Stochastic Petri net representation of discrete event simulations

In the context of discrete event simulation, the marking of a stochastic Petri net (SPN) corresponds to the state of the underlying stochastic process of the simulation and the firing of a transition corresponds to the occurrence of an event. A study is made of the modeling power of SPNs with timed and immediate transitions, showing that such Petri nets provide a general framework for simulation. The principle result is that for any (finite or) countable state GSMP (generalized semi-Markov process) there exists an SPN having a marking process that mimics the GSMP in the sense that the two processes (and their underlying general state-space Markov chains) have the same finite dimensional distributions     

Algorithms for the generation of state-level representations ofstochastic activity networks with general reward structures

Stochastic Petri nets (SPNs) and extensions are a popular method for evaluating a wide variety of systems. In most cases, their numerical solution requires generating a state-level stochastic process, which captures the behavior of the SPN with respect to a set of specified performance measures. These measures are commonly defined at the net level by means of a reward variable. In this paper, we discuss issues regarding the generation of state-level reward models for systems specified as stochastic activity networks (SANs) with “step-based reward structures”. Step-based reward structures are a generalization of previously proposed reward structures for SPNs and can represent all reward variables that can be defined on the marking behavior of a net. While discussing issues related to the generation of the underlying state-level reward model, we provide an algorithm to determine whether a given SAN is “well-specified” A SAN is well-specified if choices about which instantaneous activity completes among multiple simultaneously-enabled instantaneous activities do not matter, with respect to the probability of reaching next possible stable markings and the distribution of reward obtained upon completion of a timed activity. The fact that a SAN is well specified is both a necessary and sufficient condition for its behavior to be completely probabilistically specified, and hence is an important property to determine     

Product-form and stochastic Petri nets: a structural approach

Stochastic Petri nets (SPNs) with product-form solution are nets for which there is an analytic expression of the steady-state probabilities with respect to place markings, as it is the case for product-form queueing networks with respect to queue lengths. The most general kind of SPNs with product-form solution introduced by Coleman et al. (and denoted here by -nets) suffers a serious drawback: the existence of such a solution depends on the values of the transition rates. Thus since their introduction, it is an open question to characterize -nets with product-form solution for any values of the rates. A partial characterization has been obtained by Henderson et al. However, this characterization does not hold for every initial marking and it is expressed in terms of the reachability graph. In this paper, we obtain a purely structural characterization of -nets for which a product-form solution exists for any value of probabilistic parameters of the SPN and for any initial marking. This structural characterization leads to the definition of -nets (Stochastic Parametric Product-form Petri nets). We also design a polynomial time (with respect to the size of the net structure) algorithm to check whether a SPN is a -net. Then, we study qualitative properties of -nets and -nets, the non-stochastic versions of -nets and -nets: we establish two results on the complexity bounds for the liveness and the reachability problems, which are central problems in Petri nets theory. This set of results complements previous studies on these classes of nets and improves the applicability of product-form solutions for SPNs.     

Embedded processes in stochastic Petri nets

Embedded discrete time processes are used to study a class of SPNs (stochastic Petri nets) which have a closed-form equilibrium distribution. These SPNs have probabilistic output bags, colored tokens, and alternating periods of arbitrarily distributing enabling and firing times (periods of time between transitions becoming enabled and absorption of tokens and between transitions absorbing tokens and depositing them in output places, respectively). In addition, an aggregation procedure is proposed which, in certain nets, not only reduces a complex SPN to a much simpler skeleton SPN but also obtains results for the skeleton SPN with are exact marginal distributions for the original SPN     

分布式功能块控制应用的性能分析

IEC61499功能块逐渐被工业采纳。本文针对分布式功能块控制应用（DFBCA）缺乏性能分析方法的情况，提出了一种基于随机Petri网的DFBCA性能分析方法。该方法以DFBCA的运行状态为着手点，利用Petri网易于表示系统中可能发生的各种状态变化及其关系的特点，将DFBCA转换为随机Petri网模型。再利用随机Petri网模型与马尔可夫链（MC）同构的特征，将随机Petri网模型转换为MC。得到的MC为DFBCA的性能分析提供了数学基础。最后基于MC的状态转移矩阵和稳态概率，对在每个状态中的驻留时间、变迁的利用率、变迁的标记流速、子系统延时时间等性能指标进行了分析。通过具体的示例说明了这种性能分析方法的可行性。     

基于随机Petri网的可修系统可用性模糊评价

结合模糊集理论和随机Petri网理论提出了一种可修系统可用性建模与分析的新方法——模糊随机Petri网方法。随机Petri网的状态可达图同构于连续时间马尔可夫链,由可达图可得到系统的稳定状态概率方程组。利用模糊代数理论解该模糊方程组即可得到系统转移概率和各种性能指标的模糊数,通过解模糊可得到系统的可用性指标值。文章进行了实例分析并与已有文献作比较,举例进行分析求解,结果表明该方法是可行的。     

A deadlock prevention approach for a class of timed Petri nets using elementary siphons

To solve the problem of deadlock prevention for timed Petri nets, an effective deadlock prevention policy based on elementary siphons is proposed in this paper. Without enumerating reachable markings, deadlock prevention is achieved by adding monitors for elementary siphons, increasing control depth variables when necessary, and removing implicit, liveness‐restricted and redundant control places. The final supervisor is live. First, a timed Petri net is stretched into a stretched Petri net (SPN). Unchanging the system performance, each transition in the SPN has a unit delay time. Then the siphon‐control‐based approach is applied. Monitors computed according to the marking constraints are added to the SPN model to ensure all strict minimal siphons in the net invariant‐controlled. A liveness‐enforcing supervisor with simple structure can be obtained by reverting the SPN into a TdPN. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Decentralized service discovery and selection in Internet of Things applications based on artificial potential fields

The Internet of Things (IoT) vision involves a future Internet integrated with real-world objects that can commonly offer their functionality trough services. In such pervasive environments of IoT networks, locating and invoking suitable services is quite challenging and traditional service discovery and selection approaches have been proven inadequate. In this paper, taking inspiration from natural metaphors, a decentralized service discovery and selection model is proposed. The model is based on artificial potential fields (APFs) which are formed upon each user service request and become active at points where services can be provided. Such points are termed as service provision nodes (SPNs). The strength of each APF depends on the percentage of requested services that can be provided by the respective SPN, as well as on SPN service load and availability with the aim to balance service load among SPNs. Service discovery and selection is then driven by artificial forces applied among user service requests and SPNs. Simulation results indicate that the proposed approach maintains satisfactory performance and scalability as the number of SPNs in an IoT network increase and efficient load balancing of the requested services among the SPNs in comparison with other approaches.     

一种资源共享系统的模型和近似性能分析

本文提出一种随机Ｐｅｔｒｉ网（ＳＰＮ）的资源共享系统的模型，并给出了模型分解和子模型迭代近似求解的两种方法：标识概率交换和平均标志个数交换。例子显示了这两种方法的有效性和相对误差。本文还证明了主述两种方法在固定迭代求解中，固定点解的存在。本文的复杂模型近似性能求解方法可以应用到很多复杂系统的性能分析中。     

Simulation for passage times in closed, multiclass networks of queues with unrestricted priorities

Regenerative simulation for passage times in networks of queues with priorities among job classes (and one or more job types) can be based on observation of a fully augmented job stack process which maintains the position of each of the jobs in a linear ‘job stack’, an enumeration of the jobs by service center and job class. In this paper we develop an estimation procedure for passage times through a subnetwork of queues. Observed passage times for all the jobs enter into the construction of point and interval estimates. The confidence intervals obtained using this estimation procedure are shorter than those obtained from simulation using a marked job.     

非马尔可夫随机Petri网模型的混合状态分析法

讨论具有发射时间任意分布之变迁的随机Petri网的解析问题.定义了随机Petri网的混合状态和混合状态密度,提出混合状态分析法,并给出具有一步转移关系标识下的混合状态密度的递推公式.使非马尔可夫型随机Petri网的分析成为可能.通过算例说明了混合状态分析法在系统性能评估中的应用.     

Globally robust confidence intervals for simple linear regression

It is well known that when the data may contain outliers or other departures from the assumed model, classical inference methods can be seriously affected and yield confidence levels much lower than the nominal ones. This paper proposes robust confidence intervals and tests for the parameters of the simple linear regression model that maintain their coverage and significance level, respectively, over whole contamination neighbourhoods. This approach can be used with any consistent regression estimator for which maximum bias curves are tabulated, and thus it is more widely applicable than previous proposals in the literature. Although the results regarding the coverage level of these confidence intervals are asymptotic in nature, simulation studies suggest that these robust inference procedures work well for small samples, and compare very favourably with earlier proposals in the literature.     

Product form solution for generalized stochastic Petri nets

In this paper, we show the structural characteristics that a particular class of generalized stochastic Petri nets must exhibit in order for their stationary probabilities to have a product-form. Sufficient conditions for identifying such a class are derived and proven with the development of a series of transformations that can also be used to construct, for any GSPN of the class, an equivalent SPN. These resulting SPNs represent the structures that can be analyzed with standard methods for product-form SPNs to establish whether the original GSPNs have product-form solutions and to compute their performance indices with effective approaches based on computationally efficient algorithms that avoid the generation of their underlying state spaces.     

Coverage of confidence intervals in sequential steady-state simulation

Stochastic discrete-event simulation has become one of the most-used tools for performance evaluation in science and engineering. But no innovation can replace the responsibility of simulators for obtaining credible results from their simulation experiments. In this paper we address the problem of the statistical correctness of simulation output data analysis, in the context of sequential steady-state stochastic simulation, conducted for studying long run behavior of stable systems. Such simulations are stopped as soon as the relative precision of estimates, defined as the relative half-width of confidence intervals at a specified confidence level, reaches the required level. We formulate basic rules for the proper experimental analysis of the coverage of steady-state interval estimators. Our main argument is that such an analysis should be done sequentially. The numerical results of our coverage analysis of the method of non-overlapping batch means and spectral analysis are presented, and compared with those obtained by the traditional, non-sequential approach. Two scenarios for stochastic simulation are considered: traditional sequential simulation on a single processor, and fast concurrent simulation based on multiple replications in parallel (MRIP), with multiple processors cooperating in the production of output data.     

Differential and linear cryptanalysis for 2-round SPNs

In this paper, we examine the security of block ciphers referred to as substitution-permutation networks (SPNs). When the SPN has 2-round, we obtain an upper bound on the maximum differential probability. We also obtain an upper bound on the maximum linear hull probability. Our results extend and sharpen the known results for the 2-round SPNs.     

A Simulation Tool for Efficient Analogy Based Cost Estimation

Estimation of a software project effort, based on project analogies, is a promising method in the area of software cost estimation. Projects in a historical database, that are analogous (similar) to the project under examination, are detected, and their effort data are used to produce estimates. As in all software cost estimation approaches, important decisions must be made regarding certain parameters, in order to calibrate with local data and obtain reliable estimates. In this paper, we present a statistical simulation tool, namely the bootstrap method, which helps the user in tuning the analogy approach before application to real projects. This is an essential step of the method, because if inappropriate values for the parameters are selected in the first place, the estimate will be inevitably wrong. Additionally, we show how measures of accuracy and in particular, confidence intervals, may be computed for the analogy-based estimates, using the bootstrap method with different assumptions about the population distribution of the data set. Estimate confidence intervals are necessary in order to assess point estimate accuracy and assist risk analysis and project planning. Examples of bootstrap confidence intervals and a comparison with regression models are presented on well-known cost data sets.     

Perturbation analysis of stochastic Petri nets

This paper addresses the sensitivity analysis of stochastic Petri nets (SPNs) using simulations. The goal is to evaluate the derivatives of performance measures with respect to timing parameters. To characterize the underlying stochastic processes of SPNs, we use a generalized semi-Markov process (GSMP) representation and propose a new representation, called GSMP*, which differs from GSMP in the routing mechanism. By using existing results on perturbation analysis of GSMPs and by extending them to GSMP*, unbiased sensitivity estimators are obtained for SPNs simulated under a GSMP or GSMP* framework. Most importantly, we prove that only one simulation run is needed for evaluating both the performance measures and their derivatives for a class of free-choice nets simulated under a GSMP framework and for any free-choice net simulated under a GSMP* framework     

基于Petri网仿真的产品概念设计效率分析

产品概念设计的效率直接关系到企业竞争力及市场占有率,团队工作是企业进行产品概念设计的本质特征。该文在分析出团队工作特征及Petri网能很好表述这些特征的基础上,用Petri网对产品概念设计流程进行了建模,给出了用随机Petri网(SPN)分析团队工作效率不足的同时,提出用仿真手段进行分析的方法。具体过程中,给出了变迁时间确定方法和变迁行为的控制策略,得出了不同仿真次数下特定库所获得托肯的平均时间及方差。结果表明,基于Petri网仿真的产品概念设计效率分析不仅效果可行而且比传统的SPN方法更为通用。