Оптимальное планирование встреч

Эффективное планирование встреч

Планирование встреч без перекрытий может быть сложной задачей, особенно когда речь идет о нескольких участниках с загруженными графиками и большим количеством встреч.

Планирование встреч можно выполнить с использованием различных инструментов оптимизации, таких как Pyomo, GAMS, Google OR-Tools, AIMMS или AMPL. Для эффективного использования этих инструментов необходимо построить хорошо определенную математическую модель, которая точно представляет подлежащую задачу планирования. В этой статье используется пакет Google OR-Tools.

Давайте опробуем нашу силу и решим проблему:

Чтобы проиллюстрировать описание проблемы, рассмотрим сценарий, в котором организация имеет 20 сотрудников, каждый из которых может быть членом различных команд. Внутри этой организации существует шесть различных команд:

  1. Продажи
  2. Финансы
  3. Юриспруденция
  4. Поддержка клиентов
  5. Исследования и разработка
  6. Контроль качества

Следующий граф представляет визуальное изображение принадлежности сотрудников к этим командам:

{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]}

Есть пять временных слотов (1, 2, 3, 4, 5), которым эти команды должны быть назначены.

Очевидно, что когда сотрудник (p) одновременно является членом как команды i, так и команды j, планирование встреч для этих двух команд в один и тот же временной слот вызывает дилемму, поскольку сотрудник p не может присутствовать на обеих встречах. Концепция заключается в создании модели с минимальным количеством таких конфликтов в расписании.

Модель оптимизации

Python-код

Для решения этой проблемы может быть использован пакет OR-Tools следующим образом:

Импортировать необходимые пакеты:

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

Перед созданием и вызовом модели нам нужно подготовить данные:

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

Модель CP

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"Статус = {solver.StatusName(status)}")        print('Превышение' , [i[0] for i in over_pt if solver.Value(over_pt[i]) ])SearchForAllSolutionsSampleSat()

Визуализация результатов

Расписание команд будет следующим:

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} ------>  время {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}",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"Расписание команд.png")    plt.show()

Чтобы проверить количество встреч для каждого сотрудника на каждом временном слоте, можно использовать следующую визуализацию:

 plt.figure(figsize=(11,7))    print(f"Участник команды   {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(' Слоты времени ',fontsize=14, fontweight='bold')    plt.xlabel(' Участники ',fontsize=14, fontweight='bold')    plt.savefig(f"все сотрудники.png")    plt.show()

Видно, что все сотрудники оптимально распределены без превышения назначений.

Вывод

Оптимизация, особенно с помощью линейного смешанного целочисленного программирования (MILP), оказывается очень полезной для планирования встречи по нескольким ключевым причинам:

  1. Повышение эффективности: Модели линейного целочисленного программирования (MILP) позволяют эффективно распределять ограниченные ресурсы, такие как переговорные комнаты и время участников, что приводит к сокращению потерь и улучшению использования ресурсов.
  2. Разрешение конфликтов: Оптимизация может определять и устранять конфликты в расписаниях встреч, учитывая ограничения, обеспечивая отсутствие двойных бронирований и минимизируя перекрытие в расписаниях.
  3. Снижение затрат: Минимизация общих затрат, связанных с составлением расписаний встреч, позволяет организациям экономить ресурсы и сокращать накладные расходы, делая операции более эффективными с точки зрения затрат.
  4. Настройка: Модели линейного целочисленного программирования (MILP) могут быть адаптированы для учета конкретных бизнес-требований, учитывая различные ограничения и цели, чтобы соответствовать уникальным потребностям организации.
  5. Экономия времени: Применение методов оптимизации упрощает процесс составления расписания, экономя время для административного персонала и участников, что в конечном итоге повышает общую производительность и эффективность в организации.

Хотите связаться?

  • 📖 Подпишитесь на меня в VoAGI
  • Получите доступ к коду на Github
  • 💌 Подпишитесь, чтобы получать электронные письма с моими публикациями
  • 🤓 Свяжитесь со мной на LinkedIn