Princeton University Invention #
06-2223-1
In this work, an enhanced version of the generalized assignment problem
(GAP), called the NSF panel assignment problem, is posed. The GAP has been
the subject of considerable research over the last two decades and has many real
life applications including job scheduling, production planning, modeling of
computer and communication networks, storage space allocation, vehicle routing
and facility location problems. The GAP seeks to determine the minimum
cost assignment of n jobs to m agents so that each job is assigned
to exactly one agent subject to resource restrictions on the agents. The
GAP can be formulated as an integer programming problem where binary assignment
variables are used to indicate if an agent is to perform a job. Because
the GAP is an NP-hard problem, heuristic solutions are often necessary to solve
large-scale instances.
Researchers at Princeton University have developed a new mathematical
formulation to solve a modified version of the generalized assignment problem
(GAP), called the panel assignment problem. The mathematical formulation and
associated solution process have been thoroughly tested and implemented in a
publicly available on-line solver.
The NSF panel assignment is an enhanced version of the multi-resource
GAP. Each job has a specific number of agents assigned to it and each
agent has a lower and upper bound on the number of jobs that can be assigned to
it. In addition, preference criteria are incorporated to assign each agent
to a specific position for a job, introducing preference-based
constraints. The panel assignment problem seeks to find an assignment of
reviewers to proposals on a panel so as to optimize the sum of the preference
criteria for each reviewer on each proposal while ensuring that each reviewer is
assigned to approximately the same number of proposals. This
multi-resource and preference-constrained generalized assignment problem can be
formulated as an integer linear programming problem and can be solved to
optimality.
In this work, a mathematical model has been developed to address the NSF
panel assignment problem and some representative example problems are solved to
demonstrate the effectiveness of the proposed approach. In addition, a
web-based interface has been created to allow users to solve different instances
of the NSF panel assignment problem.
Princeton is currently seeking industrial collaborators to commercialize
this technology. Patent protection is pending.
For more information on Princeton University Invention # 06-2223-1,
please contact:
Laurie Tzodikov
Office of Technology Licensing and Intellectual
Property
Princeton University
4 New South Building
Princeton, NJ 08544-0036
(609) 258-7256
(609) 258-1159 fax
tzodikov@princeton.edu