bluuebunny/crossref_metadata_2025 huggingface dataset:
The Vector Partition Problem for Convex Objective Functions
Authors: Onn Shmuel , Schulman Leonard J.
Published: December 2003

The partition problem concerns the partitioning of a given set of n vectors in d-space into p parts to maximize an objective function that is convex on the sum of vectors in each part. The problem has broad expressive power and captures NP-hard problems even if either p or d is fixed. In this article we show that when both p, d are fixed, the problem is solvable in strongly polynomial time using O(nd(p−1)−1) arithmetic operations. This improves upon the previously known bound of O(ndp2). Our method is based on the introduction of the signing zonotope of a set of points in space. We study this object, which is of interest in its own right, and show that it is a refinement of the so-called partition polytope of the same set of points.
On the Wagner-Whitin Lot-Sizing Polyhedron
Authors: Pereira Olivier , Wolsey Laurence
Published: December 2003

We study a family of unbounded polyhedra arising in the study of uncapacitated lot-sizing problems with Wagner-Whitin costs. We present a new proof of integrality based on completely characterizing the bounded faces of maximal dimension, and in particular showing that they are integral. With n the number of periods, we derive an O(n2) algorithm to express any point within the polyhedron as a convex combination of extreme points and extreme rays. We also study adjacency on the polyhedra, and give a simple O(n) test for adjacency. Finally we observe that for a given objective function the face of optimal solutions can be found in O(n2).
A Model for Investments in the Natural Resource Industry with Switching Costs
Authors: Lumley Richard R. , Zervos Mihail
Published: December 2003

We consider a model for investment decisions in the natural resource industry with switching costs. This model gives rise to a problem combining features of both absolutely continuous and impulse stochastic control that we explicitly solve. The solution takes qualitatively different forms, depending on parameter values.
An Exact Bound on Epsilon for Nonemptiness of Epsilon Cores of Games
Authors: Kovalenkov Alexander , Wooders Myrna Holtz
Published: December 2003

We consider collections of games with and without side payments described by certain natural parameters. Given the parameters π describing a collection of games and a lower bound n0 on the number of players, we obtain a bound ϵ0(π, n0) so that, for any ϵ ≥ ϵ0(π, n0), all games in the collection with at least n0 players have nonempty ϵ-cores. Examples are provided in which the bound on ϵ is met. For parameter values ensuring that there are many close substitutes for most players and that relatively small groups of players can realize nearly all gains to collective activities, for games with many players the bound on ϵ is small.
A Differential Calculus for Random Matrices with Applications to (max, +)-Linear Stochastic Systems
Authors: Heidergott Bernd
Published: December 2003

We introduce the concept of weak differentiability for random matrices and thereby obtain closed-form analytical expressions for derivatives of functions of random matrices. More specifically, we develop a calculus of weak differentiation for random matrices that resembles the standard calculus of differentiation. Our formalism enables us to (algebraically) calculate derivatives of finite-horizon performance measures of stochastic event graphs. More precisely, we develop a theory of weak differentiation for (max, +)-linear systems. The resulting derivatives provide unbiased estimators for gradients of finite-horizon performance measures. For various types of (max, +)-linear systems, we compute these estimators explicitly and state the corresponding gradient estimation algorithm.
The Symmetric Traveling Salesman Polytope Revisited
Authors: Naddef Denis , Pochet Yves
Published: December 2003

In this paper we present a tour of the symmetric traveling salesman polytope, focusing on inequalities that can be defined on sets of nodes. Most widely known inequalities are of this type. Many papers have appeared that give increasingly complex valid inequalities for this polytope, but little intuition on why these inequalities are valid has been given.

To help in understanding these inequalities, we develop an intuition into their validity by giving a unifying way of defining them through a sequential lifting procedure. This procedure is based on lifting the slack variables associated with subtour elimination inequalities defined on sets of nodes (called teeth). We apply this procedure to some known classes of valid inequalities for the traveling salesman polytope (TSP) respectively comb, brush, star, path, and bipartition inequalities, where the lifting coefficients are sequence independent. For comb, star, and bipartition inequalities, we provide new and noninductive proofs of validity directly inspired by this lifting procedure. We also give an example where a facet-defining inequality is derived from the lifting procedure, but where the lifting coefficients are sequence dependent. We finally study the ladder inequalities and show that they can be generated by an extension of the general procedure, where the lifted variables are different from the slack variables of subtour elimination inequalities.
Constraint Aggregation in Infinite-Dimensional Spaces and Applications
Authors: Kryazhimskii Arkadii V. , Ruszczyński Andrzej
Published: December 2003

