Каков наиболее эффективный способ решить проблему планирования семинара? - PullRequest
Новая
       41

Каков наиболее эффективный способ решить проблему планирования семинара?

0 голосов
/ 27 мая 2019

Я пытаюсь разработать алгоритм для решения задачи планирования семинара.

Проблема заключается в следующем: мне нужно запланировать семинар, состоящий из конечного числа временных интервалов и конечного числа студентов.,Каждый временной интервал имеет емкость, которая должна быть выполнена.У каждого учащегося есть список предпочтений, соответствующий набору временных интервалов, в которых он / она хочет работать.

Например, представьте себе следующую мастерскую: , где временной интервал 1,1 имеет емкость 3 ивременной интервал 1,2 имеет емкость 4 и так далее.

Я хочу оптимизировать свое расписание, чтобы у студентов было как можно меньше накладных расходов.Накладные расходы определяются как необходимость «ждать» между работой.Например, на следующем рисунке показан студент, который может работать во всех трех временных интервалах за день, но назначается только первому и последнему, и, таким образом, имеет накладные расходы на один временной интервал. Таким образом: Моя цель состоит в том, чтобы найти выполнимое решение, минимизируя общие накладные расходы студентов.

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

График: Редактировать: Объяснение графика: На приведенном выше графике показаны 5 учеников, каждый из которых может быть подключен до 3 разслоты.Каждое ребро между учеником и временным интервалом символизирует, что студент хочет работать в этом конкретном временном интервале.Каждое из этих ребер имеет емкость 1. Исходный узел S имеет ребра для каждого ученика с неограниченной способностью, потому что каждый ученик может работать столько, сколько он / она хочет.Каждый фронт от временного интервала до узла-приемника T имеет емкость, соответствующую емкости конкретного временного интервала.

Псевдокод 

function solve-this(timeslots, students) {
    create graph from time slots and students
    run ford-folkerson max-flow algorithm to determine a feasible solution
    while(local optimal solution not found) {
        compute penalty / overhead
        if(computed penalty < current solution) {
            current solution = this solution
        }
        change schedule based on some sort of randomization factor
    }
    return solution
}

Есть ли какой-нибудь более умный способ сделать это?Является ли это наилучшим способом найти несколько оптимальное решение без проверки всех возможных графиков?

Любая помощь, комментарии и / или отзывы приветствуются.

...