Search

In this paper we propose a methodology to set prices of perishable items in the context of a retail chain with coordinated prices among its stores and compare its performance with actual practice in a real case study. We formulate a stochastic dynamic programming problem and develop heuristic solutions that approximate optimal solutions satisfactorily. To compare this methodology with current practices in the industry, we conducted two sets of experiments using the expertise of a product manager of a large retail company in Chile. In the first case, we contrast the performance of the proposed methodology with the revenues obtained during the 1995 autumn-winter season. In the second case, we compare it with the performance of the experienced product manager in a “simulation-game” setting. In both cases, our methodology provides significantly better results than those obtained by current practices.

Based on our interactions with managers at two large hotels, we present a realistic model of the hotel reservation problem. Unlike traditional models, ours does not assume that all customers arrive simultaneously on the targeted booking date. We explain why this assumption may not be appropriate for the hotel industry and develop a model of reservation booking which explicitly includes the room allocation decisions which are made on the targeted booking date. Based on observations of how the problem is solved in practice as well as the insights gained from this analysis, we develop simple heuristic procedures for accepting reservations. Computational results demonstrate that these heuristics perform well relative to an upper bound that is based on perfect information about reservations requests and customer arrivals.

In this paper we study optimal strategies for renting hotel rooms when there is a stochastic and dynamic arrival of customers from different market segments. We formulate the problem as a stochastic and dynamic programming model and characterize the optimal policies as functions of the capacity and the time left until the end of the planning horizon. We consider three features that enrich the problem: we make no assumptions concerning the particular order between the arrivals of different classes of customers; we allow for multiple types of rooms and downgrading; and we consider requests for multiple nights. We also consider implementations of the optimal policy. The properties we derive for the optimal solution significantly reduce the computational effort needed to solve the problem, yet in the multiple product and/or multiple night case this is often not enough. Therefore, heuristics, based on the properties of the optimal solutions, are developed to find “good” solutions for the general problem. We also derive upper bounds which are useful when evaluating the performance of the heuristics. Computational experiments show a satisfactory performance of the heuristics in a variety of scenarios using real data from a medium size hotel.

A wide variety of manufacturing operations can be characterized as co-production with substitutable demand. That is, there are many situations in which the availability of two or more items are related, and because of randomness in either supply or demand, it can be advantageous to substitute one of these items for another. Our research was motivated by the semiconductor industry, where chips are produced in large batches. Because of the presence of randomness in the process, individual chips in a given batch can perform differently. Because some customers have stricter specifications than others, chips within the same batch can be classified and sold as different products according to their measurable performance. We model the production and inventory problem as a stochastic dynamic program in which the objective is to minimize the costs of meeting contractual obligations. After developing heuristic methods of solving the problem in practice, we validate them against a lower bound on the cost of an optimal solution to the dynamic program.

In this paper, we analyze a queue to which the arrival process is the superposition of separate arrival streams, each of whose interarrival time distributions is of phase type, and the service time distribution is also of phase type. The performance measures derived for this queue include: the distribution of the number in the system as seen by each customer class upon arrival, Laplace-Stieltjes transform (LST) of the waiting-time distribution for each customer class, stationary interdeparture time distribution and the lag correlation coefficients of the departure process, and characteristics of the tails of the waiting time and queue length distributions.

We study a class of point processes generated by transitions in Markov chains. We are primarily concerned with approximating superposed phase renewal processes by these point processes. We identify a subclass of Markov chains that we call Super-Erlang chains. These chains have special properties that facilitate the development of approximations. We outline an approximation procedure and provide computational results that demonstrate the potential of the approach. The primary motivation for this study is the analysis of open queueing networks.

In this paper we consider deterministic approximations to a nonsequential stochastic production problem with setup costs. We show that, for the most commonly used probability distributions of the demands, the relative error bounds tend to be very small. We also consider a sequential stochastic problem, without setup costs, and discuss its relationship to the nonsequential case. Throughout the paper, we present limited computational results and indicate topics for further research.