An aggregation technique for constraints with values in Hilbert spaces is suggested. The technique allows us to replace the original optimization problem by a sequence of subproblems having scalar or finite-dimensional constraints. Applications to optimal control, games, and stochastic programming are discussed in detail.
When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
Authors: Goemans Michel X. , Tunçel Levent
Published: December 2003

We study the lift-and-project procedures of Lovász and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help.
Learning Sets in State Dependent Signalling Game Forms: A Characterization
Authors: Renault Jérôme
Published: December 2003

We consider repeated game forms with incomplete information and state dependent signalling structure. We study the information a player can learn about the state of nature through a communication procedure, in a way robust to unilateral deviations. More precisely, we say that player i can distinguish state ω from state ω′ if there exists a strategy profile such that if ω is the true state and at most one player deviates from the profile, then player i will know after a finite number of stages that ω′ is not the true state. The learning set of player i at ω is the set of states that player i cannot distinguish from ω. It corresponds to the information player i can learn, in a way immune against unilateral deviations, if the state is ω and players communicate through the game form for a finite number of stages. This notion was introduced in a joint paper with T. Tomala (Renault and Tomala 2000). We provide here a general characterization of the learning sets.
Risk, Ambiguity, and the Separation of Utility and Beliefs
Authors: Ghirardato Paolo , Marinacci Massimo
Published: December 2003

We introduce a general model of static choice under uncertainty, arguably the weakest model achieving a separation of cardinal utility and a unique representation of beliefs. Most of the nonexpected utility models existing in the literature are special cases of it. Such separation is motivated by the view that tastes are constant, whereas beliefs change with new information. The model has a simple and natural axiomatization.

Elsewhere (forthcoming), we show that it can be very helpful in the characterization of a notion of ambiguity aversion, as separating utility and beliefs allows us to identify and remove aspects of risk attitude from the decision maker's behavior. Here we show that the model allows us to generalize several results on the characterization of risk aversion in betting behavior. These generalizations are of independent interest, as they show that some traditional results for subjective expected utility preferences can be formulated only in terms of binary acts.
A Fixed-Point Approach to Stable Matchings and Some Applications
Authors: Fleiner Tamás
Published: December 2003

We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of Sands et al. In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope.
On the Complexity of Coordination
Authors: Gossner Olivier , Hernández Penélope
Published: December 2003

Many results on repeated games played by finite automata rely on the complexity of the exact implementation of a coordinated play of length n. For a large proportion of sequences, this complexity appears to be no less than n. We study the complexity of a coordinated play when allowing for a few mismatches. We prove the existence of a constant C such that if (m ln m)/n ≥ C, for almost any sequence of length n, there exists an automaton of size m that achieves a coordination ratio close to 1 with it. Moreover, we show that one can take any constant C such that C > e|X| ln |X|, where |X| is the size of the alphabet from which the sequence is drawn. Our result contrasts with Neyman (1997) that shows that when (m ln m)/n is close to 0, for almost no sequence of length n there exists an automaton of size m that achieves a coordination ratio significantly larger 1/|X| with it.
A Generalized Stochastic Differential Utility
Authors: Lazrak Ali , Quenez Marie Claire
Published: December 2003

This paper generalizes, in the setting of Brownian information, the Duffie–Epstein (1992) stochastic differential formulation of intertemporal recursive utility (SDU). We provide a utility functional of state-contingent consumption plans that exhibits a local dependency with respect to the utility intensity process (the integrand of the quadratic variation) and call it the generalized SDU. This mathematical generalization of the SDU permits, in fact, more flexibility in the separation between risk aversion and intertemporal substitution and allows to model asymmetry in risk aversion.

We extensively use the backward stochastic differential equation theory to give sufficient conditions for comparative and absolute risk aversion behavior as well as aversion to specific directional risk. Additionally, we discuss whether our functional exhibits monotonicity to its information filtration argument. For purposes of illustration, we provide some applications to the consumption/portfolio strategy selection problem in a complete securities market.
A Note on the Convergence of Policy Iteration in Markov Decision Processes with Compact Action Spaces
Authors: Golubin A. Y.
Published: December 2003

The undiscounted, unichain, finite state Markov decision process with compact action space is studied. We provide a counterexample for a result in Hordijk and Puterman (1987) and give an alternate proof of the convergence of policy iteration under the condition that there exists a state that is recurrent under every stationary policy. The analysis essentially uses a two-term matrix representation for the relative value vectors generated by policy iteration procedure.
Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems
Authors: Pang Jong-Shi , Sun Defeng , Sun Jie
Published: December 2003

