Создание алгоритма планирования на основе предпочтений

В настоящее время мы пытаемся создать соответствующее приложение, которое сопоставляет студентов и выпускников для мероприятия. Мероприятие состоит из нескольких временных интервалов, в каждом из которых каждый из студентов может быть закреплен за одним выпускником.

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

Алгоритм должен создать расписание, содержащее «справедливое» распределение студентов по выпускникам и временные интервалы.

Мы уже пришли к выводу, что, вероятно, не сможем найти оптимальное решение, поэтому мы хотим попытаться использовать локальный поиск, чтобы получить несколько «справедливое» расписание. Однако для запуска локального поиска нам сначала нужно создать несколько случайных (но действительных!) расписаний с учетом возможностей и ограничений. В этом алгоритме «случайного заполнения» мы сталкиваемся с некоторыми проблемами, поскольку не можем понять, как создать недетерминированный алгоритм, который с указанными выше ограничениями создает даже случайное расписание.

Мы попытались преобразовать проблему в задачу потока, но полученный граф слишком велик, чтобы решить его за разумное время, и мы попробовали какой-то подход FCFS, но всегда есть крайние случаи, в которых существуют конфликты, требующие алгоритма. чтобы войти в рекурсивный цикл, который может занять так много времени, что мы могли бы также переборщить с расписанием.

Хотя мы сами ничего не можем понять, нам кажется, что должна быть какая-то похожая задача, которую можно решить с помощью уже найденного ранее алгоритма. Если у кого-то есть опыт решения подобной проблемы, мы будем рады их помощи.

Думали ли вы о том, чтобы назначать их детерминистически, но игнорировать их предпочтения, а затем использовать алгоритмический подход, такой как имитация отжига, для постепенной замены назначений, если они удовлетворяют ограничениям, и улучшить некоторый общий рейтинг ранжирования, оценивая, сколько людей получили то, что они хотели? Или, может быть, даже просто полностью имитировать отжиг, включая ограничения присваивания как часть оценки, но проверяя в конце, что присвоения соответствуют ограничениям на числа?

Ian Mercer 22.05.2019 16:29

Каково примерное количество выпускников и студентов?

Richard 22.05.2019 18:23

Оценивают ли учащиеся свои предпочтения по всем выпускникам или только по N лучших?

Richard 22.05.2019 18:26

Студенты входят только в число лучших н выпускников, и в нем участвуют не более 1000 студентов и 500 выпускников с максимум 10 временными интервалами. На самом деле мы сначала рассматривали возможность создания простого действительного расписания (игнорируя предпочтения), но мы уже пытаемся найти алгоритм, который находит действительное решение, удовлетворяющее всем ограничениям.

Bubbleneck 23.05.2019 14:27
3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
1
4
561
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

  1. Если какой-либо желательный выпускник не достиг минимума в какой-то временной интервал, доступный для студента, то наиболее желательный такой выпускник в доступном интервале, наиболее удаленном от достижения минимума.
  2. Если какой-либо желаемый выпускник не достиг максимума в каком-то временном интервале, доступном для студента, то наиболее желаемый такой выпускник в доступном интервале, наиболее удаленном от достижения максимума.
  3. Если учащийся не достиг своего минимума, все выпускники во всех доступных слотах достигли максимума, и любой учащийся в этих слотах преодолел свой минимум, а затем поднимите назначенного учащегося. Выберите учащегося, основываясь на предпочтениях этого учащегося за вычетом того, что предпочтения учащегося максимально высоки (т. е. легче вытолкнуть кого-то из его 5-го слота, чем из 1-го), и разорвите ничью, вытолкнув учащегося, который больше всех превышает свой минимум.
  4. На этот раз без задания.

Распределите всех учащихся в случайном порядке и попытайтесь распределить их. Смешайте их снова и повторите. Остановитесь, когда есть проход без заданий вообще.

Этот алгоритм не гарантирует, что найдет лучшее решение или найдет решение. Но при разумных ограничениях вполне вероятно найти достойное решение за полиномиальное время.

Другие вопросы по теме