Sponsored Sessions by


Applied Probability Society at
INFORMS 2000 San Antonio (Nov. 5~8, 2000)
 

In honor of Carl M. Harris


Cluster Chair: Jim Dai (dai@isye.gatech.edu)

               ISyE, Georgia Tech, Atlanta, GA 30332-0205

  

Sessions

- Sunday,  Nov. 5
SA. Analysis and Control of Communications Networks
    Doug Down, McMaster University

SB. [TUTORIAL] Moment Problems and their Applications in Probability Theory, Finance, Stochastic Networks and Combinatorial Optimization
    Dimitris Bertsimas, MIT
SC. Analysis and Control of Queueing Systems
    Hayriye Ayhan, Georgia Tech
SD. Computational Finance
    Benjamin Van Roy, Stanford University


- Monday,  Nov. 6
MA. Probabilistic Models in Networks
    Harold Mortazavian, Univ. of California - Los Angles
MC. [TUTORIAL] Traffic Modeling for Queues and its Impact on Performance Analysis
    Peter Glynn, Stanford University
MD. Dynamic Control for Stochastic Networks I
    Sunil Kumar, Stanford University and Ruth Williams, Univ. of California - San Diego

- Tuesday,  Nov. 7
TA. Stability of Queueing Networks

    John Hasenbein, Univ. of Texas - Austin
TC. [TUTORIAL] Some Mathematical Models of Cancer Treatment
    Lawrence M. Wein, MIT
TD. Dynamic Control for Stochastic Networks II
    Sunil Kumar, Stanford University and Ruth Williams, Univ. of California - San Diego
TE. Analysis and Control of Flexible Service Networks
    Costis MaglarasColumbia Business School

- Wednesday,  Nov. 8
WA. Dynamic Control and Performance for Stochastic Networks

    Sunil Kumar, Stanford University and Ruth Williams, Univ. of California - San Diego

WB. Numerical Applied Probability Methods --- in honor of Carl M. Harris
    L. D. Servi, GTE Laboratories
 


Session SA. 

Title:  Analysis and Control of Communications Networks
Chair:  Doug Down, Dept of Computing and Software, McMaster University, 1280 Main Street West, Hamilton, Ontario L8S 4L7, Canada
        Email: downd@mcmail.cis.mcmaster.ca

Paper 1.

Title:  Dynamics of a Congestion Pricing Model
Author: A. Ganesh, Microsoft UK
        Email: ajg@microsoft.com
Abstract:

We study the use of pricing as a mechanism for allocating bandwidth in communication networks. Starting with a 0/1 pricing scheme proposed by Gibbens and Kelly, we use a distributed control framework to study whether providing more information to users can lead to faster convergence to an efficient allocation of bandwidth in the network.


Paper 2.

Title:  Overloading a Queueing Network: Bifurcations in Path Behavior
Author: David McDonald, Dept. of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Ontario, Canada, K1N 6N5
        Email: dmdsg@omid.mathstat.uottawa.ca
Abstract:

When the heaviest loaded node in a Jackson network overloads, the other nodes remain stable with larger loads. If, however, the network is modified so that an idle server helps the busy ones then the numbers of customers in the other nodes perform a Brownian excursion.


Paper 3.

Title:  A Conditional Large Deviation Result for Levy Processes
Author 1: Gregory Richardson, Dept. of Mathematics, University of Texas - Austin, RLM 8.100, Austin, TX 78712-1082
        Email: gregorys@math.utexas.edu
Author 2: Takis Konstantopoulos, ECE Dept., University of Texas - Austin, Austin, TX 78712
        Email: takis@alea.ece.utexas.edu
Abstract:

We look at the way a communications node, driven by certain Levy heavy-tailed -type input, overflows, and identify the optimal path, which, as in similar situations, consists of a large jump, instead of building up linearly. We also discuss some implications of this result.


Paper 4.

Title:  Asymptotics for Polling Models with Limited Service Policies
Author 1: Woojin Chang, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: woojin@isye.gatech.edu
Author 2: Doug Down, Dept of Computing and Software, McMaster University, 1280 Main Street West, Hamilton, Ontario L8S 4L7, Canada
        Email: downd@mcmail.cis.mcmaster.ca