Based on an inverse function theorem for a system of semismooth equations, this paper establishes several necessary and sufficient conditions for an isolated solution of a complementarity problem defined on the cone of symmetric positive semidefinite matrices to be strongly regular/stable. We show further that for a parametric complementarity problem of this kind, if a solution corresponding to a base parameter is strongly stable, then a semismooth implicit solution function exists whose directional derivatives can be computed by solving certain affine problems on the critical cone at the base solution. Similar results are also derived for a complementarity problem defined on the Lorentz cone. The analysis relies on some new properties of the directional derivatives of the projector onto the semidefinite cone and the Lorentz cone.
The Distribution of Values in the Quadratic Assignment Problem
Authors: Barvinok Alexander , Stephen Tamon
Published: December 2003

We obtain a number of results regarding the distribution of values of a quadratic function f on the set of n × n permutation matrices (identified with the symmetric group Sn) around its optimum (minimum or maximum). We estimate the fraction of permutations σ such that f(σ) lies within a given neighborhood of the optimal value of f and relate the optimal value with the average value of f over a neighborhood of the optimal permutation. We describe a natural class of functions (which includes, for example, the objective function in the Traveling Salesman Problem) with a relative abundance of near-optimal permutations. Also, we identify a large class of functions f with the property that permutations close to the optimal permutation in the Hamming metric of Sn tend to produce near optimal values of f (such is, for example, the objective function in the symmetric Traveling Salesman Problem). We show that for general f , just the opposite behavior may take place: an average permutation in the vicinity of the optimal permutation may be much worse than an average permutation in the whole group Sn.
Reconfirming the Prenucleolus
Authors: Orshan Guni , Sudhölter Peter
Published: December 2003

By means of an example, it is shown that the prenucleolus is not the only minimal solution that satisfies nonemptiness, Pareto optimality, covariance, the equal treatment property, and the reduced game property, even if the universe of players is infinite. This example also disproves a conjecture of Gurvich et al. (1994). As a second result, we prove that the prenucleolus is axiomatized by nonemptiness, covariance, the equal treatment property, and the reconfirmation property, provided the universe of players is infinite.
The Empirical Bayes Envelope and Regret Minimization in Competitive Markov Decision Processes
Authors: Mannor Shie , Shimkin Nahum
Published: December 2003

This paper proposes an extension of the regret minimizing framework from repeated matrix games to stochastic game models, under appropriate recurrence conditions. A decision maker, P1, who wishes to maximize his long-term average reward is facing a Markovian environment, which may also be affected by arbitrary actions of other agents. The latter are collectively modeled as a second player, P2, whose strategy is arbitrary. Both states and actions are fully observed by both players. While P1 may obviously secure the min-max value of the game, he may wish to improve on that when the opponent is not playing a worst-case strategy. For repeated matrix games, an achievable goal is presented by the Bayes envelope, that traces P1's best-response payoff against the observable frequencies of P2's actions. We propose a generalization to the stochastic game framework, under recurrence conditions that amount to fixed-state reachability. The empirical Bayes envelope (EBE) is defined as P1's best-response payoff against the stationary strategies of P2 that agree with the observed state-action frequencies. Because the EBE may not be attainable in general, we consider its lower convex hull, the convex Bayes envelope (CBE), which is proved to be achievable by P1. The analysis relies on Blackwell's approachability theory. The CBE is lower bounded by the value of the game and for irreducible games turns out to be strictly above the value whenever P2's frequencies deviate from a worst-case strategy. In the special case of single-controller games where P2 alone affects the state transitions, the EBE itself is shown to be attainable.
Drift Conditions for Matrix-Analytic Models
Authors: Latouche Guy , Taylor P. G.
Published: December 2003

In his seminal work, Neuts gave drift criteria by which one can determine whether processes of GI/M/1 or M/G/1 type are positive recurrent. Recently, a different drift condition to determine the ergodic character of a quasi-birth-and-death process (QBD) appeared in the literature, although its justification does not seem to have been formally established.

In this paper, we provide a proof for this new drift condition in a general context. We also give a simple proof for Neuts' original condition and establish a number of new drift conditions for the ergodic character of matrix-analytic models.
Bayesian Adaptive Stochastic Process Termination
Authors: Hu Inchi , Lee Chi-Wen Jevons
Published: December 2003

