Ordering Combinations for Maximum Effectiveness

Question

So recently I was given a problem, which I have been mulling over and am still unable to solve; I was wondering if anyone here could point me in the right direction by providing me with the psuedo code (or at least a rough outline of the pseudo code) for this problem. PS I'll be building in PHP if that makes a difference...

Specs

There are ~50 people (for this example I'll just call them a,b,c... ) and the user is going to group them into groups of three (people in the groups may overlap), and in the end there will be 50-100 groups (ie {a,b,c}; {d,e,f}; {a,d,f}; {b,c,l}...). *

So far it is easy, it is a matter of building an html form and processing it into a multidimensional array

---

There are ~15 time slots during the day (eg 9:00AM, 9:20AM, 9:40AM...). Each of these groups needs to meet once during the day. And during one time slot the person cannot be double booked (ie 'a' cannot be in 2 different groups at 9:40AM).

It gets tricky here, but not impossible, my best guess at how to do this would be to brute force it (pick out sets of groups that have no overlap (eg {a,b,c}; {l,f,g}; {q,n,d}...) and then just put each into a time slot

---

Finally, the schedule which I output needs to be 'optimized', by that I mean that 'a' should have minimal time between meetings (so if his first meeting is at 9:20AM, his second meeting shouldn't be at 2:00PM).

Here's where I am lost, my only guess would be to build many, many schedules and then rank them based on the average waiting time a person has from one meeting to the next

---

However My 'solutions' (I hesitate to call them that) require too much brute force and would take too long to create. Are there simpler, more elegant solutions?

Answer 1

These are the table laid out, modified for your scenerio

+----User_Details------+  //You may or may not need this
| UID | Particulars... |
+----------------------+

+----User_Timeslots---------+  //Time slots per collumn
| UID | SlotNumber(bool)... |  //true/false if the user is avaliable
+---------------------------+  //SlotNumber is replaced by s1, s2, etc

+----User_Arrangements--------+  //Time slots per collumn
| UID | SlotNumber(string)... |  //Group session string
+-----------------------------+

Note: That the string in the Arrangement table, was in the following format : JSON

'[12,15,32]' //From SMALLEST to BIGGEST!

So what happens in the arrangement table, was that a script [Or an EXCEL column formula] would go through each slot per session, and randomly create a possible session. Checking all previous sessions for conflicts.

/**
* Randomise a session, in which data is not yet set
**/
function randomizeSession( sesionID ) {
    for( var id = [lowest UID], id < [highest UID], id++ ) {
        if( id exists ) {
            randomizeSingleSession( id, sessionID );
        } //else skips
    }
}

/**
* Randomizes a single user in a session, without conflicts in previous sessions
**/
function randomizeSingleSession( id, sessionID ) {

    convert sessionID to its collumns name =)
    get the collumns name of all ther previous session

    if( there is data, false, or JSON ) {
        Does nothing (Already has data)
    }

    if( ID is avaliable in time slot table (for this session) ) {
        Get all IDs who are avaliable, and contains no data this session
        Get all the UID previous session
        while( first time || not yet resolved ) {
            Randomly chose 2
            if( there was conflict in UID previous session ) {
                try again (while) : not yet resolved
            } else {
                resolved
            }
        }

        Registers all 3 users as a group in the session

    } else {
        Set session result to false (no attendance)
    }
}

You will realize the main part of the assignment of groups is via randomization. However, as the amount of sessions increases. There will be more and more data to check against for conflicts. Resulting to a much slower performance. However large being, ridiculously large, to an almost perfect permutation/combination formulation.

EDIT:

This setup will also help ensure, that as long as the user is available, they will be in a group. Though you may have pockets of users, having no user group (a small number). These are usually remedied by recalculating (for small session numbers). Or just manually group them together, even if it is a repeat. (having a few here and there does not hurt). Or alternatively in your case, along with the remainders, join several groups of 3's to form groups of 4. =)

And if this can work for EXCEL with about 100+ ppl, and about 10 sessions. I do not see how this would not work in SQL + PHP. Just that the calculations may actually take some considerable time both ways.