bluuebunny/crossref_metadata_2025 huggingface dataset:
On Mutually Interfering Parallel Servers Subject to External Disturbances
Authors: Wasserman Kimberly M. , Olsen Tava Lennon
Published: December 2003

This paper considers a continuous-time non-Markovian parallel queueing system subject to external disturbances. The servers are mutually interfering in that their service rates are nonlinearly interdependent functions of the controls applied by the servers, and external discrete-valued continuous-time random disturbances. At certain time epochs, namely, every Δ time units, the servers may adjust their service rates by changing the values of their controls; however, the system may change its state several times between successive decision epochs. The stability region of the system is established and a service rate control policy π* is provided, where an arrival rate vector in the interior of the region is sufficient for stability under π*, and a vector in the closure is necessary for stability under any policy. The stability region depends on Δ and the variations of the disturbances between decision epochs, and π* does not require knowledge of the arrival rates. The stability region is not in general monotonic in Δ, but under perfect continuous control (Δ = 0) the stability region is a superset of that under Δ > 0. This queueing model captures essential features of resource allocation and stochastic control problems encountered in a number of telecommunication, transportation, and manufacturing systems.
Inverse Optimization
Authors: Ahuja Ravindra K. , Orlin James B.
Published: December 2003

In this paper, we study inverse optimization problems defined as follows. Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x0 be a given feasible solution. The solution x0 may or may not be an optimal solution of P with respect to the cost vector c. The inverse optimization problem is to perturb the cost vector c to d so that x0 is an optimal solution of P with respect to d and ‖d−c‖p is minimum, where ‖d−c‖p is some selected Lp norm. In this paper, we consider the inverse linear programming problem under L1 norm (where ‖d−c‖p = Σi∈J wj|dj−cj|, with J denoting the index set of variables xj and wj denoting the weight of the variable j) and under L∞ norm (where ‖d−c‖p = maxj∈J{wj|dj−cj|}). We prove the following results: (i) If the problem P is a linear programming problem, then its inverse problem under the L1 as well as L∞ norm is also a linear programming problem. (ii) If the problem P is a shortest path, assignment or minimum cut problem, then its inverse problem under the L1 norm and unit weights can be solved by solving a problem of the same kind. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iii) If the problem P is a minimum cost flow problem, then its inverse problem under the L1 norm and unit weights reduces to solving a unit-capacity minimum cost flow problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iv) If the problem P is a minimum cost flow problem, then its inverse problem under the L∞ norm and unit weights reduces to solving a minimum mean cycle problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost-to-time ratio cycle problem. (v) If the problem P is polynomially solvable for linear cost functions, then inverse versions of P under the L1 and L∞ norms are also polynomially solvable.
Alternative Models of Restructured Electricity Systems, Part 1: No Market Power
Authors: Boucher Jacqueline , Smeers Yves
Published: December 2003

Different equilibrium concepts have been proposed by various authors (Schweppe et al., Hogan et al., Chao and Peck, Wu et al.) to analyse competitive electricity systems. We establish correspondences between these different models through a single framework and provide additional interpretations of these equilibrium concepts. This unifying conceptual view also provides a computationally feasible approach to simulate the market. It also opens the way to the modeling of some imperfect markets.
Importance Sampling and the Cyclic Approach
Authors: Juneja Sandeep
Published: December 2003

The method of importance sampling is widely used for efficient rare-event simulation of stochastic systems. This method involves simulating the system under a new distribution that accentuates the probability along the most likely paths to the rare event. Traditionally, insights from large deviations theory are used to identify the distribution emphasizing these most likely paths. In this paper we develop an intuitive cyclic approach for selecting such a distribution. The key idea is to select a distribution under which the event of interest is no longer rare and the probability of occurrence of a cycle in any sample path remains equal to the original probability of that cycle. We show that only an exponentially twisted distribution can satisfy this equiprobable cycle condition. Using this approach we provide an elementary derivation of the asymptotically optimal change of measure for level crossing probability for Markov-additive processes. To demonstrate its ease of use for more complex stochastic systems, we apply it to determine the asymptotically optimal change of measure for estimating buffer overflow probability of a single-server queue subject to server interruptions.
A Min-Max-Sum Resource Allocation Problem and Its Applications
Authors: Karabati Selcuk , Kouvelis Panagiotis , Yu Gang
Published: December 2003

