Efficient Algorithm for Scheduling 140 Predefined 1:1 Meetings with Variable Participant Constraints Over 7 Slots?

Question

I’m tasked with organizing a large number (130) 1:1 meetings for 50 people across a limited number of time slots (7) during a conference. I am seeking advice on the best algorithmic approach to tackle this scheduling optimization problem efficiently.

Problem Summary:

Participants: 50 guests. Total Meetings: 130 predefined pairings. Meeting Slots: 7 available.

Constraints: Each pair of guests has been predetermined to meet exactly once. No participant can have more than one meeting per slot. Participants have variable numbers of total meetings ranging from just a few to many across the slots. A small number of meetings have 3 or 4 people (this can be ignored if it make it much more complex)

Objective: Schedule all meetings within the 7 slots, respecting all constraints, or at least find the solution that will mean the fewest meetings need to be cancelled.

It would be helpful to understand the right algorithm to use here, as well as any pointers to existing software that will help me all that algorithm.

Answer 1

You could also use a MIP. Here's an example using JuMP and HiGHS:

julia> using JuMP, HiGHS

julia> function solve_problem(;
           meetings::Vector{Set{Int}},
           num_time_slots::Int,
           num_people::Int,
       )
           model = Model(HiGHS.Optimizer)
           set_silent(model)
           # z[meeting, t] is 1 if `meeting` meets in time slot `t`
           @variable(model, z[meeting in meetings, t in 1:num_time_slots], Bin)
           # Meeting `meeting` can meet in at most one time slot
           @constraint(model, [meeting in meetings], sum(z[meeting, :]) <= 1)
           # Person `person` can meet with at most one meeting in time slot `t`
           @constraint(
               model,
               [person in 1:num_people, t in 1:num_time_slots],
               sum(z[meeting, t] for meeting in meetings if person in meeting) <= 1
           )
           # Maximize the number of meetings that meet
           @objective(model, Max, sum(z))
           # Solve the problem and check we found a solution
           optimize!(model)
           @assert is_solved_and_feasible(model)
           num_scheduled = round(Int, objective_value(model))
           println("Scheduled $(num_scheduled) / $(length(meetings)) meetings")
           solution = Dict(t => [] for t in vcat(nothing, 1:num_time_slots))
           for meeting in meetings
               t = findfirst(t -> value(z[meeting, t]) >= 0.5, 1:num_time_slots)
               push!(solution[t], meeting)
           end
           return solution
       end
solve_problem (generic function with 1 method)

julia> num_people = 50
50

julia> num_time_slots = 7
7

julia> meetings = Set{Int}[]
Set{Int64}[]

julia> while length(meetings) < 130
           meeting = Set(rand(1:num_people, rand(2:3)))
           if !(meeting in meetings)
               push!(meetings, meeting)
           end
       end

