8
$\begingroup$

My wife teaches AM and PM kindergarten classes. AM has 14 students and PM 11. At the beginning of each month, she puts out a new seating chart where she rotates students in such a way that they (ideally) sit at a different table and with different students for that month.

There are 3 students per table, but if numbers force the issue, the last may have more or less. We realize that, by the end of the year, there will be some unavoidable situations where students end up sitting with each other or at the same tables again, and this is okay.

She works on this seating diagram every month and it's a huge chore. It's agonizing to see her do this because it's very time-consuming, and I feel helpless. I know there has to be a mathematical way to do it. I did find one formula on here, but couldn't figure out what the variables represented and how to change them to meet her needs as students come and go. Can anyone help me out? It would be even better if I could use Excel to automate this process. [sorry if the tags are inappropriate; I just guessed]

$\endgroup$
  • $\begingroup$ Do any students attend both am and pm sessions? $\endgroup$ – tomi Nov 29 '16 at 15:29
  • $\begingroup$ By "more or less" I assume that there can be 2, 3 or 4 on a table, but probably never only 1 student on a table. $\endgroup$ – tomi Nov 29 '16 at 15:31
  • $\begingroup$ You want to add "linear-programming" as a tag and remove "multivariable-calculus" and "complex-analysis" $\endgroup$ – tomi Nov 29 '16 at 15:32
  • 1
    $\begingroup$ See e.g. link. $\endgroup$ – Erwin Kalvelagen Nov 29 '16 at 16:36
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Kirkman's_schoolgirl_problem $\endgroup$ – Ethan Bolker Dec 1 '16 at 19:11
1
$\begingroup$

If I understand the problem well (english can be ambiguous, maths are not), here is a model you can use. The link in comment is not exactly the same problem (here, you have only students, not customers and suppliers). For resolution, excel should be OK (I have other stuff at work I can advise, any integer programming/constraint programming solver should do the trick). You have

A set $[1,N]$ of tables (this is not abstract, put a sticker with a number on each one)

