Computer Program Streamlines Complex Work Scheduling

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, multidisciplinary 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 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 November. Princeton's Office of Technology Licensing filed a patent application on behalf of the researchers in July.

--Teresa Riordan, Princeton University