Abstract:

We develop expressions for the exact asymptotics of exponential polling models under limited service policies. In addition, we explore the implications of these results for system performance (contrasting with usual measures such as expected waiting times) and buffer allocation problems.

 

 

Session SB.

Title:  [TUTORIAL] Moment Problems and their Applications in Probability Theory, Finance, Stochastic Networks and Combinatorial Optimization
Author: Dimitris Bertsimas, Sloan School of Management, MIT, Cambridge, MA 02139
        Email: dbertsim@mit.edu
Abstract:

Problems involving moments of random variables arise naturally in many areas of mathematics, economics, and operations research. How do we obtain optimal bounds on the probability that a random variable belongs in a set, given some of its moments? How do we price financial derivatives without assuming any model for the underlying price dynamics, given only moments of the price of the underlying asset? How do we obtain stronger relaxations for stochastic optimization problems exploiting the knowledge that the decision variables are moments of random variables? Can we generate near optimal solutions for a discrete optimization problem from a semidefinite relaxation by interpreting an optimal solution of the relaxation as a covariance matrix? In this talk, we demonstrate that convex, and in particular semidefinite, optimization methods lead to interesting and often unexpected answers to these questions.


 
 

Session SC. 

Title:  Analysis and Control of Queueing Systems
Chair:  Hayriye Ayhan, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: hayhan@isye.gatech.edu

Paper 1.

Title:  A Diffusion Approximation for Queues with Reneging
Author 1: Amy Ward, Stanford University, Dept. of Management Science and Engineering, Terman Engineering Center, Stanford, CA 94305-4026
        Email: award@leland.stanford.edu
Author 2: Peter Glynn, Stanford University, Dept. of Management Science and Engineering, Terman Engineering Center, Stanford, CA 94305-4026
        Email: glynn@leland.stanford.edu
Abstract:

We develop a diffusion approximation for a queueing system that includes job deadlines. We propose a nonstandard approximation: an Ornstein-Uhlenbeck process with additional downwards drift and reflection at the origin. We further provide explicit formulas for estimating important system performance measures and compare these estimations with exact results.


Paper 2.

Title:  Increasing Flexibility
Author: Mark E. Lewis, Industrial and Operations Engineering, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI 48109-2117
        Email: melewis@engin.umich.edu
Abstract:

Consider a controlled M/M/1/K system where customers may be subject to two assessments. The first occurs upon arrival and the second which occurs with some probability p, occurs when the customer reaches the front of the queue. The initial decision-maker has limited knowledge of the customer's work requirements.


Paper 3.

Title:  Exact Asymptotics for Rare Events in a Queueing System with Multiple Customer Types
Author 1: Jerome Coombs-Reyes, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: jerome@isye.gatech.edu
Author 2: Robert D. Foley, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: rfoley@isye.gatech.edu
Abstract:

Consider two queues and four customer types. Two are dedicated, the third joins the shorter queue, and the fourth, the queue with the shorter expected waiting time. We obtain exact asymptotic expressions for the stationary probability of and the expected time until some large level of customers.


Paper 4.

Title:  Laplace Transform and Moments of Waiting Times in Poisson Driven (max,+)-Linear Systems
Author 1: Hayriye Ayhan, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: hayhan@isye.gatech.edu
Author 2: Dong-Won Seo, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: dongwon@isye.gatech.edu
Abstract:

(Max,+) linear systems can be used to model a class of queueing networks. We provide explicit expressions for the moments and the Laplace transform of transient waiting times in Poisson driven (max,+) linear systems. Furthermore, starting with these closed form expressions, we also derive explicit expressions for the moments and the Laplace transform of stationary waiting times in a class of (max,+) linear systems with deterministic service times. Examples pertaining to queueing theory are given to illustrate the results.


 
 

Session SD.

Title:  Computational Finance
Chair:  Benjamin Van Roy, Stanford University, Terman 427, Stanford, CA 94307
        Email: bvr@stanford.edu

Paper 1.

