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.     

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.     

A Primal-Dual Decomposition Algorithm for Multistage Stochastic Convex Programming

This paper presents a new and high performance solution method for multistage stochastic convex programming. Stochastic programming is a quantitative tool developed in the field of optimization to cope with the problem of decision-making under uncertainty. Among others, stochastic programming has found many applications in finance, such as asset-liability and bond-portfolio management. However, many stochastic programming applications still remain computationally intractable because of their overwhelming dimensionality. In this paper we propose a new decomposition algorithm for multistage stochastic programming with a convex objective and stochastic recourse matrices, based on the path-following interior point method combined with the homogeneous self-dual embedding technique. Our preliminary numerical experiments show that this approach is very promising in many ways for solving generic multistage stochastic programming, including its superiority in terms of numerical efficiency, as well as the flexibility in testing and analyzing the model.Research supported by Hong Kong RGC Earmarked Grant CUHK4233/01E.     

Value Estimation Approach to the Iri-Imai Method for Constrained Convex Optimization

In this paper we propose an extension of the so-called Iri-Imai method to solve constrained convex programming problems. The original Iri-Imai method is designed for linear programs and assumes that the optimal objective value of the optimization problem is known in advance. Zhang (Ref. 9) extends the method for constrained convex optimization but the optimum value is still assumed to be known in advance. In our new extension this last requirement on the optimal value is relaxed; instead only a lower bound of the optimal value is needed. Our approach uses a multiplicative barrier function for the problem with a univariate parameter that represents an estimated optimum value of the original optimization problem. An optimal solution to the original problem can be traced down by minimizing the multiplicative barrier function. Due to the convexity of this barrier function the optimal objective value as well as the optimal solution of the original problem are sought iteratively by applying Newtons method to the multiplicative barrier function. A new formulation of the multiplicative barrier function is further developed to acquire computational tractability and efficiency. Numerical results are presented to show the efficiency of the new method.His research supported by Hong Kong RGC Earmarked Grant CUHK4233/01E.Communicated by Z. Q. Luo     

Analysis of a Duopoly Supply Chain and its Application in Electricity Spot Markets

This paper studies a supply chain consisting of two suppliers and one retailer in a spot market, where the retailer uses the newsvendor solution as its purchase policy, and suppliers compete for the retailer’s purchase. Since each supplier’s bidding strategy affects the other’s profit, a game theory approach is used to identify optimal bidding strategies. We prove the existence and uniqueness of a Nash solution. It is also shown that the competition between the supplier leads to a lower market clearing price, and as a result, the retailer benefits from it. Finally, we demonstrate the applicability of the obtained results by deriving optimal bidding strategies for power generator plants in the deregulated California energy market. Supported in part by RGC (Hong Kong) Competitive Earmarked Research Grants (CUHK4167/04E and CUHK4239/03E), a Distinguished Young Investigator Grant from the National Natural Sciences Foundation of China, and a grant from Hundred Talents Program of the Chinese Academy of Sciences.     

Deterministic near-optimal control,part 1: Necessary and sufficient conditions for near-optimality

Near-optimization is as sensible and important as optimization for both theory and applications. This paper concerns dynamic near-optimization, or near-optimal control, for systems governed by deterministic ordinary differential equations. Necessary and sufficient conditions for near-optima control are studied. It is shown that any near-optimal control nearly maximizes the Hamiltonian in some integral sense, and vice versa, if some additional concavity conditions are imposed. Error estimates for both the near-optimality of the controls and the near-maximality of the Hamiltonian are obtained. A number of examples are presented to illustrate these results.This work was supported by the RGC Earmarked Grant CUHK 249/94E. Helpful comments from L. D. Berkovitz are gratefully acknowledged.     

The Fermat rule for multifunctions on Banach spaces

Using variational analysis, we study vector optimization problems with objectives being closed multifunctions on Banach spaces or in Asplund spaces. In particular, in terms of the coderivatives, we present Fermat’s rules as necessary conditions for an optimal solution of the above problems. As applications, we also provide some necessary conditions (in terms of Clarke’s normal cones or the limiting normal cones) for Pareto efficient points.This research was supported by a postdoctoral fellowship scheme (CUHK) and an Earmarked Grant from the Research Grant Council of Hong Kong. Research of the first author was also supported by the National Natural Science Foundation of P. R. China (Grant No. 10361008) and the Natural Science Foundation of Yunnan Province, P. R. China (Grant No. 2003A002M).     

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.     

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd ＞ 0 is a constant depending on the problem dimension and data.     

Merit functions in vector optimization

We study the weak domination property and weakly efficient solutions in vector optimization problems. In particular scalarization of these problems is obtained by virtue of some suitable merit functions. Some natural conditions to ensure the existence of error bounds for merit functions are also given. This research was supported by a direct grant (CUHK) and an Earmarked Grant from the Research Grant Council of Hong Kong.     

Single-Machine Scheduling with Exponential Processing Times and General Stochastic Cost Functions

