Asymptotically optimal production policies in dynamic stochastic jobshops with limited buffers

We consider a production planning problem for a jobshop with unreliable machines producing a number of products. There are upper and lower bounds on intermediate parts and an upper bound on finished parts. The machine capacities are modelled as finite state Markov chains. The objective is to choose the rate of production so as to minimize the total discounted cost of inventory and production. Finding an optimal control policy for this problem is difficult. Instead, we derive an asymptotic approximation by letting the rates of change of the machine states approach infinity. The asymptotic analysis leads to a limiting problem in which the stochastic machine capacities are replaced by their equilibrium mean capacities. The value function for the original problem is shown to converge to the value function of the limiting problem. The convergence rate of the value function together with the error estimate for the constructed asymptotic optimal production policies are established.     

Optimal control of piecewise deterministic markov process

The trajectories of piecewise deterministic Markov processes are solutions of an ordinary (vector)differential equation with possible random jumps between the different integral curves. Both continuous deterministic motion and the random jumps of the processes are controlled in order to minimize the expected value of a performance functional consisting of continuous, jump and terminal costs. A limiting form of the Hamilton-Jacobi-Bellman partial differential equation is shown to be a necessary and sufficient optimality condition. The existence of an optimal strategy is proved and acharacterization of the value function as supremum of smooth subsolutions is also given. The approach consists of imbedding the original control problem tightly in a convex mathematical programming problem on the space of measures and then solving the latter by dualit     

Hierarchical production policies in stochastic two-machine flowshops with finite buffers

This paper concerns production planning in manufacturing systems with two unreliable machines in tandem. The problem is formulated as a stochastic control problem in which the objective is to minimize the expected total cost of production, inventories, and backlogs. Since the sizes of the internal and external buffers are finite, the problem is one with state constraints. As the optimal solutions to this problem are extremely difficult to obtain due to the uncertainty in machine capacities as well as the presence of state constraints, a deterministic limting problem in which the stochastic machine capacities are replaced by their mean capacities is considered instead. The weak Lipschitz property of the value functions for the original and limiting problems is introduced and proved; a constraint domain approximation approach is developed to show that the value function of the original problem converges to that of the limiting problem as the rate of change in machine states approaches infinity. Asymptotic optimal production policies for the orginal problem are constructed explicity from the near-optimal policies of the limiting problem, and the error estimate for the policies constructed is obtained. Algorithms for constructing these policies are presented.This work was partly supported by CUHK Direct Grant 220500660, RGC Earmarked Grant CUHK 249/94E, and RGC Earmarked Grant CUHK 489/95E.     

Optimal joint survival reinsurance: An efficient frontier approach

The problem of optimal excess of loss reinsurance with a limiting and a retention level is considered. It is demonstrated that this problem can be solved, combining specific risk and performance measures, under some relatively general assumptions for the risk model, under which the premium income is modelled by any non-negative, non-decreasing function, claim arrivals follow a Poisson process and claim amounts are modelled by any continuous joint distribution. As a performance measure, we define the expected profits at time x of the direct insurer and the reinsurer, given their joint survival up to x, and derive explicit expressions for their numerical evaluation. The probability of joint survival of the direct insurer and the reinsurer up to the finite time horizon x is employed as a risk measure. An efficient frontier type approach to setting the limiting and the retention levels, based on the probability of joint survival considered as a risk measure and on the expected profit given joint survival, considered as a performance measure is introduced. Several optimality problems are defined and their solutions are illustrated numerically on several examples of appropriate claim amount distributions, both for the case of dependent and independent claim severities.     

Hierarchical controls in stochastic manufacturing systems with machines in tandem

This paper presents an asymptotic analysis of hierarchical production planning in a manufacturing system with serial machines that are subject to breakdown and repair, and with convex costs. The machines capacities are modeled as Markov chains. Since the number of parts in the internal buffers between any two machines needs to be non-negative, the problem is inherently a state constrained problem. As the rate of change in machines states approaches infinity, the analysis results in a limiting problem in which the stochastic machines capacity is replaced by the equilibrium mean capacity. A method of “lifting” and “modification” is introduced in order to construct near optimal controls for the original problem by using near optimal controls of the limiting problem. The value function of the original problem is shown to converge to the value function of the limiting problem, and the convergence rate is obtained based on some a priori estimates of the asymptotic behavior of the Markov chains. As a result, an error estimate can be obtained on the near optimality of the controls constructed for the original problem.     

A Deterministic Approach To Stochastic Optimal Control With Application To Anticipative Control

