Breakthrough streamlines complex work assignments

Nov 16, 2005

Christodoulos Floudas and his students Stacy Janak and Martin Taylor have invented a mathematical formula that may transform the way that day-to-day work assignments are made across government and industry.

They didn't set out to accomplish such a broad goal. Initially they were simply attempting to solve a seemingly obscure problem: figuring out the best way for the National Science Foundation to efficiently and fairly assign funding proposals for review to its many reviewers.

NSF program managers Maria Burka and T.J. Mountziaris asked Floudas, a professor of chemical engineering at Princeton, to do just that. What he, Janak (a fifth-year graduate student) and Taylor (now an M.D./Ph.D. student at Johns Hopkins) came up with is an algorithm that within seconds can optimally assign 100 proposals to dozens of different reviewers.

NSF receives more than 40,000 grant applications every year, of which about one-quarter receive funding based upon recommendations made by reviewers. Assigning applications to appropriate reviewers in a fair way, so that individual reviewers are not inundated, is a huge headache.

"It's very time consuming," said Burka. "We've been doing it by hand for years. But this is much more efficient. And frankly sometimes it gives us a better solution than if we did it by hand."

The solution that Floudas and his colleagues invented has potentially broad applications that extend far beyond the NSF 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 number of potential applications is mind-boggling," said Floudas.

This month, the journal Industrial & Engineering Chemistry Research electronically published a paper by the team. Princeton's Office of Technology Licensing filed a patent application on behalf of the researchers in July.

The NSF 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 last 20 years.

The GAP is referred to as being an NP-hard problem. In lay terms, this means that as the number of variables in a mathematical 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 possible ways to do that. The Princeton model narrowed down those possibilities to the best way to assign several papers to each reviewer.

How is it that chemical engineers like Floudas and his team ended up solving a problem that doesn't have anything to do with chemical engineering?

They specialize in optimization, a field that has burgeoned since World War II and which is essentially the science of inventing mathematical formulas to make things run efficiently. The Floudas group has applied optimization to problems in engineering, computational chemistry and molecular biology.

Floudas is the author of two textbooks on optimization and his research group has made fundamental contributions to two branches of the field which are known as deterministic global optimization and nonlinear mixed-integer optimization. Floudas is associated faculty member in the Program in Applied and Computational Mathematics and the Department of Operations Research and Financial Engineering.

The researchers had to incorporate the following conditions into their model:

-- Each reviewer had to be assigned to 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; for example with 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 that proposal.
-- 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 interest in the proposal.

Janak said that 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 said.

Maria Burka of the NSF began using the algorithm on an experimental basis in April. "It works beautifully," she said.

Source: Princeton University

Explore further: Report shines spotlight on incapacitating chemical agent weapons

add to favorites email to friend print save as pdf

Related Stories

MasterCard, Zwipe announce fingerprint-sensor card

3 hours ago

On Friday, MasterCard and Oslo, Norway-based Zwipe announced the launch of a contactless payment card featuring an integrated fingerprint sensor. Say goodbye to PINs. This card, they said, is the world's ...

Plastic nanoparticles also harm freshwater organisms

4 hours ago

Organisms can be negatively affected by plastic nanoparticles, not just in the seas and oceans but in freshwater bodies too. These particles slow the growth of algae, cause deformities in water fleas and impede communication ...

Atomic trigger shatters mystery of how glass deforms

4 hours ago

Throw a rock through a window made of silica glass, and the brittle, insulating oxide pane shatters. But whack a golf ball with a club made of metallic glass—a resilient conductor that looks like metal—and the glass not ...

US company sells out of Ebola toys

13 hours ago

They might look tasteless, but satisfied customers dub them cute and adorable. Ebola-themed toys have proved such a hit that one US-based company has sold out.

UN biodiversity meet commits to double funding

13 hours ago

A UN conference on preserving the earth's dwindling resources wrapped up Friday with governments making a firm commitment to double biodiversity aid to developing countries by 2015.

Recommended for you

Insider trading study shows stronger enforcement

56 minutes ago

The first major study of the enforcement of Australia's insider trading laws has shown the number of insider trading cases brought by the Australian Securities and Investment Commission (ASIC) is increasing, ...

Study examines effects of credentialing, personalization

1 hour ago

Chris Gamrat, a doctoral student in learning, design and technology, recently had his study—completed alongside Heather Zimmerman, associate professor of education; Jaclyn Dudek, a doctoral student studying learning, design ...

New evidence on Neanderthal mixing

1 hour ago

New research on a 45,000-year-old Siberian thighbone has narrowed the window of time when humans and Neanderthals interbred to between 50,000 and 60,000 years ago, and has shown that modern humans reached ...

User comments : 0