We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E.     

Periodic-Review Inventory Model with Three Consecutive Delivery Modes and Forecast Updates

This paper is concerned with a periodic-review inventory system with three consecutive delivery modes (fast, medium, and slow) and demand forecast updates. At the beginning of each period, the inventory level and demand information are updated and decisions on how much to order using each of the three delivery modes are made. It is shown that there is a base-stock policy for fast and medium modes which is optimal. Furthermore, the optimal policy for the slow mode may not be a base-stock policy in general.This research was supported in part by a Faculty Research Grant from the University of Texas at Dallas, a RGC (Hong Kong) Competitive Earmarked Research Grant, a Distinguished Young Investigator Grant from the National Natural Sciences Foundation of China, and a Grant from the Hundred Talents Program of the Chinese Academy of Sciences.     

Best Approximation and Perturbation Property in Hilbert Spaces

We study the perturbation property of best approximation to a set defined by an abstract nonlinear constraint system. We show that, at a normal point, the perturbation property of best approximation is equivalent to an equality expressed in terms of normal cones. This equality is related to the strong conical hull intersection property. Our results generalize many known results in the literature on perturbation property of best approximation established for a set defined by a finite system of linear/nonlinear inequalities. The connection to minimization problem is considered.The authors thank the referees for valuable suggestions.K.F. Ng - This author was partially supported by Grant A0324638 from the National Natural Science Foundation of China and Grants (2001) 01GY051-66 and SZD0406 from Sichuan Province. Y.R. He -This author was supported by a Direct Grant (CUHK) and an Earmarked Grant from the Research Grant Council of Hong Kong.     

Hierarchical controls in stochastic manufacturing systems with convex costs

This paper presents an extension of earlier research on heirarchical control of stochastic manufacturing systems with linear production costs. A new method is introduced to construct asymptotically optimal open-loop and feedback controls for manufacturing systems in which the rates of machine breakdown and repair are much larger than the rate of fluctuation in demand and rate of discounting of cost. This new approach allows us to carry out an asymptotic analysis on manufacturing systems with convex inventory/backlog and production costs as well as obtain error bound estimates for constructed open loop controls. Under appropriate conditions, an asymptotically optimal Lipschitz feedback control law is obtained.This work was partly supported by the NSERC Grant A4619, URIF, General Motors of Canada, and Manufacturing Research Corporation of Ontario.     

On the average cost optimality equation and the structure of optimal policies for partially observable Markov decision processes

We consider partially observable Markov decision processes with finite or countably infinite (core) state and observation spaces and finite action set. Following a standard approach, an equivalent completely observed problem is formulated, with the same finite action set but with anuncountable state space, namely the space of probability distributions on the original core state space. By developing a suitable theoretical framework, it is shown that some characteristics induced in the original problem due to the countability of the spaces involved are reflected onto the equivalent problem. Sufficient conditions are then derived for solutions to the average cost optimality equation to exist. We illustrate these results in the context of machine replacement problems. Structural properties for average cost optimal policies are obtained for a two state replacement problem; these are similar to results available for discount optimal policies. The set of assumptions used compares favorably to others currently available.This research was supported in part by the Advanced Technology Program of the State of Texas, 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 Air Force Office of Scientific Research (AFSC) under Contract F49620-89-C-0044.     

Droplet solutions in the diblock copolymer problem with skewed monomer composition

A droplet solution characterizes the lamellar phase of a diblock copolymer when the two composing monomers maintain a skewed ratio. We study the threshold case where the free energy of a droplet solution is comparable to the free energy of the constant solution. Using a Lyapunov-Schmidt reduction approach, adapted to calculus of variations, we prove the existence of a free energy local minimizer with a given number of droplets. Also determined are the free energy, the droplet location, and the droplet size. Supported in part by a Direct Grant from CUHK and an earmarked Grant of RGC of Hong Kong.     

Asymptotic properties of constrained Markov Decision Processes

We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Based on the convergence of MDPs with a truncated state space to the problem with infinite state space, we show that an optimal stationary policy exists such that the number of randomisations it uses is less or equal to the number of constraints plus one. We finally apply the results to a dynamic scheduling problem.This work was partially supported by the Chateaubriand fellowship from the French embassy in Israel and by the European Grant BRA-QMIPS of CEC DG XIII     

Variable Programming: A Generalized Minimax Problem. Part II: Algorithms

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions. Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

Simple Conformal Superalgebras of Finite Growth

In this paper, we construct six families of infinite simple conformal superalgebras of finite growth based on our earlier work on constructing vertex operator superalgebras from graded assocaitive algebras. Three subfamilies of these conformal superalgebras are generated by simple Jordan algebras of types A, B, and C in a certain sense.Research supported by Hong Kong RGC Competitive Earmarked Research Grant HKUST709/96P.2000 Mathematics Subject Classification: primary 17A30, 17A60; secondary 17B20, 81Q60     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.