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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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