Title:  Callibration in Interest Rate Markets
Author 1: Yaser S. Abu-Mostafa, Caltech, 136-93, Pasadena, CA 91125
        Email: yaser@caltech.edu
Author 2: Malik Magdon-Ismail, Rensselaer Polytechnic Institute, 207 Lally Building, CS department, RPI, 110 8th Street, Troy, NY 12189
        Email: magdon@cs.rpi.edu
Abstract:

In this presentation, we will discuss the problem of callibrating multifactor Vasicek models to interest rate data, in particular, to swaps data. Of particular importance is the ability to extract the correct volatility term structure for the purposes of pricing interest rate options. We will demonstrate how conventionally used techniques are not successful, especially as the number of factors increases beyond two. The addition of a consistency hint into the callibration produces a dramatic improvement, resulting in realistic volatility term structures. The use of such callibration techniques for relative value trading will be discussed and the techniques will be illustrated using simulations on real data.


Paper 2.

Title:  Tax-Aware Multiperiod Portfolio Optimization
Author 1: Dimitris Bertsimas, Sloan School of Management, Bldg. E53-359, Massachusetts Institute of Technology, Cambridge, MA 02139
        Email: dbertsim@aris.mit.edu
Author 2: Georgia Mourtzinou, Dynamic Ideas, LLC, P.O.Box 425547, Cambridge, MA 02142
        Email: gina@aris.mit.edu
Abstract:

We formulate the problem of optimally trading a taxable portfolio as a stochastic dynamic programming problem. Because of its dimensionality, we develop an approximation algorithm that can solve large scale problems involving thousands of assets over several periods. We show that optimal multiperiod strategies outperform single period and buy-and-hold strategies.


Paper 3.

Title:  Pricing American Options: A Comparison of Monte Carlo Simulation Approaches
Author 1: Michael Fu, The Robert H. Smith School of Business, Van Munching Hall, University of Maryland, College Park, MD 20742-1815
        Email: mfu@rhsmith.umd.edu
Author 2: Scott B. Laprise, Dept. of Mathematics, University of Maryland, College Park, MD 20742
        Email: sbl@math.umd.edu
Author 3: Dilip B. Madan, The Robert H. Smith School of Business, University of Maryland, College Park, MD 20742
        Email: dmadan@rhsmith.umd.edu
Author 4: Yi Su, The Robert H. Smith School of Business, Van Munching Hall, University of Maryland, College Park, MD 20742
        Email: ysu@glue.umd.edu
Author 5: Rongwen Wu, Dept. of Mathematics, University of Maryland, College Park, MD 20742
        Email: rxw@math.umd.edu
Abstract:

We compare various Monte Carlo simulation-based approaches for pricing American-style derivatives on a common set of numerical problems. We also introduce another simulation-based approach that employs a simultaneous perturbation stochastic approximation (SPSA) algorithm.


Paper 4.

Title:  Regression Methods for Pricing Complex American-Style Options 
Author: Benjamin Van Roy, Stanford University, Terman 427, Stanford, CA 94307
        Email: bvr@stanford.edu
Abstract:

A number of researchers have proposed methods for approximating pricing functions of high-dimensional American-style options. We discuss characteristics common to these methods and a key ingredient possessed by some that reduces approximation error dramatically. We also propose extensions to the methodology that should lead to further computational advantages. 


 
 

Session MA.

Title:  Probabilistic Models in Networks
Chair:  Harold Mortazavian, Computer Science Department, University of California - Los Angles
        Email: mor@cs.ucla.edu

Paper 1.

Title:  Traffic and Mobility Modeling in Wireless Networks
Author 1: Brian Mark, Dept. of Electrical and Computer Engineering, George Mason University, 4400 University Drive, Fairfax, VA 22030-4444
        Email: bmark@gmu.edu
Author 2: Shun-Zheng Yu, Dept. of Electrical and Computer Engineering, George Mason University
        Email:
Author 3: Hisashi Kobayashi, Dept. of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ 08544-5263
        Email: hisashi@ee.princeton.edu
Abstract:

Most previous work on traffic modeling and service provisioning has not considered thoroughly he impact of mobility in wireless networks. In this paper, we develop an integrated set of probabilistic models for traffic and mobility in wireless networks. We discuss applications of these models to quality-of-service provisioning and fast web access at the wireless/wired network interface.


