Using genetic algorithms, Moody's Investors Services schedules its help-desk troubleshooters and increases its efficiency
Mark Clarkson
It takes an expert and busy help desk to resolve the computer problems of the 1100 users at Moody's Investors Services, a bond-rating agency based in New York City that analyzes the credit risk associated with securities. Like any large organization today, Moody's has a lot of computers--everything from mainframes running proprietary analytical software to PCs running plain old Microsoft Word. To support this computer infrastructure and its users, Moody's technology department runs a help desk.
Computer users at Moody's call the help desk with problems ranging from the mechanical (e.g., ``My PC won't boot'' or ``My monitor went out'') to the
mundane (e.g., ``I can't get Harvard Graphics to print my charts''). If a help-desk representative can't resolve a problem over the phone, he or she writes up a ticket, and the user gets a visit from a TSA (technical-support analyst), who tries to solve the problem in person.
And therein lay Moody's help-desk problem--scheduling hundreds of jobs for dozens of staff troubleshooters.
The Trouble with Schedules
``The problem,'' says
Roger Stein
, senior analyst at Moody's Quantitative Analytics Group, ``was how to efficiently schedule and route these requests for visitation [by a TSA] so that the right people end up with the right tasks, which are then executed in the right order. You don't want a TSA to spend a lot of time adjusting the colors on one person's monitor when somebody else's hard disk has crashed.''
To schedule repairs efficiently, you must contend with the almost paradoxical arithmetic of organizational downtime. For instance, take two
hardware problems of equal severity and priority--in both cases, the user is unable to do his or her work until the problem is fixed. One problem will take 5 minutes for a TSA to fix; the other will take 5 hours. Which one do you schedule first? From a time-expenditure standpoint, it doesn't matter. But from the standpoint of time lost to the organization, there is a big difference indeed.
Consider this: If you make the 5-minute repair first, both users wait 5 minutes, and then one user waits an additional 5 hours. Total time lost to the organization: 5 hours, 10 minutes. But if you make the 5-hour repair first, both users wait 5 hours, and one waits an additional 5 minutes; the total time lost swells to 10 hours, 5 minutes.
But what if the longer task has a far-higher priority? What if one of the users has already been waiting for three days? ``Things get pretty complicated when you're talking about tasks of varying priority and varying durations,'' Stein says.
Genetic Algorithms
A quick glance out the window, or even at your own hands, should convince you that nature is the uncontested master of evolving solutions to complicated problems. All of nature's answers are phrased in the form of genes. In nature, genes express themselves as such things as people, slime molds, or oak trees. But back in the 1970s, scientist John Holland realized that, with a little cleverness, all sorts of things--from airplane propellers to mathematical proofs--could be described in genetic form. He called his approach the genetic algorithm, or GA.
To get a better propeller or proof using a GA, all you have to do is establish a colony of them and encourage them to breed. You periodically select the best individuals to use as the parents for a new generation. It's a lot like breeding livestock, except it's usually--but not always--conducted on a computer.
The almost magical thing about GAs is that they have no idea what they are doing. They are capable of finding elegant solutio
ns to complicated problems, but there's no intelligence behind the way they formulate those solutions; it's pure, blind sex.
And that's just what Stein likes about them for Moody's problem: ``If we were going to design a traditional expert system, we would spend hours and hours of very expensive time with help-desk personnel, figuring out the rules for scheduling the help desk,'' he says.
Instead, the help desk's new scheduling system, dubbed SOGA (Schedule Optimizing Genetic Algorithm), breeds efficient schedules using the GA. ``The nice thing about genetic algorithms is that you don't have to tell them how to solve problems,'' he says. ``You tell them what you want done and let them percolate away for a while, and they'll come up with some pretty-good solutions to your problem. They're totally unaware of how they did it, but that's irrelevant to finding a solution.''
Stein usually applies his analytic skills to Moody's fiscal concerns and to intellectual exercises in mathematics. As one
such exercise, Stein, along with friend and colleague Vasant Dhar of New York University, had already designed and built a prototype of SOGA. When the prototype was finished and they were writing up a paper outlining its performance, it occurred to Stein that SOGA might be useful for scheduling tickets for Moody's own help desk.
Because Stein and Dhar had already implemented a prototype system in DOS, the implementation went fairly quickly and was up and running in about two months. The production version of SOGA that runs on Moody's help desk is written in Microsoft's Visual C++ and runs under Windows. The majority of the code was written by one programmer. The system schedules tasks for the 12 TSAs and the approximately 20 second-line support personnel who assist Moody's more-than-1000 computer users.
A Close-Up on the Genes
In SOGA, schedules are represented by chromosomes made up of many genes. Each gene is a ticket--a problem received by the help desk, needing to be
resolved. The system starts with a population of completely random schedules. As the GA runs and the schedules ``breed,'' the genes are shuffled around from place to place, and eventually efficient schedules are produced.
SOGA uses a pair of GAs to produce its schedules. The first one breeds a master schedule made up of all the unassigned tickets. The second one then optimizes the schedules of individual TSAs.
Here's how it works. When a problem call comes in, a help-desk representative creates a ticket entry in the help-desk data-base. This ticket contains information on the problem, including where the hardware is within the building and the general category of the failure (e.g., ``PC fails with diagnostics'' or ``Modem at desk fails'').
The trouble ticket doesn't usually have the name of any particular TSA on it. Whenever possible, SOGA is allowed to recommend a technician for the job. This is because the more latitude SOGA is allowed, the more efficiently it does its job.
Every
10 minutes or so, SOGA reaches into the help-desk database and pulls out copies of all unassigned tickets. Each of these tickets becomes one gene in the chromosomes that SOGA builds.
Suppose there are seven tasks to be completed: A, B, C, D, E, F, and G. SOGA begins by constructing a population of ``chromosomes'' (i.e., schedules) made up of these genes. Initially, the individual genes appear in a different, random order in each chromosome; for example, ACDFGEB, CGBDAEF, BGDAECF, and so forth. Next, the resulting chromosomes are broken apart again into their component tickets.
All of Moody's many TSAs have different skill sets. Some specialize in software problems, for example, and others concentrate on hardware. On any given day, a particular TSA might be on vacation, out sick, or busy. The problem category on each ticket is matched against a database of TSAs and their skills, and tickets are assigned to a TSA who is qualified and available to handle the particular task. When every task in a c
hromosome has been assigned, it is converted into a potential schedule.
Each of these resulting schedules is then evaluated for fitness to determine how efficient it is and how happy it's likely to keep the computer users. The best few schedules are kept as ``parents'' for the next generation; the rest are discarded. The new parent schedules are used to produce the next generation. There is no question about which genes the offspring receive from their parents; the only variable in this system is the order in which the genes appear. The processes used to create a new schedule from two parents are shown in the figure ``Genetics at Work in the GA.''
Each of this new crop of schedules is submitted to the same fitness test, which yields a new set of parents, and the entire process is repeated until either a given number of generations has transpired or the solutions converge--that is, when additional breeding no longer produces offspring that are superior to their parents.
An Imperfect
World
It's important to take note that, at least in Moody's case, the GA does not produce a perfect schedule. There are other approaches that can guarantee a mathematically optimal schedule, but they don't guarantee it in any particular time frame. A perfect schedule might take two weeks to compute.
Although SOGA doesn't produce perfect schedules, it does produce good ones, and it spits them out every 10 minutes. ``In an academic environment,'' says Stein, ``you need an exact solution. But in a business domain, it's different. If you have a system that doesn't give you perfectly optimal schedules, you are often not concerned--you just want very good schedules.''
Maybe, he muses, with a lot of hard work somebody could figure out a more efficient schedule, ``but what's the cost of that?,'' he asks. And because schedules are based on the average time needed to complete a given task, there's no guarantee that a perfect schedule would be any more efficient. And besides, says Stein, i
t's not enough to schedule all the right tasks at the right time; you've got to keep the users happy, too.
Warm Fuzzies
But what does happy mean? It's a hard concept to define precisely, but the real world is full of concepts that are hard to define: hot, fast, long, and heavy, to name a few (e.g., Is it hot outside? Is this a fast computer? Is this a hot computer?). The answer to this dilemma is fuzzy logic, which deals with such hard-to-define terms and allows things to be, say, somewhat heavy or absolutely not empty.
SOGA uses fuzzy logic to define the sketchy idea of user satisfaction in terms of how long a user has been waiting and how much longer he or she must continue to wait before a problem is resolved. In SOGA's framework, a user's satisfaction can fall anywhere on a scale from 1 to 0, where 1 means totally satisfied and 0 is totally dissatisfied. The initial priority given to a task at Moody's is divided or modified by the user's satisfaction so that, as the us
er becomes less happy, the problem's priority climbs higher. Thus, if a user's satisfaction drops to 0.5, a ticket's priority doubles; should his or her satisfaction drop to 0.1, the ticket's priority increases by an order of magnitude.
As time passes and a Moody's user becomes less satisfied, even tasks that started out with low priorities will rise in the queue. A low-priority software update, for example, can't be put off forever by higher-priority repairs.
A Culture Change
``I was surprised,'' admits Rich Nelson, Moody's director of technical support, ``at the degree to which we fell in love with the visual part of the system.'' With a terminal program that runs under Windows, the help-desk manager can monitor tickets as they arrive at the help desk, are routed to the TSAs, and are eventually resolved.
Each TSA is represented by an icon at the top of the screen, with a pile of colored tickets beneath it. Each ticket's length represents the average resolution tim
e for that type of problem. At the top of the pile, in gray, are tickets assigned to that individual. The border of the ticket is colored blue, pink, or red. The hotter the color, the hotter the job's priority (i.e., red-bordered tickets are the hottest, followed by pink, then blue). (See the screen
Moody's TSAs
).
Underneath these tickets are any currently unassigned tickets that SOGA is recommending for that TSA. Again, a ticket's color, ranging from blue to red, indicates its priority. Clicking on a ticket reveals further details about the job.
Although help-desk personnel never lost many tickets before SOGA's introduction, they now lose even fewer. ``One of the surprise benefits of this system,'' says Nelson, ``is the way it lights up the tickets and puts them `on stage.' We can find tickets now that in the old days would have been dropped, or disappeared, or gone into the `Twilight Zone.' [SOGA] allows us to find a problem 20 minutes after the ticket is created rather th
an letting it twitch in the wind for weeks.''
Still, the transition to the new system caused some discomfort. At first, some people resisted the idea of taking orders from a computer. To deal with this, TSAs were reminded that although the system recommends that certain individuals accept particular tasks, it doesn't actually assign the jobs. A TSA can accept a ticket, refuse it, throw it back to the help desk, or even assign it to another TSA who is more qualified for the job. ``We did not want to create a system that jammed tickets down people's throats,'' says Nelson.
Some people were uncomfortable with the way in which unassigned tickets jump around in the system. SOGA runs every 10 minutes, building new schedules for all unassigned tasks. A unassigned ticket that appears in one TSA's queue might have appeared in someone else's queue 10 minutes ago, and it might move to yet another queue in another 10 minutes. Once a TSA has accepted a ticket, it is assigned to him or her and stays in that q
ueue, but unassigned tasks might be rerouted at any time. (See the screen
TSA Schedules
).
There was also some degree of concern that the new system represented Big Brother, watching every move that the technical-support staff made. But, says Nelson, ``there's nothing that this system tells me that I couldn't find out with a report in the old system. We just want to get tickets out there faster and to make people more productive.''
Just a Little Too Perfect
The efficiency with which SOGA performs its scheduling has led to some unanticipated problems. ``Some concerns have surfaced recently,'' admits Nelson, ``about the way the system doles out assignments.'' With the old system, TSAs with free time could browse through paper tickets at the help desk, looking for problems they wanted to learn how to solve. But since SOGA recommends tasks only to technicians who are already qualified to perform them, people became worried that they would lose the opportunity
to learn new skills.
To remedy this problem, ``we showed them how to go into the system and `poach' tickets from other people's queues,'' explains Nelson, ``and how to look at all the tickets throughout the system and find those that interest them.'' Now TSAs can once again stretch and grow. Nelson notes that working only on the problems that you already know how to solve ``gets pretty dull and depressing.''
By placing networked PCs throughout the building, Moody's allows the TSAs to spend more time with their customers. Instead of having to return to the help desk on the seventh floor, they can simply check in with the nearest networked PC for more assignments. Also, with the new system, everybody on the technical-support staff--not just management--can see when things are going well and when they aren't and can take appropriate steps much sooner. ``This system,'' says Nelson, ``gives people a tool to verify that whatever they are working on right now is really the most important problem.''
With people's initial fears dispelled and the inevitable shakedown bugs swatted, Moody's SOGA is now being expanded to bring more technical-support personnel on-line. SOGA first came on-line supporting six TSAs. It now builds schedules for about 30 TSAs and is still growing. More technical-support groups are being added all the time.
So what's next? ``Probably a bigger machine,'' Nelson says.
Scheduling: Think Of It As Evolution In Action
Moody's Help Desk
-- It supports about 1000 PCs and 1000 computer users on 11 floors.
-- Four people answer phones, 15 people are TSAs, and 40 to 50 people
work as second-line support personnel.
-- About 120 phone calls are received on an average day.
-- About 40 problems are resolved over the phone each day.
Supported Systems
-- Unix boxes
-- VAXes
-- Mainframes
-- IBM-compatible PCs
-- Macintoshes
-- All systems are networked together
SOGA System Highlights
-- Genetic algorithms create and refine schedules for trouble
tickets.
-- Schedules are recomputed every 10 minutes.
-- Unassigned tickets cannot drop out of sight.
-- Fuzzy logic helps to model user satisfaction.
-- Jobs are assigned according to individual TSA skills.
-- A graphical interface quickly and concisely shows the current status of
all tickets, whether they're scheduled or not.
-- For each ticket represented on-screen, the size of its icon represents
the average resolution time, and its border color indicates job priority.
-- The longer a job sits unresolved, the more its priority rises.
-- Schedules can be consulted from anywhere on the network.
Lessons Learned
-- People resist being scheduled by a machine. Build in some flexibility
and allow a certain amount of human selectivity.
-- You don't need to create perfect schedules; ``good enough'' is good enough.
-- Scheduling matters. Waiting unnecessary hours for a 5-minute fix
wastes everyone's time.
Genetics at Work in the GA
illustration_link (42 Kbytes)
(1) The proud parents
(2) Reproduction starts
(3) A schedule is born
(4) Mutation occurs
To produce children that differ from their parents, SOGA performs two different operations: crossover and mutation. In a crossover, genetic information is copied from one parent's chromosome to the child's chromosome up to a certain point. After that crossover point, all genetic information comes from the other parent. In SOGA, all genes from both parents are carried over to the child schedule. Only the order of the genes is affected.
For example, suppose the two fittest parent schedules, or chromosomes, are CGBDAEF and FBGDECA--called Dad and Mom, respectively, as shown in (1). They unite through a crossover operation to create a new child schedule, Junior, which inherits the order of specific genes from both parents.
In (2), a set of genes--in this case, the first three--are chosen from the Dad schedule. These same genes are selected in the Mom schedule; note that they appear in different places and in a different order within Mom, because Mom and Dad are different.
To create a new schedule, you start with the Mom schedule and then rearrange the order--which starts as B, G, C--of her three selected genes so that they match the order of Dad's first three genes--C, G, B. Note that you do not change the relative position of any other genes (3). The result is Junior, a new schedule that has characteristics of both its parents.
But there's more to evolution than just sexual reproduction. There's also mutation, as shown in (4). Here, you create a mutation by selecting any two genes at random within Junior--G and A--and swapping them to create a new, mutant schedule.
illustration_link (39 Kbytes)
Schedules for Moody's TSAs are presented in the graphical format shown above. Each TSA is represented by a separate column; beneath the TSA's initials appear assigned trouble tickets, as well as those that have been only tentatively scheduled.
illustration_link (52 Kbytes)
From any terminal attached to Moody's network, TSAs can use the screen shown at right to review their own schedules or look into other TSAs' schedules and ``poach'' jobs from their queues.
photo_link (15 Kbytes)
Mark Clarkson is a freelance science writer living in Wichita, Kansas. His new book, Windows Hotho
use (Addison-Wesley, 1995), explores genetic algorithms and other artificial-life topics. You can contact him on the Internet or BIX at
mclarkson@bix.com
.
Moody's Evolving Help Desk