A set $[1,S]$ of students (put a sticker with a number on each one's forehead)

A set $[1,M]$ of months

Define, $\forall$ (for all, you can understand it as the english word if it helps you) $n \in [1,N], s \in [1,S], m \in [1,M] $ the boolean variable (variable which is equal to either $0$ or $1$) $x_{n,s,m}$ which is equal to $1$ if student $s$ is assigned table $n$ on month $m$.

Define, $\forall (s,s') \in [1,S]^2$ (couple of students), $\forall m \in [1,M],y_{s,s',m}$ the binary variable which is equal to $1$ if and only if students $s$ and $s'$ are on the same table on month $m$

Then, you want to have values for $x$ which verify

$\forall n \in [1,N], \forall m \in [1,M], \sum_{s} x_{n,s,m} \leq 3$ (at most $3$ students per table at the same time)

$ \forall s \in [1,S], \forall m \in [1,M], \sum_{n} x_{n,s,m} = 1 $ (each student has a table affected to him at each time period)

$\forall (s,s') \in [1,S]^2$ such that $ s \neq s', \forall m \in [1,M], \forall n \in [1,N], x_{n,s,m} + x_{n,s',m} \leq 1 + y_{s,s',m} $ (make $y$ equal to $1$ at least where it should be according to its definition )

$\forall (s,s') \in [1,S]^2$ such that $ s \neq s', \sum_m y_{s,s',m} \leq 1$ (no more than $1$ month together for each couple of students)

This model I wrote holds a LOT of symmetry, and I'm guessing you do not want to look into how to break symmetry in integer linear programming. Hence, do not look for an optimal solution, only a feasible one (if you ever heard of branch and bound algorithms, it sucks whenever symmetry is present).

If the system is not feasible, tell me, and with something a little more elaborate you can try to put the students together only on the most distant time spans (you will need a little more variables if you want it to stay linear).

PS : I live with a woman who is a teacher, watching her do this kind of thing is indeed agonizing

$\endgroup$
0
$\begingroup$

Someone else has pointed out that this is pretty much equivalent to "Kirkman's schoolgirl problem."

I found the standard wikipedia article quite helpful (here), but I preferred another article (here) that explained the algorithms for finding a solution.

In the articles quoted there is a solution given for 15 students. Your wife's kindergarten has 14 students in the morning, so it is possible to let the 15th student be an empty seat. The solution as listed only works for seven months and doesn't satisfy the constraint of changing tables:

$$\begin{array}{|m{cm}|m{cm}|} \hline & \text{Sep} &\text{Oct} &\text{Nov} &\text{Dec} &\text{Jan} &\text{Feb} &\text{Mar} \\ \hline \hline \hline\text{Table 1}& 1, 6, 11 & 1, 2, 5 & 2, 3, 6 & 5, 6, 9 &3, 5, 11 &5, 7, 13& 4, 11, 13\\ \hline \text{Table 2}& 2, 7, 12 & 3, 4, 7 & 4, 5, 8 & 7, 8, 11 &4, 6, 12 &6, 8, 14& 5, 12, 14\\ \hline \text{Table 3} & 3, 8, 13 &8, 9, 12&9, 10, 13&1, 12, 13& 7, 9, 15&2, 9, 11&2, 8, 15 \\ \hline \text{Table 4}&4, 9, 14&10, 11, 14& 11, 12, 15& 3, 14, 15 & 1, 8, 10& 3, 10, 12& 1, 3, 9\\ \hline \text{Table 5} & 5, 10, 15& 6, 13, 15& 1, 7, 14 & 2, 4, 10 &2, 13, 14 & 1, 4, 15 & 6, 7, 10 \\ \hline \end{array}$$

To be a proper solution to your wife's problem, the positions on the tables need to be moved and a further five months added. I translated the numbers in the first five columns to give a new set of triplets (none repeated from the first set) then added these on as the next five columns. I also shuffled the positions so that every student sat at each table at least once.

Final arrangement is:enter image description here

To attempt a solution to your wife's 11 student problem in the afternoon, I amended Foster's algorithm. I treated the problem as if there were 12 students, one of whom can be later allocated as an empty seat.

First, it was not possible to set up triplets in the form $(x, a_1, a_2), (x, b_1, b_2)$ etc.

Instead I decided to leave out the $x$ and go straight into thinking of the students as being pairs: $a_1, a_2, b_1, b_2, c_1, c_2, ... , e_1, e_2$

I then identified a set of triplets that would allow all combinations.

I worked alphabetically so that my triplets were: $abc, ade, bdf, cef$. This would be the basis of my arrangement for Month 1.

I created another set of triplets by finding the complement of each of the first set of triplets: $def, bcf, ace, abd$. This would be the basis of my arrangement for Month 2.

I then counted the number of pairings that existed and discovered that so far there were no triplets with the pairings: $af, be, cd$. I used these pairings to create the triplets: $aaf, bbe, ccd$ together with a fourth triplet $def$ (to complete the list of possible pairings). This would be for Month 3.

I then created a fourth set of triplets as a kind of complement to the third set: $add, cee, bff, abc$. This would be for Month 4.

I now had the following:

$$\begin{array}{|m{cm}|m{cm}|} \hline & \text{Sep} &\text{Oct} &\text{Nov} &\text{Dec} \\ \hline \hline \hline\text{Table 1}& a, b, c & d, e, f & a, a, f & a, d, d \\ \hline \text{Table 2}& a,d,e&b,c,f&b,b,e&c,e,e \\ \hline \text{Table 3} & b,d,f&a,c,e&c,c,d&b,f,f \\ \hline \text{Table 4}&c,e,f&a,b,d&d,e,f&a,b,c\\ \hline \end{array}$$

I then used Frost's method to label the letters:

$$\begin{array}{|m{cm}|m{cm}|} \hline & \text{Sep} &\text{Oct} &\text{Nov} &\text{Dec} \\ \hline \hline \hline\text{Table 1}& a_1, b_1, c_1 & d_1, e_2, f_1 & a_1, a_2, f_1 & a_1, d_1, d_2 \\ \hline \text{Table 2}& a_2,d_1,e_1&b_2,c_1,f_2&b_1,b_2,e_2&c_1,e_1,e_2 \\ \hline \text{Table 3} & b_2,d_2,f_1&a_1,c_2,e_1&c_1,c_2,d_1&b_1,f_1,f_2 \\ \hline \text{Table 4}&c_2,e_2,f_2&a_2,b_1,d_2&d_2,e_1,f_2&a_2,b_2,c_2\\ \hline \end{array}$$

I then replaced the letters with the numbers 1 to 12.

I only have the first four months, so I need to increase this up to 12 months - more to come!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.