In this paper we consider a class of discrete resource-allocation problems with a min-max-sum objective function. We first provide several examples of practical applications of this problem. We then develop a branch-and-bound procedure for solving the general case of this computationally intractable problem. The proposed solution procedure employs a surrogate relaxation technique to obtain lower and upper bounds on the optimal objective function value of the problem. To obtain the multipliers of the surrogate relaxation, two alternative approaches are discussed. We also discuss a simple approximation algorithm with a tight bound. Our computational results support the effectiveness of the branch-and-bound procedure for fairly large-size problems.
A Dynamic Airline Seat Inventory Control Model and Its Optimal Policy
Authors: Feng Youyi , Xiao Baichun
Published: December 2003

We consider an airline seat inventory control problem with multiple origins, one hub, and one destination. Passengers from the origins fly to the destination via the hub. Seat capacity of the hub-destination flight is fixed. Demands at origins are assumed to obey the Poisson process. To maximize the expected revenue, management faces decisions on allocating seats among competing origin-destination routes. This study presents a stochastic control model and develops optimal control rules. The basic model is subsequently distended to consider multiple fares on each route, time-dependent demands, and booking control on an extended network. A numerical example shows that optimal seat control is simple and efficient.
Army Operations Research—Historical Perspectives and Lessons Learned
Authors: Bonder Seth
Published: December 2003

This paper provides some of my historical perspectives on Operations Research (OR) in the U.S. Army. It is based on my 40+ years of personal experience and, thus, focuses on the modeling and analysis (M&A) aspects of OR in the Army. I have attempted to highlight the changing problems and growth of M&A in the Army over the past 40 years. Although I refer to approaches taken by others for some of this growth, more information is provided on those of Vector Research,Incorporated (VRI),since all of my experience has been with VRI since 1969. The paper has four main sections. Since OR in the Army started before 1960 and my activities interacted with many others in the Army, the first section briefly reviews the lineage of some of the Army's main OR organizations. The second and third summarize my M&A activities and perspectives for the periods 1960–1989 (the “Cold War” era) and 1990–2000, respectively. Based on this experience, I offer some “lessons learned” for today's military M&A community in the concluding section.
Simplex and Interior Point Specialized Algorithms for Solving Nonoriented Multicommodity Flow Problems
Authors: Chardaire P. , Lisser A.
Published: December 2003

Multicommodity network flow models arise in a wide variety of contexts, typical among which is the dimensioning of telecommunication networks. In this paper, we present various approaches based on specialization of the simplex algorithm and interior-point methods to solve nonoriented multicommodity flowproblems. Algorithms are tested with data from the France-Telecom Paris district transmission network. First, we focus on a specialization for the node-arc formulation of the problem. A Primal simplex and Dual Affine Scaling algorithms exploiting the particular structure of the constraint matrix are presented and compared. Numerical results are provided for problems up to about 800,000 constraints and 6,000,000 variables. However, much more powerful approaches based on specialized decomposition methods can be implemented for solving the problem. A Dantzig-Wolfe decomposition method is designed and compared with a specialized implementation of the Analytic Center Cutting Plane Method (ACCPM). Partitioning techniques are used to exploit the structure of the master programs involved in those methods.
Modeling Farmers' Response to Uncertain Rainfall in Burkina Faso: A Stochastic Programming Approach
Authors: Maatman Arno , Schweigman Caspar , Ruijs Arjan , van Der Vlerk Maarten H.
Published: December 2003

Farmers on the Central Plateau of Burkina Faso in West Africa cultivate under precarious conditions. Rainfall variability is extremely high in this area and accounts for much of the uncertainty surrounding the farmers' decision-making process. Strategies to cope with these risks are typically dynamic. Sequential decision making is one of the most important ways to cope with risk due to uncertain rainfall. In this paper, a stochastic programming model is presented to describe farmers' sequential decisions in reaction to rainfall. The model describes farmers' strategies of production, consumption, selling, purchasing, and storage from the start of the growing season until one year after the harvest period. This dynamic model better describes farmers' strategies than do static models that are usually applied. This study draws important policy conclusions regarding reorientation of research programs and illustrates how operations research techniques can be usefully applied to study grass root problems in developing countries.
Global Optimization Procedures for the Capacitated Euclidean and lp Distance Multifacility Location-Allocation Problems
Authors: Sherali Hanif D. , Al-Loughani Intesar , Subramanian Shivaram
Published: December 2003

