Discovery
Computer Program Streamlines Complex Work Scheduling
Chemical engineers develop an algorithm that could transform scheduling
December 6, 2005
Princeton University chemical engineer Christodoulos Floudas and his
students didn't set out to invent a computer program that could
transform the way day-to-day work assignments are made across
government and industry.
Initially, in fact, Floudas, graduate student Stacy Janak, and
Martin Taylor, who is now an M.D.- Ph.D. student at Johns Hopkins, were
attempting to solve just one very specialized problem: What is the best
way for the National Science Foundation (NSF) to efficiently and fairly
assign funding proposals to its many reviewers?
"We've been doing this by hand for years," explains NSF program manager Maria Burka, "and it's very time-consuming."
The foundation receives more than 40,000 grant applications every
year, of which about 11,000 receive funding based upon reviewer
recommendations. The challenge is to assign each grant application to
the appropriate reviewers, so no one reviewer is over worked or has a
conflict that would render his or her judgment suspect.
Over the past decade, moreover, the assignment task has become
vastly more difficult, as NSF has launched large-scale,
multi-disciplinary programs in fields such as nanotechnology and
next-generation sensor development. These programs can draw hundreds of
proposals, which then have to be assigned to reviewers in many
different disciplines, says Burka. "It's just an unbelievable
undertaking."
So finally, Burka and her fellow NSF program officer, T.J. Mountziaris, turned to Floudas and his students for help.
The Princeton team came up with an algorithm that within seconds can
optimally assign 100 proposals to dozens of different reviewers. "And
frankly," says Burka, "it sometimes gives us a better solution than if
we did it by hand."
Indeed, the solution Floudas and his colleagues invented has
potential applications that extend far beyond NSF's review problem. The
researchers say the same solution could be used by hospitals to
schedule interns and nurses, by the military to deploy combat units or
by school administrations to assign teachers to classes.
The NSF review dilemma belongs to a class of mathematical problems
known as the "General Assignment Problem" or GAP, which has been the
subject of considerable research over the past 20 years. Basically, as
the number of variables in a mathematics problem increases, the
computer power required to solve the problem can increase
exponentially--making large problems potentially intractable.
For example, when Janak came up with a model for figuring out the
optimal way to assign 100 proposals to 40 reviewers, she was confronted
with more than 100,000 possibilities. The Princeton model narrowed
those options down to the best way to assign several papers to each
reviewer.
The researchers had to incorporate the following conditions into their model:
• Each reviewer had to be assigned approximately the same number of proposals.
• Each proposal had to be assigned to the same number of reviewers,
each of whom had to have a different rank.Of four reviewers, each would
hold a rank of either lead reviewer, scribe, first reviewer or second
reviewer, and each reviewer had to hold different ranks approximately
the same number of times.
• Reviewers who had a conflict of interest with a proposal could not be assigned to review it.
• Assignments had to take into account reviewer preferences for
proposals; a reviewer who expressed a strong desire to review a
particular proposal had to be given a higher reviewer rank than someone
who had expressed less.
Janak says the difficult part of developing the model was
distributing the proposals to reviewers in a fair way while taking into
account the reviewers' preferences for certain proposals over others.
To ensure that the model hewed to these restrictions, Janak had to
use an unusual set of techniques called "logic inference principles."
"It's not a methodology that a lot of people use or are aware of, but
it was something that was necessary in this case to derive our model,"
she says.
Maria Burka of the NSF began using the algorithm on an experimental basis in April. "It works beautifully," she said.
How is it that chemical engineers like Floudas and his team ended up
solving a problem that apparently has nothing to do with chemical
engineering? They specialize in optimization, which is essentially the
science of inventing mathematical formulas to make things run
efficiently. Floudas' group has applied optimization to problems in
engineering, computational chemistry and molecular biology.
Floudas, who is an associate faculty member in the Program in
Applied and Computational Mathematics and the Department of Operations
Research and Financial Engineering, has written of two textbooks on
optimization, and his research group has made fundamental contributions
to the field.
The Industrial & Engineering Chemistry Research journal
electronically published a paper by the team about the algorithm in
Nov. Princeton's Office of Technology Licensing filed a patent
application on behalf of the researchers in July.
--Teresa Riordan, Princeton University
Locations
Princeton University, New Jersey
Related Websites
The researchers' panel assignment problem solver: http://ares.princeton.edu/casl_nsf_mgap/login.php
|