Using the decomposition of solution of SDE, we consider the stochastic optimal control problem with anticipative controls as a family of deterministic control problems parametrized by the paths of the driving Wiener process and of a newly introduced Lagrange multiplier stochastic process (nonanticipativity equality constraint). It is shown that the value function of these problems is the unique global solution of a robust equation (random partial differential equation) associated to a linear backward Hamilton-Jacobi-Bellman stochastic partial differential equation (HJB SPDE). This appears as limiting SPDE for a sequence of random HJB PDE's when linear interpolation approximation of the Wiener process is used. Our approach extends the Wong-Zakai type results [20] from SDE to the stochastic dynamic programming equation by showing how this arises as average of the limit of a sequence of deterministic dynamic programming equations. The stochastic characteristics method of Kunita [13] is used to represent the value function. By choosing the Lagrange multiplier equal to its nonanticipative constraint value the usual stochastic (nonanticipative) optimal control and optimal cost are recovered. This suggests a method for solving the anticipative control problems by almost sure deterministic optimal control. We obtain a PDE for the “cost of perfect information” the difference between the cost function of the nonanticipative control problem and the cost of the anticipative problem which satisfies a nonlinear backward HJB SPDE. Poisson bracket conditions are found ensuring this has a global solution. The cost of perfect information is shown to be zero when a Lagrangian submanifold is invariant for the stochastic characteristics. The LQG problem and a nonlinear anticipative control problem are considered as examples in this framework     

Generalized Derivatives of Lexicographic Linear Programs

Lexicographic linear programs are fixed-priority multiobjective linear programs that are a useful model of biological systems using flux balance analysis and for goal-programming problems. The objective function values of a lexicographic linear program as a function of its right-hand side are nonsmooth. This work derives generalized derivative information for lexicographic linear programs using lexicographic directional derivatives to obtain elements of the Bouligand subdifferential (limiting Jacobian). It is shown that elements of the limiting Jacobian can be obtained by solving related linear programs. A nonsmooth equation-solving problem is solved to illustrate the benefits of using elements of the limiting Jacobian of lexicographic linear programs.     

Actuator placement based on reachable set optimization for expected disturbance

This paper examines the role of the control objective and the control time in determining fuel-optimal actuator placement for structural control. A general theory is developed that can be easily extended to include alternative performance metrics such as energy and timeoptimal control. The performance metric defines a convex admissible control set which leads to a max-min optimization problem expressing optimal location as a function of initial conditions and control time. A solution procedure based on a nested genetic algorithm is presented and applied to an example problem. Results indicate that the optimal placement varies widely as a function of both control time and disturbance location. An approximate fitness function is presented to alleviate the computational burden associated with finding exact solutions. This function is shown to accurately predict the optimal actuator locations for a 6th-order system, and is further demonstrated on a 12th-order system.This work was supported by the US Department of Energy at Sandia National Laboratories under Contract DE-AC04-76DP00789.     

Hierarchical Production Control in Dynamic Stochastic Jobshops with Long-Run Average Cost

We consider a production planning problem for a dynamic jobshop producing a number of products and subject to breakdown and repair of machines. The machine capacities are assumed to be finite-state Markov chains. As the rates of change of the machine states approach infinity, an asymptotic analysis of this stochastic manufacturing systems is given. The analysis results in a limiting problem in which the stochastic machine availability is replaced by its equilibrium mean availability. The long-run average cost for the original problem is shown to converge to the long-run average cost of the limiting problem. The convergence rate of the long-run average cost for the original problem to that of the limiting problem together with an error estimate for the constructed asymptotic optimal control is established.     

Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation

In this paper, we propose a new deterministic global optimization method for solving nonlinear optimal control problems in which the constraint conditions of differential equations and the performance index are expressed as polynomials of the state and control functions. The nonlinear optimal control problem is transformed into a relaxed optimal control problem with linear constraint conditions of differential equations, a linear performance index, and a matrix inequality condition with semidefinite programming relaxation. In the process of introducing the relaxed optimal control problem, we discuss the duality theory of optimal control problems, polynomial expression of the approximated value function, and sum-of-squares representation of a non-negative polynomial. By solving the relaxed optimal control problem, we can obtain the approximated global optimal solutions of the control and state functions based on the degree of relaxation. Finally, the proposed global optimization method is explained, and its efficacy is proved using an example of its application.     

Convergence and Error Bound for Perturbation of Linear Programs

In various penalty/smoothing approaches to solving a linear program, one regularizes the problem by adding to the linear cost function a separable nonlinear function multiplied by a small positive parameter. Popular choices of this nonlinear function include the quadratic function, the logarithm function, and the x ln(x)-entropy function. Furthermore, the solutions generated by such approaches may satisfy the linear constraints only inexactly and thus are optimal solutions of the regularized problem with a perturbed right-hand side. We give a general condition for such an optimal solution to converge to an optimal solution of the original problem as the perturbation parameter tends to zero. In the case where the nonlinear function is strictly convex, we further derive a local (error) bound on the distance from such an optimal solution to the limiting optimal solution of the original problem, expressed in terms of the perturbation parameter.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

A Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints

