A stochastic approximation method for the single-leg revenue management problem with discrete demand distributions

We consider the problem of optimally allocating the seats on a single flight leg to the demands from multiple fare classes that arrive sequentially. It is well-known that the optimal policy for this problem is characterized by a set of protection levels. In this paper, we develop a new stochastic approximation method to compute the optimal protection levels under the assumption that the demand distributions are not known and we only have access to the samples from the demand distributions. The novel aspect of our method is that it works with the nonsmooth version of the problem where the capacity can only be allocated in integer quantities. We show that the sequence of protection levels generated by our method converges to a set of optimal protection levels with probability one. We discuss applications to the case where the demand information is censored by the seat availability. Computational experiments indicate that our method is especially advantageous when the total expected demand exceeds the capacity by a significant margin and we do not have good a priori estimates of the optimal protection levels.     

Inventory management for dual sales channels with inventory-level-dependent demand

This paper studies the inventory management problem of dual channels operated by one vendor. Demands of dual channels are inventory-level-dependent. We propose a multi-period stochastic dynamic programming model which shows that under mild conditions, the myopic inventory policy is optimal for the infinite horizon problem. To investigate the importance of capturing demand dependency on inventory levels, we consider a heuristic where the vendor ignores demand dependency on inventory levels, and compare the optimal inventory levels with those recommended by the heuristic. Through numerical examples, we show that the vendor may order less for dual channels than those recommended by the heuristic, and the difference between the inventory levels in the two cases can be so large that the demand dependency on inventory levels cannot be neglected. In the end, we numerically examine the impact of different ways to treat unmet demand and obtain some managerial insights.     

Advertising decisions for a segmented market

We consider the problem of choosing the levels of a set of advertising media in order to maximize the firm profit when the market is heterogeneous. Advertising efforts affect the demand of the different segments variably and we assume that the advertising effects on demand over time are mediated by a vector goodwill variable. A first general advertising decision problem is stated and solved in the non-linear programming framework. A preference index is then obtained for the medium selection problem when each segment demand function is linear in goodwill and each medium advertising cost function is quadratic in its level. Finally the theoretical case of disjoint advertising media is discussed.     

Manufacturer incentives to improve retail service levels

In this paper we provide a solution to the problem of how a manufacturer can provide an incentive to a separately-owned retailer to raise its service level above the level it would choose on its own. We analyze the effects the manufacturer's incentive has on the individual profits of the retailer and manufacturer, as well as their joint profits. Our work is an application of game theory in which we tackle the problem posed by separate ownership of the two firms and the resulting conflict over the gains from cooperation. We utilize a plausible model of service-sensitive demand, one which is relatively free of ad hoc assumptions. Our approach has the strength that it proposes a credible solution to the problem of manufacturer-retailer cooperation when profits are sensitive to retail service levels. Our results indicate that the optimal level of incentive for the manufacturer and the resulting shares of the manufacturer and retailer in increased profits are particularly sensitive to the underlying variability of demand and to the relative variability of additional demand induced by higher service levels.     

Planning Annualised Hours with a Finite Set of Weekly Working Hours and Joint Holidays

The need to adjust productive capacity to seasonal demand and the increasing flexibility in the distribution of annual working hours has given rise to new problems with respect to the organisation of staff working time. This paper presents a problem of planning annual working hours, in which the number of weekly working hours for any worker must belong to a previously agreed finite set and holiday weeks are the same for all the staff members. The problem is modelled and solved as a mixed integer linear program.     

Interactive High-low Search: The Case of Lost Sales

We consider the problem of supplying perishable goods to disloyal customers. As in traditional stock-control literature, a penalty is incurred whenever there is a stockout. However, in contrast to mainstream models, loss of goodwill is explicitly treated by incorporating the behavioural assumption that a fixed proportion of unsatisfied demand is lost forever after each stockout. The problem consists of finding supply levels which minimize costs of over- and underproduction, given unknown but deterministic demand. We derive optimal adaptive search procedures under varying assumptions of a priori knowledge about demand. Optimal strategies are compared to myopic strategies. Our methodology extends the mathematical theory of ‘high-low search’ for a hidden point to incorporate the ‘Heisenberg principle’: the position of the hidden point (demand) is directly influenced by the actions (supply levels) of the searcher.     

Cyclical schedules for one-warehouse,multi-retailer systems with dynamic demands

In a one-warehouse, multi-retailer system, a cyclical schedule is characterised by fixed order intervals at the warehouse and retailers. Cyclical schedules offer advantages in terms of simplicity and ease of control, but under dynamic demand conditions they are higher in cost than non-cyclical schedules. This study presents a mathematical formulation of the cyclical problem, and then outlines an algorithm to obtain optimal solutions. An experiment is then conducted to investigate the additional cost of cyclical schedules as a function of problem characteristics relevant to one-warehouse, multi-retailer systems. Results show that coefficient of demand variation has the strongest effect on the additional cost of cyclical scheduling. However, even at relatively high levels of demand variation, the additional costs of cyclical scheduling are quite moderate.     

