National Science Foundation awards grants to Prof. Mark E. Lewis

Professor Mark Lewis works with equal facility on both theory and applications.  For example, he studies and teaches about the design and behavior of queues, or waiting lines,* and also develops a theory for this and other problems that are applicable well beyond bank lines.

One particular area of application of queueing theory has been experienced by anyone who calls into a customer service center and is told that 'all our agents are busy serving other customers.'   Most customer service organizations, including those that outsource their phone banks to call center companies, prefer not to have callers wait very long for service. Assuring that long waits will be rare requires careful analysis of the system, typically using software that predicts necessary staffing or other resource allocation to improve responsiveness.

Call Center Grant

In 2008 the National Science Foundation awarded a grant to Mark Lewis to study the impact of three possible alterations in the routing of calls.  One would upgrade lower priority customers (in a system that divides customers into priority classes) if they have already spent too much time in the system.  Another would improve the treatment of the "largely ignored phenomenon of customer reneging (also called abandonment)."   And a third would encourage some customers to try again later rather than wait, in order to temporarily reduce demand.  These variations challenge the scope of existing theory, so Lewis expects the research to break new ground. 

Markov Decision Processes Grant

In a second grant awarded by the National Science Foundation in 2009, Lewis and E.A. Feinberg of Stony Brook University propose to expand theoretical results about a broader class of processes that encompasses call center control, inventory management, and revenue management.  They point out that "the methods to be developed in this project stand to fill important gaps left in the literature," gaps "that are becoming increasingly more crucial to applications."  

The processes covered by the second grant are known as Markov decision processes.  The theory of such processes (also known as stochastic dynamic programming) starts with a description of the possible states of a system, the transition probabilities of moving among the states, the actions available to the decision-maker that influence movement between states, and the costs and returns that are a consequence of the actions.   The objective is to determine the optimal action to be taken for each state and at all points in time, typically summarized (as a mathematical function) in a 'policy.'  The model's characterization captures the elements of many practical decision-making situations.

The grantees propose to develop methods to analyze and find optimal policies for Markov decision processes that move in discrete time steps but have no a priori bound on the states and/or actions, and for processes that move continuously in time and may not even have a priori bounds how frequently on the transitions can occur.   

While this newer grant, unlike the earlier one about call centers, is largely intended to extend the theory, Lewis intends to apply the results to practical problems as diverse as determining how much cash a financial firm must have on hand, how prices should be set and inventory maintained at highly dynamic internet sales sites, and how airlines manage the inventory and pricing of seats in order to maximize revenue.  Although such problems would seem to have bounded states and actions, it may be impractical to determine the bound - for example, Stanford University enlists a virtually inexhaustible amount of computing capacity from home users around the world for protein folding.

MITRE award

"I like to work on a mix of theoretical and applied problems," Lewis says. "One challenges me technically, while the other keeps me grounded."  With respect to the latter category, he recently was awarded funding by the MITRE Corporation to study a problem that would arise in the event of a large-scale catastrophic event.  In the case of an event that impacts multiple municipalities, each controlling separate emergency response resources, MITRE has asked how the resources should be reallocated under central control over time. 

"From a modeling perspective this is interesting since one has to analyze how many resources are available for reallocation, where they should be allocated and what is the potential cost," Lewis says.  "Moreover, this has to be done several times over the planning horizon, and with regard to both previous and future decisions."  Lewis first came into contact with MITRE as an advisor to a series of Master of Engineering projects for the not-for-profit organization chartered to work in the public interest.

This award and the grants are being used to support Ph.D. students, summer research, travel, and dissemination of research results. 

Lewis joined ORIE in 2005 after teaching Industrial and Operations Engineering at the University of Michigan.  He is a graduate of Eckerd College, the Florida State University and the Georgia Institute of Technology. 

  * In the U.S., where people stand on waiting lines, the discipline is known as queueing theory; in Britain, where people stand in queues, it is known as waiting line theory.