This paper considers the problem of optimally terminating a number of stochastic processes when the time varying random rewards have distributions belonging to an exponential family with an unknown parameter. The problem is formulated as a Bayesian adaptive control model with the objective of minimizing the difference between the expected reward and the optimal reward when the parameter is known. The paper establishes an asymptotic lower bound on this difference and constructs policies based on a Kullback-Leibler index that obtain this lower bound. The results are applied to models of tree harvesting and destructive testing. A simulation study shows that these policies are efficient when the number of processes is large.
Optimal Replacement Under Partial Observations
Authors: Makis V. , Jiang X.
Published: December 2003

In this paper, we present a framework for the condition-based maintenance optimization. A technical system which can be in one of N operational states or in a failure state is considered. The system state is not observable, except the failure state. The information that is stochastically related to the system state is obtained through condition monitoring at equidistant inspection times. The system can be replaced at any time; a preventive replacement is less costly than failure replacement. The objective is to find a replacement policy minimizing the long run expected average cost per unit time. The replacement problem is formulated as an optimal stopping problem with partial information and transformed to a problem with complete information by applying the projection theorem to a smooth semimartingale process in the objective function. The dynamic equation is derived and analyzed in the piecewise deterministic Markov process stopping framework. The contraction property is shown and an algorithm for the calculation of the value function is presented, illustrated by an example.
Some Asymptotic Results in Discounted Repeated Games of One-Sided Incomplete Information
Authors: Cripps Martin W. , Thomas Jonathan P.
Published: December 2003

The paper analyzes the Nash equilibria of two-person discounted repeated games with one-sided incomplete information and known own payoffs. If the informed player is arbitrarily patient, relative to the uninformed player, then the characterization for the informed player's payoffs is essentially the same as that in the undiscounted case. This implies that even small amounts of incomplete information can lead to a discontinuous change in the equilibrium payoff set. For the case of equal discount factors, however, and under an assumption that strictly individually rational payoffs exist, a result akin to the Folk Theorem holds when a complete information game is perturbed by a small amount of incomplete information.
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Authors: Laurent Monique
Published: December 2003

Sherali and Adams (1990), Lovász and Schrijver (1991) and, recently, Lasserre (2001b) have constructed hierarchies of successive linear or semidefinite relaxations of a 0–1 polytope P ⫅ ℝn converging to P in n steps. Lasserre's approach uses results about representations of positive polynomials as sums of squares and the dual theory of moments. We present the three methods in a common elementary framework and show that the Lasserre construction provides the tightest relaxations of P. As an application this gives a direct simple proof for the convergence of the Lasserre's hierarchy. We describe applications to the stable set polytope and to the cut polytope.
Extended Matrix Cube Theorems with Applications to μ-Theory in Control
Authors: Ben-Tal Aharon , Nemirovski Arkadi , Roos Cornelis
Published: December 2003

In this paper, we study semi-infinite systems of Linear Matrix Inequalities which are generically NP-hard. For these systems, we introduce computationally tractable approximations and derive quantitative guarantees of their quality. As applications, we discuss the problem of maximizing a Hermitian quadratic form over the complex unit cube and the problem of bounding the complex structured singular value. With the help of our complex Matrix Cube Theorem we demonstrate that the standard scaling upper bound on μ(M) is a tight upper bound on the largest level of structured perturbations of the matrix M for which all perturbed matrices share a common Lyapunov certificate for the (discrete time) stability.
A Nonlinear Extension of Hoffman's Error Bounds for Linear Inequalities
Authors: Zălinescu C.
Published: December 2003

In a recent paper Li and Singer (1998) introduced the notion of global error bound for a convex multifunction at a point of its domain. They showed the existence of such a global error bound when the image of the multifunction at the respective point is bounded and conjectured a result for the case when the image is not bounded. In this paper we solve their conjecture with a positive answer. For this we establish a criterion for the existence of a global error bound using the Pompeiu-Hausdorff excess. We also improve slightly some results of Li and Singer and introduce a gage associated to a multifunction similar to that for well-conditioning of convex functions, with similar properties.
A Unified Augmented Lagrangian Approach to Duality and Exact Penalization
Authors: Huang X. X. , Yang X. Q.
Published: December 2003

In this paper, the existence of an optimal path and its convergence to the optimal set of a primal problem of minimizing an extended real-valued function are established via a generalized augmented Lagrangian and corresponding generalized augmented Lagrangian problems, in which no convexity is imposed on the augmenting function. These results further imply a zero duality gap property between the primal problem and the generalized augmented Lagrangian dual problem. A necessary and sufficient condition for the exact penalty representation in the framework of a generalized augmented Lagrangian is obtained. In the context of constrained programs, we show that generalized augmented Lagrangians present a unified approach to several classes of exact penalization results. Some equivalences among exact penalization results are obtained.
Large Deviation Analysis of Subexponential Waiting Times in a Processor-Sharing Queue
Authors: Jelenković P. , Momčilović P.
Published: December 2003