In this paper, we study the capacitated Euclidean and lp distance location-allocation problems. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. Beginning with the Euclidean distance problem, we design a branch-and-bound algorithm based on a partitioning of the allocation space that finitely converges to a global optimum for this nonconvex problem. For deriving lower bounds at node subproblems in this partial enumeration scheme, we employ two types of procedures. The first approach computes a lower bound via a projected location space subproblem. The second approach derives a significantly enhanced lower bound by using a Reformulation-Linearization Technique (RLT) to transform an equivalent representation of the original nonconvex problem into a higher dimensional linear programming relaxation. In addition, certain cut-set inequalities are generated in the allocation space, and objective function based cuts are derived in the location space to further tighten the lower bounding relaxation. The RLT procedure is then extended to the general lp distance problem, for p > 1. Computational experience is provided on a set of test problems to investigate both the projected location space and the RLT-lower bounding schemes. The results indicate that the proposed global optimization approach using the RLT-based scheme offers a promising viable solution procedure. In fact, among the problems solved, for the only two test instances available in the literature for the Euclidean distance case, we report significantly improved solutions.
Confidentiality via Camouflage: The CVC Approach to Disclosure Limitation When Answering Queries to Databases
Authors: Gopal Ram , Garfinkel Robert , Goes Paulo
Published: December 2003

A practical method is presented for giving unlimited, deterministically correct, numerical responses to ad-hoc queries to an online database, while not compromising confidential numerical data. The method is appropriate for any size database, and no assumptions are needed about the statistical distribution of the confidential data. Responses are in the form of a number plus a guarantee, so the user can determine an interval that is sure to contain the exact answer. Virtually any imaginable query type can be answered, and in the absence of insider information, collusion among the users presents no problem. Experimental analysis supports the practical viability of the proposed method.
The Censored Newsvendor and the Optimal Acquisition of Information
Authors: Ding Xiaomei , Puterman Martin L. , Bisi Arnab
Published: December 2003

This paper investigates the effect of demand censoring on the optimal policy in newsvendor inventory models with general parametric demand distributions and unknown parameter values. We show that the newsvendor problem with observable lost sales reduces to a sequence of single-period problems, while the newsvendor problem with unobservable lost sales requires a dynamic analysis. Using a Bayesian Markov decision process approach we show that the optimalin ventory level in the presence of censored demand is higher than would be determined using a Bayesian myopic policy. We explore the economic rationality for this observation and illustrate it with numerical examples.
Hybrid Fiber Coaxial Network Design
Authors: Patterson Raymond A. , Rolland Erik
Published: December 2003

Much interest exists in broadband network services to deliver a variety of products to consumers, such as Internet access, telephony, interactive TV, and video on demand. Due to its cost efficiency, Hybrid Fiber Coaxial (HFC) technology is currently being considered by most Telcos and cable companies as the technology to deliver these products. The topological HFC network design problem as implemented by several major companies is a form of the capacitated tree-star network design problem. We propose a new formulation for this problem and present a heuristic based on hierarchical decomposition of the problem. The proposed solution methodology exploits an Adaptive Reasoning Technique (ART), embedded as a meta-heuristic over specialized heuristics for the subproblems. In this context, we demonstrate the dynamic use of an exact solution technique within ART. The generalizability of the proposed solution methodology is demonstrated by applying it to a second problem, the Traveling Salesman Problem (TSP). Computational results are presented for both the HFC network design problem and the TSP, indicating high-quality solutions expending a very modest computational effort. The proposed solution method is found to be effective, and is shown to be easily adaptable to new problems without much crafting, and as such, has a broad appeal to the general operations research community.
An Adaptive Bayesian Replacement Policy with Minimal Repair
Authors: Dayanik Savaş , Gürler Ülkü
Published: December 2003

In this study, an adaptive Bayesian decision model is developed to determine the optimal replacement age for the systems maintained according to a general age-replacement policy. It is assumed that when a failure occurs, it is either critical with probability p or noncritical with probability 1 – p, independently. A maintenance policy is considered where the noncritical failures are corrected with minimal repair and the system is replaced either at the first critical failure or at age τ, whichever occurs first. The aim is to find the optimal value of τ that minimizes the expected cost per unit time. Two adaptive Bayesian procedures that utilize different levels of information are proposed for sequentially updating the optimal replacement times. Posterior density/mass functions of the related variables are derived when the time to failure for the system can be expressed as a Weibull random variable. Some simulation results are also presented for illustration purposes.
Due-Date Scheduling: Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules
Authors: Van Mieghem Jan A.
Published: December 2003