Paper 2.

Title:  A Unified Approach to the Analysis of Teletraffic Models and their Computational Solution
Author: Khosrow Sohraby, Computer Science Telecommunications Department, University of Missouri-Kansas City, 5100 Rockhill Road, Kansas City, MO 64110-2499
        Email: sohraby@cstp.umkc.edu
Abstract: 

In this talk we present a system-theoretic approach to the solution of a large class of teletraffic problems. Under the assumption of rationality of the generating functions of input processes, and having obtained a state-space realization of the system, we derive an efficient matrix-geometric solution for the state probability vector of the system.


Paper 3.

Title:  An Approach to Distributed Probabilistic Routing and Congestion Control in Networks
Author: Harold Mortazavian, Computer Science Department, University of California - Los Angeles
        Email: mor@cs.ucla.edu
Abstract: 

In this talk, we present a new approach to distributed probabilistic routing and congestion control in networks in which routers are viewed as local controllers. The concepts of probabilistic controllability and observability with specified parameters and a differential equation, depending on these parameters, whose solution provides the probability distribution of routing at each node are introduced. 


Paper 4.

Title:  Continuous Flow Models: Modeling, Simulation, IPA and Telecommunications Approaches
Author: Benjamin Melamed, 
Faculty of Management, Rutgers University,256 Janice H. Levin Building, Rockafeller Rd., New Brunswick, NJ 08903
        Email: melamed@rutcor.rutgers.edu
Abstract:

In this talk , we introduce a simple class of fluid-flow models, called continuous flow models(CFM), reporting on joint work with Yorai Wardi. We will discuss problems of modeling propagation delays, loss-related performance measures, real-time computation and other pertinent issues. Also, the relation with infinitesimal perturbation analysis will be discussed.


 
 

Session MC.

Title:  [TUTORIAL] Traffic Modeling for Queues and its Impact on Performance Analysis
Author: Peter Glynn, Dept. of Management Science and Engineering, Stanford University, Stanford, CA 94305-4026
        Email: glynn@leland.stanford.edu
Abstract:

We discuss three different types of traffic environments: short-range dependent with light ( marginal ) tails, short-range dependent with heavy tails, and long-range dependent with light tails. Specifically, we describe the qualitative behavior of a queue fed by such traffic ( heavy-traffic scaling, most likely path to buffer overflow, relaxation time, etc. ).


 
 

Session MD.

Title:  Dynamic Control for Stochastic Networks I
Chair 1: Sunil Kumar, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: kumar_sunil@gsb.stanford.edu
Chair 2: Ruth Williams, Dept. of Mathematics, University of California - San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112
        Email: williams@russel.ucsd.edu

Paper 1.

Title:  A Multiclass Queue in Heavy Traffic with Throughput Time Constraints: Asymptotically Optimal Dynamic Controls
Author: Erica Plambeck, Stanford University
        Email: elp@leland.stanford.edu
Abstract:

Consider a queueing system with multiple classes of jobs, each having its own renewal input process, service time distribution, revenue contribution, and maximum allowed throughput time. A system manager must decide whether or not to accept new jobs as they arrive, and also the order in which to serve jobs that are accepted. The goal is to minimize the revenue lost by rejecting jobs, subject to the upper bound on throughput time for any job that is accepted. This problem formulation does not make sense in a conventional queueing model, because throughput times are random variables, but we show that the formulation is meaningful in an asymptotic sense, under diffusion scaling as the system utilization approaches the critical value of one. Moreover, using a method developed recently by Bramson and Williams, we prove that a relatively simple dynamic control policy is asymptotically optimal in this framework. Our proposed policy rejects jobs from one particular class whenever the server's nominal workload exceeds a threshold value, accepting all other arrivals; and the sequencing rule for accepted jobs is one that maintains near equality of the relative backlogs for different classes, defined in a natural sense.


Paper 2.

Title:  Dynamic Scheduling of a Parallel Server System with Complete Resource Pooling
Author 1: Ruth Williams, Dept. of Mathematics, University of California - San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112
        Email: williams@russel.ucsd.edu