We investigate the distribution of the waiting time V in a stable M/G/1 processor-sharing queue with traffic intensity ρ < 1. When the distribution of a customer service request B belongs to a large class of subexponential distributions with tails heavier than e−√x, it is shown that [Formula: see text] Furthermore, we demonstrate that the preceding relationship does not hold if the service distribution has a lighter tail than e−√x.
Unifying Condition Numbers for Linear Programming
Authors: Cheung Dennis , Cucker Felipe , Peña Javier
Published: December 2003

In recent years, several condition numbers were defined for a variety of linear programming problems based upon relative distances to ill-posedness. In this paper, we provide a unifying view of some of these condition numbers. To do so, we introduce yet another linear programming problem and show that its distance to ill-posedness naturally captures the most commonly used distances to ill-posedness.
On a Class of Nonsmooth Composite Functions
Authors: Shapiro Alexander
Published: December 2003

We discuss in this paper a class of nonsmooth functions which can be represented, in a neighborhood of a considered point, as a composition of a positively homogeneous convex function and a smooth mapping which maps the considered point into the null vector. We argue that this is a sufficiently rich class of functions and that such functions have various properties useful for purposes of optimization
An Approach to Location Models Involving Sets as Existing Facilities
Authors: Nickel Stefan , Puerto Justo , Rodriguez-Chia Antonio M.
Published: December 2003

In this paper, we deal with single facility location problems in a general normed space in which the existing facilities are represented by convex sets of points. The criterion to be satisfied by the service facility is the minimization of an increasing, convex function of the distances from the service facility to the closest point of each demand set. We obtain a geometrical characterization of the set of optimal solutions for this problem. Two remarkable cases—the classical Weber problem and the minimax problem with demand sets—are studied as particular instances of our problem. Finally, for the planar polyhedral case, we give an algorithm to find the solution set of the considered problems.
Functional Limit Theorems for a Simple Auction
Authors: Kruk Łukasz
Published: December 2003

We consider a continuous transparent auction with one asset. Buyers and sellers arrive at the auction according to independent renewal processes, willing to transact a random number of units (shares) of the asset for one of N possible prices. Upon arrival, they buy/sell as many units of the asset as they can for the best price available at that time. However, if the prices offered for sale/purchase are worse than their initial preferences, they do not transact, but instead they stay at the auction, posting buying/selling orders and waiting for a suitable counterparty. We model the numbers of outstanding orders of each type, together with the numbers of assets exchanged up to date by customers of different types, by stochastic processes and find the limiting distributions of these (suitably scaled) processes.
The Value Iteration Algorithm in Risk-Sensitive Average Markov Decision Chains with Finite State Space
Authors: Cavazos-Cadena Rolando , Montes-de-Oca Raúl
Published: December 2003

This work concerns discrete-time Markov decision chains with finite state space and bounded costs. The controller has constant risk sensitivity λ, and the performance of a control policy is measured by the corresponding risk-sensitive average cost criterion. Assuming that the optimality equation has a solution, it is shown that the value iteration scheme can be implemented to obtain, in a finite number of steps, (1) an approximation to the optimal λ-sensitive average cost with an error less than a given tolerance, and (2) a stationary policy whose performance index is arbitrarily close to the optimal value. The argument used to establish these results is based on a modification of the original model, which is an extension of a transformation introduced by Schweitzer (1971) to analyze the the risk-neutral case.
Management of Worksharing Systems
Authors: McClain John O. , Schultz Kenneth L. , Thomas L. Joseph
Published: December 2003

Worksharing occurs in serial manufacturing when machines are not uniquely assigned to workers. For example, two workers can operate three machines by alternating usage of the middle one. In some other worksharing systems operators move down the line carrying an item (or batch) with them, working on it at each machine until they are met by another worker who is coming back upstream. The work is then handed off even if the operation is underway. “Bucket Brigade” and “TSS” are worksharing systems based on this idea.