This paper presents a hierarchical approach to plan and schedule production in a manufacturing environment that can be modeled as a two-stage process. A conceptual framework for this approach is described. The specific mathematical models proposed for the various hierarchical levels are discussed. The methodology is evaluated in an actual setting. The performance of the hierarchical system is contrasted with an MRP design. Encouraging results are reported.

This paper presents a hierarchical approach to plan and schedule production in a manufacturing environment that can be modeled as a single stage process. Initially, the basic tradeoffs inherent to production planning decisions are represented by means of an aggregate model, which is solved on a rolling horizon basis. Subsequently, the first solution of the aggregate plan is disaggregated, considering additional cost objectives and detailed demand constraints. Several improvements in the methodology related to hierarchical production planning are suggested. Special attention is given to alternative disaggregation procedures, problems of infeasibilities, and the treatment of high setup costs. Computational results, based on real life data, are presented and discussed.

This paper describes a scheduling system developed and implemented at a semiconductor company that manufactures specialty epitaxial wafers. We discuss implementation issues and describe the algorithms that form the basis of the scheduling system. We present computational results with representative data, and illustrate that scheduling procedures can be simplified considerably when they are preceded by a planning stage. The authors learned this fact through interaction with managers of the firm, and this changed the preconceived direction of the work in this application. The result is a formalization of the planning and scheduling problems.

In this paper we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real-valued functions. We discuss a procedure suggested by Dinkelbach for solving the problem, its relation to certain approaches via variable transformations, and a variant of the procedure that has convenient convergence properties. The duality correspondences that are developed do not require either differentiability or the existence of an optimal solution. The sensitivity analysis applies to linear fractional problems, even when they “solve” at an extreme ray, and includes a primal-dual algorithm for parametric right-hand-side analysis.

In this paper we study a problem, common to a wide variety of manufacturing companies, of determining the production schedule of style goods, such as clothing and consumer durables, under capacity constraints. Demand for items is stochastic and occurs in the last season of the planning horizon. Demand estimates are revised in each period. We exploit the problem's two-level hierarchical structure, which is characterized by families and items. Production changeover costs from one family to another are high, compared to other costs. However, changeover costs between items in the same family are negligible. We first formulate this problem as a difficult-to-solve stochastic mixed integer programming problem. Then, exploiting the problem's hierarchical structure, we formulate a deterministic, mixed integer programming problem and solve it by means of an algorithm that provides an approximate solution. A lower bound is obtained by applying generalized linear programming to the approximate problem. We illustrate the procedure using the disguised data of a consumer electronics company. The computational results demonstrate the effectiveness of the proposed approach in a practical setting.

We consider two approximation formulations for the single-product capacitated lot size problem. One formulation restricts the number of production policies and the other rounds demands up to multiples of a constant. After briefly reviewing the literature within a new framework, we discuss the relations between these approximation formulations. Next, we provide relative error bounds and algorithms for solving the approximation problems. We demonstrate that these approximation formulations require a significantly smaller number of calculations than the original formulation, and that the relative error bounds are satisfactory for practical purposes.

In this paper, we introduce the notions of tradeoff curves, targeting and balancing in manufacturing systems to describe the relationship between variables such as work-in-process, lead-time and capacity. We consider multiproduct manufacturing systems modeled by open networks of queues and formulate the targeting (TP) and balancing (BP) problems as nonlinear programs. These formulations are based primarily on parametric decomposition methods for estimating performance measures in open queueing networks. Since TP and BP typically are hard to solve, we show that under fairly realistic conditions they can be approximated by easily solvable convex programs. We present heuristics to obtain approximate solutions to these problems and to derive tradeoff curves. We also provide bounds on the performance of the heuristics, relative to the approximation problems, and show that they are asymptotically optimal under mild conditions.

This paper presents an algorithm, based on the simplex routine, that provides a way to solve a problem in which the objective function is not linear, but rather is represented by a ratio of two linear functions. This algorithm has a computational advantage over two previous ones because it requires neither variable transformations nor the introduction of new variables and constraints.