Optimal Control of Markov Processes with Age-Dependent Transition Rates

We study optimal control of Markov processes with age-dependent transition rates. The control policy is chosen continuously over time based on the state of the process and its age. We study infinite horizon discounted cost and infinite horizon average cost problems. Our approach is via the construction of an equivalent semi-Markov decision process. We characterise the value function and optimal controls for both discounted and average cost cases.     

Improved algorithms for single machine scheduling with release dates and rejections

We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.     

串联式多级火箭成本问题初论

本文以火箭最大速度值的一般变化规律为基础, 改进了以前考虑火箭发射的成本问题的常用数学模型：最省的最省推进剂方案, 详细研究了各种情况下串联式多级火箭的成本问题,并以算例验证了所得的新成本计算模型的有效性.     

Economic Production Lot Size Model with Variable Production Rate and Imperfect Quality

The classical economic production lot size (EPL) model assumes a constant production rate that is predetermined and inflexible, and perfect quality. Recent models have removed the assumption of perfect quality while maintaining the inflexible production rate assumption. Production rates in many cases, such as orders filled by a machine, can be changed. Moreover, unit production cost and process quality depend on the production rate. In this paper, we extend the EPL model to cases where the production rate is a decision variable. Unit production cost becomes a function of the production rate. Also, the quality of the production process deteriorates with increased production rate. We solve the proposed model for special cost and quality functions and illustrate the results with a numerical example. The results show that, for cases where increases in the production rate lead to a significant deterioration in quality, the optimal production rate may be smaller than the rate that minimizes unit production cost. For cases where quality is largely independent of the production rate, the optimal production rate may be larger than the rate that minimizes unit production cost.     

A single-item economic lot-sizing problem with a non-uniform resource: Approximation

We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. Fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero.     

The approximability of three-dimensional assignment problems with bottleneck objective

We discuss two special cases of the three-dimensional bottleneck assignment problem where a certain underlying cost function satisfies the triangle inequality. We present polynomial time 2-approximation algorithms for the broadest class of these special cases, and we prove that (unless P = NP) this factor 2 is best possible even in the highly restricted setting of the Euclidean plane.     

On the complexity of the one-terminal network design problem

The one-terminal network design problem considered here is to select a subset of the set of potential edges so as to minimize the sum of construction cost plus expected usage cost with discounting. We distinguish between easy and hard cases of this problem.     

Optimal cost and policy for a Markovian replacement problem

We consider the computation of the optimal cost and policy associated with a two-dimensional Markov replacement problem with partial observations, for two special cases of observation quality. Relying on structural results available for the optimal policy associated with these two particular models, we show that, in both cases, the infinitehorizon, optimal discounted cost function is piecewise linear, and provide formulas for computing the cost and the policy. Several examples illustrate the usefulness of the results.This research was supported by the Air Force Office of Scientific Research Grant AFOSR-86-0029, by the National Science Foundation Grant ECS-86-17860, by the Advanced Technology Program of the State of Texas, and by the Air Force Office of Scientific Research (AFSC) Contract F49620-89-C-0044.     

一类博弈排序问题的纳什均衡存在性证明

研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、 激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机, 其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并证明各算法得到的排序都是纳什均衡.     

Optimal Consumption Portfolio and No-Arbitrage with Nonproportional Transaction Costs

In this paper we consider a finite-state financial market with non-proportional transaction cost and bid-ask spreads. The transaction cost consists of two parts: a fixed cost and a proportional cost to the size of transaction. We show that the existence of an optimal consumption policy implies that the market has no strong arbitrage; the opposite, however, is not true, i.e., no strong arbitrage does not imply the existence of an optimal consumption policy. This is in sharp contrast with the case of proportional transaction cost and other cases reported in the literature, where no strong arbitrage is equivalent to the existence of an optimal consumption policy. We also study the relationship between weak arbitrage and strong arbitrage. Different from the market with proportional transaction cost, we find that these two forms of arbitrage are equivalent unless the fixed cost is zero. A necessary and sufficient condition for the existence of an optimal consumption policy is also obtained. Supported by CAS, NSFC, RGC of Hong Kong and NSF under Grant No. DMI-0196084 and DMI-0200306.     

Stochastic ultimate load analysis:models and solution methods 1