This paper examines worksharing in a variety of situations, including unequal work content across machines, uncertain processing times, unequal workers, handoffs with and without preemption, and a range of machine-to-worker ratios. Some systems restrict workers to “zones” of machines. Work zones must overlap if sharing is to occur. The appropriate size of the overlapis shown to depend on the circumstances. Inventory-based rules to control access to shared machines are demonstrated to increase productivity when processing times vary. Worker sequence is found to be quite important; Slowest-to-Fastest is recommended for some situations, but is shown to perform poorly in others. Finally, the issue of whether or not to allow preemption is shown to have a large impact on productivity if inventory is not allowed, and to strongly affect the choice of designs when inventory is allowed. With and without preemption, proper combinations of worker sequence, zone size, and production control rules are shown to nearly eliminate idle time.
Optimizing Strategic Safety Stock Placement in Supply Chains
Authors: Graves Stephen C. , Willems Sean P.
Published: December 2003

Manufacturing managers face increasing pressure to reduce inventories across the supply chain. However, in complex supply chains, it is not always obvious where to hold safety stock to minimize inventory costs and provide a high level of service to the final customer. In this paper we develop a framework for modeling strategic safety stock in a supply chain that is subject to demand or forecast uncertainty. Key assumptions are that we can model the supply chain as a network, that each stage in the supply chain operates with a periodic-review base-stock policy, that demand is bounded, and that there is a guaranteed service time between every stage and its customers. We develop an optimization algorithm for the placement of strategic safety stock for supply chains that can be modeled as spanning trees. Our assumptions allow us to capture the stochastic nature of the problem and formulate it as a deterministic optimization. As a partial validation of the model, we describe its successful application by product flow teams at Eastman Kodak. We discuss how these flow teams have used the model to reduce finished goods inventory, target cycle time reduction efforts, and determine component inventories. We conclude with a list of needs to enhance the utility of the model.
Properties of Optimal-Weighted Flowtime Policies with a Makespan Constraint and Set-up Times
Authors: Van Oyen Mark P. , Pichitlamken Juta
Published: December 2003

We characterize optimal policies for the problem of allocating a single server to a set of jobs from N families. Each job is an instance of demand for an item and is associated with a family, a holding cost rate, and a mean processing time. Set-up times are required to switch from one family to another, but are not required to switch within a family. We consider the case in which the order of jobs within the family is unconstrained, and a variation in which the order is fixed. The optimization is with respect to the weighted flowtime, and we treat problems both with and without a makespan-constraint. Practical examples based on this model are described. We partially characterize an optimal policy by means of a Gittins rewardrate index and a similar switching index derived from multi-armed bandit theory. For deterministic problems with a makespan constraint, we present an optimization algorithm for the special case of two families and at most three set-ups . Without a makespan constraint and without preemption, we prove that our analysis of a deterministic model extends to stochastic set-up and processing times without loss of optimality. Managerial insights based on our technical results are provided.
Customer Service Competition in Capacitated Systems
Authors: Hall Joseph , Porteus Evan
Published: December 2003

We investigate a simple dynamic model of firm behavior in which firms compete by investing in capacity that is used to provide a good or service to their customers. There is a fixed total market of customers whose demands for the good or service are random and who divide their patronage between the firms in each period. Periodically, the market shares of the two firms can change based on the realized level of customer service provided in the prior period. We assume that the expected level of customer service can be expressed as a function of the (per customer) capacity of the firms' service delivery systems, and that service declines as the capacity decreases. The firms differ in their customers' willingness to defect when confronted by service failure. The primary issue we address is the firms' capacity decisions in response to customer service concerns and competitive pressure. We provide conditions under which the firms' optimal (i.e., equilibrium) capacity levels in a period are proportional to the size of their respective customer bases in that period. Further, we develop expressions for the value of a firm's customers and the implicit cost of service failure. Results for both single-period and finite-horizon problems are investigated and applied to two examples: (1) competition between Internet service providers who operate systems that we approximate by simple loss-type queueing models, and (2) competition between make-to-stock producers who operate systems that we approximate by newsvendor inventory models. For both examples, solutions are derived and interpreted.
Contract Assembly: Dealing with Combined Supply Lead Time and Demand Quantity Uncertainty
Authors: Song Jing-Sheng , Yano Candace A. , Lerssrisuriya Panupol
Published: December 2003

We consider a problem faced by a contract assembler that both assembles finished goods and procures the associated component parts for one of its major customers. Because of rapid changes in technology and ongoing engineering changes, all parts subject to obsolescence are purchased only for the current customer order. The procurement lead times of the components are random. Moreover, although the order for the finished product has a defined due date, the contract allows the customer to change the order quantity. Consequently, the assembler also faces a random demand. The assembler must determine how much to order and when to order each component part. The objective is to minimize the total expected cost, including the cost of holding components prior to their assembly, penalties for tardiness visa-vis the assembly due date, and overage and underage costs in satisfying the demand quantity. We present some structural results and discuss insights regarding optimal policies. We also present several simple heuristic policies and compare them to optimal policies. Computational results indicate that ignoring lead time variability can be costly, but relatively simple heuristics that consider lead time variability perform quite well.
Optimizing Delivery Fees for a Network of Distributors
Authors: Balakrishnan Anantaram , Natarajan Harihara Prasad , Pangburn Michael S.
Published: December 2003

