Optimal control of demand-paging systems

Demand-paging systems are characterized as stochastic control processes, and optimal page replacement decisions are determined by means of dynamic programming. This approach is distinguished from others by its utilization of page structure information, which may be either supplied a priori or else dynamically learned. The main result is an optimal realizable solution for a general class of replacement problems. The resulting algorithm subsumes others (including “A₀”) as special cases.     

Page size in demand-paging systems

Summary The problem of determining page size in a page on demand system is discussed in detail in this paper. After having introduced the problem, the effect page size may have on various system performance measures is reviewed based on measurements of program behaviour and on simple models of system behaviour.This discussion is followed by a detailed study of the effect of the choice of page size on the efficient utilization of primary memory space. The wasted space-time integral (WSTI) of primary memory space is selected as a measure of this utilisation and a new model of program and system behaviour is used to compute the WSTI for different secondary memory devices (drum, ECS and LCS) and different system behaviour parameters such as the time spent in supervisor mode by the operating system to initiate a page transfer, the time spent in the CPU queue by a program which has recovered from a page fault before it receives the attention of the CPU, the global page fault rate (or arrival rate at the secondary storage devices used for paging) and other factors. The influence of each of these factors is discussed and analyzed, and the conditions under which one or another of these dominates the problem is identified.In the Appendix, one of the problems posed by our model, the use of approximate formulae for fragmentation which remain valid for a large class of probability distribution functions of program size, is analyzed in detail. Some tests are developed for the validity of these formulae.     

Optimal control of self-reproduction systems

An optimization problem for a system of self-reproducing objects is studied. The goal is to maintain the existence of the system arbitrarily long. A feature of the problem is that the cost function is represented by the limit of a certain quantity as the time tends to infinity.     

Optimal control of switching systems

This paper considers an optimal control problem for a switching system. For solving this problem we do not make any assumptions about the number of switches nor about the mode sequence, they are determined by the solution of the problem. The switching system is embedded into a larger family of systems and the optimization problem is formulated for the latter. It is shown that the set of trajectories of the switching system is dense in the set of trajectories of the embedded system. The relationship between the two sets of trajectories (1) motivates the shift of focus from the original problem to the more general one and (2) underlies the engineering relevance of the study of the second problem. Sufficient and necessary conditions for optimality are formulated for the second optimization problem. If they exist, bang-bang-type solutions of the embedded optimal control problem are solutions of the original problem. Otherwise, suboptimal solutions are obtained via the Chattering Lemma.     

Optimal control of neutral systems

This correspondence considers the necessary conditions for optimal control of a nonlinear neutral system with general cost function. Using variational techniques, it is shown that the adjoint variable is discontinuous, and furthermore, the form of the discontinuity is characterized.     

Optimal control of production-inventory systems

Optimal policies for the pontrol of a class of production-inventory systems are derived. Typical response characteristics are presented which illustrate the effects of using different weighting parameter values in the performance cost functional.     

事件驱动的网络化系统最优控制

针对随机事件驱动的网络化控制系统, 研究其中的有限时域和无限时域内最优控制器的设计问题. 首先, 根据执行器介质访问机制将网络化控制系统建模为具有多个状态的马尔科夫跳变系统; 然后, 基于动态规划和马尔科夫跳变线性系统理论设计满足二次型性能指标的最优控制序列, 通过求解耦合黎卡提方程的镇定解, 给出最优控制律的计算方法, 使得网络化控制系统均方指数稳定; 最后, 通过仿真实验表明了所提出方法的有效性.

     

Optimal control of neutral systems†

A method is presented whereby an optimal control may be obtained for a linear time-varying neutral system. The performance measure is quadratic with fixed finite upper limit. A form is derived for the coat functional, and the optimal control is obtained as the solution to a set of differential equations. A numerical technique for the solution of the equations is given and existence and uniqueness are proven.     

Optimal control of systems possessing symmetries

It is shown that a symmetry in an optimization problem induces a decomposition of the optimal feedback control law into factors. One factor can be calculated algebraically and depends only on the symmetry; the other factor corresponds to a lower dimensional optimization problem. This gives a priori information about the structure of the optimal feedback control law and indicates a possibly more efficient method for optimizing such systems.     

Optimal control of distributed bilinear systems

The optimal control problem for a bilinear distributed parameter system subject to a quadratic cost functional is solved. It is shown that the optimal control is given by a convergent power series in the state with tensor coefficients.     

Optimal control of two-level quantum systems

