Optimal Meeting Scheduling

Optimal Meeting Scheduling.

Overview

Author(s): Optimization team

Originally published on Towards AI.

Scheduling meetings without overlaps can be a complex task, especially when dealing with multiple participants with busy schedules and big number of meetings.

The meeting schedulling can be done using various optimization tools such as Pyomo, GAMS, Google OR-Tools, AIMMS or AMPL . To effectively utilize these tools, it is essential to construct a well-defined mathematical model that accurately represents the underlying scheduling problem. This article uses Google OR-Tools package.

Let's get our hands dirty and tackle the problem:

To illustrate the problem description, let’s consider a scenario where an organization employs 20 staff members, each of whom may belong to various teams. Within this organization, there are six distinct teams:

  1. Sales
  2. Finance
  3. Legal
  4. Customer Support
  5. R&D
  6. Quality Assurance

The subsequent graph provides a visual representation of the staff members’ affiliations with these teams:

{1: [1, 2, 4, 5, 9, 10, 11, 14, 15, 18],
2: [1, 2, 3, 5, 6, 9, 10, 11, 15, 17, 18],
3: [5, 13, 14, 18, 19],
4: [1, 5, 6, 9, 12, 13, 14, 17, 18, 20],
5: [3, 6, 7, 8, 10, 16, 17, 20],
6: [2, 6, 8, 9, 10, 13, 15]}

There are five-time slots (1,2,3,4,5) which these teams should be assigned to them.

Clearly, when a staff member (p) is concurrently part of both team i and team j, scheduling meetings for these two teams during the same time slot presents a dilemma, as staff member p cannot attend both. The concept is to create a model aimed at minimizing such scheduling conflicts.

Optimization model

Python Code

For this problem, the OR-Tools package can be used as follows:

Import the required packages:

from ortools.sat.python import cp_model
import numpy as np
import matplotlib.pyplot as plt
import random

Before creating and calling the model we need to prepare the data:

Timeslots = [1,2,3,4, 5]
Individuals = [i+1 for i in range(20)]
Teams = [team+1 for team in range(6)]

individual_member = {}
for p in Individuals:
n = random.randint(1,4)
individual_member[p] = random.sample(Teams, n)
team_members = {team:[] for team in Teams}
for p , team_list in individual_member.items():
for team in team_list:
team_members[team].append(p)
team_members

The CP model

def SearchForAllSolutionsSampleSat():
model = cp_model.CpModel()
x = {(team,t):model.NewBoolVar(f"x_{team}_{t}") for team in Teams for t in Timeslots}
over_pt = {(p,t):model.NewIntVar(0,len(Teams)-1, f"over_{p}_{t}") for p in Individuals for t in Timeslots}

for team in Teams:
model.AddExactlyOne([x[team,t] for t in Timeslots])

for t in Timeslots:
for p in Individuals:
expressions = [x[team,t] for team in Teams if p in team_members[team] ]
model.Add(sum(expressions)-1<= over_pt[p,t])

of_expr = sum([over_pt[p,t] for p in Individuals for t in Timeslots])
model.Minimize(of_expr)
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinter([x,over_pt])
solver.parameters.enumerate_all_solutions = False
# Solve.
status = solver.Solve(model, solution_printer)
print(f"Status = {solver.StatusName(status)}")
print('Overassigned' , [i[0] for i in over_pt if solver.Value(over_pt[i]) ])

SearchForAllSolutionsSampleSat()

Visualizing the Results

Team scheduling will be as follows:

plt.figure(figsize=(6,6))
team_assignment = {}
for (team,t),v in x.items():
if solver.Value(v)>0:
team_assignment[team,t] =1
print(f"Team {team} ------> time {t}")

plt.scatter(t,team,s=300,c= 'g', zorder=3)
plt.scatter(0,team,s=300,c= 'k', zorder=3)
plt.text(-0.2*len(Timeslots),team,s=f"team{team}",c= 'k', zorder=3,fontsize=14, fontweight='bold')

for t in Timeslots:
plt.text(t,team+0.3,s=f"t{t}",c= 'k', zorder=3,fontsize=14, fontweight='bold')
plt.axis('off')
plt.savefig(f" Teams schedule.png")
plt.show()

To check the number of meetings for each staff at each time slot, the following visualization can be handy:

 plt.figure(figsize=(11,7))
print(f"Team member {1} {2} {3} ")
for p in Individuals:
time_assign = []
for t in Timeslots:
a = [team for team in Teams if p in team_members[team] and (team,t) in team_assignment]
if len(a)>0:
time_assign.append(len(a))
plt.text(p-0.02,t+0.2,s=L2S(a),fontsize=8, fontweight='bold', rotation = 90)
plt.scatter(p,t,s=200)
else:
time_assign.append(0)
print(f"{p} {time_assign[0]} {time_assign[1]} {time_assign[2]} ")
plt.grid()
plt.xticks(Individuals ,fontsize=14, fontweight='bold')
plt.yticks(Teams ,fontsize=14, fontweight='bold')
plt.ylim(0.5,len(Timeslots)*1.2)
plt.ylabel(' Time slots ',fontsize=14, fontweight='bold')
plt.xlabel(' Individuals ',fontsize=14, fontweight='bold')
plt.savefig(f"all staffs.png")
plt.show()

It can be observed that all staffs are optimally scheduled without any over assignment.

Conclusion

Optimization, particularly through Linear Mixed-Integer Programming (MILP), proves invaluable for meeting scheduling due to several key reasons:

  1. Efficiency Enhancement: MILP models allow for the efficient allocation of limited resources, such as meeting rooms and participants’ time, leading to reduced waste and improved resource utilization.
  2. Conflict Resolution: Optimization can identify and resolve conflicts in meeting schedules by considering constraints, ensuring that participants are not double-booked and minimizing scheduling overlaps.
  3. Cost Reduction: By minimizing the overall cost associated with meeting scheduling, organizations can save resources and reduce overhead expenses, making operations more cost-effective.
  4. Customization: MILP models can be tailored to address specific business requirements, accommodating various constraints and objectives to meet an organization’s unique needs.
  5. Time Savings: Implementing optimization techniques streamlines the scheduling process, saving time for administrative staff and participants, and ultimately enhancing overall productivity and effectiveness in an organization.

Want to connect?

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI

.

AI Applications

One AI application for businesses facing the choice between open-source and proprietary models to deploy generative AI is natural language processing (NLP) for customer service or support chatbots. Businesses can utilize generative AI models to develop chatbots that can understand and respond to customer queries in a more human-like manner. The choice between open-source and proprietary models can impact the accuracy, scalability, and customization capabilities of the NLP models deployed in these chatbots.

Additionally, another AI application is the development of recommendation systems. Generative AI models can be used to create personalized recommendations for products or content based on user behavior and preferences. The choice between open-source and proprietary models can affect the quality of the recommendations, as well as the ability to tailor the recommendation system to specific business needs.

Furthermore, businesses can leverage generative AI for content generation, such as automated text summarization, language translation, and creative writing. The choice between open-source and proprietary models can influence the linguistic fluency, coherence, and originality of the generated content.

In each of these applications, the decision between open-source and proprietary models for generative AI deployment can significantly impact the performance, interpretability, and ethical considerations of the AI systems utilized by businesses.