The individual station technique for the analysis of cyclic polling systems

Polling systems are used to model a wide variety of real-world applications, for example, telecommunication and material handling systems. Consequently, there is continued interest in developing efficient algorithms to analyze the performance of polling systems. Recent interest in the optimization of these systems has brought up the need for developing very efficient techniques for analyzing their waiting times. This article presents the Individual Station technique for cyclic polling systems. The technique possesses the following features: (a) it allows the user to compute the mean waiting time at a selected station independent of the mean waiting time computations at other stations, and (b) its complexity is low and independent of the system utilization. In addition the technique provides explicit closed-form expressions for (i) the mean waiting times in a system with 3 stations, and (ii) the second moment of the waiting times in a system with 2 stations, for an exhaustive service system. © 1996 John Wiley & Sons, Inc.     

Exploiting symmetry in the reliability analysis of coherent systems

Components in a complex system are usually not structurally identical. However, in many cases we may find components that are structurally symmetric, and one should make use of this additional information to simplify reliability analysis. The main purpose of this article is to define and study one such class of systems, namely, those having symmetric components, and to derive some reliability-related properties. © 1996 John Wiley & Sons, Inc.     

Multi-period airline overbooking with multiple fare classes

Consider a multi-period multi-fare class airline overbooking problem that relates to a single-leg flight. Passengers may cancel their reservations at any time, including being no-shows at flight-time. Canceling passengers receive a refund that depends on their fare class, e.g., supersaver, coach, etc. At flight-time, the airline bumps passengers in excess of flight capacity and pays a penalty for so doing. A continuous state-space dynamic programming model is developed in which the state is the numbers of reservations currently on hand in each fare class. In each period, reservation requests occur in only one fare class and the fraction of reservations canceling in each class is independent of the number of reservations therein. A booking-limit policy is optimal, i.e., in each period the airline accepts reservation requests up to a booking limit if the number of initial reservations in the fare class is less than the booking limit, and declines reservation requests otherwise. The booking limits for each class depend on the numbers of reservations in the other classes. When there are two fare classes the optimal booking limits in each class decrease with the number of reservations in the other class. © 1996 John Wiley & Sons, Inc.     

On the timing of adoption of multiproduct technologies

This article examines a game of multiproduct technology adoption. We consider a duopoly model in which firms choose when to switch from a traditional single-product technology to a more flexible and more expensive multiproduct technology. The multiproduct technology allows a firm to invade the other firm's market, creating a more competitive environment and reducing profits. We analyze this investment decision as a game of timing using two different equilibrium concepts. First, we utilize the “silent” equilibrium concept, where firms commit at time zero to a switching time. This concept would be applicable to situations where firms cannot observe each other's actions, or when the implementation of the technology requires long lead times and the investment decision is private information. Using this notion we find that both firms adopt the multiproduct technology simultaneously within a certain time interval. We then characterize this time interval in terms of cost and demand conditions. We also derive conditions under which sequential adoption of the multiproduct technology occurs. The second concept used is that of noisy equilibrium, where firms cannot precommit themselves to an adoption time. This concept is appropriate when investment decisions are common knowledge. In this case a firm can credibly threaten to immediately follow suit if the other firm decides to adopt. This threat is sufficient to ensure the collusive outcome where neither firm adopts the flexible technology. © 1994 John Wiley & Sons, Inc.     

A penalty for concave minimization derived from the tuy cutting plane

A wide variety of optimization problems have been approached with branch-and-bound methodology, most notably integer programming and continuous nonconvex programming. Penalty calculations provide a means to reduce the number of subproblems solved during the branch-and-bound search. We develop a new penalty based on the Tuy cutting plane for the nonconvex problem of globally minimizing a concave function over linear constraints and continuous variables. Computational testing with a branch-and-bound algorithm for concave minimization indicates that, for the problems solved, the penalty reduces solution time by a factor ranging from 1.2 to 7.2. © 1994 John Wiley & Sons, Inc.     

On the set of (perfect) equilibria of a bimatrix game

This article provides a new approach to the set of (perfect) equilibria. With the help of an equivalence relation on the strategy space of each player. Nash sets and Selten sets are introduced. The number of these sets is finite and each of these sets is a polytope. As a consequence the set of (perfect) equilibria is a finite union of polytopes. © 1994 John Wiley & Sons. Inc.     

Minimax resource allocation problems with ordering constraints

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high-tech industries confronted with large-scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.     

General models for the supplier's all-unit quantity discount policy

The purpose of this article is to investigate some managerial insights related to using the all-unit quantity discount policies under various conditions. The models developed here are general treatments that deal with four major issues: (a) one buyer or multiple buyers, (b) constant or price-elastic demand, (c) the relationship between the supplier's production schedule or ordering policy and the buyers' ordering sizes, and (d) the supplier either purchasing or manufacturing the item. The models are developed with two objectives: the supplier's profit improvement or the supplier's increased profit share analysis. Algorithms are developed to find optimal decision policies. Our analysis provides the supplier with both the optimal all-unit quantity discount policy and the optimal production (or ordering) strategy. Numerical examples are provided. © 1993 John Wiley & Sons. Inc.     

Decomposition-based approximation algorithms for the one-warehouse multi-retailer problem with concave batch order costs

We study the one-warehouse multi-retailer problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem into single-facility subproblems, then propose approximation algorithms by judiciously recombining the subproblem solutions. For piecewise linear concave batch order costs with a constant number of slopes we obtain a constant-factor approximation, while for general concave batch costs we propose an approximation within a logarithmic factor of optimality. We also extend some results to subadditive order and/or holding costs.