Author 2: Steven L. Bell, Dept. of Mathematics, University of California - San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112
        Email: slbell@math.ucsd.edu
Abstract:

We consider a parallel server queueing system with flexible scheduling capabilities. Under a complete resource pooling condition, a continuous review threshold control policy is proposed, and it is shown to be asymptotically optimal in the heavy traffic limit.


Paper 3.

Title:  Dynamic Control for Stochastic Networks: A Comparison of Fluid vs. Brownian Approximations
Author: Costis Maglaras, 409 Uris Hall, Columbia Business School, 3022 Broadway, NYC, NY 10027
        Email: c.maglaras@columbia.edu
Abstract:

A promising approach for designing control policies for stochastic networks is based on (a) analysis of fluid or Brownian approximating models, and (b) translation of the corresponding controls through, for example, tracking or discrete-review policies. We contrast the solutions extracted from these two model approximations through simple examples.


Paper 4.

Title:  A New Numerical Method for Solving Brownian Control Problems
Author 1: Sunil Kumar, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: kumar_sunil@gsb.stanford.edu
Author 2: Muthukumar Muthuraman, Scientific Computing and Computational Mathematics, Dept. of Computer Science, Stanford University
        Email: mkumar@stanford.edu
Abstract:

We present a new method for numerically solving Brownian control problems. We adapt nonlinear finite element methods to numerically solve the Hamilton-Jacobi-Bellman equation associated with the Brownian control problem. The solution to this partial differential equation is then used to construct an optimal control for the Brownian system.


 
 

Session TA.

Title:  Stability of Queueing Networks
Chair:  John Hasenbein, Mechanical Engineering Dept., University of Texas - Austin, Austin, TX 78712-1063
        Email: jhas@mail.utexas.edu

Paper 1.

Title:  Stability and Optimization of Packet Routing in Communication Networks
Author: David Gamarnik, Math Sciences Department, T.J. Watson Research Center, P.O.Box 218, Yorktown Heights, NY 10598
        Email: gamarnik@watson.ibm.com
Abstract:

In the packet routing problem, digital communication packets have a specified origin and destination in the communication graph, and the scheduler has to choose paths along which to process the packets. We construct an asymptotically optimal offline schedule for the static version of this problem and a stable schedule for the dynamic (online) version of the problem. Both are constructed using multicommodity flow type linear programming formulation, which is also proven to give a sharp condition for existence of a stable schedule in the dynamic version.


Paper 2.

Title:  Establishing Stability for Multiclass Queueing Networks with Setups
Author: Otis Jennings, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: otisj@isye.gatech.edu
Abstract:

In multiclass networks with setups, one cannot ignore questions of stability. We present a general framework for proving stability, provide a heuristic service meta-policy for guaranteeing stability, and prove stability of the heuristic when used in conjunction with Last-Buffer-First-Served (LBFS), FBFS, or a specific round robin policy. The framework, whose core is a fluid limit model of the original queueing network, is an extension and refinement of the works of Dai(1995), Chen(1995), and Bramson(1998). The heuristic dictates the process batch size after a default service policy makes a dispatch decision.


Paper 3.

Title:  Stability of Reentrant Lines with Batch Servers
Author 1: Sunil Kumar, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: kumar_sunil@gsb.stanford.edu
Author 2: Hao Zhang, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: 
Abstract:

We explore stability in open reentrant lines with batch servers. We present simple combinations of fluctuation smoothing policies and minimum batch size rules that guarantee stability of reentrant lines with batch servers. We prove stability by adapting a fluid model method, first proposed by Dai.


Paper 4.

Title:  Scheduling and Stability of Queues with Wait-Dependent Service Times
Author 1: John Hasenbein, Graduate Program in OR/IE, Dept. of Mechanical Engineering, University of Texas - Austin, Austin, TX 78712-1063
        Email: jhas@mail.utexas.edu
Author 2: Valerie Tardif, Graduate Program in OR/IE, Dept. of Mechanical Engineering, University of Texas - Austin, Austin, TX 78712-1063
        Email: vtardif@mail.utexas.edu