julia> solution = solve_problem(; meetings, num_people, num_time_slots)
Scheduled 115 / 130 meetings
Dict{Union{Nothing, Int64}, Vector{Any}} with 8 entries:
  nothing => [Set([29, 26]), Set([47, 16, 48]), Set([21, 43]), Set([21, 33]), Set([47, 45]), Set([35, 18, 48]), Set([33, 9]), Set([15, …
  4       => [Set([37, 3]), Set([34, 40]), Set([15, 45]), Set([42, 14, 19]), Set([6, 43, 10]), Set([41, 33]), Set([5, 21, 18]), Set([27…
  5       => [Set([43, 24]), Set([34, 11]), Set([33, 27]), Set([45, 25]), Set([22, 6, 42]), Set([50, 46, 14]), Set([10, 18, 9]), Set([4…
  6       => [Set([39, 41]), Set([20, 37, 40]), Set([46, 23]), Set([47, 27, 28]), Set([4, 38]), Set([50, 33, 1]), Set([30, 17]), Set([4…
  2       => [Set([5, 24]), Set([22, 6]), Set([47, 2]), Set([9, 31, 46]), Set([14, 1]), Set([18, 37]), Set([42, 40]), Set([25, 12]), Se…
  7       => [Set([4, 46]), Set([7, 2, 21]), Set([47, 26, 17]), Set([36, 31, 3]), Set([22, 8]), Set([41, 27, 42]), Set([6, 18, 1]), Set…
  3       => [Set([41, 33, 36]), Set([32, 6]), Set([49, 35, 30]), Set([3, 23]), Set([21, 31]), Set([24, 42, 48]), Set([13, 47]), Set([2…
  1       => [Set([45, 8]), Set([21, 25, 11]), Set([14, 37]), Set([15, 33, 19]), Set([26, 28]), Set([22, 30]), Set([47, 29]), Set([32,

I once built something very similar, https://github.com/odow/interview-scheduler, but it requires https://solverstudio.org to run, and I haven't touched it in 10 years.

Answer 2

With 1:1 meetings only, this is a classical application of graph coloring. The graph has a node for each person and an edge for each required meeting. The edge colors correspond to time slots, and you want to find an edge coloring with $7$ colors. More generally, you can ask for the minimum number of colors needed (the chromatic index).

With more than two people per meeting, your problem is hypergraph coloring, and similar methods apply.

Are you able to share your data?

---

For your data, the minimum number of colors turns out to be $8$, but you can color all but two groups with only $7$ colors:

Group ID       N1 N2 N3 N4 Color
8Fkxo2VxPboFzJ A  WA UA    1
dN5q8i66UkafMb A  P        2
i9GsRWU6Y50kB6 P  MA       6
VnGB1mIzBf4zYJ HA NA       3
Wp57uaQkQXu6F8 J  Y        1
sfa0kq01bPRGho H  O        7
aMhvB6Id21vCri B  CA X     1
woTQDtmPkCvTR8 B  HA X     2
vJCXk8ne9COYHr P  I        7
BSM9agepCfnW2X W  SA       4
r9XR5BAdcqbTZD W  U  D     2
TB9Ecurf8NVMiA QA PA       1
6DRyNWLBxj68GV QA J        2
8tOO55iE5CvxMq QA SA       3
JjWZ9VUDaCfbBP QA DA       6
yTyi0pCv9SLT0l HA S        1
TBNsUAJP7mL4aJ Q  LA       1
FrUIyNQJdLhAAn WA CA UA    2
NCY3S1PSFl6Msz C  JA       1
HcLkNoeO2WS05I L  S        5
pgobuiMUEkQpH4 T  U  D     1
1OLqoCfLhjkI4K FA JA       2
svPq9TmRoYmtsC FA SA       5
hJgkkbFBLeW4Fa O  S  E     2
j8tMpTnQgcMy8V GA Y        2
RIJcVZYiI4ck7n GA W        1
y4XpVJ2ICJjMDP GA G        7
hqFSqRv8WYmv4E GA TA OA    4
lPg03BO1rvtTOV H  N  VA    2
5iWT3r5OiJJB8l H  Z        3
Nwc1Nqk5XTLovy H  PA       4
ABVBgiuRSAUA6N I  X  B     4
Ad2t7tjlwfTyrV I  Q        2
LumcM0eIZyvCvj N  SA VA    6
KtT1xlKOuZq96W N  Y  VA    3
xdF8YKijmezTij N  MA VA    4
04zpCSPo2Fk0DQ N  I  VA    1
M5oaSiy1qyqAWj JA IA       3
jLbmXUEJAPxDi5 JA P        4
BCp5RwsyBSltf8 JA WA UA    5
TWGs3uFEUpD5Xx JA K        6
zW7M5zhMGRR8dA O  IA       4
UALbDSGvnw8nZ8 O  KA       5
WAB1PXAvWTpuz9 O  I        3
brlknhnQY2s9sY O  A        6
KlzUwzxDnSosQC Z  IA OA    1
kRAQAXr1rs73fs Z  I        6
Ny2arIc0myFrji Z  LA       2
7r3fo9iBfANfhW Z  W        5
P7rA7UEsCJnULZ Z  DA       4
aCK3kAWN6J0YAS Z  JA       7
XVyEw2sENQAyoI Q  KA       4
8ZX8hFFRsl8a9e V  AA OA K  2
tMJBRYRtJiaNW2 Q  K        3
LKm9sbQWWrkybv V  AA U  D  3
tQavTyZrOlBGmW V  AA FA    1
mLCAU5HH0DLtbS V  AA Y     4
Xn1acGBVYMmJFp V  AA P     5
SPXkLe5VXPXdft V  AA W     6
sHAJ6M0pBBMpus V  AA LA    7
DDtWE1eDbKk2gq A  IA       5
SY4gupCDdW3zUh A  K        4
bxlAxtOXpmAo4d EA U  D     4
KclEBNAKugv4Yw EA KA       1
H5cRsS6r0K3vR0 EA K        5
poehGjlhnzKsUA EA Y        6
FvyGa1iIqM30cD EA MA       2
sJBSDSR4GLaEdh EA S        7
35yPdDyZV1NGKn MA QA       5
qJ2m1ExHo7R1uy MA WA UA    3
98WxxC4C1NmXMl MA W        7
iFu3vj3nzADmvy C  OA       3
orq770ty7JWk7r C  B  X     5
iS6zYVeyGYRF9e C  QA       4
XvOEFeBmk94RcC C  BA       2
HQdXAo6FUPAn3S C  L        6
bPatOvlZj5p2vN C  Y        7
EuTUiOCDRS9gyK BA IA       6
aM7odkAxEUiwtl BA QA       7
SeaNwuMdQOB425 BA Y        5
WpmRMCgPd2KbpO BA KA TA    3
IEueDXLY0iCoFb BA H        1
KYFqaPC49f1V0h BA J        4
qh6wPjPL1fcs9K E  DA       1
QNNOo9GcvLMw5q E  F        3
rd9tHKKtSt15z5 E  LA       6
ySeSIRT6Tvc7Ag E  HA       5
68VPyd0vJeIQa5 E  T        4
GzGFFs8CX9kwLT HA TA       6
L2U7KsvmNkkuLv J  DA       7
xirb6F1pHCo0rn NA TA       2
Is4zmRoCld2Z1O NA E        7
mWA85PQiuWCvNs PA IA       2
a2EqFfFsZXVxBP PA A        3
ylocSCkUBFuMw1 PA CA       5
Y09yF18NDz5kzq SA B  X     7
0HXnRupNbfpIzY CA OA KA    6
q6kHDbB37KOyQy CA K        7
9iSVveHGIxu9p1 CA P        3
2NOjraVuik9shr EA FA       3
kFTKn1DOJvEBJW RA OA IA    7
44Fwr8vLGf0VrR RA L        4
CMJUh9orSayJCU RA J        6
5fb3kDlySvbY66 RA SA       2
VStGHDtehXot69 J  TA OA    5
rmmnVfusye8Qgl J  W        3
0rR7csVnVIdvKv H  T  F     5
lBnAE30Zg5Ct2h RA P        1
7ToXuMvQF79Mu2 RA B  X     3
TvKix2p4R5RV2Y RA I        5
YfQUbWZG745rJH GA LA       5
kGWo6BNSExaPdM GA FA       6
HOx8Fo5lBoSQDA WA Q  UA    6
1bM6W7LSPa6RQg WA PA UA    7
BfUsgUz6NhZN78 U  DA D     5
2szwZBE3xXFqkJ FA HA       7
RzVfWbLNKvDyN7 NA B  X     6
XeIYC3soZ616Th N  KA VA    7
NeZmFAngIFXvJh N  VA WA U  
tTrluW342VGhz9 PA S        6
FZhX07iQ3tclAU F  DA       2
Hpiy2JzkqgBKKZ F  L        7
9fMXmgmePBBd9G K  MA       1
ZgVRXueKRp76sB K  TA       
GpuPEOdB9DSAsL H  U  F  D  6
6nAtaD79SQrloO L  T        2
sqUj3yQXEBsxjt S  GA       3
jaJkvfyybHbQ4n U  D  TA    7
J1LPKM5HThB6ar DA LA T     3
5RDIrDh8OFRLgL HA LA       4
zQK602Gnp6P81R SA O        1

Answer 3

Our meeting scheduling example covers these constraints.

It even allows for the meetings to be of different lengths: for example 30 minutes, 1 hours, etc. And for the number of rooms to be limited. And for meetings to have multiple required participants (not just two) and also preferred participants (soft). We've used in the past for breakout meetings.

You can find it here. It's all open source (Apache License). This example is in Java - we don't have a Python port of it yet (but that shouldn't be too hard).

Simply go in to the DemoGenerator class and change it to use your data (ChatGPT can help a lot there). Create new Meeting instances, with the 2 persons that need to meet in the requiredParticipants list.

BTW, if you also need to schedule the actual conference talks, the conference scheduling example is used for several big conferences.