Consider the following due-date scheduling problem in a multiclass, acyclic, single-station service system: Any class k job arriving at time t must be served by its due date t+Dk. Equivalently, its delay τk must not exceed a given delay or lead-time Dk. In a stochastic system, the constraint τk≤Dk must be interpreted in a probabilistic sense. Regardless of the precise probabilistic formulation, however, the associated optimal control problem is intractable with exact analysis. This article proposes a new formulation which incorporates the constraint through a sequence of convex-increasing delay cost functions. This formulation reduces the intractable optimal scheduling problem into one for which the Generalized cμ (Gcμ) scheduling rule is known to be asymptotically optimal. The Gcμ rule simplifies here to a generalized longest queue (GLQ) or generalized largest delay (GLD) rule, which are defined as follows. Let Nk be the number of class k jobs in system, λk their arrival rate, and ak the age of their oldest job in the system. GLQ and GLD are dynamic priority rules, parameterized by θ: GLQ(θ) serves FIFO within class and prioritizes the class with highest index θkNk, whereas GLD(θ) uses index θkλkak.

The argument is presented first intuitively, but is followed by a limit analysis that expresses the cost objective in terms of the maximal due-date violation probability. This proves that GLQ(θ*) and GLD(θ*), where θ*,k = 1/λkDk, asymptotically minimize the probability of maximal due-date violation in heavy traffic. Specifically, they minimize [Formula: see text] for all positive t and x, where τk(s) is the delay of the most recent class k job that arrived before time s. GLQ with appropriate parameter θα also reduces “total variability” because it asymptotically minimizes a weighted sum of αth delay moments. Properties of GLQ and GLD, including an expression for their asymptotic delay distributions, are presented.
Stabilizing Batch-Processing Networks
Authors: Dai J. G. , Li Caiwei
Published: December 2003

In a batch-processing network, multiple jobs can be formed into a batch to be processed in a single service operation. The network is multiclass in that several job classes may be processed at a server. Jobs in different classes cannot be mixed into a single batch. A batch policy specifies which class of jobs is to be served next. Throughput of a batch-processing network depends on the batch policy used. When the maximum batch sizes are equal to one, the corresponding network is called a standard-processing network, and the corresponding service policy is called a dispatch policy. There are many dispatch policies that have been proven to maximize the throughput in standard networks. This paper shows that any normal dispatch policy can be converted into a batch policy that preserves key stability properties. Examples of normal policies are given. These include static buffer priority (SBP), first-in-first-out (FIFO), and generalized round robin (GRR) policies.
Continuity of DEA Efficiency Measures
Authors: Scheel Holger , Scholtes Stefan
Published: December 2003

Data envelopment analysis (DEA) is a methodology that allows, in one way or other, the assignment of efficiency scores to members of a group of decision-making units. We call an efficiency measure “continuous” if small perturbations of the input-output data cause only small changes in the score. Continuity is a desirable property of an efficiency measure, in particular in the presence of measurement tolerances. Continuity is also desirable from a numerical point of view because the scores are computed by linear programming software.

Focusing on convex production possibility sets, we give examples where radial DEA measures fail to be continuous, i.e., they “jump” under small data perturbations. We present necessary and sufficient conditions for continuity in terms of the data and show that these conditions are satisfied for “almost all” data. We also discuss continuity of nonradial measures and identify possible problems of “multistage approaches” to compute mix efficiencies.
A Stochastic Integer Program with Dual Network Structure and Its Application to the Ground-Holding Problem
Authors: Ball Michael O. , Hoffman Robert , Odoni Amedeo R. , Rifkin Ryan
Published: December 2003

In this paper, we analyze a generalization of a classic network-flow model. The generalization involves the replacement of deterministic demand with stochastic demand. While this generalization destroys the original network structure, we show that the matrix underlying the stochastic model is dual network. Thus, the integer program associated with the stochastic model can be solved efficiently using network-flow or linear-programming techniques. We also develop an application of this model to the ground-holding problem in air-traffic management. The use of this model for the ground-holding problem improves upon prior models by allowing for easy integration into the newly developed ground-delay program procedures based on the Collaborative Decision-Making paradigm.
Production Planning with Flexible Product Specifications: An Application to Specialty Steel Manufacturing
Authors: Balakrishnan Anantaram , Geunes Joseph
Published: December 2003

Responding to varying customer needs for product customization, quantities, or lead times requires increased manufacturing flexibility. In certain contexts, the reverse is true, i.e., customer requirements are somewhat flexible, providing additional options in production planning. This paper considers such an opportunity faced by a specialty steel manufacturer whose customers allow flexibility in product specifications. We develop and test a model and solution methodology to exploit this flexibility during production planning. The model also applies to other situations in which manufacturers can select, within limits, the size or quantities of items produced using limited capacity. We formulate the problem as a profit-maximizing mixed-integer program with an interesting embedded packing subproblem using “expandable” items. We develop a composite solution method that combines model enhancement using strong valid inequalities, Lagrangian relaxation, and heuristic approaches. Computational results using real data from a specialty steel manufacturer and randomly generated test problems show that the algorithm generates solutions that are, on average, within 0.59% of optimality. For the problem instances based on real data, the model increases contribution to profit by over 7% relative to current practice at the steel manufacturing facility.
Pricing Options on Scalar Diffusions: An Eigenfunction Expansion Approach
Authors: Davydov Dmitry , Linetsky Vadim
Published: December 2003

