hi everyone - we need to assign students to testing groups which consist of
four people, but they cannot be from the same class, and their homeroom
teachers cannot be their test proctors. so we have a long (1500 or so) list
of ID numbers, in the next column their class #s, and in the next column
their homeroom teacher. is there any way to automatically assign them to
particular groups and times so that the two exclusionary criteria are met?

thanks for the help, not sure if this is possible in excel but thought i'd
give it a try

bill

I don't see any reason that code couldn't be written to do this. However,
your details are incomplete in terms of how the groups are assigned a test
proctor and what the other limitations are (how many test proctors, room
capacity, and so forth).
--
Regards,
Tom Ogilvy

"bonkerz" wrote in message
...
hi everyone - we need to assign students to testing groups which consist
of
four people, but they cannot be from the same class, and their homeroom
teachers cannot be their test proctors. so we have a long (1500 or so)
list
of ID numbers, in the next column their class #s, and in the next column
their homeroom teacher. is there any way to automatically assign them to
particular groups and times so that the two exclusionary criteria are met?

thanks for the help, not sure if this is possible in excel but thought i'd
give it a try

bill

here are some more details. 1500 people, and about 40 homeroom teachers. we
want each student to be assigned to a room and testing time (room 1,
9:00-9:15), so there are like 10 different rooms used all at the same time.
the data look like this for students:

ID HR teacher Class #
001 Dale 1
002 Dale 1
003 Dale 1
025 James 2
026 James 2
027 James 2
etc etc.

and for rooms
Room # Proctor Time
1 James 9:00
2 Carole 9:00
3 Nate 9:00
4 Peter 9:00
etc. etc.

so in the final scheduling array, it looks like this:

9:00 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)

(i put students in parentheses because they are not decided yet, just empty
cells)

what i'd like the program to do is go through the list of students and
assign them to one (and only one) room and time which a) is not proctored by
their homeroom teacher, and b) will not put them with any other students from
their same class number.

does this help? i just have no idea how to do this in excel, but it seems
like it should be feasible. thanks if anyone can help!

bill

Hi Bill;
Been thinking about this and working on a few ideas, also keep checking back
to see if anyone else had posted. I like problems like this where I need to
come up with an algorithm to do something unique.

I have an algorithm that works - sort of. The "sort of" part is the
problem. It correctly assigns students to groups, but I am having trouble
guaranteeing a solution for the last few students - it is possible to have no
group openings available that meet the criteria for that student. Trying to
think of ways to avoid that - alternatively, to find some smart way of
swapping with another student if it does happen.

Basically, here is how I approached the problem:
1) Step through the student list
2) Assign a random number to select a group
3) Check if we have a fit:
a) Proctor is homeroom teacher - no match, skip back to step 2
b) How many students already in group? If 4, can't join - skip back to 2
c) Step through current group members checking class numbers - if any
match skip back to step 2
4) If we made it this far, add student to group

But you can see that as group openings get fewer and fewer it is likely we
need to repeat step 2 several times to try the group openings, and that it is
possible to wind up in an endless loop if no suitable openings are left. I
can detect this by using a counter, but what to do when it happens is the
tough part. Would rather prevent it from happening by trying a different
approach.

Anyway, bottom line is this problem has me interested but need to think a
bit on it (and time has to be squeezed in among other work). Hope maybe
someone else has a better solution, but will keep at it. If you want to
discuss, you could email me at the following (address is altered to avoid
spam, you will figure it out):

Ken Dales

"bonkerz" wrote:

here are some more details. 1500 people, and about 40 homeroom teachers. we
want each student to be assigned to a room and testing time (room 1,
9:00-9:15), so there are like 10 different rooms used all at the same time.
the data look like this for students:

ID HR teacher Class #
001 Dale 1
002 Dale 1
003 Dale 1
025 James 2
026 James 2
027 James 2
etc etc.

and for rooms
Room # Proctor Time
1 James 9:00
2 Carole 9:00
3 Nate 9:00
4 Peter 9:00
etc. etc.

so in the final scheduling array, it looks like this:

9:00 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)

(i put students in parentheses because they are not decided yet, just empty
cells)

what i'd like the program to do is go through the list of students and
assign them to one (and only one) room and time which a) is not proctored by
their homeroom teacher, and b) will not put them with any other students from
their same class number.

does this help? i just have no idea how to do this in excel, but it seems
like it should be feasible. thanks if anyone can help!

bill

The ID list appears to be ordered by Teacher, so you could just go to each
class and pick the next available student. Assign that student to the next
testing slot if the HR teacher is not the proctor. If the HR student is the
proctor, hold that student's name until the next testing room, and assign
the available student in the next HR instead. This should work unless you
have significantly different class sizes.

--
Regards,
Tom Ogilvy



"bonkerz" wrote in message
...
here are some more details. 1500 people, and about 40 homeroom teachers.
we
want each student to be assigned to a room and testing time (room 1,
9:00-9:15), so there are like 10 different rooms used all at the same
time.
the data look like this for students:

