具有多项式时间复杂性的避免制造系统死锁控制策略

基于系统 Petri 网模型, 研究自动制造系统的避免死锁问题. 对不含中心资源的制造系统, 证明了它只包含安全和死锁两类可达状态. 通过一步向前看的方法, 给出了系统多项式时间复杂性的最佳避免死锁策略. 对一般系统定义了一种辅助 Petri 网. 利用辅助网的最佳避免死锁策略, 提出了综合一般制造系统多项式复杂性的避免死锁策略的方法.     

避免FMS死锁的控制策略

本文利用ＦＭＳ的Ｐｅｔｒｉ网模型讨论系统的死锁问题，给出了系统死锁的必要充分条件，提出了避免系统死锁的反馈控制策略，这种策略对系统的限制小，在许多情形下是最优的。     

分布式系统死锁的预防、避免和检测

分布式系统涉及到资源和数据的高度共享,从而可能引发死锁。分布式系统的死锁是由于资源和通讯产生的。从分布式系统死锁产生的条件,解决策略,以及分布式系统中死锁预防、避免和检测的各种算法进行了具体阐述。     

Deadlock and Blockage Control of Automated Manufacturing Systems with an Unreliable Resource

This work studies the deadlock and blockage control problem of an automated manufacturing system (AMS) with a single unreliable resource. It aims to develop a robust control policy to ensure that AMS can produce all parts in the absence of resource failures, and when the unreliable resource fails, the system can continuously produce all parts that do not require the failed resource. To this end, we divide the system into two regions, continuous and non‐continuous, based on whether all parts in them can be produced continuously or not. For the non‐continuous region, dominating region constraints are established to ensure that all parts in it do not block the production of parts in the continuous region, and an optimal deadlock avoidance policy based on a Petri net model is introduced to guarantee its deadlock‐free operation. For the continuous region, we configure a resource order policy to ensure the smooth productions of AMS. By integrating the dominating region constraints and deadlock avoidance policy with the configured resource order policy, we propose a novel robust control policy. It is proven to be of polynomial complexity and more permissive than the existing one with the same resource order policy. Also, it is tested to be more permissive than other existing policies.     

Deciding the liveness for a subclass of weighted Petri nets based on structurally circular wait