Author 3: Elizabeth Campbell, Graduate Program in OR/IE, Dept. of Mechanical Engineering, University of Texas - Austin, Austin, TX 78712-1063
        Email: ecampbell@mail.utexas.edu
Abstract:

We consider single-station queueing systems in which the service time of a job may depend on its time spent in queue. We first present some new results on the optimal scheduling policy for such queues. Next, we consider the stability region for these systems under optimal policies. We examine two notions of stability, q-stability (queue-length stability) and w-stability (workload stability). It turns out that the w-stability region is non-trivial, even for the case of deterministic single-station wait-dependent queues.


 
 

Session TC.

Title:  [TUTORIAL] Some Mathematical Models of Cancer Treatment
Author: Lawrence M. Wein, Sloan School of Management, MIT, Cambridge, MA 02142
        Email: lwein@mit.edu
Abstract:

This talk will describe several (about five) mathematical problems concerning the analysis, design and/or control of traditional (chemotherapy, radiation, surgery) and novel (gene therapy, angiogenesis inhibitors) cancer therapies. We will omit most of the mathematical details, and instead focus on the biological aspects of the model formulations and the insights from our analyses.


 
 

Session TD.

Title:  Dynamic Control for Stochastic Networks II
Chair 1: Sunil Kumar, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: kumar_sunil@gsb.stanford.edu
Chair 2: Ruth Williams, Dept. of Mathematics, University of California - San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112
        Email: williams@russel.ucsd.edu

Paper 1.

Title:  Heavy-Traffic Limit Theorems for Controlled Queues Through Linear Programs
Author: Thomas Kurtz, Dept. of Mathematics, University of Wisconsin - Madison, 480 Lincoln Drive, Madison, WI 53706-1388
        Email: kurtz@math.wisc.edu
Abstract:

Stochastic control problems for queueing networks are formulated as martingale problems and the optimal solutions are characterized as the solutions of infinite dimensional linear programs. Assuming heavy traffic scaling, the solution of the linear program is shown to converge to the optimal solution of the limiting singular control problem.


Paper 2.

Title:  Multiclass Queueing Networks with Batch Processing
Author 1: Jim Dai, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: dai@isye.gatech.edu
Author 2: Caiwei Li, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205
        Email: cwli@isye.gatech.edu
Abstract:

If a server is capable of grouping a certain number of jobs into a single processing batch at its service station, the server is said to be a batch processing server. A furnace in a semiconductor wafer fabrication facility is an example of a batch processing server. We consider multiclass queueing networks for which one or many service stations have batch processing servers. We discuss a number of insights, based on fluid limits analysis, to efficiently schedule such networks.


Paper 3.

Title:  Inventory Control in Supply Chains: A Large Deviations Approach
Author 1: Ioannis Ch. Paschalidis, Boston University, Dept. of Manufacturing Engineering, Boston, MA 02215
        Email: yannisp@bu.edu
Author 2: Yong Liu, Boston University, Dept. of Manufacturing Engineering, Boston, MA 02215
        Email: liuyong@bu.edu
Abstract:

We consider a supply chain of a single product class consisting of a tandem of production facilities. We derive large deviations asymptotics to devise production policies that minimize expected inventory costs subject to given service-level constraints. Extensions to multiple product classes will be discussed.


Paper 4.

Title:  Largest Weighted Delay First Discipline
Author: Alexander Stolyar, Bell Laboratories, Lucent Technologies, 600 Mountain Av., Murray Hill, NJ 07974-0636
        Email: stolyar@research.bell-labs.com
Abstract:

It was shown recently that the LWDF discipline is optimal in a single server system with arbitrary number of flows, in that LWDF achieves the desired exponential decay rates of the waiting time distributions if this is feasible at all. We will discuss some extensions of this result.
 
 

Session TE.

Title:  Analysis and Control of Flexible Service Networks
Chair:  Costis Maglaras, 409 Uris Hall, Columbia Business School, 3022 Broadway, NYC, NY 10027
        Email: c.maglaras@columbia.edu

Paper 1. 