Multi-source facility location–allocation and inventory problem

We consider a joint facility location–allocation and inventory problem that incorporates multiple sources of warehouses. The problem is motivated by a real situation faced by a multinational applied chemistry company. In this problem, multiple products are produced in several plants. Warehouse can be replenished by several plants together because of capabilities and capacities of plants. Each customer in this problem has stochastic demand and certain amount of safety stock must be maintained in warehouses so as to achieve certain customer service level. The problem is to determine number and locations of warehouses, allocation of customers demand and inventory levels of warehouses. The objective is to minimize the expected total cost with the satisfaction of desired demand weighted average customer lead time and desired cycle service level. The problem is formulated as a mixed integer nonlinear programming model. Utilizing approximation and transformation techniques, we develop an iterative heuristic method for the problem. An experiment study shows that the proposed procedure performs well in comparison with a lower bound.     

An implementation of Lagrangian decomposition in solving a multi-item production scheduling problem with changeover cost and restrictions

This paper considers a production system where several products are manufactured over several time periods with specified demand levels. The minimal changeover and holding cost problem is formulated as a mixed integer program model. An efficient heuristic method is proposed by decomposing the problem into a pair of network subproblems. Some computational results showing the efficiency of the method are presented for a set of test problems. Finally, extensions to the general problem are discussed.     

A two-level hedging point policy for controlling a manufacturing system with time-delay,demand uncertainty and extra capacity

This paper focuses on the production control of a manufacturing system with time-delay, demand uncertainty and extra capacity. Time-delay is a typical feature of networked manufacturing systems (NMS), because an NMS is composed of many manufacturing systems with transportation channels among them and the transportation of materials needs time. Besides this, for a manufacturing system in an NMS, the uncertainty of the demand from its downstream manufacturing system is considered; and it is assumed that there exist two-levels of demand rates, i.e., the normal one and the higher one, and that the time between the switching of demand rates are exponentially distributed. To avoid the backlog of demands, it is also assumed that extra production capacity can be used when the work-in-process (WIP) cannot buffer the high-level demands rate. For such a manufacturing system with time-delay, demand uncertainty and extra capacity, the mathematical model for its production control problem is established, with the objective of minimizing the mean costs for WIP inventory and occupation of extra production capacity. To solve the problem, a two-level hedging point policy is proposed. By analyzing the probability distribution of system states, optimal values of the two hedging levels are obtained. Finally, numerical experiments are done to verify the effectiveness of the control policy and the optimality of the hedging levels.     

Workforce planning at USPS mail processing and distribution centers using stochastic optimization

Service organizations that operate outside the normal 8-hour day and face wide fluctuations in demand constantly struggle to optimize the size and composition of their workforce. Recent research has shown that improved personnel scheduling methods that take demand uncertainty into account can lead to significant reductions in labor costs. This paper addresses a staff planning and scheduling problem that arises at United States Postal Service (USPS) mail processing & distribution centers (P&DCs) and develops a two-stage stochastic integer program with recourse for the analysis. In the first stage, before the demand is known, the number of full-time and part-time employees is determined for the permanent workforce. In the second stage, the demand is revealed and workers are assigned to specific shifts during the week. When necessary, overtime and casual labor are used to satisfy demand. This paper consists of two parts: (1) the analysis of the demand distribution in light of historical data, and (2) the development and analysis of the stochastic integer programming model. Using weekly demand for a three-year period, we first investigate the possibility that there exists an end-of-month effect, i.e., the week at the end of month has larger volume than the other weeks. We show that the data fail to indicate that this is the case. In the computational phase of the work, three scenarios are considered: high, medium, and low demand. The stochastic optimization problem that results is a large-scale integer program that embodies the full set of contractual agreements and labor rules governing the design of the workforce at a P&DC. The usefulness of the model is evaluated by solving a series of instances constructed from data provided by the Dallas facility. The results indicate that significant savings are likely when the recourse problem is used to help structure the workforce. This work was supported in part by the National Science Foundation under grants DMI-0218701 and DMI-0217927.     

The dynamic multilevel assignment problem as a stochastic extremal process

This paper considers the multilevel assignment problem (i.e. the assignment problem where the supply alternatives are ranked in hierarchical levels) under the assumption that the utility components for each pairwise matching are stochastic. A dynamic version of the multilevel stochastic assignment model is developed, where both demand and supply evaluate alternatives according to a stochastic extremal process, i.e. a process where the maximum of a sequence of random variables is taken into account. The probability distributions of the random variables which describe the joint dynamic behaviour of demand and supply are found. It is also shown that the assignment probabilities assume the structure of a nested-logit model.     

Decision-making and the newsvendor problem: an experimental study