We study the manipulation of two-level quantum systems. This research is motivated by the design of quantum mechanical logic gates which perform prescribed logic operations on a two-level quantum system, a quantum bit. We consider the problem of driving the evolution operator to a desired state, while minimizing an energy-type cost. Mathematically, this problem translates into an optimal control problem for systems varying on the Lie group of special unitary matrices of dimension two, with cost that is quadratic in the control. We develop a comprehensive theory of optimal control for two-level quantum systems. This includes, in particular, a classification of normal and abnormal extremals and a proof of regularity of the optimal control functions. The impact of the results of the paper on nuclear magnetic resonance experiments and quantum computation is discussed     

Optimal control of pull manufacturing systems

We consider the problem of optimal control of pull manufacturing systems. We study a fluid model of a flow shop, with buffer holding costs nondecreasing along the route. The system is subject to a constant exogenous demand, thus incurring additional shortfall/inventory costs. The objective is to determine the optimal control for the production rate at each machine in the system. We exhibit a decomposition of the flow shop into “sections” of contiguous machines, where, in each section, the head machine is the bottleneck for the downstream system. We exhibit the form of an optimal control and show that it is characterized by a set of “deferral times”, one for each head machine. Machines which are upstream of a head machine simply adopt a “just-in-time” production policy. The head machines initially stay idle for a period equal to their deferral time and thereafter produce as fast as possible, until the initial shortfall is eliminated. The optimal values of these deferral times are simply obtained by solving a set of quadratic programming problems. We also exhibit special cases of re-entrant lines, for which the optimal control is similarly computable     

Optimal feedback control of non-linear systems

A method is proposed for computing optimal nonlinear feedback control laws. It is shown that the feedback loop satisfies a system of quasi-linear partial differential equations. This system is of first order when the dimensions of the state and the control vector are the same. Hereby, it degenerates into algebraic equations when the performance index does not depend on the control. These important results offer new ways for determining optimal feedback laws. Connections with the Volterra series and the Hamilton-Jacobi-Bellman equation are treated. Some examples are given to illustrate the advantages of this method.     

Optimal impulse control of hyperbolic systems

The work was financed by the Ukrainian State Foundation for Basic Research.     

Optimal control of 2-D systems

Two-dimensional (2-D) optimal control theory that parallels one-dimensional (1-D) optimal control is developed. A generalized performance measure suited to 2-D systems is introduced. The canonical equations associated with this performance measure and a general nonlinear model are obtained. The 2-D linear quadratic regulator problem is formulated, and its canonical equations are derived for the Roesser model. An earlier result by T. Kaczorek and J. Klamka (1986) for the solution of the minimum-energy problem with fixed-final local state is rederived using this approach. A new problem, minimum-energy with fixed-final-pass local states is formulated and solved, and a numerical example is given     

Optimal control of unknown parameter systems

The problem is discussed of finding a cost functional for which an adaptive control law is optimal. The system under consideration is a partially observed linear stochastic system with unknown parameters. It is well known that an optimal finite-dimensional filter for this problem can be derived when the parameters belong to a finite set. Since the optimal filter involves the evaluation of a finite set of a posteriori probabilities for each of the parameter values given the observations, a natural adaptive control scheme is: (i) develop the optimal linear feedback law given each parameter; (ii) use the a posteriori probabilities to form the weighted average (convex combination) of the individual control policies; and (iii) use the weighted average as the control law. A quadratic cost functional is devised for which this strategy is optimal, in a general case, and it is shown that the probing effect identified with dual control problems is inherent in the standard linear-quadratic-Gaussian problem with parameter uncertainty     

Optimal control of distributed parameter systems

A method for determining the optimum control for distributed parameter systems is presented. The method is based upon mathematical programming and is restricted to systems which can be represented by discrete time models having coefficients which are functions of the spatial variables. The control function is assumed to be spatially concentrated. A closed form Bolutton is given which is valid when no constraints exist. An illustrative example is provided.     

Optimal discrete-pulse control of linear systems

Consideration was given to the linear problems of optimal control in the class of discrete-pulse and discrete-quasipulse control actions. Proposed was a dual method for construction of the open-loop solutions underlying the algorithms of the optimal controllers generating in real time the current values of the optimal feedbacks. The results obtained were illustrated by examples.     

Optimal decentralized control of dynamic systems

In this paper, several aspects of decentralized control theory applied to dynamic systems are studied. First of all, some classical definitions about matricial functions and new results on gradient calculations are presented. In the following we generalize to matricial problems the method of gradient projection of Rosen. Finally, some aspects of stability, initialization and initial condition independence are studied in detail, and two numerical examples are considered in order to emphasize the advantages of the given procedure: the decentralized Kalman filter and the optimal power-frequency control.