The third-party logistics industry has grown rapidly in recent years, accounting for $46 billion of the total $921 billion in logistics spending in the United States during 1999. This figure is expected to grow by 15 to 20% annually as manufacturing firms increasingly partner with third-party logistics providers to cost effectively distribute their products, while meeting increasingly stringent service expectations of customers. These logistics partnerships have introduced a new set of decision requirements to negotiate compensation for distribution services. Based on a collaborative project with a leading building products manufacturer, this paper describes the development and implementation of a novel linear programming model to decide the delivery fees paid to distributors. The model applies to manufacturer-distributor partnerships where distributors are compensated using fee values that depend on delivery weights and distances. It ensures that the expected compensation, considering stochastic demands, is adequate to cover the aggregate distribution costs for each distributor, and permits imposing various consistency conditions to ensure that fee values are credible. The model proved effective in helping the manufacturer develop a new fee table that generated considerable economic savings and provided more equitable compensation to distributors.
An Analysis of Several New Product Performance Metrics
Authors: Cohen Morris A. , Eliashberg Jehoshua , Ho Teck H.
Published: December 2003

For most firms, new product development is the engine for growth and profitability. A firm's new product success depends on its ability to manage the product development process in a way that employs scarce resources to achieve the goal of the firm as well as the specific project's objectives. Simple and measurable performance metrics have been proposed and applied to monitor and compensate the development teams. In this paper, we develop a modeling frame work to analyze the implications of setting managerial priorities for three commonly used new product performance metrics: (1) time-to-market, (2) product performance, and (3) total development cost. We model new product development as a “product performance production” process that requires scarce development resources. Setting a target for development teams for each of these performance metrics can constrain this performance production process and, thereby, affect the other performance metrics. We model the constrained process as a restricted case of a general process that does not have such constraints. We benchmark each constrained process against the optimal, unrestricted process with respect to the level of the resource intensity employed during the development process, the time-to-market, and the performance level of the new product at launch. We show that an overly ambitious time-to-market target leads to an upward bias in resource intensity usage and a downward bias in product performance (i.e., evolutionary product innovation). In addition, our results suggest that the target time-to-market approach may ignore the effect of cannibalization and, thus, can perform suboptimally if a significant degree of cannibalization in the existing product market is expected. Given a target product performance, we show that the coordination between marketing and R&D is easier because the resulting development resource intensity and time-to-market decisions becomes separable. However, an overly ambitious product performance target leads to an upward bias in the development resource intensity and a delayed product launch that misses the window of opportunity. Finally, we show that the target development cost approach can lead a downward bias in product performance and a premature product launch. The above analyses are performed for a monopolistic firm, and they are extended to passive and active competitive environment.
Serial Production/Distribution Systems Under Service Constraints
Authors: Boyaci Tamer , Gallego Guillermo
Published: December 2003

We analyze the problem of minimizing average inventory costs subject to fill-rate type of service-level constraints in serial and assembly production/distribution systems. We propose optimal and heuristic procedures to solve this problem. Our model and solution procedures can be used to manage the fill rate or fill rate within a “time window” service measures. We also relate our service-constrained model to the traditional model with back-order costs and show that it is possible to prespecify backorder cost rates to achieve desired service levels. We explore the inventory cost impact of such a practice, and we find that the cost penalty can be very high.
Supply Chain Coordination when Demand Is Shelf-Space Dependent
Authors: Wang Yunzeng , Gerchak Yigal
Published: December 2003

Consider a manufacturer or wholesaler who supplies some item to retailers facing demand rates that depend on the shelf or display space that is devoted to that product by themselves and their competitors. The manufacturer, via the use of financial levers at her disposal, wishes to coordinate this decentralized chain while making a profit. We model the physical scenario as one of constant displayed inventory level (on which demand rate depends positively) and continuous replenishment. With a single retailer, we show that to coordinate the channel and make a profit the manufacturer needs to augment the wholesale price lever by another-an inventory holding costs subsidy offered to the retailer. When multiple retailers compete in that product's market, there are two ways to envision and model the demand and market split. One assumes that market demand depends on aggregate inventory displayed, and then splits according to individual display levels. The other “assigns” customers to retailers according to their display levels, and then assumes that purchases are a function of the display level at the retailer selected. We characterize retailers' Nash equilibria in these models, and we explore whether the manufacturer can coordinate such channels.
A Comparison of U-Line and Straight-Line Performances Under Stochastic Task Times
Authors: Chand Suresh , Zeng Ting
Published: December 2003