The stochastic ultimate load analysis model used in the safety analysis of engineering structures can be treated as a special case of chance-constrained problems (CCP) which minimize a stochastic cost function subject to some probabilistic constraints. Some special cases (such as a deterministic cost function with probabilistic constraints or deterministic constraints with a random cost function) for ultimate load analysis have airady been investigated by various researchers. In this paper, a generai probabilistic approach to stochastic ultimate load analysis is given. In doing so, some approximation techniques are needed due to the fact that the problems at hand are too complicated to evaluate precisely. We propose two extensions of the SQP method in which the variables appear in the algorithms inexactly. These algorithms are shown to be globally convergent for all models and locally superlinearly convergent for some special cases     

Designing contracts for a closed-loop supply chain under information asymmetry

This paper studies the problem of designing contracts in a closed-loop supply chain when the cost of collection effort is the retailer’s private information. We investigate four cases: two contracts (a two-part nonlinear contract and a collection effort requirement contract), each under complete information and asymmetric information. We derive the manufacturer’s optimal contracts for all four cases and analyze the impact of information on the equilibrium results of supply chain members.     

How to minimize the cost of iterative methods in the presence of perturbations

We consider iterative methods for approximating solutions of nonlinear equations, where the iteration cannot be computed exactly, but is corrupted by additive perturbations. The cost of computing each iteration depends on the size of the perturbation. For a class of cost functions, we show that the total cost of producing an ε-approximation can be made proportional to the cost c(ε) of one single iterative step performed with the accuracy proportional to ε. We also demonstrate that for some cost functions the total cost is proportional to c(ε)². In both cases matching lower bounds are shown. The results find natural application to establishing the complexity of nonlinear boundary-value problems, where they yield an improvement over the known upper bounds, and remove the existing gap between the upper and lower bounds.     

Weber problems with mixed distances and regional demand

We consider a location problem where the distribution of the existing facilities is described by a probability distribution and the transportation cost is given by a combination of transportation cost in a network and continuous distance. The motivation is that in many cases transportation cost is partly given by the cost of travel in a transportation network whereas the access to the network and the travel from the exit of the network to the new facility is given by a continuous distance.      

Markov control processes with randomized discounted cost

In this paper we consider Markov Decision Processes with discounted cost and a random rate in Borel spaces. We establish the dynamic programming algorithm in finite and infinity horizon cases. We provide conditions for the existence of measurable selectors. And we show an example of consumption-investment problem. This research was partially supported by the PROMEP grant 103.5/05/40.     

Cost efficiency measures in data envelopment analysis with data uncertainty

This paper extends the classical cost efficiency (CE) models to include data uncertainty. We believe that many research situations are best described by the intermediate case, where some uncertain input and output data are available. In such cases, the classical cost efficiency models cannot be used, because input and output data appear in the form of ranges. When the data are imprecise in the form of ranges, the cost efficiency measure calculated from the data should be uncertain as well. So, in the current paper, we develop a method for the estimation of upper and lower bounds for the cost efficiency measure in situations of uncertain input and output data. Also, we develop the theory of efficiency measurement so as to accommodate incomplete price information by deriving upper and lower bounds for the cost efficiency measure. The practical application of these bounds is illustrated by a numerical example.     

The dynamics of asset lifetime under technological change

The variable lifetime of assets is analyzed in a serial replacement problem. Technological change impacts the maintenance cost and new asset cost. The optimal asset lifetime appears to be constant only when both costs decrease with the same rate. We identify cases when the technological change decreases or increases the optimal lifetime.     

Robust inverse optimization

Given an observation of a decision-maker’s uncertain behavior, we develop a robust inverse optimization model for imputing an objective function that is robust against mis-specifications of the behavior. We characterize the inversely optimized cost vectors for uncertainty sets that may or may not intersect the feasible region, and propose tractable solution methods for special cases. We demonstrate the proposed model in the context of diet recommendation.     

Stochastic scheduling of parallel queues with set-up costs

We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a set-up cost. The objective is to minimize the expected cost due to the waiting of jobs and the switching of the server. A set-up cost is required to effect an instantaneous switch from one queue to another. We partially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cases of two and three queues by comparison with a numerically obtained optimal policy. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances with four queues.     

Minmax scheduling problems with common flow-allowance

In due-date assignment problems with a common flow-allowance, the due-date of a given job is defined as the sum of its processing time and a job-independent constant. We study flow-allowance on a single machine, with an objective function of a minmax type. The total cost of a given job consists of its earliness/tardiness and its flow-allowance cost components. Thus, we seek the job schedule and flow-allowance value that minimize the largest cost among all the jobs. Three extensions are considered: the case of general position-dependent processing times, the model containing an explicit cost for the due-dates, and the setting of due-windows. Properties of optimal schedules are fully analysed in all cases, and all the problems are shown to have polynomial time solutions.