We consider a mathematical program whose constraints involve a parametric P-matrix linear complementarity problem with the design (upper level) variables as parameters. Solutions of this complementarity problem define a piecewise linear function of the parameters. We study a smoothing function of this function for solving the mathematical program. We investigate the limiting behaviour of optimal solutions, KKT points and B-stationary points of the smoothing problem. We show that a class of mathematical programs with P-matrix linear complementarity constraints can be reformulated as a piecewise convex program and solved through a sequence of continuously differentiable convex programs. Preliminary numerical results indicate that the method and convex reformulation are promising.     

Stable sequential convex programming in a Hilbert space and its application for solving unstable problems

A parametric convex programming problem with an operator equality constraint and a finite set of functional inequality constraints is considered in a Hilbert space. The instability of this problem and, as a consequence, the instability of the classical Lagrange principle for it is closely related to its regularity and the subdifferentiability properties of the value function in the optimization problem. A sequential Lagrange principle in nondifferential form is proved for the indicated convex programming problem. The principle is stable with respect to errors in the initial data and covers the normal, regular, and abnormal cases of the problem and the case where the classical Lagrange principle does not hold. It is shown that the classical Lagrange principle in this problem can be naturally treated as a limiting variant of its stable sequential counterpart. The possibility of using the stable sequential Lagrange principle for directly solving unstable optimal control problems and inverse problems is discussed. For two illustrative problems of these kinds, the corresponding stable Lagrange principles are formulated in sequential form.     

Simplicial zero-point algorithms: A unifying description

In this paper, we consider the limiting paths of simplicial algorithms for finding a zero point. By rewriting the zero-point problem as a problem of finding a stationary point, the problem can be solved by generating a path of stationary points of the function restricted to an expanding convex, compact set. The limiting path of a simplicial algorithm to find a zero point is obtained by choosing this set in an appropriate way. Almost all simplicial algorithms fit in this framework. Using this framework, it can be shown very easily that Merrill's condition is sufficient for convergence of the algorithms.     

Adaptive neural dynamic surface control with fixed-time prescribed performance for uncertain nonstrict-feedback stochastic switched systems

An adaptive neural dynamic surface control (DSC) problem with fixed-time prescribed performance (FTPP) is investigated for a class of nonstrict-feedback stochastic switched systems. Differently from the existing works for FTPP problem, the stochastic switched systems with nonstrict-feedback form and completely unknown systems are considered in this paper, and the unknown functions are approximated by some radial basis function (RBF) neural networks (NNs). The desired adaptive neural controller is designed by using common Lyapunov function method and defining fixed-time prescribed performance function (PPF). And based on the adaptive DSC scheme with the nonlinear filter, the “explosion of complexity” problem is avoided. Besides, the constructed fixed-time PPF just need to meet the requirement of second derivative exists. According to the Lyapunov stability theory, the FTPP of output tracking error is achieved, and all signals of closed-loop system remain bounded in probability. Finally, simulation results are presented to verify the availability of the designed control strategy.     

A genetic algorithm approach on tree-like telecommunication network design problem

In the context of telecommunication networks, the network terminals involve certain constraints that are either related with the performance of the corresponding network or with the availability of some classes of devices. In this paper, we discuss a tree-like telecommunication network design problem with the constraint limiting the number of terminals. First, this problem is formulated as a leaf-constrained minimum spanning tree (lc-MST). Then we develop a tree-based genetic representation to encode the candidate solutions of the lc-MST problem. Compared with the existing heuristic algorithm, the numerical results show the high effectiveness of the proposed GA approach on this problem.     

A limited-feedback approximation scheme for optimal switching problems with execution delays

We consider a type of optimal switching problems with non-uniform execution delays and ramping. Such problems frequently occur in the operation of economical and engineering systems. We first provide a solution to the problem by applying a probabilistic method. The main contribution is, however, a scheme for approximating the optimal control by limiting the information in the state-feedback. In a numerical example the approximation routine gives a considerable computational performance enhancement when compared to a conventional algorithm.     

On some properties of the control problem under a program disturbance in a formalization based on the minimax risk (regret) criterion

A control problem under uncertainty for a system described by an ordinary differential equation with a terminal performance index is considered. The control and disturbance are subject to geometric constraints. The problem is formalized in classes of nonanticipating control strategies and program disturbances with the use of constructive ideal motions and the Savage minimax risk (regret) criterion. The properties of the used motion bundles are described and a number of relations characterizing the optimal risk function, which is an element of the formalization, are presented.     

A nonlinear programming approach for the sliding mode control design

We treat the sliding mode control problem by formulating it as a two phase problem consisting of reaching and sliding phases. We show that such a problem can be formulated as bicriteria nonlinear programming problem by associating each of these phases with an appropriate objective function and constraints. We then scalarize this problem by taking weighted sum of these objective functions. We show that by solving a sequence of such formulated nonlinear programming problems it is possible to obtain sliding mode controller feedback coefficients which yield a competitive performance throughout the control. We solve the nonlinear programming problems so constructed by using the modified subgradient method which does not require any convexity and differentiability assumptions. We illustrate validity of our approach by generating a sliding mode control input function for stabilization of an inverted pendulum.