This paper develops an eigenfunction expansion approach to pricing options on scalar diffusion processes. All contingent claims are unbundled into portfolios of primitive securities called eigensecurities. Eigensecurities are eigenvectors (eigenfunctions) of the pricing operator (present value operator). All computational work is at the stage of finding eigenvalues and eigenfunctions of the pricing operator. The pricing is then immediate by the linearity of the pricing operator and the eigenvector property of eigensecurities. To illustrate the computational power of the method, we develop two applications:pricing vanilla, single- and double-barrier options under the constant elasticity of variance (CEV) process and interest rate knock-out options in the Cox-Ingersoll-Ross (CIR) term-structure model.
A Call-Routing Problem with Service-Level Constraints
Authors: Gans Noah , Zhou Yong-Pin
Published: December 2003

We consider a queueing system, commonly found in inbound telephone call centers, that processes two types of work. Type-H jobs arrive at rate λH, are processed at rate μH , and are served first come, first served within class. A service-level constraint of the form E[delay] ≤ α or P {delay ≤ β} ≥ limits the delay in queue that these jobs may face. An infinite backlog of type-L jobs awaits processing at rate μH, and there is no service-level constraint on this type of work. A pool of c identical servers processes all jobs, and a system controller must maximize the rate at which type-L jobs are processed, subject to the service-level constraint placed on the type-H work.

We formulate the problem as a constrained, average-cost Markov decision process and determine the structure of effective routing policies. When the expected service times of the two classes are the same, these policies are globally optimal, and the computation time required to find the optimal policy is about that required to calculate the normalizing constant for a simple M/M/c system. When the expected service times of the two classes differ, the policies are optimal within the class of priority policies, and the determination of optimal policy parameters can be determined through the solution of a linear program with O(c3) variables and O(c2) constraints.
On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation
Authors: Fernández Elena , Meza Oscar , Garfinkel Robert , Ortega Maruja
Published: December 2003

The Rural Postman Problem (RPP) is a classic “edge-routing” problem. A mathematical programming formulation of the RPP that differs fundamentally from those in the literature was introduced, but not tested computationally, by Garfinkel and Webb (1999). A rudimentary algorithm that yields lower bounds via cutting planes and upper bounds via heuristics is developed and tested for a variation of that formulation. Computational results are encouraging, especially in terms of the relatively small number of added inequalities needed to get good lower bounds, and the fact that the vast majority of these have efficient, exact separation procedures. Note that a first algorithm based on this new formulation is computationally competitive, allowing the possibility of far more efficient and complex future realizations.
Incentive Efficient Control of a Make-to-Stock Production System
Authors: Plambeck Erica L. , Zenios Stefanos A.
Published: December 2003

This paper considers a principal-agent variant of the classical make-to-stock single-server queueing system. The principal incurs all costs for holding inventory and backordering demand. The agent dynamically controls the production rate at the server and incurs a convex production cost. The principal cannot monitor the production rate but can draw inference from increases in the inventory level. Furthermore, by making payments contingent on the inventory level, the principal motivates the agent to control the production rate in a manner that will minimize the principal's own total expected discounted cost. We show that an optimal incentive payment scheme consists of piece rates and inventory penalties that vary dynamically with the inventory level. This scheme coordinates the system if the agent is risk neutral. Otherwise, operational performance is degraded by the conflict in incentives between principal and agent. We identify some drivers of this agency loss: In addition to discounting and risk aversion in the agent's preferences, which are standard causes of friction in dynamic agency models, an increasing marginal cost of production and slack in the agent's capacity are also found to be lead contributors. Heavy traffic analysis supports these findings through closed-form expressions for the performance of the system under the optimal incentive scheme.
Multilevel Lot Sizing with Setup Times and Multiple Constrained Resources: Internally Rolling Schedules with Lot-Sizing Windows
Authors: Stadtler Hartmut
Published: December 2003

