Combinations of orders for maximum efficiency

Question

Recently, I have had a problem that I have been considering and still cannot solve; I was wondering if anyone here could point me in the right direction by giving me the psuedo code (or at least the rough pseudo-code scheme) for this problem. PS I will build on PHP, if that matters ...

the functions

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

It’s still easy, it’s a matter of building an html form and processing it in a multidimensional array

---

There are ~ 15 time intervals during the day (for example, 9:00 AM, 9:20 AM, 9:40 AM ...). Each of these groups should occur once during the day. And during one time interval, a person cannot be booked twice (ie, “a” cannot be in 2 different groups at 9:40 in the morning).

It is difficult, but not impossible, my best guess on how to do this would be brute force (choose groups of groups that do not have matches (for example, {a, b, c}; {l, f, g}; { q, n, d} ...), and then just put each in a time interval

---

Finally, the schedule that I output should be “optimized,” by which I mean that “a” should have a minimum time between meetings (so if his first meeting is at 9:20, his second meeting shouldn’t be at 2:00 pm).

Here, where I am lost, the only thing I think is to build many, many schedules, and then rank them based on the average waiting time that a person has from one meeting to the next

---

However, my "decisions" (I do not want to call them) require too much brute force and will create for too long. Are there simpler, more elegant solutions?

Answer 1

This is a 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. The row in the Location table was in the following format: JSON

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

So what was going on in the layout table was that the script [or EXCEL column formula] would go through each slot per session and arbitrarily create a possible session. Check all previous conflict sessions.

 /** * 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 that the main part of group assignments is randomization. However, as the number of sessions increases. There will be more data to check for conflicts. The result is much lower performance. However, a large creature, ridiculously large, to an almost perfect permutation / combination.

EDIT:

This setting will also help ensure that as long as the user is available, they will be in the group. Although you may have pockets of users without user groups (a small number). They are usually corrected by recounting (for small session numbers). Or just group them together, even if it's a repetition. (with a few here and there it doesn’t hurt). Or, alternatively, in your case, join several groups of 3 together with the leftovers to form groups of 4. =)

And if it can work for EXCEL with about 100 + ppl and about 10 sessions. I do not see how this will not work in SQL + PHP. It’s just that the calculations may take some time in both directions.

Answer 2

Well, for those who simply join this post, read all the comments on this question before considering the contents of this answer, as this will most likely fly over your head.

Here are some PHP-style pseudo-codes:

 /* Array with profs (this is one dimensional here for the show, but I assume it will be multi-dimensional, filled with availability and what not; For the sake of this example, let me say that the multi-dimensional array contains the following keys: [id]{[avail_from],[avail_to],[last_ses],[name]}*/ $profs = array_fill(0, $prof_num, "assoc_ids"); // Array with time slots, let say UNIX stamps of begin time $times = array_fill(0, $slot_num, "time"); // First, we need to loop through all the time slots foreach ($times as $slot) { // See when session ends $slot_end = $slot + $session_time; // Now, run through the profs to see who available $avail_profs = array(); // Empty foreach ($profs as $prof_id => $data) { if (($data['avail_from'] >= $slot) && ($data['avail_to'] >= $slot_end)) { $avail_prof[$prof_id] = $data['last_ses']; } } /* Reverse sort the array so that the highest numbers (profs who have been waiting the longest) will be up top */ arsort($avail_profs); $profs_session = array_slice($avail_profs, 0, 3); $profs_session_names = array(); // Empty // Reset the last_ses counters on those profs foreach ($profs_session as $prof_id => $last_ses) { $profs[$prof_id]['last_ses'] = 0; $profs_session_names[0] = $profs[$prof_id]['name']; } // Now, loop through all profs to add one to their waiting time foreach ($profs as $prof_id = > $data) { $profs[$prof_id]['last_ses']++; } print(sprintf('The %s session will be held by: %s, $s, and %s<br />', $slot, $profs_session_names[0], $profs_session_names[1], $profs_session_names[2]); unset ($profs_session, $profs_session_names, $avail_prof); } 

This should print something like:

 The 9:40am session will be held by: C. Hicks, A. Hole, and BEN Dover 

Answer 3

I see an object model consisting of:

• Discussion participants: a fixed repository of your participants (Tom, Dick, Harry, etc.).
• Panel: consists of X panels (X = 3 in your case)
• Time slots: a fixed storage of your time slots. Assuming a fixed duration only takes one day, all you need is a start time.
• Meeting: consists of a panel and a time interval
• Schedule: consists of many meetings

Now, as you have noticed, optimization is the key. For me, the question is: "Optimized by what criteria?". Optimal for Tom may mean that the panels on which he is a member are laid out without large spaces. But Harry Panels can be everywhere. So, perhaps for a given schedule, we calculate something like totalMemberDeadTime (= the sum of all spaces in spaces in the schedule). The optimal schedule is the minimum value for this amount

If we are interested in calculating a technically optimal graph among the universe of all graphs, I really see no alternative to brute force.

It is possible that the universe of schedules should not be as large as it might seem at first. It seems that the panels are composed of the first, and then the question is to assign them to the Meetings, which they schedule. Thus, we eliminated the variation in panel composition; The full range of variability is presented at meetings and in the Schedule. However, there seems to be a lot of variability here.

But, perhaps, optimal with respect to all possible schedules is more than we really need.

Can we define a schedule as acceptable if a participant does not have a total dead time of more than X? Or if this is not so, if no more than X participants have more dead time than X (they cannot satisfy everyone, but minimize it)? Then the user can make an appointment for panels containing first the more “important” participants, and the less important guys just have to take what they get. Then all we need to do is a great, only acceptable schedule.

Could it be enough for your purposes to compare any two graphs? In combination with the interface (I see the drag and drop interface, but this clearly does not correspond to the point), which allows the user to schedule, clone it into the second schedule and configure the second, trying to reduce the aggregate dead time until we can find an acceptable one.

In any case, not a complete answer. Just out loud. Hope this helps.