ID HR teacher Class #
001 Dale 1
002 Dale 1
003 Dale 1
025 James 2
026 James 2
027 James 2
etc etc.

and for rooms
Room # Proctor Time
1 James 9:00
2 Carole 9:00
3 Nate 9:00
4 Peter 9:00
etc. etc.

so in the final scheduling array, it looks like this:

9:00 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:00 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:15 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #1 Nate (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #2 Tina (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #3 Dina (Student 1) (Student 2)
(Student 3) (Student 4)
9:30 Room #4 Pete (Student 1) (Student 2)
(Student 3) (Student 4)

(i put students in parentheses because they are not decided yet, just
empty
cells)

what i'd like the program to do is go through the list of students and
assign them to one (and only one) room and time which a) is not proctored
by
their homeroom teacher, and b) will not put them with any other students
from
their same class number.

does this help? i just have no idea how to do this in excel, but it seems
like it should be feasible. thanks if anyone can help!

bill

thanks for the help guys

i'm not sure if this is possible, but a flexible procedure where there could
be more criteria would work best. say, if i had gender data for students and
wanted to form some groups with all girls, some with half girls and half
boys, and some with all boys.

thanks again, i'm working on this myself and will report any progress.

bill

Hey, if you are still checking...
No matter how I approach this I always run into the possibility at the very
end of not finding a suitable opening for the last few students. (when you
get down to the last few, there is always a chance that the only available
openings either have another student from their class or are proctored by
their homeroom teacher).

There probably is an algorithm to ensure this does not happen, but it would
be more complex than any of the straightforward approaches I have considered.
With any simple sorting/choosing routine, you will probably need to have a
procedure at the end that allows for "swapping" students in some smart way to
fit those last few students into appropriate groups.

But I am still wondering if there is a more sophisticated algorithm to do
some kind of intelligent sorting of students to avoid any conflicts at the
end. In any case it is an interesting mathematical problem - the kind of
thing my brain enjoys!

K Dales

"bonkerz" wrote:

thanks for the help guys

i'm not sure if this is possible, but a flexible procedure where there could
be more criteria would work best. say, if i had gender data for students and
wanted to form some groups with all girls, some with half girls and half
boys, and some with all boys.

thanks again, i'm working on this myself and will report any progress.

bill

yes i'm still checking. even if the last few students are left unplaced, that
would be a great interim solution to have. please let me know if you have
something like this by e-mail.

apparently perl is pretty good at this sort of task but i'm not much of a
programmer.

thanks,

tillie6584 at yahoo.com

Keep posted. Busy here at work so no time, but I want to work on this "for
fun" this weekend (I know, sad, isn't it). My orignal code has been
butchered by now with all my attempts to modify it, but at the very least I
can recreate it. Still have some thoughts to try though - the idea of a
smart sort first followed by the selection seems to have some advantages. I
am also thinking about the underlying logic: is there an optimized solution
for a problem like this? It is basically a probability problem with
combinations.

"bonkerz" wrote:

yes i'm still checking. even if the last few students are left unplaced, that
would be a great interim solution to have. please let me know if you have
something like this by e-mail.

apparently perl is pretty good at this sort of task but i'm not much of a
programmer.

thanks,

tillie6584 at yahoo.com

OK, got the code written and seems to work, though I won't guarantee it is
bug-free. New approach steps through groups first - a bit more efficient.
My code assumes a few things:
Sheet with student list is called "STUDENTS" and has 3 columns with labels
in first row: student ID, Class, Homeroom - in that order. Another sheet
called "GROUPS" has a pre-built list of the groups, again starting in A1 and
having labels in 1st row: 1st column does not matter to the routine, but 2nd
must be the proctor and entries must match the "homeroom" from the student
list exactly. Columns 3,4,5,6 are for the four students to be listed (by the
ID from the student list).
I still cannot guarantee a full solution, but if a student cannot be found
to match a group, two things happen:
- A new worksheet called UNASSIGNED is created and any students who could
not be fit into existing openings will be listed on this sheet. A blank list
means all students were assigned to groups.
- Any group openings that could not be filled will be labelled "UNASSIGNED"
on the group list sheet.
Tests with a few random samples of 1500 students worked every time I tested
it with no students left unassigned, and on my 750MHz machine it does the
processing in less than a minute.
You could add even more criteria - looking at how I test the criteria using
the boolean variable Success should give a clue what you would need to do if
you decided to do this.

With all that, here is the code:

Public Sub FormGroups()
' Iterates through group list and assigns 4 students(max) to each group
' If routine has problems finding eligible student in reasonable number of
attempts
' student will be left on "UNASSIGNED" list (new sheet created by this
routine)
' If "UNASSIGNED" list is empty, all students are in appropriate groups!

Dim SSheet As Worksheet
Dim SList As Range, GList As Range
Dim SCount As Integer, GCount As Integer, GStep As Integer, SStep As Integer
Dim Iterations As Integer, Success As Boolean
Dim SRow As Integer, CCheck As Integer
Dim SClass(4) As String, MyClass As String, Homeroom As String, Proctor As
String
Dim CalcMode As Integer

