Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to schedule a meeting between (P) number of parties, having (T) number of timeslots such that multiple meetings are arranged in one timeslot and of course, no party has more than one meeting in a single timeslot. This however, is not a classical round-robin problem because I have a peculiar requirement: The timeslots T and locations L will ALWAYS be less than the number required to accommodate all meetings for all P parties. So the most lucrative meetings will be pre-determined and they have to placed in a schedule. The pre-determination is not-calculable, it will be made at the last moment by a third-party without any way for me to compute it.

Let me clarify this by an example scenario that I face: 12 delegations (P) are coming for a training event. My organizations wishes the delegations to meet amongst themselves in a formal method using a round-robin method. If we want to cover all meetings we will need (12 x 11) / 2 = 66 meetings with 11 timeslots (T), with 6 meetings conducted in each timeslot. However, we have only 6 timeslots = 36 meetings. So the 'expert' will decide the 36 most-promising meetings, such that each party has only 6 instead of 11 meetings; this at the last moment and give me the 36 meetings to schedule. How can I generate a schedule for a list of pre-determined meetings such that no party has overlapping meetings in a slot? The number of parties (P) and the number of timeslots (T) changes every-time. (I tried doing this manually, it was a nightmare!)

Question rephrased for more clarification: If I have to layout 66 meetings for 12 parties in 11 timeslots, I know how to do that. However, if random meetings are knocked out, how do I reschedule? We cannot have empty timeslots, so I have to 'fit' 36 meetings in 6 timeslots only. (The expert does not give me a schedule with meetings crossed out, rather a linear list of meetings: X meets Y, C meets F, A meets K etc.) Is there an algo to layout a linear list of ramdom meetings into a schedule?

share|improve this question
    
The problem you run into here is a pigeonhole problem - if the expert suggests 36 meetings but one particular party is involved in 7 of the 36, you will not be able to meet the demand. On the other hand, if the expert never selects meetings such that one party is required in more meetings than available timeslots then the problem is the classic round-robin scheduling, just with a whole bunch of meetings thrown out. –  process91 Aug 28 '12 at 13:56
    
@MichaelBoratko Ok, the expert never chooses 7, he has someone make sure that the schedule is never impossible. I rephrase my question: If I have to layout 66 meetings for 12 parties in 11 timeslots, I know how to do that. However, if random meetings are knocked out, how do I reschedule? We cannot have empty timeslots, so I have to 'fit' 36 meetings in 6 timeslots only. (The expert does not give me a schedule with meetings crossed out, rather a linear list of meetings: X meets Y, C meets F, A meets K etc.) Is there an algo to layout a linear list of ramdom meetings into a schedule? –  Huzhasan Aug 28 '12 at 14:16
    
If random meetings are knocked out, it's more likely than not that one party will have more than 6 meetings and it will be impossible to schedule them. The question only makes sense under the condition that each party has exactly $6$ meetings, independent of whether the selection is random or carried out by an expert. Also, please don't rephrase the question in the comments but by editing the question; people shouldn't have to delve into the comments to understand the question. –  joriki Aug 28 '12 at 14:35
    
@joriki I think I have settled the issue in the main question and in my comments; the schedule by the expert will NEVER be impossible. Please, lets get to the solution instead of delving on the flaws in the question. And the question rephrase was meant for michael-boratko for clarification, I think the original question seems clear enough. Even then, thanks joriki, I shall add part of my comment to the question. –  Huzhasan Aug 28 '12 at 15:07
    
I think you've got it backwards @Huzhasan: better to clearly formulate your question first, then worry about solutions. –  user641 Aug 28 '12 at 20:18
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.