In this paper a new time-oriented decomposition heuristic is proposed to solve the dynamic multi-item multilevel lot-sizing problem in general product structures with single and multiple constrained resources as well as setup times. While lot-sizing decisions are made sequentially within an internally rolling planning interval (or lot-sizing window), capacities are always considered over the entire planning horizon. For each submodel a model formulation based on the “Simple Plant Location” representation is developed. These mixed-integer linear submodels are solved by standard mathematical programming software even for relatively large test instances. Extensive computational tests show that the heuristic proposed provides a better solution quality than a well-known special purpose heuristic.
How Multiserver Queues Scale with Growing Congestion-Dependent Demand
Authors: Whitt Ward
Published: December 2003

We investigate how performance scales in the standard M/M/n queue in the presence of growing congestion-dependent customer demand. We scale the queue by letting the potential (congestion-free) arrival rate be proportional to the number of servers, n, and letting n increase. We let the actual arrival rate with n servers be of the form λn=f(ξn)n, where f is a strictly-decreasing continuous function and ξn is a steady-state congestion measure. We consider several alternative congestion measures, such as the mean waiting time and the probability of delay. We show, under minor regularity conditions, that for each n there is a unique equilibrium pair (λ*n, ξ*n) such that ξ*n is the steady-state congestion associated with arrival rate λ*n and λ*n=f(ξ*n)n. Moreover, we show that, as n increases, the queue with the equilibrium arrival rate λ*n is brought into heavy traffic, but the three different heavy-traffic regimes for multiserver queues identified by Halfin and Whitt (1981) each can arise depending on the congestion measure used. In considerable generality, there is asymptotic service efficiency: the server utilization approaches one as n increases. Under the assumption of growing congestion-dependent demand, the service efficiency can be achieved even if there is significant uncertainty about the potential demand, because the actual arrival rate adjusts to the congestion.
A Problem of Forest Harvesting and Road Building Solved Through Model Strengthening and Lagrangean Relaxation
Authors: Andalaft Nicolas , Andalaft Pablo , Guignard Monique , Magendzo Adrian , Wainer Alexis , Weintraub Andres
Published: December 2003

We consider a problem of forest planning on pine plantations over a two to five year horizon. Basic decisions concern the areas to harvest in each period, the amount of timber to produce to satisfy aggregate demands for log exports, sawmills and pulp plants, and the roads to build for access and storage of timber. A linear programming model with 0–1 variables describes the decision process. Solution strategies involve strengthening of the model, lifting some of the constraints, and applying Lagrangean relaxation. Results on real planning problems show that even as these problems become more complex, the proposed solution strategies lead to very good solutions, reducing the residual gap for the most difficult data set from 162% to 1.6%, and for all data sets to 2.6% or less.
Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design
Authors: Ghamlouche Ilfat , Crainic Teodor Gabriel , Gendreau Michel
Published: December 2003

We propose new cycle-based neighbourhood structures for metaheuristics aimed at the fixed-charge capacitated multicommodity network design formulation. The neighbourhood defines moves that explicitly take into account the impact on the total design cost of potential modifications to the flow distribution of several commodities simultaneously. Moves are identified through a shortest-pathlike network optimization procedure and proceed by redirecting flow around cycles and closing and opening design arcs accordingly. These neighbourhoods are evaluated and tested within a simple tabu search algorithm. Experimental results show that the proposed approach is quite powerful and outperforms existing methods reported in the literature.
Still Flowing: Approaches to Traffic Flow and Traffic Jam Modeling
Authors: Nagel Kai , Wagner Peter , Woesler Richard
Published: December 2003

Certain aspects of traffic flow measurements imply the existence of a phase transition. Models known from chaos and fractals, such as nonlinear analysis of coupled differential equations, cellular automata, or coupled maps, can generate behavior which indeed resembles a phase transition in the flow behavior. Other measurements point out that the same behavior could be generated by geometrical constraints of the scenario. This paper looks at some of the empirical evidence, but mostly focuses on different modeling approaches. The theory of traffic jam dynamics is reviewed in some detail, starting from the well-established theory of kinematic waves and then veering into the area of phase transitions. One aspect of the theory of phase transitions is that, by changing one single parameter, a system can be moved from displaying a phase transition to not displaying a phase transition. This implies that models for traffic can be tuned so that they display a phase transition or not.

This paper focuses on microscopic modeling, i.e., coupled differential equations, cellular automata, and coupled maps. The phase transition behavior of these models, as far as it is known, is discussed. Similarly, fluid-dynamical models for the same questions are considered. A large portion of this paper is given to the discussion of extensions and open questions, which makes clear that the question of traffic jam dynamics is, albeit important, only a small part of an interesting and vibrant field. As our outlook shows, the whole field is moving away from a rather static view of traffic toward a dynamic view, which uses simulation as an important tool.
A Three-Stage Model for a Decentralized Distribution System of Retailers
Authors: Granot Daniel , Sošić Greys
Published: December 2003