Traditionally, assembly lines are laid out in a straight-line configuration where a worker covers only adjacent stations. In a U-line layout, on the other hand, two or more non-adjacent stations can be physically close to each other, making it possible for a worker to cover nonadjacent stations. This added flexibility increases the decision space for U-line layouts and can result in better balanced lines. This paper examines the impact of stochastic task times on the relative performance of U-line and straight-line layouts. Several analytical and simulation results are presented, and insights are provided to explain the difference in the performance of U-line and straight-line layouts. To summarize our main results, although balanced U-line layouts are at least as productive as balanced straight-line layouts given deterministic task times, they can be less productive given stochastic task times if they are balanced deterministically using mean times.
Coordinating Production and Delivery Under a (z, Z)-Type Vendor-Managed Inventory Contract
Authors: Fry Michael J. , Kapuscinski Roman , Olsen Tava Lennon
Published: December 2003

This paper models a type of vendor-managed inventory (VMI) agreement that occurs in practice called a (z, Z) contract. We investigate the savings due to better coordination of production and delivery facilitated by such an agreement. The optimal behavior of both the supplier and the retailer are characterized. The optimal replenishment and production policies for a supplier are found to be up-to policies, which are shown to be easily computed by decoupling the periods when the supplier outsources from those when the supplier does not outsource. A simple application of the newsvendor relation is used to define the retailer's optimal policy. Numerical analysis is conducted to compare the performance of a single supplier and a single retailer operating under a (z, Z) VMI contract with the performance of those operating under traditional retailer-managed inventory (RMI) with information sharing. Our results verify some observations made in industry about VMI and show that the (z, Z) type of VMI agreement performs significantly better than RMI in many settings, but can perform worse in others.
Consequences of Order Crossover Under Order-Up-To Inventory Policies
Authors: Robinson Lawrence W. , Bradley James R. , Thomas L. Joseph
Published: December 2003

Order crossover occurs whenever replenishment orders do not arrive in the sequence in which they were placed. This paper argues that order crossover is becoming more prevalent and analyzes the dangers of ignoring it. We present an exact iterative algorithm for computing the distribution of the number of orders outstanding, and formulae for the inventory shortfall distribution (the quantity of inventory in replenishment at the start of a period) and the more common lead-time demand distribution, which are different when order crossover is possible. The lead-time demand distribution can have much higher variability than the shortfall distribution. We show that basing inventory policies on the lead-time demand distribution—rather than the shortfall distribution—can lead to significantly higher inventory cost, even if the probability of order crossover is small. We give an alternative proof to that of Zalkind (1976), which shows that the variance of shortfall is less than the variance of the standard lead-time demand.
A Modeling Framework for Category Assortment Planning
Authors: Chong Juin-Kuan , Ho Teck-Hua , Tang Christopher S.
Published: December 2003

The complexity of managing a category assortment has grown tremendously in recent years due to the increased product turnover and proliferation rates in most categories. It is an increasingly difficult task for managers to find an effective assortment due to uncertain consumer preferences and the exponential number of possible assortments. This paper presents an empirically based modeling framework for managers to assess the revenue and lost sales implication of alternative category assortments. Coupled with a local improvement heuristic, the modeling framework generates an alternative category assortment with higher revenue.

This framework, which consists of a category-purchase-incidence model and a brand-share model, is calibrated and validated using 60,000 shopping trips and purchase records. Specifically, the purchase-incidence model predicts the probability of an individual customer who purchases (and who does not purchase) from a given product category during a shopping trip. The no-purchase probability enables us to estimate lost sales due to assortment changes in the category. The brand-share model predicts which brand the customer chooses if a purchase incidence occurs in the category. Our brand-share model extends the classical Guadagni and Little model (1983) by utilizing three new brand-width measures that quantify the similarities among products of different brands within the same category.

We illustrate how our modeling framework is used to reconfigure the category assortment in eight food categories for five stores in our data set. This reconfiguration exercise shows that a reconfigured category assortment can have a profit improvement of up to 25.1% with 32 products replaced. We also demonstrate how our modeling framework can be used to gauge lost sales due to assortment changes. We find the level of lost sales could range from 0.9% to 10.2% for a period of 26 weeks.