SOFTWARE REVIEW
Assigning Student Project Teams with SPAT
by Scott E. Sampson, Brigham Young University
Many of us use team projects for
our courses, particularly at the masters level. Team projects have
many advantages such as developing teamwork skills, decreasing the
amount of work we have to grade, and allowing students the
opportunity to focus on projects they are interested in. So, we
attempt to organize project teams that somehow consider student
preferences while meeting various team composition requirements
(such as a specific number of students per team and specific types
of students on each team).
Of course, being the analytical decision scientists that we are, we
put together a spreadsheet or database tool to help us solve this
project assignment problem. Some of us code up integer programs or
develop heuristic solution techniques. A few of us have even
written papers about our solution techniques to such problems.
After publishing a few papers on a related assignment problem,
people said to me, "This is quite usefulžyou should market it." I
never did. It seems to me that there is a big difference between an
algorithm that solves a useful problem, and one that is easy enough
to actually be used by the general population. My procedure has
been used because I sat down and trained the people at the
institution where I developed it (The Darden Graduate School of
Business). It is quite a different thing to develop software that
can be used without developer training. Indeed, the procedure
"packaging" effort can be many times greater than the algorithm
development effort.
Well, Art Hill is perhaps more ambitious than I am. In 1983 he
published a paper with David Naumann and Norman Chervany titled
"SCAT and SPAT: Large-scale Computer-based Optimization Systems for
the Personnel Assignment Problem" (Hill, 1983). The paper described
a network-based solution technique for the project assignment
problem described above. Their method was useful. But, who of us
would be willing to code up the network solution procedure, then
gather all of the project preference information from students?
Well, Art has done the coding, and created a relatively easy to use
Windows application called SPAT (Student Project Assignment
Technique). As for gathering the information from students, he has
made it quite easy. The information can be entered manually or
pasted from a spreadsheet. Or, students can e-mail their project
selections which can be pasted into the data base.
Perhaps the best way to describe how SPAT works is to tell how it
could be used to solve an actual problem. I teach an elective
course that currently has 20 students. During the semester there
are four guest speakers. It would have been good for me to schedule
five students to go to lunch with each of the guest speakers. Five
of my students are MBA students, and the rest are undergraduates.
I would like to have at least one MBA student at lunch with each
guest speaker. I would also like the students to meet with speakers
from industries they are most interested in. Here is how I solved
the problem with SPAT.
First, I called up a spreadsheet that had the students names and
whether each was an MBA or an undergraduate. In SPAT, I defined two
respective ``concentrations,'' MBA and UND. Then, I cut and pasted
my student list spreadsheet into SPAT (as a block, not student by
student). Next, I took a list of my guest speakers and pasted it
into SPAT (again, as a block). I then designated that each guest
speaker (i.e. "project") needed to have at least one student from
the MBA "concentration." Finally, I had to tell SPAT what the
student preferences were. Since I did not have actual student
preferences for speakers, I simply created hypothetical data in a
spreadsheet, and pasted it into SPAT. (These preferences are in the
form of rankings, with 1 as the most desirable speaker and 4 as the
least.) Again, in an actual situation I might have had the students
e-mail their rankings to me.
Once this data is entered, SPAT has a feature that checks or
corrects ranking problems, such as a student that uses the same
rank value more than once. Then, it is simply a matter of clicking
on the "optimize" button for SPAT to come up with a solution. SPAT
has the ability to print out all types of reports by student, by
project, etc. The solution appeared to be optimal, as we would
expect from a network formulation. (I set up the problem as a
spreadsheet integer program and got the same solution as SPAT.) My
20 student problem was not too difficult for SPAT. I seem to recall
that the solution time of the network problem only grows as a
polynomial function of problem size. Therefore, I would expect that
SPAT would produce quick solutions even for larger problems (such
as assigning 250 MBA students to study groups).
The program did have a few problems running on my system, but Art
was quick to make fixes and send me updated files. One particularly
interesting advancement he is working on is the ability to collect
student rankings of projects over the World Wide Web. Students
would simply call up a Web page that contains fields for entering
information. Then, presumably, the data could be automatically
posted to the SPAT data files, further avoiding manual entry errors
and effort.
The development of SPAT is a good example of the practical
application of decision science tools.
Administrators in business
schools and other professional schools often need to assign
students to projects for field projects or other educational
experiences. Ask any administrator who has ever tried to make these
assignments and they will agree that it is a very difficult
problemžthe process is complex, takes a long time, and is full of
potential for conflict.
In order to address this problem, we developed a computer program
to help administrators make these assignments. We call the program
"SPAT," which stands for the Student-Project Assignment Technique.
The name "SPAT" is appropriate because SPAT helps us to avoid
conflicts ("spats") in assigning students to projects.
SPAT is a Windows program designed to help project administrators
quickly make optimal, equitable, and defensible assignments of
students to project teams. SPAT maximizes overall student happiness
while satisfying all of the problem constraints.
SPAT tries to maximize "happiness" (satisfaction) for the students
as a whole by minimizing the sum of the ranks for all project
assignments.
In order to make this a practical solution, we impose the following
constraints:
Given that SPAT minimizes the sum of the ranks across all students,
we run the optimization several times in order to find the solution
that has the minimum value for the "maximum rank parameter" and
still satisfies all of the constraints. In this way, we first
minimize the worst ranking that we assignžand then minimize the sum
of the ranks across all of the students.
Students can be assured that the SPAT solution is the global
optimal solutionžabsolutely no better solution can be found.
Students can also be assured that SPAT is fair in that all students
are given the same level of importance in the mathematical
procedure.
A: SPAT uses an iterative primal simplex procedure that brings the
variable into the basis that has the highest c(j)-z(j) with ties
broken lexicographically. In other words, the program breaks žtiesž
based on a complex mathematical procedure with no human
intervention and no human bias.
Q: How does SPAT decide which student to assign to a project?
A: SPAT essentially evaluates ALL possible assignments and selects
the best one. It does this with a network optimization approach to
find the mathematically optimal solution to minimize the sum of the
ranks across all students subject to the constraints that all
concentration requirements are met and that no student is assigned
a rank larger than the maximum rank parameter.
Q: How can I beat the system...in other words, what games should I
play in order to try to get my best desired outcome?
A: Any games that you might try are likely to backfire. The best
policy is to be honest about your rankings. SPAT will do the best
it possibly can to try to assign students to the lowest possible
ranking. What you CAN do it to make sure that you are careful in
giving us your rank datažparticularly for your first 10 or so
projects.
Q: What if I rank all of the projects as number 1...or miss some
rankings...or just don't bother to rank anything after my 10th
rank? Is there ANY way that I can trick the system?
A: SPAT will check and fix the rank data for students. When SPAT
fixes rank data, it first increases all duplicate ranks by one. For
example, the second occurrence of rank 1 is renumbered rank 2. SPAT
then decreases all ranks to fill in missing ranks. For example, if
rank 2 is missing, then all ranks above 2 are decreased by one.
Finally, SPAT randomly assigns ranks to the missing ranks at the
end of the list. If you don't care about the rankings after rank
10, then only rank the first 10 and SPAT will fill in the remaining
ranks with random ranks higher than number 10. No, there is NO WAY
that you can trick the system.
A: No, usually less than a minute. The computing time depends, of
course, on how many students and projects you havežand the speed of
your computer.
Q: Do I have to know anything about operations research to use
SPAT?
A: Nope.
Q: Isn't it a lot of work to type all of this data into SPAT?
A: Do NOT type that data! SPAT allows you to copy and paste nearly
all of data from other programs. Lets say you have an Excel
spreadsheet with all of the student data (names, phone numbers, and
concentrations) organized in three adjacent columns in the
spreadsheet. Select the data by pointing to the top left of the
data and then dragging the mouse down to the bottom right of the
data. Then click copy from the edit menu. Then move back over into
SPAT by hitting alt and tab until you find SPAT. Then go to SPAT's
"edit" menu to click "paste student data" and then click "ok."
Simple! You can do the same thing with lists of ranks for all
students, ranks for one student, list of projects and the list of
legal concentrations.
Q: What if I need to impose a special constraint such as...
A: Easy. For constraints such as the first one, just have the
student rank the project with a very large rank (low priority) and
it is almost certain that it will not appear in the solution. For
constraints such as the second one, you can have the student rank
Company X as number 1 and rank all other projects with a very large
number. (Be sure to not have SPAT automatically fix the ranks for
this student!)
Q: What if I need to change the "optimized" solution to deal with
constraints that SPAT cannot handle such as...
A: You can always edit the student data after the optimization has
been run to change assignments for one or more students. You can
use SPAT to get you a nearly optimal solution, and then manually
re-assign students to create a final solution that is closer to
meeting all of your constraints.
Q: How does SPAT store data?
A: We are just using simple flat files to store all of the SPAT
data. While this is clearly not a very sophisticated approach, it
is helpful when you need to edit the data and/or use it in another
application. These files can be edited by any word processoržjust
be sure to save it as a text file.
SPAT
A.V. Hill Associates
10316 Meade Lane Eden
Prairie, MN 55347
tel: 612-617-0449
fax: 612-626-1316
email: ahill@csom.umn.edu
Reference
Hill, Arthur V., Naumann, J. David, and Chervany, Norman L., "SCAT
and SPAT: Large-scale Computer-based Optimization Systems for the
Personnel Assignment Problem," Decision Sciences, Vol. 14,
April 1983, pp. 207-20.
SPAT Questions & Answers
by Arthur V. Hill, University of Minnesota
Questions Often Asked by Students
Q: How does SPAT handle ties? My friend and I submitted exactly the
same rankings but we were assigned to different projects. Why?
Questions Often Asked by Administrators
Q: Does SPAT take a long time to find a solution?