A model for strategic planning under uncertainty

Summary In this paper the multi-period strategic planning problem for a consumer sumer product manufacturing chain is considered. Our discussion is focused on investment decisions which, are economically optimal over the whole planning horizonT, while meeting customer demands and conforming to technological requirements. In strategic planning, time and uncertainty play important roles. The uncertainties in the model are due to different levels of forecast demands, cost estimates and equipment behaviour. The main aim of this paper is to develop and analyse a multiperiod stochastic model representing the entire manufacturing chain, from the acquisitions of raw material to the delivering of final products. The resulting optimization problem is computationally intractable because of the enormous, and sometimes unrealistic, number of scenarios that must be considered in order to identify the optimal planning strategy. We propose two different solution approaches; firstly, we apply a scenario risk analysis giving the related results of experiments on a particular real data set. We then describe and investigate an Integer Stochastic Programming formulation of the problem and propose, as a solution technique, a variation of Benders decomposition method, namely theL-shaped method.     

Optimal replacement policy for a deteriorating system with increasing repair times

This paper considers an optimal maintenance policy for a practical and reparable deteriorating system subject to random shocks. Modeling the repair time by a geometric process and the failure mechanism by a generalized δ-shock process, we develop an explicit expression of the long-term average cost per time unit for the system under a threshold-type replacement policy. Based on this average cost function, we propose a finite search algorithm to locate the optimal replacement policy N^∗ to minimize the average cost rate. We further prove that the optimal policy N^∗ is unique and present some numerical examples. Many practical systems fit the model developed in this paper.     

On optimal algorithms for the joint replenishment problem

In this paper, we demonstrate that the algorithm for determining the optimal strict cyclic policy for the Joint Replenishment Problem suggested by Fung and Ma¹ does not guarantee an optimal solution. We propose a modification that will ensure that the algorithm obtains the optimal strict cyclic policy. We then perform a comprehensive computational study to compare the modified Fung and Ma algorithm with other optimal algorithms for the problem. The study reveals that the optimal algorithm of Viswanathan² is computationally more efficient than other methods.     

Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm

The Multi-commodity Capacitated Multi-facility Weber Problem (MCMWP) is concerned with locating I-capacitated facilities in the plane in order to satisfy the demands of J customers for K commodities so that the total transportation cost is minimized. We propose a Lagrangean relaxation scheme and a subgradient-like algorithm based on the relaxation of the capacity and commodity bundle constraints. The resulting subproblem is a variant of the well-known Multi-facility Weber Problem and it can be solved by using column generation and branch-and-price on an equivalent set covering formulation, which is accurate but extremely inefficient. Therefore, we devise different strategies to increase the efficiency. They mainly benefit from the effective usage of the lower and upper bounds on the optimal value of the Lagrangean subproblem. On the basis of extensive computational tests, we can say that they increase the efficiency considerably and result in accurate Lagrangean heuristics.     

Stochastic Optimization over a Pareto Set Associated with a Stochastic Multi-Objective Optimization Problem

We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-objective Optimization Problem, whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation method in order to approach this problem. We prove that the Hausdorff–Pompeiu distance between the weakly Pareto sets associated with the Sample Average Approximation problem and the true weakly Pareto set converges to zero almost surely as the sample size goes to infinity, assuming that our Stochastic Multi-objective Optimization Problem is strictly convex. Then we show that every cluster point of any sequence of optimal solutions of the Sample Average Approximation problems is almost surely a true optimal solution. To handle also the non-convex case, we assume that the real objective to be minimized over the Pareto set depends on the expectations of the objectives of the Stochastic Optimization Problem, i.e. we optimize over the image space of the Stochastic Optimization Problem. Then, without any convexity hypothesis, we obtain the same type of results for the Pareto sets in the image spaces. Thus we show that the sequence of optimal values of the Sample Average Approximation problems converges almost surely to the true optimal value as the sample size goes to infinity.     

A new algorithm for a multi-item periodic review inventory system

In this paper, we deal with a multi-item, stochastic, periodic review inventory system with general cost structure which permits partial or complete backlogging of unfilled demand. Since both the (, S) policy and the mixed reorder policy are not optimal, we derive several properties of an optimal ordering policy and propose a new algorithm for computing it. This algorithm is based on the policy iteration method (PIM), but reduces substantially computation times in the policy evaluation and improvement routines of the PIM.     

Admission control for a multi-server queue with abandonment

