Google OR-Tools - планирование одного мероприятия - PullRequest
Новая
       42

Google OR-Tools - планирование одного мероприятия

0 голосов
/ 12 января 2020

Google OR-Tools предоставляет пример примера кода , демонстрирующий, как решить проблему с расписанием медсестер. Я пытаюсь адаптировать его для решения сценария планирования интервью, при котором один кандидат будет присутствовать на двух встречах. Каждое собрание имеет следующее требование:

  1. На каждом собрании должно быть 2 участника

Требование к решению (1) довольно простое: 

meetings = ["phone_screen", "in_person"]
users = ["alice", "bob", "carl", "donna"]
days = ["Mon", "Tue", "Wed"]
times = ["morning", "afternoon"]

model = cp_model.CpModel()

# Build a boolean variable for every possible meeting time attendee
data = {}
for meeting in meetings:
  for day in days:
    for time in times:
      for user in users:
        id = 'meeting={},day={},time={},user={}'.format(meeting, day, time, user)
        data[(meeting, day, time, user)] = model.NewBoolVar(id)

## Requirement 1: Ensure 2 attendees for each time slot
for meeting in meetings:
  for day in days:
    for time in times:
      per_time_data = []
      for user in users:
        per_time_data.append(data[(meeting, day, time, user)])
      model.Add(sum(per_time_data) == 2)

# Solve and print solutions
solver = cp_model.CpSolver()
solver.Solve(model)
for day in days:
  for time in times:
    for meeting in meetings:
      string = '{} {}\t| {}\t| '.format(day, time, meeting)
      for user in users:
        if solver.Value(data[(meeting, day, time, user)]) == 1:
          string += user + '\t'
      print(string)

Это работает как положено, распечатывая единственное решение, в котором в каждом слоте собраний (в основном) случайный выбор из 2 участников: 

Mon morning     | phone_screen  | bob   carl    
Mon morning     | in_person     | alice bob     
Mon afternoon   | phone_screen  | alice bob     
Mon afternoon   | in_person     | alice bob     
Tue morning     | phone_screen  | alice bob     
Tue morning     | in_person     | alice bob     
Tue afternoon   | phone_screen  | alice bob     
Tue afternoon   | in_person     | alice bob     
Wed morning     | phone_screen  | alice bob     
Wed morning     | in_person     | alice bob     
Wed afternoon   | phone_screen  | alice bob     
Wed afternoon   | in_person     | alice bob

Но это не совсем то, что я хочу. Кандидат на собеседование должен присутствовать только на двух общих собраниях (одно phone_screen и одно in_person), тогда как вышеупомянутое «решение» показывает 12. Я хочу закончить примерно так: 

Mon morning     | phone_screen  | bob   carl      
Mon afternoon   | in_person     | alice bob

Поэтому Требование (2):

Каждый тип собрания должен происходить только один раз

Требование решения (2) по какой-то причине сложнее, даже если кажется, что я должен следовать очень похожей стратегии. 

## Requirement 2: Ensure only 1 of each type of meeting exists
for meeting in meetings:
  per_meeting_data = []
  for user in users:
    for day in days:
      for time in times:
        per_meeting_data.append(data[(meeting, day, time, user)])
    # Ensure the number of attendees for this meeting type on all days is 2
    model.Add(sum(per_meeting_data) == 2)

Добавление приведенного выше кода приводит к сбою в качестве решения INFEASIBLE. Куда я иду не так?

1 Ответ

1 голос
/ 12 января 2020

Разве ваше первое требование не должно быть? 

for meeting in meetings:
  for day in days:
    for time in times:
      per_time_data = []
      for user in users:
        per_time_data.append(data[(meeting, day, time, user)])
      # notice the indentation and <=
      model.Add(sum(per_time_data) <= 2)

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

Что касается вашего второго требования, я не совсем понимаю это, вы хотите, чтобы каждая пара (пользователь, встреча) встречалась только один раз?

Если это так, вы можете просто сделать: 

for meeting in meetings:
    for user in users:
        per_meeting_data = []
        for day in days:
            for time in times:
                per_meeting_data.append(data[(meeting, day, time, user)])
        model.Add(sum(per_meeting_data) == 1)
...