Title:  Scheduling Open Queueing Networks with Sufficiently Flexible Resources
Author: Sunil Kumar, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: kumar_sunil@gsb.stanford.edu
Abstract:

We study asymptotically optimal scheduling of open queueing networks with flexible non-identical servers with overlapping capabilities. We articulate a condition that ensures the corresponding Brownian control problem is one dimensional. We propose an asymptotically optimal Discrete Review scheduling policy for networks satisfying this condition.


Paper 2. 

Title:  Diffusion Limits for Multiskill Call Centers with Many Agents
Author: Martin I. Reiman, Bell Labs, Lucent Technologies, 600 Mountain Ave., Room 2C-315, Murray Hill, NJ 07974
        Email: marty@research.bell-labs.com
Abstract:

We consider a queueing model of a call center providing service to several customer types (skills), where each server (agent) can handle some subset of the skills. We examine this model in the Halfin-Whitt regime, which involves the number of servers growing large while the traffic intensity approaches unity.


Paper 3.

Title:  Skills-Based Routing with Service-Level Constraints
Author 1: Noah Gans, OPIM Dept. - Wharton, University of Pennsylvania, Philadelphia, PA 19104-6366
        Email: gans@wharton.upenn.edu
Author 2: Yong-Pin Zhou, OPIM Dept. - Wharton, University of Pennsylvania, Philadelphia, PA 19104-6366
        Email: yongpin@wharton.upenn.edu
Abstract:

In the skill-based routing problem, many types of jobs arrive to queues with heterogeneous servers. The objective is to devise a routing scheme that best utilizes the server capacities, subject to a service-level constraint. We analyze a common special-case of the problem with simple, MDP-type models.


Paper 4.

Title:  Service Networks with Channel and Service Level Flexibility
Author 1: Mor Armony, Operations Management Dept., Stern School of Business, New York University, 40 West 4th street, suite 7-02, New York, NY 10012-1118
        Email: marmony@stern.nyu.edu
Author 2: Costis Maglaras, 409 Uris Hall, Columbia Business School, 3022 Broadway, NYC, NY 10027
        Email: c.maglaras@columbia.edu
Abstract:

Consider flexible service networks that provide customers' interaction through a variety of channels with differentiated quality of service specifications. The users may choose their service channel based on the respective expected waiting times provided by the system. We characterize system equilibrium and quantify the benefits of service flexibility.


 
 

Session WA.

Title:  Dynamic Control and Performance for Stochastic Networks
Chair 1: Sunil Kumar, Graduate School of Business, 518 Memorial Way, Stanford University, Stanford, CA 94305-5015
        Email: kumar_sunil@gsb.stanford.edu
Chair 2: Ruth Williams, Dept. of Mathematics, University of California - San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112
        Email: williams@russel.ucsd.edu

Paper 1.

Title:  A Processor Sharing Queue in Heavy Traffic 
Author: H. Christian Gromoll, Dept. of Mathematics, University of California - San Diego, 9500 Gilman Drive, La Jolla, CA 92093-0112
        Email: cgromoll@math.ucsd.edu
Abstract:

We discuss some recent results on the heavy traffic behavior of a processor sharing queue. Our main approach is to study a certain measure valued process, which encodes information about the residual service times and from which standard measures of performance such as queue length, workload and sojourn time can be recovered. 


Paper 2.

Title:  Performance of the Closed Lu-Kumar Network
Author: Jenny Steichen, Dept. of Mathematics, University of Illinois, Champaign-Urbana
        Email: steichen@kungpao.csl.uiuc.edu
Abstract:

We study the performance of the closed Lu-Kumar network under heavy traffic. The idleness processes and throughput are compared in the supercritical, critical, and subcritical cases. In addition, the performance of the Lu-Kumar policy is compared to performance under the optimal control policy (studied by Harrison, Wein, S. Kumar).


Paper 3.

Title:  A Dynamic Threshold Routing System in Heavy Traffic
Author 1: Vlada Limic, Dept. of Mathematics, Cornell University, Malott Hall, Ithaca, NY 14850-4201
        Email: limic@math.cornell.edu