This paper investigates repetitive purchase decisions of perishable items in the face of uncertain demand (the newsvendor problem). The experimental design includes: high, or low profit levels; and uniform, or normal demand distributions. The results show that in all cases both learning and convergence occur and are effected by: (1) the mean demand; (2) the order-size of the maximal expected profit; and (3) the demand level of the immediately preceding round. In all cases of the experimental design, the purchase order converges to a value between the mean demand and the quantity for maximizing the expected profit.     

Modeling fuzzy multi-period production planning and sourcing problem with credibility service levels

A great deal of research has been done on production planning and sourcing problems, most of which concern deterministic or stochastic demand and cost situations and single period systems. In this paper, we consider a new class of multi-period production planning and sourcing problem with credibility service levels, in which a manufacturer has a number of plants and subcontractors and has to meet the product demand according to the credibility service levels set by its customers. In the proposed problem, demands and costs are uncertain and assumed to be fuzzy variables with known possibility distributions. The objective of the problem is to minimize the total expected cost, including the expected value of the sum of the inventory holding and production cost in the planning horizon. Because the proposed problem is too complex to apply conventional optimization algorithms, we suggest an approximation approach (AA) to evaluate the objective function. After that, two algorithms are designed to solve the proposed production planning problem. The first is a PSO algorithm combining the AA, and the second is a hybrid PSO algorithm integrating the AA, neural network (NN) and PSO. Finally, one numerical example is provided to compare the effectiveness of the proposed two algorithms.     

Two-resource stochastic capacity planning employing a Bayesian methodology

We examine a stochastic capacity-planning problem with two resources that can satisfy demand for two services. One of the resources can only satisfy demand for a specific service, whereas the other resource can provide both services. We formulate the problem of choosing the capacity levels of each resource to maximize expected profits. In addition, we provide analytic, easy-to-interpret optimal solutions, as well as perform a comparative statics analysis. As applying the optimal solutions effectively requires good estimates of the unknown demand parameters, we also examine Bayesian estimates of the demand parameters derived via a class of conjugate priors. We compare the optimal expected profits when demands for the two services follow independent distributions with informative and non-informative priors, and demonstrate that using good informative priors on demand can significantly improve performance.     

Finding and identifying optimal inventory levels for systems with common components

In this article, we consider the problem of finding the optimal inventory level for components in an assembly system where multiple products share common components in the presence of random demand. Previously, solution procedures that identify the optimal inventory levels for components in a component commonality problem have been considered for two product or one common component systems. We will here extend this to a three products system considering any number of common components. The inventory problem considered is modeled as a two stage stochastic recourse problem where the first stage is to set the inventory levels to maximize expected profit while the second stage is to allocate components to products after observing demand. Our main contribution, and the main focus of this paper, is the outline of a procedure that finds the gradient for the stochastic problem, such that an optimal solution can be identified and a gradient based search method can be used to find the optimal solution.     

Hybrid heuristics for a short sea inventory routing problem

We consider a short sea fuel oil distribution problem where an oil company is responsible for the routing and scheduling of ships between ports such that the demand for various fuel oil products is satisfied during the planning horizon. The inventory management has to be considered at the demand side only, and the consumption rates are given and assumed to be constant within the planning horizon. The objective is to determine distribution policies that minimize the routing and operating costs, while the inventory levels are maintained within their limits. We propose an arc-load flow formulation for the problem which is tightened with valid inequalities. In order to obtain good feasible solutions for planning horizons of several months, we compare different hybridization strategies. Computational results are reported for real small-size instances.     

基于二层信用支付的变质物品库存模型

基于时变需求的库存问题一直是库存管理者关注的重点之一,大多数基于二层信用支付的库存模型都是假设需求率为常数.假设需求率是时间的指数函数,建立了二层信用支付条件下的变质物品库存模型,并证明了最优解是存在且唯一的,给出了确定最优补货策略的算法步骤,最后通过数值例子对主要参数进行了灵敏度分析.     

Alternate risk measures for emergency medical service system design

The stochastic nature of emergency service requests and the unavailability of emergency vehicles when requested to serve demands are critical issues in constructing valid models representing real life emergency medical service (EMS) systems. We consider an EMS system design problem with stochastic demand and locate the emergency response facilities and vehicles in order to ensure target levels of coverage, which are quantified using risk measures on random unmet demand. The target service levels for each demand site and also for the entire service area are specified. In order to increase the possibility of representing a wider range of risk preferences we develop two types of stochastic optimization models involving alternate risk measures. The first type of the model includes integrated chance constraints (ICCs ), whereas the second type incorporates ICCs  and a stochastic dominance constraint. We develop solution methods for the proposed single-stage stochastic optimization problems and present extensive numerical results demonstrating their computational effectiveness.     

The network equilibrium problem with mixed demand

We formulate the network equilibrium problem with mixed demand which generalizes the problems of network equilibrium with fixed and elastic demand. We prove the equilibrium conditions for this problem and propose some conditions of existence of a solution that are based on the coercivity property.We establish a connection between the problem of network equilibrium with mixed demand and the problem of auction equilibrium. The results of test calculations are presented for a model example.