** Title: ** Modeling of LAS-based scheduling polices in packet switched networks

** Abstract: ** In recent years there has been an increased interest in size-based
scheduling policies such as SRPT (Shortest Remaining Processing Time)
that was motivated by empirical observations showing that job sizes
are heavy-tailed or at least have a coefficient of variation larger
than one. In this case, SRPT as compared to FCFS can significantly
reduce the response time of short jobs without too much penalizing
large jobs.
However, SRPT requires the jobs size to be known ahead of time, which
is not always the case. For this reason, we have been studying LAS
(Least Attained Service) scheduling policies that give service to the
job in the system that has so far received the least amount of
service. We are interested in using LAS in packet switched networks
and develop analytical models to asses its performance. LAS
scheduling up to now has been analyzed for jobs that arrive to the
server all at once. However, in packet switched networks, LAS is
applied to flows; a flow being defined as a sequence of packets that
are exchanged between two particular end-points. While a job arrives
to the server all at once, the packets of a flow arrive to the router
at disparate points of time. We show how to model LAS in packet
switched networks and we introduce a family of Two-Class LAS policies,
for which the service priority of packets in the regular class (class
1) is computed as under (plain) LAS, while the service priority of
packets in the priority class (class 2) is computed using a policy
function P(x). We discuss the performance for several of these policy
functions and show that a logarithmic policy function greatly improves
the mean flow transfer time for priority long flows while providing
performance similar to (plain) LAS for regular flows.

** Co-authors: **Idris Rai, Guillaume Urvoy-Keller, and Mary Vernon

** Short bio: ** Ernst Biersack has received his M.S. and Ph.D. degrees in Computer
Science from the Technische Universitaet Muenchen, Munich, Germany and
his "Habilitation a diriger la Recherche" from the University of Nice
Sophia Antipolis. From 1989 to 1992 he was a Member of Technical
Staff of Bell Communications Research in Morristown, US. Since then
he has been a Professor in Telecommunications at Institut Eurecom, in
Sophia Antipolis, France. His research interest is in the area of design
and evaluation of scalable protocols and mechanisms for the
Internet. His research covers topics such as Multicast Error and
Congestion Control, Caching and Content Distribution Networks,
Scalable Video Distribution on the Internet, Peer-to-Peer Systems,
Network Tomography, and Scheduling in Edge Routers.

** Interest areas in multiserver scheduling: **Scheduling policies in
packet networks, fairness, load balancing

** Papers relevant to talk: ** Click Here

** Title: ** Combinatorial Service Disciplines in the Multi-Server Queue

** Abstract: ** We consider multi-server queues where optimal customer
scheduling solves NP-hard packing and fragmentation problems,
and where the infinite server queue models arrivals and
departures. Illustrative applications are bandwidth packing,
reservation systems, channel re-use in LANs, and dynamic
storage allocation. These problems are as well or better known for
intriguing open questions, which will be the focus of the
talk, than they are for strong results with substantial
generality.

** Co-authors: ** ....Far too many to name

** Short bio: ** Professor Coffman rejoined the Columbia University E.E. faculty in
the summer of 2000. During most of the period since his first
appointment at Columbia, he spent 20 years at Bell Labs in Murray
Hill, NJ. He is an IEEE Fellow (and Life Member), an ACM Fellow,
and a Distinguished Member of Technical Staff (ret.) at Bell Labs.
He is currently an editor for the Journal of Interconnection
Networks and the Journal of Algorithms. In the past, he has also
served as an editor for the Journal of the ACM, SIAM Journal of
Computing, among others. He is one of the five
system programmers who built the SDC/ARPA time-sharing system,
which became fully operational at the same time (1963) as the CTSS
system at MIT. The SDC/ARPA time-sharing system also introduced
the first computer network at that time.

** Interest areas in multiserver scheduling: **Interests are very broad.

** Papers relevant to talk: ** Click Here