We present and study a three-stage model of a decentralized distribution system consisting of n retailers, each of whom faces a stochastic demand for an identical product. In the first stage, before the demand is realized, each retailer independently orders her initial inventory. In the second stage, after the demand is realized, each retailer decides how much of her residual supply/demand she wants to share with the other retailers. In the third stage, residual inventories are transshipped to meet residual demands, and an additional profit is allocated. Our model is an extension of the two-stage model of Anupindi et al. (ABZ) (2001), which implicitly assumes that all residuals enter the transshipment stage. We show, however, that allocation rules in the third stage based on dual solutions, which were used in the ABZ model, may induce the retailers to hold back some of their residual supply/demand. In general, we study the effect of implementing various allocations rules in the third stage on the values of the residual supply/demand the retailers are willing to share with others in the second stage, and the trade-off involved in achieving an optimal solution for the corresponding centralized system.
Using Ranking and Selection to “Clean Up” after Simulation Optimization
Authors: Boesel Justin , Nelson Barry L. , Kim Seong-Hee
Published: December 2003

In this paper we address the problem of finding the simulated system with the best (maximum or minimum) expected performance when the number of systems is large and initial samples from each system have already been taken. This problem may be encountered when a heuristic search procedure—perhaps one originally designed for use in a deterministic environment—has been applied in a simulation-optimization context. Because of stochastic variation, the system with the best sample mean at the end of the search procedure may not coincide with the true best system encountered during the search. This paper develops statistical procedures that return the best system encountered by the search (or one near the best) with a prespecified probability. We approach this problem using combinations of statistical subset selection and indifference-zone ranking procedures. The subset-selection procedures, which use only the data already collected, screen out the obviously inferior systems, while the indifference-zone procedures, which require additional simulation effort, distinguish the best from the less obviously inferior systems.
Using Technology and Constituting Structures: A Practice Lens for Studying Technology in Organizations
Authors: Orlikowski Wanda J.
Published: December 2003

As both technologies and organizations undergo dramatic changes in form and function, organizational researchers are increasingly turning to concepts of innovation, emergence, and improvisation to help explain the new ways of organizing and using technology evident in practice. With a similar intent, I propose an extension to the structurational perspective on technology that develops a practice lens to examine how people, as they interact with a technology in their ongoing practices, enact structures which shape their emergent and situated use of that technology. Viewing the use of technology as a process of enactment enables a deeper understanding of the constitutive role of social practices in the ongoing use and change of technologies in the workplace. After developing this lens, I offer an example of its use in research, and then suggest some implications for the study of technology in organizations.
Prior Knowledge and the Discovery of Entrepreneurial Opportunities
Authors: Shane Scott
Published: December 2003

Before technological change leads to new processes, products, markets, or ways of organizing, entrepreneurs must discover opportunities in which to exploit the new technology. To date, research has not explained adequately why entrepreneurs discover these opportunities, which creates several conceptual problems in the entrepreneurship literature. Drawing on Austrian economics, I argue that opportunity discovery is a function of the distribution of information in society (Hayek 1945). Through in-depth case studies of eight sets of entrepreneurs who exploit a single MIT invention, I show that entrepreneurs discover opportunities related to the information that they already possess. I use these findings to draw several implications that differ from those prevailing in the entrepreneurship literature, including: (1) entrepreneurs do not always select between alternative market opportunities for new technologies; (2) the source of entrepreneurship lies in differences in information about opportunities; (3) the results of prior studies of entrepreneurial exploitation may suffer from bias; and (4) individual differences influence the opportunities that people discover, how their entrepreneurial efforts are organized, and how the government can influence this process.
Is Organization Theory Obvious to Practitioners? A Test of One Established Theory
Authors: Priem Richard L. , Rosenstein Joseph
Published: December 2003

Critics have argued that organization theories which “work” are obvious to practitioners; that is, the theories simply confirm relationships that are already well understood by experienced managers. In our study, four types of respondents—Chief Executive Officers (CEOs) with business school education, CEOs without such education, graduating MBA students, and liberal arts graduate students—were presented with theory-based performance-rating tasks. These tasks identified respondents' beliefs regarding high-performance alignments of businesslevel strategy, structure, and environment for manufacturing firms. The respondents' cause maps were then compared to one another and to the alignment-performance relationships prescribed by business-level contingency theory.

