|
 |
Business Optimization and Operations Research Workshop 2006
IBM Haifa Labs
|
May 28, 2006
Organized by the IBM Haifa Research Lab (HRL) and the Caesarea Rothschild Institute (CRI), University of Haifa, Israel
QED Q's: Quality- and Efficiency-driven Queues in Call Centers
Avishai Mandelbaum ,Technion
QED queues arise in large service systems that are both quality- and efficiency-driven (QED). Our prime example for such systems are large best-practice telephone call centers. At such centers, hundreds of agents could cater to thousands of callers per hour, with an average agents' occupancy of 95%, about half of the callers being answered immediately without delay, and waiting time of the rest being measured in seconds.
The design of call center operations, and the management of their performance, has traditionally relied on classical queueing models. However, the modern complex call center, and its emerging successor the contact center (i.e., telephone + IVR + Internet + email + chat + ...), are challenging the relevance of this conservative approach. My goal is thus to survey ongoing research that addresses some of these challenges. This covers, broadly speaking, empirically based research (queueing science) and management rules-of-thumb (e.g., square-root staffing), which are combined to create a service engineering of call centers.
Formally, our queueing models are analyzed asymptotically, as the number of servers increases indefinitely and utilization levels approach 100%, so that in the limit, the fraction of customers served immediately without wait is neither 0 (quality-driven) nor 1 (efficiency-driven), but in fact strictly between 0 and 1 (QED). The latter (0,1)-limit turns out equivalent to the square root staffing principle.
Historically, the advantages of the QED operational regime were already clear to Erlang and his co-workers at the Copenhagen Telephone Company, around 1910. But a rigorous mathematical articulation of the QED regime had to await the seminal paper by Halfin and Whitt, in 1981, which will be our theoretical starting point.
A Quasi-PTAS for Unsplittable Flow on Line and Cycle Graphs
Baruch Schieber, IBM T.J. Watson Research Center
We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on-line graphs, thereby ruling out an APX-hardness result, unless NP i contained in DTIME(2^polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cyclic graphs.
Earlier results for this problem included a polynomial time (2+epsilon)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption'') and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.
This is joint work with Nikhil Bansal, Amit Chakrabarti, and Amir Epstein.
How to Solve Large-scale Integer Programs
Martin Groetschel, ZIB, Germany
Integer or mixed-integer programs arising in practice are usually theoretically hard and often very large-scale. Nevertheless, they can often be solved to optimality or with satisfactory quality guarantees. In this tutorial, directed towards a general mathematical audience, I intend to outline the mathematical and computational machinery that is used nowadays to successfully tackle such problems.
Container Logistics Optimization
Yosi Shiloach, IBM Haifa Research Lab
The logistics of empty containers is a major task in any container shipping company. Its main objective is to provide empty containers to any export point by quantity, type, and time as required and do it with minimal cost. A medium shipping company may possess hundreds of thousands of containers, serving hundreds of export ports (many inland). The cost of empty container logistics may reach 10% of the annual turnover. The talk overviews an ongoing project indicating possible savings of 10% in empty container logistics costs.
Keynote: Designing Telecommunication Networks
Martin Groetschel, Zuse Institute Berlin, Germany
Discrete optimization problems abound in telecommunications. I will focus on the design of low cost telecommunication networks that provide sufficient capacity to serve a given demand, satisfy various technical side constraints, and survive certain failure situations. I will report on the successful solution of several instances by my telecom research group.
Distributed Constraints: Algorithms, Performance, Communication
Amnon Meisels, Ben-Gurion University
Distributed constraints satisfaction and optimization problems (DisCSPs/DisCOPs) are composed of agents, each holding its local constraints network, connected by constraints among variables of different agents. Agents assign values to variables, attempting to generate a locally consistent assignment that is also consistent with all constraints between agents. For DisCOPs, agents search for a global assignment that incurs a minimal cost. A search algorithm on DisCSP or DisCOP is thus a distributed algorithm, run by agents that communicate by sending and receiving messages.
Many real-world problems are naturally modeled by a distributed constraints network. University timetabling is composed of multiple departments that schedule their classes independently, but that are connected by constraints due to sharing of classes and classrooms. These real-world examples point to many potential uses of Distributed Constraints Reasoning (DCR) in multi-agent research. The well-defined model of DisCSPs and DisCOPs can serve as the basis for agent negotiations and search.
The talk will introduce distributed constraint satisfaction and optimization problems and describe the underlying model. The following topics will be presented (time permitting):
- Families of search algorithms on DisCSPs and DisCOPs - asynchronous backtracking (ABT), asynchronous lookahead, concurrent search
- Performance measures of distributed search algorithms on DisCSPs - concurrency measures, logical time, communication load
- Impact of message delay on algorithm efficiency
- Ordering heuristics - for sequential algorithms, reordering asynchronous search
Applications of Combinatorial Optimization in the Steel Industry
Andrew J Davenport, IBM T.J. Watson Research Center
The complexity of production planning and scheduling for steel manufacturing is higher than in many other industries. Furthermore, companies that compete by offering a wider variety of product types and customization face increased complexity in their production planning and scheduling processes. Off-the-shelf applications cannot cope with this complexity. IBM Research has been involved in a number of projects involving the application of a wide range of combinatorial optimization technologies to solve complex planning and scheduling problems with some of the world's largest and most innovative steel manufacturers. In this presentation, we will give an overview of some of the problems we have solved and the techniques we have used to solve them.
Human Resources Matching by Constraint Satisfaction
Yehuda Naveh, IBM Haifa Research Lab
Matching highly skilled human resources to available positions is a high-stakes task that requires careful considerations by resource managers. A wrong decision may result in significant loss of value due to understaffing of positions, under/over qualifications of assigned personnel, and decreased retention times. On the other hand, dealing with pools of hundreds of jobs and resources in a dynamic market creates a pressure for fast decisions. I will present a resource matching technology based on constraint satisfaction that is designed to bridge the gap between these two observations. The technology successfully deals with the complex constraints encountered in this field, and provides near-optimal matches taking into account all resources and positions in a pool. I will describe usages by IBM's Global Services organizations, where a large number of IT service and consultation employees are considered when forming project teams assigned to customers' businesses.
| |
|
|