** Title: ** Classical k-server queues revisited: some problems

** Abstract: ** The talk surveys both recent and `classical' studies of k-server queueing systems, and will include reference to some of the following
problem areas.

1. EXISTENCE. -- Kiefer and Wolfowitz' (1955) proof of the existence of a stationary regime for the GI/GI/k FCFS system relies on `An Essential Lemma'. In reality it hinges on a strong law of large numbers, of which variants are useful in a range of problems including k-fast servers and the tail behaviour of the work-load vector. It depends on ergodicity and not the independence assumptions of GI/GI/k (cf. Loynes' Lemma and Construction).

2. CYCLES. -- Much work on busy period analysis has relied on either regeneration points or weakened versions of them. The prime underlying result again is one of ergodicity and stationarity, and exploits ideas of point processes, albeit subsequent to Khinchin's (1955) monograph.

3. MOMENTS. -- The fact that a sub-minimally stable GI/GI/k system has finite mean delay when E(S^{3/2})< infinity for a generic service-time r.v. S is now better understood. An intermediate result concerns the moment index kappa(X) = sup{k : E(X^k)< infinity } of independent r.v.s X and Y, with kappa(min(X,Y)) > = kappa(X) + kappa(Y). Equality holds if X has a d.f. with a regularly varying tail, but the class is a little larger than this.