Author 2: Ruth Williams, Dept. of Mathematics, University of Wisconsin - Madison, 480 Lincoln Drive, Madison, WI 53706-1388
        Email: kurtz@math.wisc.edu
Abstract:

We derive, under suitable regularity conditions, a heavy traffic approximation for a sequence of dynamic threshold routing queueing systems. A special case of this problem was first considered by Kelly and Laws (1993). The diffusion approximation is related to the submartingale reflecting Brownian motion of Varadhan and Williams (1985).


Paper 4.

Title:  Critical Thresholds for Dynamic Scheduling in Heavy Traffic
Author: Yih-Choung Teh, Analysys Consulting, St Giles Court, 24 Castle Street, Cambridge CB3 0AJ, UK
        Email: teh@stats.ox.ac.uk
Abstract:

We consider queueing systems which exhibit complete resource pooling in heavy traffic and, in particular, a threshold routing strategy. The behaviour of the limiting system depends critically on thresholds which grow at a logarithmic rate. We establish necessary and sufficient conditions for reflected Brownian motion, stability and asymptotic optimality.


 
 

Session WB.

Title:  Numerical Applied Probability Methods --- in honor of Carl M. Harris
Chair:  L. D. Servi, GTE Laboratories, 40 Sylvan Rd., Waltham, MA 02254-1128
        Email: lds0@gte.com

Paper 1. 

Title:  Analysis of a Machine Repair Problem with an Unreliable Server and Phase Type Repairs and Services
Author 1: Srinivas R. Chakravarthy, Dept. of Industrial and Manufacturing Engineering & Business, Kettering University, Flint, MI 48504
        Email: schakrav@kettering.edu
Author 2: Atul Agarwal, Dept. of Industrial and Manufacturing Engineering & Business, Kettering University, Flint, MI 48504
        Email: aagarwal@kettering.edu
Abstract:

Using matrix-analytic methods we perform steady state analysis of a machine repair model with a single unreliable server and N identical machines. The repair times of the machine and the service times of the repairman are of phase type. An optimization problem and several illustrative numerical examples are presented. 


Paper 2.

Title:  Exploiting the Layered Structure in Matrix Geometric Tandem Priority Queues
Author 1: David A. Stanford, Dept. of Statistical and Actuarial Sciences, The University of Western Ontario, London, Ontario N2L 3G1
        Email: stanford@stats.uwo.ca
Author 2: Kandiyan Sapna, Dept. of Statistical and Actuarial Sciences, The University of Western Ontario, London, Ontario N2L 3G1
        Email: sapna@stats.uwo.ca
Author 3: Karuna Ramachandran, Exponent, Menlo Park, CA 94025
        Email: 
Abstract:

In matrix geometric models, it is often possible to arrange the state information so that computations can be carried out in a layered way. This approach enables one to focus on the calculations at the current level without being distracted by information from a lower level. We illustrate this approach in the analysis of a tandem M/PH/1 queue.


Paper 3. 

Title:  Analysis of MAP/PH/1 Multiclass General Preemptive Priority
Author 1: Attahiru Sule Alfa, University of Windsor, Windso, ON N9B 3P4
        Email: alfa@uwindsor.ca
Author 2: Qi-Ming He, Dalhousie University, Dept. of Industrial Engineering, Halifax, NS B3J2X4
        Email: qi-ming.he@del.ca
Abstract:

We use the matrix-analytic methods to study the MAP/PH/1 general preemptive priority queue with a multiple class of jobs. We show that the structure of the R matrix obtained by Miller for the Birth-Death system can be extended to the Quasi-Birth-Death case. Procedures for computing performance measures associated with the queue lengths and busy periods are developed. 


Paper 4. 

Title:  Equilibrium Distribution of Block-Structured Markov Chains with Large Numbers of States
Author: L. D. Servi, GTE Laboratories, 40 Sylvan Rd., Waltham, MA 02254-1128
        Email: lds0@gte.com
Abstract:

Many telecommunication applications require solving a Markov chain whose transition matrix has a block tridiagonal structure with each block, itself, tridiagonal. We present improvements to our previous algorithms that are specialized for systems with a very large number of states and compared with alternative algorithms such as the GTH algorithm.