In a M/M/N+M queue, when there are many customers waiting, it may be preferable to reject a new arrival rather than risk that arrival later abandoning without receiving service. On the other hand, rejecting new arrivals increases the percentage of time servers are idle, which also may not be desirable. We address these trade-offs by considering an admission control problem for a M/M/N+M queue when there are costs associated with customer abandonment, server idleness, and turning away customers. First, we formulate the relevant Markov decision process (MDP), show that the optimal policy is of threshold form, and provide a simple and efficient iterative algorithm that does not presuppose a bounded state space to compute the minimum infinite horizon expected average cost and associated threshold level. Under certain conditions we can guarantee that the algorithm provides an exact optimal solution when it stops; otherwise, the algorithm stops when a provided bound on the optimality gap is reached. Next, we solve the approximating diffusion control problem (DCP) that arises in the Halfin–Whitt many-server limit regime. This allows us to establish that the parameter space has a sharp division. Specifically, there is an optimal solution with a finite threshold level when the cost of an abandonment exceeds the cost of rejecting a customer; otherwise, there is an optimal solution that exercises no control. This analysis also yields a convenient analytic expression for the infinite horizon expected average cost as a function of the threshold level. Finally, we propose a policy for the original system that is based on the DCP solution, and show that this policy is asymptotically optimal. Our extensive numerical study shows that the control that arises from solving the DCP achieves a very similar cost to the control that arises from solving the MDP, even when the number of servers is small.     

Partially dynamic vehicle routing—models and algorithms

In this paper we propose a framework for dynamic routing systems based on their degree of dynamism. Next, we consider its impact on solution methodology and quality. Specifically, we introduce the Partially Dynamic Travelling Repairman Problem and describe several dynamic policies to minimize routing costs. The results of our computational study indicate that increasing the dynamic level results in a linear increase in route length for all policies studied. Furthermore, a Nearest Neighbour policy performed, on the average, uniformly better than the other dispatching rules studied. Among these, a Partitioning policy produced only slightly higher average route lengths.     

An analysis of Klimov's problem with parallel servers