The graduating MBAs' cause maps reflected contingency theory most closely. The MBAs' cause maps were much closer to prescriptions of the theory, however, than were those of either the liberal arts graduate students or the experienced CEOs. This suggests that business-level contingency theory is not obvious to educated laypersons, or to highly experienced practitioners; both groups would find that the theory disconfirms aspects of their causal expectations. Further, each of the four respondent types in our study emphasized different contingency factors during the decision-making exercise. We discuss these results and their implications.
Perceived Victimization in the Workplace: The Role of Situational Factors and Victim Characteristics
Authors: Aquino Karl , Bradfield Murray
Published: December 2003

Harmful interpersonal behavior at work has generally been studied from the perspective of perpetrators. In contrast, theories of victimization suggest that other factors may also determine why certain individuals are more frequently harmed than others. For example, there may be situational factors that contribute to an environment that allows or fails to inhibit harmful actions. Other incidents of workplace harm may be consciously or unconsciously influenced by the victims themselves. This empirical study extends previous research on harmful workplace behavior by examining whether the situational variable of job status and the dispositional characteristics of aggressiveness and negative affectivity predict self-perceived victimization. Based on research in criminal victimology, we hypothesized that an employee's job status would be significantly related to perceived victimization. Research on victims of bullying was the basis for the predicted effects of negative affectivity and aggressiveness. Data were provided by a randomly selected sample of employees from a city government who completed a survey as part of an organizational assessment. We performed exploratory and confirmatory factor analyses on employee responses to develop suitable measures of victimization. The analyses revealed that perceived victimization took either direct (e.g., name-calling) or indirect (e.g., sabotaging work) forms. Hierarchical regression was used to test the study hypotheses. Results showed that job status did not significantly influence perceived victimization. However, employees who were high in aggressiveness and negative affectivity perceived higher levels of victimization than those who were low in these traits. Implications for organizations are discussed and future research directions are offered.
An Empirical Investigation of the Effect of Market Orientation and Entrepreneurship Orientation Alignment on Product Innovation
Authors: Atuahene-Gima Kwaku , Ko Anthony
Published: December 2003

This article develops a concept of an alignment between market and entrepreneurship orientations and reports the results of a study designed to investigate its effect on a firm’s product innovation. A sample of 181 firms was classified into four categories labeled as market/entrepreneurship orientation (ME), entrepreneurship orientation (EO), market-oriented (MO), and conservative (CO) firms. One-way ANOVA and planned contrast tests (PCT) were used to identify whether or not specific product innovation decisions, activities, and performance vary across the groups. The results indicate that these groups of firms significantly differ with respect to both subjective and objective measures of new product performance, and with product innovation strategies and activities pertaining to timing of market entry, product quality, marketing synergy, proficiency of market launch, and management support for innovation. Further, the findings suggest that these groups of firms are not significantly different with respect to perceived environmental hostility and intensity of market competition. This finding suggests that the groups of firms are robust across environments and that the findings presented in this study are not an artifact of environmental variation. Managerial and research implications of the results are discussed.
Bringing Work Back In
Authors: Barley Stephen R. , Kunda Gideon
Published: December 2003

In this essay we argue that organization theory's effort to make sense of postbureaucratic organizing is hampered by a dearth of detailed studies of work. We review the history of organization theory to show that, in the past, studies of work provided an empirical foundation for theories of bureaucracy, and explain how such research became marginalized or ignored. We then discuss methodological requirements for reintegrating work studies into organization theory and indicate what the conceptual payoffs of such integration might be. These payoffs include breaking new conceptual ground, resolving theoretical puzzles, envisioning organizing processes, and revitalizing old concepts.
Knowledge and Organization: A Social-Practice Perspective
Authors: Brown John Seely , Duguid Paul
Published: December 2003

While the recent focus on knowledge has undoubtedly benefited organizational studies, the literature still presents a sharply contrasting and even contradictory view of knowledge, which at times is described as “sticky” and at other times “leaky.” This paper is written on the premise that there is more than a problem with metaphors at issue here, and more than accounts of different types of knowledge (such as “tacit” and “explicit”) can readily explain. Rather, these contrary descriptions of knowledge reflect different, partial, and sometimes “balkanized” perspectives from which knowledge and organization are viewed. Taking the community of practice as a unifying unit of analysis for understanding knowledge in the firm, the paper suggests that often too much attention is paid to the idea of community, too little to the implications of practice. Practice, we suggest, creates epistemic differences among the communities within a firm, and the firm's advantage over the market lies in dynamically coordinating the knowledge produced by these communities despite such differences. In making this argument, we argue that analyses of systemic innovation should be extended to embrace all firms in a knowledge economy, not just the classically innovative. This extension will call for a transformation of conventional ideas coordination and of the trade-off between exploration and exploitation.