Weighted Petri nets as a kind of formal language are widely used to model and verify discrete event systems related to resource allocation like flexible manufacturing systems. System of Simple Sequential Processes with Multi-Resources (S³PMR, a subclass of weighted Petri nets and an important extension to the well-known System of Simple Sequential Processes with Resources, can model many discrete event systems in which (1) multiple processes may run in parallel and (2) each execution step of each process may use multiple units from multiple resource types. This paper gives a necessary and sufficient condition for the liveness of S³PMR. A new structural concept called Structurally Circular Wait (SCW) is proposed for S³PMR. Blocking Marking (BM) associated with an SCW is defined. It is proven that a marked S³PMR is live if and only if each SCW has no BM. We use an example of multi-processor system-on-chip to show that SCW and BM can precisely characterise the (partial) deadlocks for S³PMR. Simultaneously, two examples are used to show the advantages of SCW in preventing deadlocks of S³PMR. These results are significant for the further research on dealing with the deadlock problem.     

Optimization of queuing system via stochastic control

The problem of access and service rate control in queuing systems as a general optimization problem for controlled Markov process with finite state space is considered. By using the dynamic programming approach we obtain the explicit form of the optimal control in the case of minimizing cost given as a mixture of an average queue length, number of lost jobs, and service resources. The problem is considered on a finite time interval in the case of nonstationary input flow. In this case we suggest the general procedure of the numerical solution which can be applied to a problems with constraints.     

Optimality of affine control system of several species in competition on a sequential batch reactor

In this paper, we analyse the optimality of affine control system of several species in competition for a single substrate on a sequential batch reactor, with the objective being to reach a given (low) level of the substrate. We allow controls to be bounded measurable functions of time plus possible impulses. A suitable modification of the dynamics leads to a slightly different optimal control problem, without impulsive controls, for which we apply different optimality conditions derived from Pontryagin principle and the Hamilton–Jacobi–Bellman equation. We thus characterise the singular trajectories of our problem as the extremal trajectories keeping the substrate at a constant level. We also establish conditions for which an immediate one impulse (IOI) strategy is optimal. Some numerical experiences are then included in order to illustrate our study and show that those conditions are also necessary to ensure the optimality of the IOI strategy.     

一类离散时间非齐次马尔可夫跳跃系统最优控制

本文研究了一类离散时间非齐次马尔可夫跳跃线性系统的线型二次高斯(linear quadratic Gaussian,LQG)问题,其中系统模态转移概率矩阵随时间随机变化,其变化特性由一高阶马尔可夫链描述.对于该系统的LQG问题,文中首先给出了线性最优滤波器,得到最优状态估计;其次,验证分离定理成立,并利用利用动态规划方法设计了系统最优控制器;最后,数值仿真结果验证了所设计控制器的有效性.     

Ergodic control of partially observed Markov chains

The ergodic or long-run average cost control problem for a partially observed finite-state Markov chain is studied via the associated fully observed separated control problem for the nonlinear filter. Dynamic programming equations for the latter are derived, leading to existence and characterization of optimal stationary policies.     

Analysis of an identification algorithm arising in the adaptive estimation of Markov chains

We investigate an algorithm applied to the adaptive estimation of partially observed finite-state Markov chains. The algorithm utilizes the recursive equation characterizing the conditional distribution of the state of the Markov chain, given the past observations. We show that the process “driving” the algorithm has a unique invariant measure for each fixed value of the parameter, and following the ordinary differential equation method for stochastic approximations, establish almost sure convergence of the parameter estimates to the solutions of an associated differential equation. The performance of the adaptive estimation scheme is analyzed by examining the induced controlled Markov process with respect to a long-run average cost criterion. This research was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860 and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

Another set of conditions for average optimality in Markov control processes

The existence of an average cost optimal stationary policy in a countable state Markov decision chain is shown under assumptions weaker than those given by Sennott (1989). This treatment is a modification of that given by Hu (1992), and is related to conditions of Hordijk (1977). An example is given for which the new axiom set holds whereas the axiom set of Sennott (1989) fails to hold.     

On the propagation of updates in distributed replicated systems

We analyse the performance and dependability of protocols which implement ‘sequence consistency’ in distributed replicated systems. Sites send messages to each other from time to time, passing information about the update requests that have been received. The recipient of a message is chosen according to some probability distribution which may depend on the sender. The random variables of main interest are (a) the interval between receiving an update request and being able to execute it on the original site, subject to the consistency requirement, and (b) the time it takes to bring all sites to a consistent state after the arrival of an update.     

Towards the optimal control of Markov chains with constraints

An optimal control problem with constraints is considered on a finite interval for a non-stationary Markov chain with a finite state space. The constraints are given as a set of inequalities. The optimal solution existence is proved under a natural assumption that the set of admissible controls is non-empty. The stochastic control problem is reduced to a deterministic one and it is shown that the optimal solution satisfies the maximum principle, moreover it can be chosen within a class of Markov controls. On the basis of this result an approach to the numerical solution is proposed and its implementation is illustrated by examples.     

多机器人网络中资源公平分配的研究

就如何实现多机器人网络中各独立任务资源的公平分配及其服务质量最优化提出了一种新方法。该方法通过对增益控制参数的模糊控制,增强了系统的鲁棒性,并尽可能快速平稳地实现各项独立任务所需资源的公平分配。     

On the detectability and observability of discrete-time Markov jump linear systems

This paper presents a new detectability concept for discrete-time Markov jump linear systems with finite Markov state, which generalizes the MS-detectability concept found in the literature. The new sense of detectability can similarly assure that the solution of the coupled algebraic Riccati equation associated to the quadratic control problem is a stabilizing solution. In addition, the paper introduces a related observability concept that also generalizes previous concepts. A test for detectability based on a coupled matrix equation is derived from the definition, and a test for observability is presented, which can be performed in a finite number of steps. The results are illustrated by examples, including one that shows that a system may be detectable in the new sense but not in the MS sense.     

Stabilization of networked control systems with short or long random delays: A new multirate method

In this paper, the stabilization of a class of networked control systems (NCSs) with time‐varying delay is discussed where the random delay is less than one sensor period or more than one sensor period but bounded. A new multirate method is proposed to formulate the union model for both short and long random delays. Sufficient conditions on the existence of stabilizing controllers are established when the transition probability matrix is known. V‐K iteration approach is employed to calculate the mode‐dependent and mode‐independent state‐feedback gains of NCSs. Copyright © 2009 John Wiley & Sons, Ltd.     

A note on the attractor-property of infinite-state Markov chains

In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n>0 is less than n−Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor.     

Limiting optimal discounted-cost control of a class of time-varying stochastic systems

We consider a class of time-varying -valued control models, and with possibly unbounded costs. The processes evolve according to the system equation x_n+1=G_n(x_n,a_n)+ξ_n ( ), where {ξ_n} are i.i.d. random vectors and {G_n} a sequence of known functions converging to some function G_∞. Under suitable hypotheses, we show the existence of an α-discount optimal policy for the limiting system x_n+1=G_∞(x_n,a_n)+ξ_n.     

论访问控制机制的一般性策略实现

从访问控制的概念和模型出发,通过对访问控制的一般性实现策略比较分析,举例介绍其在系统安全的常见应用,为用户基于策略上的选择提供帮助.     

On the Performance of Randomized Embedding of Reproduction Trees in Static Networks

High performance computing requires high quality load distribution of processes of a parallel application over processors in a parallel computer at runtime such that both the maximum load and dilation are minimized. The performance of a simple randomized tree embedding algorithm that dynamically supports tree-structured parallel computations on arbitrary static networks is analyzed in this paper. The algorithm spreads newly created tree nodes to neighboring processors, which actually provides randomized dilation-1 tree embedding in static networks. We develop a linear system of equations that characterizes expected loads on all processors under the reproduction tree model, which can generate trees of arbitrary size and shape. It is shown that as the tree size becomes large, the asymptotic performance ratio of the randomized tree embedding algorithm is the ratio of the maximum processor degree to the average processor degree. This implies that the simple randomized tree embedding algorithm is able to generate high quality load distributions on virtually all static networks commonly employed in parallel and distributed computing.