' Turn off automatic calculation if it is on, to help with speed
CalcMode = Application.Calculation
Application.Calculation = xlCalculationManual

' Make sure routine can run!
Success = True

For Each SSheet In ThisWorkbook.Worksheets
Success = Success And (SSheet.Name < "UNASSIGNED")
Next SSheet

Success = Success And _
((Sheets("STUDENTS").Range("A1").CurrentRegion.Row s.Count - 1) / _
(Sheets("GROUPS").Range("A1").CurrentRegion.Rows.C ount - 1) <= 4#)

If Success Then

' Initialize variables...
' First create a copy of the student list to work with
Set SSheet = Worksheets.Add
SSheet.Name = "UNASSIGNED"
Set SList = Sheets("STUDENTS").Range("A1").CurrentRegion
SList.Copy
SSheet.Range("A1").PasteSpecial xlPasteValues
SSheet.Range("A1").PasteSpecial xlPasteFormats
SSheet.Range("A1").PasteSpecial xlPasteColumnWidths

' Step through the groups:
Set GList = Sheets("GROUPS").Range("A1").CurrentRegion
GCount = GList.Rows.Count - 1
For GStep = 1 To GCount

Proctor = GList.Range("A1").Offset(GStep, 1).Value

' Set up a range with the remaining students and count them
Set SList = SSheet.Range("A1").CurrentRegion
SCount = SList.Rows.Count - 1

' Find a maximum of 4 students for the group
If SCount 4 Then SStep = 4 Else SStep = SCount
InGroup = 0
SClass(1) = ""
SClass(2) = ""
SClass(3) = ""
SClass(4) = ""
While SStep 0

' Try to find a qualifying student
Iterations = 0 ' To count failed attempts
Success = False ' To flag if student meets criteria

' Keep picking until we find one (or have tried too many times
with no success)
While (Not Success) And (Iterations < (SCount * 4))

Iterations = Iterations + 1
Success = True
' Pick a student at random
Randomize
SRow = Int(Rnd() * SCount) + 1

' Now see if all criteria are met:

' Check Homeroom Teacher vs Proctor:
Homeroom = SList.Offset(SRow, 2).Range("A1").Value
Success = Success And (Homeroom < Proctor)

' Check class against other group members
' (Note: SClass array contains blank string for any
unassigned group members
MyClass = SList.Offset(SRow, 1).Range("A1").Value
For CCheck = 1 To 4
Success = Success And Not (MyClass = SClass(CCheck))
Next CCheck

Wend

' If the student was a match:
If Success Then
' Add them to group
GList.Range("B1").Offset(GStep, SStep) = _
SList.Offset(SRow, 0).Range("A1").Value
SClass(SStep) = MyClass
' Delete them from list of unassigned students
SList.Offset(SRow, 0).Range("A1").EntireRow.Delete
Set SList = SSheet.Range("A1").CurrentRegion
SCount = SList.Rows.Count - 1
Else
'Show that no match was found
GList.Range("B1").Offset(GStep, SStep) = "UNASSIGNED"
End If

SStep = SStep - 1
Wend

Next GStep

Else ' MESSAGE IF CONDITIONS FOR SUCCESSFUL COMPLETION ARE VIOLATED:

MsgBox "ABORTING: Routine cannot run if a sheet is already named
'UNASSIGNED'" _
& " or if there are too few groups (4 students/group maximum)" _
, vbExclamation, "CANNOT PROCESS GROUPS"

End If

' Return to original calculation mode
Application.Calculation = CalcMode

Set SList = Nothing
Set GList = Nothing
Set SSheet = Nothing

End Sub

Hope this works for you, or at least gives a "template" you can modify and
work with. It really was a fun challenge - I enjoyed it.

By the way, if you are interested, I realized it is in some ways analogous
to a game of solitai Imagine a game where you turn up cards from a one
deck and lay them out face up in a row. Then, from another 4 decks, you turn
up cards one at a time and place them under the original cards so that in the
end you have 4 cards underneath each of the starter cards - no two of the 4
can be the same suit, and none of them can match the number of the original
card. If you can do it all without rearranging any you win! The numbers
involved are different, but the principle is the same... (and that is why I
don't think you can "guarantee" a win without stacking the deck - just
haven't found out how to do that!)

K Dales

"bonkerz" wrote:

hi everyone - we need to assign students to testing groups which consist of
four people, but they cannot be from the same class, and their homeroom
teachers cannot be their test proctors. so we have a long (1500 or so) list
of ID numbers, in the next column their class #s, and in the next column
their homeroom teacher. is there any way to automatically assign them to
particular groups and times so that the two exclusionary criteria are met?

thanks for the help, not sure if this is possible in excel but thought i'd
give it a try

bill

wow, thank you so much k dales! i'm going to try it out in the next few days.
my colleagues would thank you profusely if they were all here in my bedroom.

bill