4. EXPONENTIAL SYSTEMS. -- Let two identical ./M/1 systems be fed by the same Poisson arrival process: what is their joint stationary distribution, and correlation of the queue sizes? Alan Brown has conjectured the structure of the d.f. sufficient for use with an expression for the stationary bivariate p.g.f.: is there any `routine' approach to circumvent the relative intractability of such simple systems?

5. HEAVY TAILS. -- The same dichotomy between minimally and sub-minimally stable systems as occurs for moment behaviour affects the asymptotic tail-behaviour of the work-load vector when the service-time d.f. is heavy-tailed.

6. SECOND-ORDER PROPERTIES. -- The stationary waiting-time sequence {W_n} in a single-server system has corr(W_0, W_n) monotonic decreasing in n, and its Hurst index is a simple function of the moment index of service times. Does monotonicity hold in GI/GI/k? And what is the Hurst index of corr(W_0,W_n): is it affected by the system being minimally stable or not?

** Short bio: **
Daryl Daley is a Senior Fellow in the Institute of Advanced Studies at
the Australian National University where he has been since 1970,
now located in the Centre for Mathematics and its Applications.
His interests are in applied probability generally, including Point
Processes (joint author with David Vere-Jones of * An Introduction
to the Theory of Point Processes *), Mathematical Epidemic Modelling
(joint author with Joe Gani of * Epidemic Modelling: An
Introduction *), Stochastic Geometry (papers with Dietrich Stoyan
and others), and Queueing Theory (including work with Les Servi on
telecommunication modelling problems and Tomasz Rolski on light-traffic,
and review papers on outputs (1976), mean waiting-times (1992) and
work-load vectors (1997)).

** Interest areas in multiserver scheduling: ** queueing problems in general.

** Papers relevant to talk: ** Click Here

** Title: ** Heavy-Traffic Approximations for Many-Server and Multi-Server Systems

** Abstract: ** We will discuss some new heavy-traffic approximations in both the
multi-server setting and the many-server setting. In the many-server
context, we will describe some formulae for how to optimally split traffic
between two servers on the basis of observed job size and on the basis of
predicted job size. These results complement recently derived formulae for
Poisson arrival streams, and are based on an assumption of
"heavy-traffic". We will then turn to discussion of heavy-traffic limit
theory in the many-server setting (in which the number of servers is
infinite or large as compared to the arrival rate, which is also assumed to
be large). We will describe a new extension of the classical Gaussian
heavy-traffic limit theory to the setting of non-stationary traffic, and we
will further discuss some related modeling implications.

** Co-authors: **Kavita Ramanan, Yuqing Sun

** Short bio: ** Peter Glynn received his Ph.D in Operations Research from Stanford
University in 1982. He then joined the faculty of the University of
Wisconsin at Madison,where he held a joint appointment between the
Industrial Engineering Department and Mathematics Research Center, and
courtesy appointments in Computer Science and Mathematics. In 1987, he
returned to Stanford, where he is now the Thomas Ford Professor of
Engineering in the Department of Management Science and Engineering. He
also has a courtesy appointment in the Department of Electrical
Engineering. He is a Fellow of the Institute of Mathematical Statistics and
has research interests in computational probability, queueing theory,
statistical inference for stochastic processes, and stochastic modeling.

** Interest areas in multiserver scheduling: ** multi-server queues, many-server queues, limit theorems,
approximations

** Title: ** New Recursive Dimensionality Reduction Technique
applied to the analysis of multiserver scheduling policies including: Cycle Stealing, Priority Queueing, Task Assignment, and Threshold Policies (Part I)

** Abstract: ** We consider common scheduling policies for
multiserver systems including cycle stealing policies, priority
queuing, task assignment policies, and threshold policies. Even these
simple policies are already very difficult to analyze because their
underlying Markov chain structure grows infinitely in more than one
dimension -- the dimension of the Markov chain is typically equal to
the number of servers. We introduce a new analysis technique which we
call * Recursive Dimensionality Reduction (RDR)* which allows us
to reduce an n-dimensionally inifinite Markov chain to a
1-dimensionally infinite Markov chain which can then be solved via
numerical methods. We apply RDR to analyze the above scheduling
policies, leading to new insights about these policies and proposals
for improved policies.

** Co-authors: ** Taka Osogami, Alan Scheller-Wolf, Mark Squillante

** Short bio: ** Mor Harchol-Balter received a Ph.D. in Computer Science from the University of California at Berkeley in December 1996 under the direction of Manuel Blum. From 1996-1999, Mor was awarded the NSF Postdoctoral Fellowship in the Mathematical Sciences at M.I.T. In the Fall of 1999, she joined CMU, and in 2001 received the McCandless Chair. Mor is also a recipient of the NSF CAREER award and the Herbert A. Simon Award for Teaching Excellence.
Mor is heavily involved in the ACM SIGMETRICS research community. Mor's work focuses on designing new scheduling/resource allocation policies for various distributed computer systems including Web servers, distributed supercomputing servers, networks of workstations, and database systems. Her work spans both analysis and implementation and emphasizes integrating measured workload distributions into the problem solution. She derives often counter-intuitive theorems in the areas of scheduling theory, queueing theory, and heavy-tailed workloads and applies these theorems in building servers with improved performance.

** Interest areas in multiserver scheduling: **
Threshold policies, analysis of scheduling policies in multiserver systems, systems with time-varying load, job scheduling in supercomputing centers, analysis of Web server farms, multi-resource modeling in databases, fairness of scheduling policies.

** Papers relevant to talk: ** Click Here

** Title: ** Performance Analysis of Scheduling Strategies in Distributed
Systems

** Abstract: ** Distributed systems pose challenging problems and
require proper scheduling in order to efficiently serve users. This
presentation summarizes recent research into the performance of
scheduling strategies on distributed systems. Topic relating to
various aspects of distributed system scheduling are included. The
technique used to evaluate the performance of scheduling strategies is
experimentation using synthetic workload simulation. Open and closed
queueing network models of distributed systems are considered.

In addition to traditional methods of load sharing and temporal job
scheduling, two other methods are presented called * epoch load
sharing* and * epoch scheduling *. Epoch load sharing evenly
distributes the load mong distributed processors and performs job
migration, but only at the end of predefined intervals. The time
interval between successive load sharing events is called an * epoch
*. In epoch scheduling, job priorities in processor queues are
recalculated at the end of epochs when queues are rearranged.

Most parallel job scheduling research assumes that parameters such as job inter-arrival times, number of tasks per job and task service demans are defined by specific distributions, but we also consider distributed systems with time varying workloads. We examine scheduling of parallel jobs which consist of independent tasks that can execute at any time on any processor, as well as gang scheduling. Finally, the impact of workload parameterics on performance metrics is examined.

** Short bio: ** Helen D. Karatza is an Associate Professor in the
Department of Informatics at the Aristotle University of Thessaloniki,
Greece. Her research interests mainly include Performance Evaluation
of Parallel and Distributed Systems, Multiprocessor Scheduling, and
Simulation. Dr. Karatza is area Editor for computer systems of the
Journal of Systems and Software (Elsevier), a member of the Editorial
Board of the Simulation Modelling Practice and Theory Journal
(Elsevier), a member of the Editorial Board of the International
Journal of Simulation: Systems, Science & Technology (the UK
Simulation Society), and Associate Editor of the Journal Simulation:
Transactions of the Society for Modeling and Simulation International
(Applications Section). She has served as a member of Program
Committees and Program Chair of many Simulation/Performance/Parallel
and Distributed Systems related International Conferences/Symposia.
Her email and web address are

** Interest areas in multiserver scheduling: **
Load balancing, load sharing, task assignment and task scheduling policies.

** Papers relevant to talk: ** Click Here

** Title: ** Heavy Traffic Limit Theorems for Real-Time Computer Systems

** Abstract: ** Real-time computer and communication systems
process tasks (or packets) that have explicit deadlines. One
important system design goal is to determine if the deadlines of those
tasks can be met under various workload conditions. Real-time
scheduling theory is one approach that addresses these problems, but
this theory is based on worst case assumptions. If the average case
utilization is much less than the worst case utilization, then
standard methods will lead to a substantial under-utilization of the
system.
Real-time queueing theory is a new methodology for studying real-time
systems using the moments of the distributions governing the arrival
and service processes rather than their worst-case bounds. It
utilizes heavy traffic queueing theory to predict the faction of tasks
that will miss their deadlines. If the workload process converges
weakly to a possibly multi-dimensional Brownian motion process, then
the lead-time process of customers (the time until their deadlines
elapse) converges to a deterministic form from which the fraction of
task lateness can be determined.
This talk will focus largely on the single node case with single and
multiple traffic flows. Various scheduling policies will be
considered including earliest deadline first, FIFO, and generalized
processor sharing (or weighted fair queueing) for the multiple flow
case. Extensions to feed-forward and acyclic networks will be mentioned.

** Co-authors: **Bogdan Doytchinov, Lukasz Kruk, Steve Shreve, and Shu-Ngai Yeung

** Short bio: ** John Lehoczky is Thomas Lord Professor of Statistics and Mathematical
Science and Dean of the College of Humanities and Social Sciences at
Carnegie Mellon. He received his Ph.D. in Statistics from Stanford
University in 1969 and joined Carnegie Mellon that year. His current
research interests are in real-time queueing theory and its
application to computer and communication systems and in computational
finance.

** Interest areas in multiserver scheduling: **Real-time systems, scheduling, heavy traffic queueing

** Papers relevant to talk: To be supplied later. **

** Title: ** An Optimal Design of the M/M/C/K Queue for Call Centers

** Abstract: ** Motivated by the performance analysis of call centers, we develop
an optimal design analysis for the M/M/C/K queueing system. The
number of servers C corresponds to the number of agents and
C+K, where K equals the number of additional waiting spaces,
corresponds to the number of telephone lines. Our goal is to find
the optimal (C,K) for this multi-server, loss and delay queueing
system by holding two key service metrics below their given target
values, for a predetermined level of offered load traffic.
Using the exact steady state blocking and delay probabilities,
we construct a new efficient algorithm for finding the optimal C and
K that satisfy a given set of service level metrics. Moreover, we develop
a faster approximate algorithm by using a steady state, heavy
traffic, asymptotic analysis. The asymptotically derived number
of agents and the number of waiting spaces in the buffer are found
by iteratively solving a fixed point equation. Moreover, each
iteration uses a generic special function which can be precomputed.
Numerical examples with parameters found in typical call centers are
used to compare both of these methods to each other and to a third ad
hoc Erlang algorithm that is widely used in practice. This is joint
work with Rodney B. Wallace of IBM and the Department of Engineering
Management & Systems Engineering of George Washington University.

** Co-authors: **Rodney B. Wallace, rodney.wallace@us.ibm.com

** Short bio: ** Professor Massey is the Edwin S. Wilsey Professor
in the Department of Operations Research and Financial Engineering, a
member of the Applied and Computational Mathematics Program, and an
associate member of the Department of Mathematics at Princeton
University. From 1981 until 2001, he was a researcher in the
Mathematical Sciences Research Center at Bell Laboratories of Lucent
Technologies. His research interests include queueing theory, applied
probability, as well as performance and pricing models for
telecommunication systems. He received his undergraduate degree in
Mathematics from Princeton University in 1977 and his Ph.D. in
Mathematics from Stanford University in 1981.

** Interest areas in multiserver scheduling: **

** Papers relevant to talk: ** Click Here

** Title: ** SIFT: a randomized algorithm for determining large flows in
the Internet

** Abstract: ** Bandwidth is allocated to a flow in today's Internet due to actions by
transport protocols at end-systems and queue management schemes at
routers. While the nature of this bandwidth allocation is not yet well
understood, to minimize the average flow delay, it would be ideal to
allocate bandwidth according to a policy like SRPT (shortest remaining
processing time). Given the heavy-tailed nature of Internet flow size
distribution, the corresponding reduction in average flow delay would be
particularly pronounced. But, this ideal is impractical: to decide which
packet to transmit next a router would now need to know the residual data
in the flow corresponding to each currently buffered packet. Even a less
complex cousin of SRPT, like SFF (Shortest Flow First), is unimplementable
since it would require a knowledge of flow sizes at routers.
In this talk, we introduce a randomized algorithm called SIFT, for
separating the packets of long and short flows. It is based on the simple
observation that a randomly sampled arriving packet is much more likely to
belong to a large flow, allowing a router to differentially allocate link
bandwidth to large and small flows. We analyze the performance of SIFT
via simulations and theory, and show that it is feasible to deploy it in
Internet routers.

** Co-authors: **Costas Psounis and Arpita Ghosh

** Short bio: ** Balaji Prabhakar is with the departments of Electrical Engineering,
Computer Science and, by courtesy, of Management Science and Engineering
at Stanford University. He is interested in network algorithms, in
scaleable methods for network performance monitoring and simulation,
in wireless (imaging) sensor networks, stochastic network theory and
information theory. He has designed algorithms for switching, routing,
bandwidth partitioning, load balancing, and web caching.

** Title: ** New Recursive Dimensionality Reduction Technique
applied to the analysis of multiserver scheduling policies including: Cycle Stealing, Priority Queueing, Task Assignment, and Threshold Policies (Part II)

** Abstract: ** We consider common scheduling policies for
multiserver systems including cycle stealing policies, priority
queuing, task assignment policies, and threshold policies. Even these
simple policies are already very difficult to analyze because their
underlying Markov chain structure grows infinitely in more than one
dimension -- the dimension of the Markov chain is typically equal to
the number of servers. We introduce a new analysis technique which we
call * Recursive Dimensionality Reduction (RDR)* which allows us
to reduce an n-dimensionally inifinite Markov chain to a
1-dimensionally infinite Markov chain which can then be solved via
numerical methods. We apply RDR to analyze the above scheduling
policies, leading to new insights about these policies and proposals
for improved policies.

** Co-authors: ** Mor Harchol-Balter, Taka Osogami, Adam Wierman, Li Zhang.

** Short bio: ** Alan Scheller-Wolf is an associate professor in Operations Management at the Graduate School of Industrial Administration of CMU.
He did his doctoral studies in Operations Research at Columbia University, where he earned M.S., M. Phil., and Ph.D. degrees. Dr. Scheller-Wolf's research focuses on stochastic processes, and how they can be used to estimate and improve the performance of manufacturing and service systems.
His earliest work dealt with the performance of
multi-server queueing systems -- such as computer or telecommunication networks. In addition to his work, Dr. Scheller-Wolf is actively pursuing
research on problems dealing with inventory systems and supply chains.
He is particularly interested in how systems operate when there are capacity
constraints, alternate sourcing or delivery options, perishable inventory,
or exchange rate factors present. His work has appeared in * Operations Research *, * Queueing Systems *, and * EJOR *, as well as at Proceedings of * ICDCS *, * SPAA * and * Sigmetrics. *
Professor Scheller-Wolf
has or is currently working on operations consulting projects Caterpillar, the American Red Cross, John Deere, Intel, and Air Products International, and serves on the editorial boards of * Management Science *, * M&SOM *, * OR Letters *, * IIE Transactions *, and * POMS * journals.

** Interest areas in multiserver scheduling: **

** Papers relevant to talk: ** Click Here

** Title: ** Fluid Modeling of BitTorrent-Like Peer-to-Peer Networks

** Abstract: ** In this talk, we will present simple models to study the
performance of BitTorrent, a second generation peer-to-peer (P2P)
file-sharing application. We will first present a fluid model of
BitTorrent and study the scalability, performance and efficiency of
file-sharing. We will then consider the built-in mechanism in BitTorrent
that is designed to prevent free-riding and study its effect on network
performance.

** Co-authors: **Dongyu Qiu

** Short bio: ** R. Srikant is an Associate Professor in the Department of Electrical
and Computer Engineering Engineering and a Research Associate Professor in
the Coordinated Science Lab at the University of Illinois. His research
interests include communication networks, stochastic processes, queueing
theory, information theory, and game theory.

** Interest areas in multiserver scheduling: **Scheduling, load-balancing,
fluid models, diffusion approximations

** Title: **Analysis of Parallel-Server Systems with Dynamic Affinity Scheduling and
Load Balancing

** Abstract: ** In this study we consider a parallel-server queueing system in which a
scheduling policy directs customers to the server where they inherently
can be served most efficiently (so-called affinity scheduling) and in
which a threshold-based scheduling policy (both sender-initiated and
receiver-initiated) manages the fundamental tradeoff between balancing the
workload among the servers and serving customers where they can be served
most efficiently (so-called load balancing, as well as resource pooling).
This queueing system arises in many application areas, such as parallel
computing environments, multi-tiered web server environments, and various
business applications. We first establish the optimality of our general
dynamic threshold-based scheduling policy within the context of fluid and
diffusion limits. We then derive a matrix-analytic analysis and
fixed-point solution of this parallel-server queueing system under fairly
general stochastic processes as input and across all traffic intensities,
obtaining explicit results in several cases. This solution is shown to be
asymptotically exact (in terms of the number of servers) under certain
conditions. The results of this analysis also provide key insights into
the fundamental probabilistic behavior of dynamic threshold-based policies
in large-scale parallel-server queueing systems. This includes numerically
determining the optimal threshold values as a function of the workload,
and demonstrating the potential for some unstable behavior under dynamic
threshold-based scheduling policies if the thresholds are selected
improperly. Lastly, based on this analysis we consider the corresponding
stochastic optimization problem of dynamically determining the threshold
values that minimize expected sojourn time as a function of time-varying
workloads.

** Co-authors: **Portions of this study represent joint work with Randolph Nelson and
Andrew Conn.

** Short bio: **
Mark S. Squillante is a Research Staff Member in the Mathematical Sciences
Department at the IBM Thomas J. Watson Research Center, Yorktown Heights,
NY. He has been an adjunct faculty member of the Department of Computer
Science at Columbia University, New York, NY, from 1991 through 1996, and
a Member of the Technical Staff at Bell Telephone Laboratories, Murray
Hill, NJ, from 1982 to 1985. He received the Ph.D. degree in computer
science from the University of Washington, Seattle, WA, in 1990. His
research interests concern the mathematical analysis, modeling and
optimization of the design and control of stochastic systems, with
applications in the areas of computer, business, call center, finance,
manufacturing and communication systems and services. Mark Squillante is
a Fellow of IEEE, and a member of ACM, AMS, IFIP W.G. 7.3, INFORMS and
SIAM. He currently serves on the editorial boards of Operations Research
and Performance Evaluation.

** Interest areas in multiserver scheduling: **Very broad interests, including all areas related to the workshop.

** Title: ** Resource Pooling and Staffing in Call Centers with Skill-Based Routing

** Abstract: ** Call centers constitute an important application of scheduling for multi-server queues.
Call centers usually handle several types of calls. To do so effectively, agents
are given special training.
However, it is often not cost-effective to have every agent be able to handle every type of call.
Thus, the agents tend to have different skills, in different combinations. Call centers are
equipped with automatic call distributors to assign calls to appropriate
agents, i.e., to perform skill-based routing (SBR).
However, it is challenging to do skill-based routing well.
Moreover, it is challenging to determine the staff requirements
in an SBR call center.
This talk will discuss recent work addressing these problems.
The main idea is to seek simplification
through resource pooling, i.e., the notion that
with (i) only a limited amount of cross training (e.g., perhaps even when agents have at most
two skills)and (ii) a reasonable scheduling policy,
the call center performance may be nearly the same as if all agents had all skills
(and scheduling was not an issue at all).
First, simulation experiments within a particular SBR framework
show that resource pooling indeed occurs.
Second, resource pooling is exploited to develop an effective algorithm to generate staffing require
ments.
The classical Erlang model is used to determine an initial estimate for the total staff needed in t
he call center.
Motivated by heavy-traffic stochastic-process limits, a square-root formula is then applied to dete
rmine initial
skill requirements within the estimated total staff. Finally,
simulations are performed in order to make improvements in the initial assignment, in order to
make the total staff requirements as small as possible, while ensuring that all performance requirem
ents are met.
Simulation experiments show that the overall procedure is remarkably effective: The required staff
with limited
cross training in a reasonable SBR framework can be nearly the same as if all agents had all skills.

** Co-authors: **Rodney B. Wallace, IBM, rodney.wallace@us.ibm.com

** Short bio: ** Ward Whitt is a Professor in the Department of Industrial Engineering and Operations Research at Columbia University in the City of New York. Ward joined the faculty at Columbia in 2002, after spending twenty-five years in research at AT&T, first at Bell Labs and then at AT&T Labs. He received an A.B. in mathematics from Dartmouth College in 1964 and a Ph.D. in operations research from Cornell University in 1969. His research has concentrated on probability theory and its application to telecommunication systems, especially involving queueing theory, stochastic processes, simulation and numerical transform inversion. He published the book, * Stochastic-Process Limits * in 2002. His current talk is based on his recent paper with the same title, co-authored with Rodney B. Wallace, based on Rodney's 2004 Ph.D. thesis, * Performance Modeling and Design of Call Centers with Skill-Based Routing *, for which Ward was co-advisor with Bill Massey and Thomas Mazzuchi.

** Interest areas in multiserver scheduling: **

** Papers relevant to talk: ** Click Here

** Title: **
Dynamic Scheduling of a Parallel Server System

** Abstract: **
We consider a parallel server queueing system consisting of
a bank of buffers for holding incoming jobs
and a bank of flexible servers for processing
these jobs.
Incoming jobs are classified into one of several different
classes (or buffers).
Jobs within a class are processed on a first-in-first-out basis,
where the processing of a given job may be performed
by any server from a given (class-dependent) subset
of the bank of servers.
The random service time of a job may depend on both its class
and the server providing the service.
Each job departs the system after receiving service from one server.
The system manager seeks to minimize
holding costs by dynamically scheduling waiting jobs to available servers.
We consider a parameter regime in which the system satisfies
both a heavy traffic and a complete resource pooling condition.
Our cost function is a mean cumulative discounted cost of
holding jobs in the system, where the (undiscounted) cost per unit
time is a linear function of normalized (with heavy traffic scaling) queue
length.
Based on an interpretation of
the analytic solution to an associated Brownian control problem (formal
heavy traffic diffusion approximation),
we propose a "continuous review"
threshold scheduling policy for use in the parallel server system.
We then show that this policy
is asymptotically
optimal in the heavy traffic limit and that the limiting cost is the same
as the optimal cost in the Brownian control problem.

** Coauthors: ** S. L. Bell

** Short bio: **
Ruth Williams is a Professor of Mathematics at
the Univeristy of California at San Diego (UCSD).
Her research interests are in probability, stochastic processes and their
applications.
She is a Fellow of the American Association for the Advancement of
Science and the Institute of Mathematical Statistics.
Ruth Williams has been a U.S.
National Science Foundation (NSF) Presidential
Young Investigator (1987-93), an Alfred P. Sloan Fellow (1988-92),
a Guggenheim Fellow (2001-2002) and was an invited speaker
at the International Congress of Mathematicians held in Berlin
in 1998.

** Interest areas in multiserver scheduling: **
Load balancing, stability and performance, fluid and diffusion limits,
task assignment policies, heavy tails.

** Papers relevant to talk: ** Click Here

** Title: ** Simulation Evaluation of Hybrid SRPT Policies

** Abstract: ** This talk describes trace-driven simulation work that compares and
evaluates different Web server scheduling strategies, such as
Processor Sharing (PS), Shortest Remaining Processing Time (SRPT),
and Fair Sojourn Protocol (FSP). We use a probe-based sampling
methodology developed in prior work to study the response time
and fairness properties of these scheduling policies.
The approach is general purpose: it can be used to determine
complete response time distributions for arbitrary arrival processes,
scheduling policies, and service time distributions.
We use the approach to evaluate two novel scheduling policies
called K-SRPT and K-Threshold SRPT. Each is a variant of SRPT.
K-SRPT is a multi-threaded version of SRPT that can have up to K jobs
in service at a time, namely the K jobs with the least remaining service
times. K-Threshold SRPT is a hybrid policy that dynamically switches
from PS to SRPT when the number of jobs in the system exceeds K, and
back to PS when the load diminishes. Fairness profile plots are used to
characterize mean slowdown and variance of slowdown for these policies.
The results show that the parameter K defines a family of policies
with smooth performance tradeoffs between SRPT and PS. The extension
of our results to multi-server systems is also discussed.

** Co-authors: ** Mingwei Gong, University of Calgary

** Short bio: **
Dr. Carey Williamson is an iCORE (Informatics Circle of Research
Excellence) Professor in the Department of Computer Science at the
University of Calgary, specializing in "Broadband Wireless Networks,
Protocols, Applications, and Performance". He also holds an NSERC
Industrial Research Chair in "Wireless Internet Traffic Modeling".
His educational background includes a B.Sc.(Honours) degree in
Computer Science from the University of Saskatchewan in 1985,
and a Ph.D. in Computer Science from Stanford University in 1991.
Dr. Williamson's research interests include Internet protocols, wireless
networks, network traffic measurement, workload characterization, network
simulation, and Web server performance.

** Interest areas in multiserver scheduling: **
Load balancing, scheduling policies, fairness, workload modeling, simulation

** Papers relevant to talk: ** Click Here

Back to Workshop home page .