Алгоритм вращения расписания?

Я пытаюсь составить расписание обучения, в котором у учителя есть определенное количество учеников, которые будут преподавать индивидуально (например, на уроках музыки) один раз в неделю. Ученики должны меняться, то есть их нельзя обучать в одно и то же время, неделя за неделей (минимальный допустимый промежуток между уроками в одно и то же время я называю «периодом ротации»). Придумать простейшую форму тривиально:

        Week 1  Week 2  Week 3  Week 4  Week 5  Week 6
10.00   Alice   Edgar   David   Charles Bertha  Alice
10.30   Bertha  Alice   Edgar   David   Charles Bertha
11.00   Charles Bertha  Alice   Edgar   David   Charles
11.30   David   Charles Bertha  Alice   Edgar   David
12.00   Edgar   David   Charles Bertha  Alice   Edgar

Но я хочу, чтобы пользователь мог добавлять правила, например, Алиса не может сделать 10.30 или 11.00 на неделе 3 и т. Д. Я начал с простого цикла возврата, но вскоре понял, что количество возможностей делает это практически осуществимым. Я не очень опытный программист и понимаю, что это может привести меня к продвинутым методам программирования. Но если бы кто-нибудь мог дать мне несколько идей о том, как подойти к проблеме, я был бы очень благодарен. Я, конечно, искал помощи, но большая часть обсуждения, кажется, посвящена более сложной задаче создания всего школьного расписания. Стоит ли в этом разбираться с генетическим программированием? Я создаю программу как веб-страницу, используя php.


php algorithm timetable genetic-algorithm
person gregston    schedule 12.11.2013    source источник
comment
Подобные сценарии «что, если» лучше всего обрабатываются с помощью механизма правил, такого как Drools (jboss.org /drools/drools-expert.html). Это, вероятно, крутая кривая обучения, но в конечном итоге, вероятно, принесет вам лучший и самый гибкий результат.   -  person Shazbot    schedule 12.11.2013

Ответы (3)


arrow_upward
0
arrow_downward

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

Я знаю, что решатели судоку работают для 9 на 9 и решают за доли секунды. В зависимости от размера ваших занятий / недель эти методы могут быть применимы без использования эвристических решателей (или генетических алгоритмов и т. Д.). Я бы предложил wiki и посмотрел на обратное отслеживание, точно прикрыть или (как они это называют) перебором.

Если это не поможет. Не могли бы вы пояснить, каких правил вы ожидаете от своих окончательных расписаний? Например, минимизация количества свопов из расписания "по умолчанию" или чего-то подобного? Кроме того, есть ли причина, по которой вы рассматриваете это как проблему на несколько недель? Можно ли свести проблему к недельной проблеме без связи / соединения между неделями? Наконец, как вы представляете свои исключения? Как вы указываете, какое время плохое для каких учеников?

person abaines    schedule 12.11.2013
comment
Студенты могут посещать занятия в одно и то же время, но только после определенного минимального периода (например, можно пропускать физкультуру один раз в месяц, но не каждую неделю). В моем примере это 5, поэтому, например, Алиса может снова сделать 10,00 через пять недель. По этой причине это проблема нескольких недель. Я все же посмотрю на Содуко - как вы говорите, очень похоже. Пользователь должен иметь возможность добавлять столько правил, сколько ему нравится, хотя это может сделать решение невозможным - и он хотел бы знать об этом. - person gregston; 13.11.2013

arrow_upward
0
arrow_downward

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

Одна вещь, которая работает в вашу пользу (по сравнению с более общими задачами с расписанием), - это ограничение, которое заставляет учащихся проводить урок в разное время каждую неделю. Это значительно сокращает пространство поиска. Думаю, я прав, говоря, что количество возможных перестановок таково:

n! * (n - 1)!

где n - количество студентов, а также количество недель, на которые составлено расписание.

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

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

Если у вас не так много ограничений, этот метод должен быстро создать действительное расписание. С другой стороны, если есть достаточно ограничений, чтобы сделать расписание невозможным, тогда потребуется огромное количество проверок, чтобы убедиться, что расписание не является действительным (у 6 студентов есть 86 400 проверок, но это быстро растет с количеством студентов).

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

person Rich Smith    schedule 14.11.2013

arrow_upward
0
arrow_downward

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

Я использую два простых цикла с возвратом, по одному для каждого столбца и по одному для каждого слота в нем. Самый ограниченный столбец вычисляется каждый раз, и если столбец не может быть заполнен, он очищается, и мы возвращаемся к последнему заполненному. Каждый слот запомнил свой набор возможных вариантов, поэтому мы можем продолжить с того места, где остановились. Первый цикл ищет аккуратный блок учеников, как в примере выше. Если это не удается, аналогичный цикл позволяет столбцу начинаться и заканчиваться позже, если слотов больше, чем учеников. Если это все еще не работает, третий цикл допускает пропуски в столбце (что не очень хорошо для учителя). Если кто-то хочет увидеть его в действии, он находится здесь: http://www.studio-soft.co.uk/timetables/

(в данный момент активна только первая петля).

Gregston

person gregston    schedule 25.11.2013