We introduce a family of undiscounted branching bandits on parallel servers under controls which can impose priorities between customer classes. This family can be used to model a wide range of multi-class queueing scheduling problems, with the capacity to incorporate problem features such as machine breakdowns, complex patterns of preemption/non-preemption and semi-Markov extensions. An index policy (which we call Klimov's rule) is developed which is optimal in the particular case of a single server. An expression for its cost suboptimality is given for parallel servers. Under additional conditions on the nature of the stochastic evolution of the systems concerned, the policy is shown to be asymptotically optimal in a heavy traffic limit. These general results are utilised to develop an analysis of the index policy for a parallel server version of Klimov's classical M/GI/1 system with Bernoulli feedback. This work was supported by the Engineering and Physical Research Council through the award of grant GR/M09308. The author would also like to express his appreciation to Professor I. C. Paschalidis for helpful discussions on Klimov's problem and to Professors J. Niño-Mora and G. Weiss for many discussions and much encouragement     

Average optimality inequality for continuous-time Markov decision processes in Polish spaces

In this paper, we study the average optimality for continuous-time controlled jump Markov processes in general state and action spaces. The criterion to be minimized is the average expected costs. Both the transition rates and the cost rates are allowed to be unbounded. We propose another set of conditions under which we first establish one average optimality inequality by using the well-known “vanishing discounting factor approach”. Then, when the cost (or reward) rates are nonnegative (or nonpositive), from the average optimality inequality we prove the existence of an average optimal stationary policy in all randomized history dependent policies by using the Dynkin formula and the Tauberian theorem. Finally, when the cost (or reward) rates have neither upper nor lower bounds, we also prove the existence of an average optimal policy in all (deterministic) stationary policies by constructing a “new” cost (or reward) rate. Research partially supported by the Natural Science Foundation of China (Grant No: 10626021) and the Natural Science Foundation of Guangdong Province (Grant No: 06300957).     

Stochastic inventory problem with piecewise quadratic holding cost function containing a cost-free interval

In this paper, we consider a periodic-review stochastic inventory model with an asymmetric or piecewise-quadratic holding cost function and nonnegative production levels. It is assumed that the cost of deviating from an ideal production level or existing capacity is symmetric quadratic. It is shown that the optimal order policy is similar to the (s, S) policies found in the literature, except that the order-up-to quantity is a nonlinear function of the entering inventory level. Dynamic programming is used to derive the optimal policy. We provide numerical examples and a sensitivity analysis on the problem parameters.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A5872. The authors wish to thank an anonymous referee for very helpful comments on an earlier version of this paper.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

Dynamic pricing for perishable items with costly price adjustments

Dynamic pricing is widely adopted in inventory management for perishable items, and the corresponding price adjustment cost should be taken into account. This work assumes that the price adjustment cost comprises of a fixed component and a variable one, and attempts to search for the optimal dynamic pricing strategy to maximize the firm’s profit. However, considering the fixed price adjustment cost turns this dynamic pricing problem to a non-smooth optimal control problem which cannot be solved directly by Pontryagin’s maximum principle. Hence, we first degenerate the original problem into a standard optimal control problem and calculate the corresponding solution. On the basis of this solution, we further propose a suboptimal pricing strategy which simultaneously combines static pricing and dynamic pricing strategies. The upper bound of profit gap between the suboptimal solution and the optimal one is obtained. Numerical simulation indicates that the suboptimal pricing strategy enjoys an efficient performance.     

Multi-group support vector machines with measurement costs: A biobjective approach

Support Vector Machine has shown to have good performance in many practical classification settings. In this paper we propose, for multi-group classification, a biobjective optimization model in which we consider not only the generalization ability (modeled through the margin maximization), but also costs associated with the features. This cost is not limited to an economical payment, but can also refer to risk, computational effort, space requirements, etc. We introduce a Biobjective Mixed Integer Problem, for which Pareto optimal solutions are obtained. Those Pareto optimal solutions correspond to different classification rules, among which the user would choose the one yielding the most appropriate compromise between the cost and the expected misclassification rate.     

Lipschitzian Regularity of Minimizers for Optimal Control Problems with Control-Affine Dynamics

We study the Lagrange Problem of Optimal Control with a functional and control-affine dynamics = f(t,x) + g(t,x)u and (a priori) unconstrained control u∈ \bf R ^m . We obtain conditions under which the minimizing controls of the problem are bounded—a fact which is crucial for the applicability of many necessary optimality conditions, like, for example, the Pontryagin Maximum Principle. As a corollary we obtain conditions for the Lipschitzian regularity of minimizers of the Basic Problem of the Calculus of Variations and of the Problem of the Calculus of Variations with higher-order derivatives. Accepted 15 March 1999     

Risk-averse stochastic optimal control: An efficiently computable statistical upper bound

In this paper, we discuss an application of the Stochastic Dual Dynamic Programming (SDDP) type algorithm to nested risk-averse formulations of Stochastic Optimal Control (SOC) problems. We propose a construction of a statistical upper bound for the optimal value of risk-averse SOC problems. This outlines an approach to a solution of a long standing problem in that area of research. The bound holds for a large class of convex and monotone conditional risk mappings. Finally, we show the validity of the statistical upper bound to solve a real-life stochastic hydro-thermal planning problem.     

Dynamic control of a flexible server in an assembly-type queue with setup costs

We consider a queueing system with multiple stations attended by a single flexible server. An order arriving at this system needs to go through each station only once but there is no particular precedence relationship among these stations. One can also think of this system as an assembly system where each station processes a different component of an order and once all the components associated with an order are processed they are assembled instantaneously. A holding cost is charged for keeping the orders in the system and there is a penalty associated with the switches of the server between stations. Our objective is to minimize the long-run average costs by dynamically assigning the server to stations based on the system state. Using sample-path arguments, we provide partial characterizations of the optimal policy and provide sufficient conditions under which a simple state-independent policy that works on one order at a time is optimal. We also propose three simple threshold policies and present a numerical study that provides supporting evidence for the superior performance of our double-threshold heuristic.     

求解硬时间窗约束下随机需求库存-路径问题的优化算法

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem, SDIRP)即考虑随机需求环境下供应链中库存与配送的协调优化问题,是实施供应商管理库存策略过程中的关键所在,也是典型的NP难题之一。文章以具有硬时间窗约束的随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem with Hard Time Windows, SDIRPHTW)为研究对象,将SDIRPHTW分解为直接配送的随机库存-路径问题和具有硬时间窗约束的路径优化问题两个子问题,并以最小化系统运行成本和用车数量为目标,设计了一个基于(s,S)库存策略和修正C-W节约法的启发式算法。最后,通过相应的数值算例验证了算法的有效性。     

A three-phase matheuristic for the Packaging and Shipping Problem

E-commerce has been continuously growing in the last years to a primary retail market. Recently in France, the threshold of 1 billion of online transactions was overcome. Due to a high demand fluctuation of e-commerce, the workforce sizing for the logistic chain is a challenging problem. Companies have to develop good strategies to have a sustainable workforce size while guaranteeing a high-level service.In this paper, we consider the management of the workforce for a warehouse of an e-commerce company. Specifically, we address issues as i) How the workforce at the warehouse can be determined; ii) What is the daily operational production planning; iii) How the demand peaks can be smoothed, and the production maintained ideally constant over the time horizon.To provide answers to these issues, we introduce the Packaging and Shipping Problem (PSP). The PSP looks for a solution approach that jointly determines the workforce over a multi-period horizon and daily operational plans while minimizing the total logistics cost. We consider two strategies that aim to enhance the flexibility of the process and the efficiency of resources use: reassignment and postponement. To tackle the Packaging and Shipping Problem we propose a model, and a three-phase matheuristic. This heuristic is proved to be competitive with respect to the direct solution of the model with a commercial solver on real-life based instances.