Алгоритм создания школьного расписания

96

Мне было интересно, есть ли известные решения для алгоритма создания школьного расписания. По сути, речь идет об оптимизации «часового разброса» (как в случае учителей, так и в классе) для определенных ассоциаций класс-предмет-учитель. Мы можем предположить, что у нас есть наборы классов, предметов уроков и учителей, связанных друг с другом на входе, и что расписание должно подходить между 8:00 и 16:00.

Я предполагаю, что для этого, вероятно, нет точного алгоритма, но, возможно, кто-то знает хорошее приближение или подсказки для его разработки.

Cand
источник
2
Спасибо за ответы на все вопросы. Похоже, алгоритм требует дополнительного изучения. Я бы посчитал это хорошим предметом для магистерской диссертации или небольшого коммерческого приложения. Если я напишу один, я дам Вам знать здесь;)
Cand
10
Как сказал Ян Рингроуз из StackOverflow, отвечая на другой вопрос, «есть еще много PHD в программном обеспечении для планирования».
Рид Дебаетс 02

Ответы:

89

Эта проблема NP-Complete !
Короче говоря, нужно изучить все возможные комбинации, чтобы найти список приемлемых решений. Из-за различий в обстоятельствах, в которых возникает проблема в разных школах (например: Есть ли ограничения в отношении классов? Разделяются ли некоторые классы на подгруппы некоторое время? Это еженедельное расписание? и т. д.) не существует хорошо известного класса задач, который соответствовал бы всем задачам планирования. Возможно, проблема ранца во многом похожа на эти проблемы в целом.

Подтверждением того, что это одновременно сложная проблема и проблема, решение которой люди постоянно ищут, является проверка этого (длинного) списка (в основном коммерческих) инструментов планирования программного обеспечения.

Из-за большого количества задействованных переменных, самым большим источником которых, как правило, являются желания преподавателя; -) ..., обычно нецелесообразно рассматривать перечисление всех возможных комбинаций . Вместо этого нам нужно выбрать подход, который обращается к подмножеству областей проблемы / решения.
- Генетические алгоритмы , процитированные в другом ответе, (или, IMHO, кажется ) хорошо оснащены для выполнения такого рода полууправляемого поиска (проблема заключается в том, чтобы найти хорошую функцию оценки для кандидатов, которые будут сохранены для следующего поколения)
- График Подходы переписывания также используются с этим типом задач комбинаторной оптимизации.

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

  • Определение и ранжирование всех известных ограничений
  • Сокращение проблемного пространства за счет добавления набора дополнительных ограничений вручную .
    Это может показаться нелогичным, но, например, предоставляя начальное, частично заполненное расписание (скажем, примерно 30% временных интервалов) таким образом, чтобы полностью удовлетворить все ограничения, и, считая это частичное расписание неизменным, мы значительно сокращаем время / пространство, необходимое для выработки возможных решений.
    Другой способ помочь дополнительным ограничениям - это, например, «искусственное» добавление ограничения, которое не позволяет преподавать некоторые предметы в некоторые дни недели (если это недельный график ...); этот тип ограничений приводит к сокращению пространства проблем / решений, как правило, без исключения значительного числа хороших кандидатов.
  • Обеспечение быстрого вычисления некоторых ограничений проблемы. Это часто связано с выбором модели данных, используемой для представления проблемы; идея состоит в том, чтобы иметь возможность быстро выбрать (или исключить) некоторые из вариантов.
  • Переопределение проблемы и разрешение несколько раз нарушить некоторые ограничения (обычно в направлении конечных узлов графа). Идея здесь состоит в том, чтобы либо удалить некоторые ограничения для заполнения последних нескольких слотов в расписании, либо заставить программу автоматического генератора расписания перестать стесняться завершения всего расписания, вместо этого предоставив нам список из дюжины или около того правдоподобных кандидаты. Человек часто находится в лучшем положении, чтобы решить головоломку, как указано, возможно, нарушив несколько ограничений, используя информацию, которая обычно не передается автоматизированной логике (например, правило «Никакой математики во второй половине дня» может быть нарушено в некоторых случаях для класса "продвинутая математика и физика" или "Лучше нарушить одно из требований мистера Джонса, чем одно из требований мисс Смит ... ;-))

Корректируя этот ответ, я понимаю, что он довольно стесняется дать определенный ответ, но, тем не менее, он полон практических предложений. Я надеюсь, что это поможет в том, что, в конце концов, является «сложной проблемой».

mjv
источник
1
Отличный, точный и подробный ответ, спасибо за подсказки и упоминание о NP-полноте (это тоже было моим предположением).
Кэнд
3
Есть ли у вас цитата, объясняющая NP-полноту этой проблемы?
Дон
50

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

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

  • учитель преподает и в вашей школе, и в другом институте. Понятно, что если он заканчивает урок там в 10.30, он не может начать у вас в 10.30, потому что ему нужно время, чтобы добираться между институтами.
  • два учителя женаты. В целом считается хорошей практикой не иметь двух женатых учителей в одном классе. Следовательно, эти два учителя должны иметь два разных класса.
  • два учителя женаты, и их ребенок учится в одной школе. Опять же, вы должны запретить двум учителям преподавать в том классе, где находится их ребенок.
  • в школе есть отдельные помещения, например, сегодня класс в одном институте, а в другой - в другом.
  • в школе есть общие лаборатории, но эти лаборатории доступны только в определенные будние дни (например, из соображений безопасности, когда требуется дополнительный персонал).
  • некоторые учителя предпочитают свободный день: кто-то предпочитает понедельник, кто-то пятницу, кто-то среду. Кто-то предпочитает приходить рано утром, кто-то - позже.
  • у вас не должно быть ситуаций, когда у вас будет урок, скажем, истории в первый час, затем три часа математики, затем еще час истории. Это не имеет смысла ни для учеников, ни для учителя.
  • аргументы следует распределить равномерно. Нет смысла проводить первые дни недели только по математике, а затем в остальные дни недели только по литературе.
  • Вы должны дать некоторым учителям два часа подряд для проведения оценочных тестов.

Как видите, проблема не NP-полная, это NP-безумная.

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

Стефано Борини
источник
12
"NP-insane" - отличное имя;) Я согласен, что это действительно сложная проблема, спасибо за комментарии по поводу "реального" подхода к этой проблеме. Мой отец и моя девушка тоже учителя, и я знаю, что в большинстве школ есть таблицы с пластиковыми вставками - это привело меня к мысли о возможном алгоритме решения этой проблемы - потому что, если мужчина сможет решить эту проблему, возможно, можно будет написать это как алгоритм.
Кэнд
10
вы хотите написать экспертную систему: систему, состоящую из набора эвристических правил. Помимо экспертных систем, это область, в которой генетические алгоритмы являются одними из лучших. Сложность не только в решении проблемы. Трудность также заключается в формулировке проблемы и ее ограничений.
Стефано Борини
1
Вы правы, проблема требует предоставления сложного набора условий и ограничений для выполнения, возможно, с оценкой «приемлемого» решения. Я согласен с генетическими алгоритмами, они должны хорошо подходить к этой задаче, также я думаю, что будет лучше начать разработку с простого набора условий и улучшать его по мере получения правильного ответа на них.
канд.
1
Вы также можете напрямую перевести эти ограничения и цели в MAXSAT. Алгоритмы MAXSAT, как правило, более надежны, чем генетические алгоритмы, но у вас может произойти взрыв предложений из-за таких целей, как математические классы должны быть распределены на неделю.
Жюль
27

На Международном соревновании по расписанию 2007 г. были предусмотрены дорожки для расписания уроков и экзаменов. В этом конкурсе участвовали многие исследователи. Было испробовано множество эвристик и метаэвристик, но в конце концов метаэвристики локального поиска (такие как Tabu Search и Simulated Annealing) явно превзошли другие алгоритмы (например, генетические алгоритмы).

Взгляните на 2 фреймворка с открытым исходным кодом, которые использовали некоторые из финалистов:

  • JBoss OptaPlanner (Java, открытый исходный код)
  • Unitime (Java, открытый код) - больше для университетов
Джеффри Де Смет
источник
17

Одним из моих промежуточных заданий было создание школьной таблицы по генетическому алгоритму.

Весь стол - это один «организм». Были внесены некоторые изменения и предостережения в подход к универсальным генетическим алгоритмам:

  • Были установлены правила для «незаконных столов»: два класса в одном классе, один учитель обучает две группы одновременно и т. Д. Эти мутации сразу же считались смертельными, и на месте «умершего» немедленно появлялся новый «организм». Первоначальный был сгенерирован серией случайных попыток получить легальный (хотя и бессмысленный). Летальная мутация не учитывалась при подсчете мутаций в итерации.

  • «Обменные» мутации были гораздо более распространены, чем «Модифицирующие». Изменения коснулись только тех частей гена, которые имели смысл - учителя нельзя было заменить классом.

  • Небольшие бонусы были назначены за объединение определенных 2 часов вместе, за последовательное назначение одной и той же общей классной комнаты для одной и той же группы, за поддержание непрерывности рабочего времени учителя и нагрузки класса. Умеренные бонусы назначались за предоставление правильных классных комнат по данному предмету, за соблюдение ограничений на часы занятий (утром или днем) и тому подобное. Большие бонусы были за правильное присвоение номера предмета, заданной нагрузки учителя и т. Д.

  • Учителя могут составлять свои графики нагрузки: «хочу работать тогда», «тогда можно работать», «тогда не любит работать», «тогда не могу работать», с правильными весами. Все 24 часа были законными рабочими часами, за исключением того, что ночное время было очень нежелательным.

  • Функция веса ... о да. Весовая функция была огромным чудовищным произведением (как в умножении) весов, присвоенных выбранным функциям и свойствам. Он был чрезвычайно крутым, одно свойство легко могло изменить его на порядок в большую или меньшую сторону - а в одном организме были сотни или тысячи свойств. Это привело к абсолютно ОГРОМНЫМ числам в качестве весов и, как прямой результат, к необходимости использовать библиотеку bignum (gmp) для выполнения вычислений. Для небольшого теста, состоящего из 10 групп, 10 учителей и 10 классных комнат, начальный набор начинался с отметки 10 ^ -200something и завершался 10 ^ + 300something. Когда он был более плоским, это было совершенно неэффективно. Кроме того, ценности выросли намного дальше с большими «школами».

  • По времени вычислений разница между небольшой популяцией (100) в течение длительного времени и большой популяцией (10k +) в течение меньшего количества поколений была небольшой. Вычисления за одно и то же время дали примерно такое же качество.

  • Расчет (на некоторых процессорах с тактовой частотой 1 ГГц) потребует около 1 часа для стабилизации около 10 ^ + 300, генерируя графики, которые выглядели довольно хорошо для указанного тестового примера 10x10x10.

  • Проблему легко решить, предоставив сетевые средства, которые будут обмениваться лучшими образцами между компьютерами, выполняющими вычисления.

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

SF.
источник
5
Так что откройте его, рекламируйте и попытайтесь привлечь к этому ученых? Повторно использовать его для дальнейших проектов? С технической точки зрения такая программа для 300 сотрудников будет стоить школам денег за создание оптимального расписания, и они не против потратить несколько дней на генетический расчет оптимального расписания. Подумайте о пакетной обработке. Привет, контракты на аппаратное и программное обеспечение;)
jcolebrand
1
Звучит здорово! Интересно, можно ли выполнить весовую функцию с числами с плавающей запятой в диапазоне 0..1.
Craig McQueen
1
@Craig: Что-то такое плоское приведет к тому, что популяция будет стагнирована или даже ухудшится по качеству со временем, поскольку случайные мутации вносят больше негативных изменений, чем может компенсировать селекция / селекция. Только очень качественная функция обеспечит устойчивый рост. Конечно, функция может быть нормализована, но все же ген «на ступень лучше» должен иметь на порядок больше шансов выжить.
SF.
9

Эта проблема сложнее, чем кажется.

Как уже упоминали другие, это NP-полная проблема, но давайте проанализируем, что это значит.

По сути, это означает, что вам нужно рассматривать все возможные комбинации.

Но «посмотри на» мало что скажет о том, что вам нужно делать.

Сгенерировать все возможные комбинации легко. Это может дать огромное количество данных, но у вас не должно возникнуть особых проблем с пониманием концепций этой части проблемы.

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

Для этого вам нужно больше, чем просто «возможно ли это решение».

Например, один и тот же учитель работает 5 дней в неделю в течение X недель подряд? Даже если это рабочее решение, оно может быть не лучшим решением, чем чередование двух человек, чтобы каждый учитель работал по одной неделе каждый. О, ты не думал об этом? Помните, вы имеете дело с людьми, а не только с проблемой распределения ресурсов.

Даже если бы один учитель мог работать полный рабочий день в течение 16 недель подряд, это могло бы быть неоптимальным решением по сравнению с решением, в котором вы пытаетесь чередовать учителей, а такую ​​балансировку очень сложно встроить в программное обеспечение.

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

Лассе В. Карлсен
источник
1
Что ж, я бы сказал, что довольно сложно знать все ограничения в начале, для этого нужен опыт и расследование вопроса. Я лучше разделю задачу на две отдельные части и буду разрабатывать их одновременно. Сначала будет общая структура алгоритма - сказано, как он должен заполнять «следующее поколение расписания», скорее проект механизма, без излишней «предметной логики» (вероятно, генетический алгоритм). Второй будет поставщиком правил с набором ограничений, которые проверяют «правильность» расписания - сначала оно может быть простым, а позже улучшенным.
Кэнд
8

Мой алгоритм расписания, реализованный в FET (бесплатное программное обеспечение для расписания, http://lalescu.ro/liviu/fet/ , успешное приложение):

Алгоритм эвристический. Я назвал это «рекурсивным свопингом».

Вход: набор действий A_1 ... A_n и ограничения.

Выход: набор времен TA_1 ... TA_n (временной интервал каждого действия. Комнаты здесь исключены для простоты). Алгоритм должен помещать каждое действие в определенный временной интервал, соблюдая ограничения. Каждый TA_i находится в пределах от 0 (T_1) до max_time_slots-1 (T_m).

Ограничения:

C1) Базовый: список пар действий, которые не могут быть одновременными (например, A_1 и A_2, потому что у них один и тот же учитель или одни и те же ученики);

C2) Множество других ограничений (здесь исключены для простоты).

Алгоритм расписания (который я назвал «рекурсивным переключением»):

  1. Сортировка занятий, сначала самое сложное. Не критичный шаг, но ускоряет алгоритм может быть в 10 и более раз.
  2. Постарайтесь разместить каждое действие (A_i) в разрешенном временном интервале, следуя приведенному выше порядку, по одному. Найдите доступный слот (T_j) для A_i, в котором можно разместить это действие с соблюдением ограничений. Если доступно больше слотов, выберите случайный. Если ничего не доступно, выполните рекурсивную замену:

    а . Для каждого временного интервала T_j подумайте, что произойдет, если вы поместите A_i в T_j. Будет список других действий, которые не согласуются с этим ходом (например, действие A_k находится в том же слоте T_j и имеет того же учителя или тех же учеников, что и A_i). Ведите список конфликтующих действий для каждого временного интервала T_j.

    б . Выберите слот (T_j) с наименьшим количеством конфликтующих действий. Скажем, список действий в этом слоте содержит 3 действия: A_p, A_q, A_r.

    c . Поместите A_i в T_j и сделайте A_p, A_q, A_r нераспределенными.

    d . Рекурсивно попробуйте разместить A_p, A_q, A_r (если уровень рекурсии не слишком велик, скажем 14, и если общее количество рекурсивных вызовов, подсчитанных с момента начала шага 2) на A_i началось, не слишком велико, скажем 2 * n), как на шаге 2).

    е . Если успешно размещены A_p, A_q, A_r, вернитесь с успехом, в противном случае попробуйте другие временные интервалы (перейдите к шагу 2 b) и выберите следующий лучший временной интервал).

    f . Если все (или разумное количество) временных интервалов были испробованы безуспешно, вернитесь безуспешно.

    г . Если мы находимся на уровне 0, и нам не удалось разместить A_i, поместите его, как в шагах 2 b) и 2 c), но без рекурсии. Теперь у нас есть еще 3 - 1 = 2 задания. Перейдите к шагу 2) (здесь используются некоторые способы избежать езды на велосипеде).

Ливиу Лалеску
источник
1
FET мне очень пригодился. Спасибо, @Liviu Lalescu!
Ноэль Ллеварес
6

ОБНОВЛЕНИЕ: из комментариев ... тоже должна быть эвристика!

Я бы пошел с Prolog ... затем использовал Ruby или Perl или что-то еще, чтобы очистить ваше решение до более красивой формы.

teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

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

Рид Дебаец
источник
1
Пролог, безусловно, отличный язык для выражения требуемых проблем, однако, как вы отметили: проблема ЯВЛЯЕТСЯ NP-полной, если не NP-сложной. Это означает, что Пролог может быть недостаточно быстрым для практической реализации.
Poindexter
3
если это имеет какое-либо отношение к NP, и нас не удовлетворит аппроксимация, любой детерминированный алгоритм будет экспоненциально отстой :)
Габриэль Щербак 01
1
Таким образом, цель состоит в том, чтобы реализовать эффективную эвристику ... например, простой алгоритм планирования 9 задач занимает 3,078 секунды, но с реализованной эвристикой smallestWindowFirst та же проблема занимает всего: 0,123 секунды
Рид Дебаетс, 01
2
ХАХА, пролог (один) НИКОГДА НЕ РЕШИТ ЭТО. Извините за заглавные буквы, но 10 или 15 лет назад у меня была такая же идея, и она полностью провалилась. Не то чтобы это было медленно, нет. Он просто не мог решить ни одного реального случая;)!
Каруселл
5

Вот несколько ссылок, которые я нашел:

Расписание занятий - список некоторых проблем

Гибридный генетический алгоритм для составления школьного расписания

Утилиты и инструменты для планирования

Нияз
источник
1
Ссылка на утилиты и инструменты планирования не работает
Баран
@Baran Используйте машину обратного пути, и вы найдете список
srijanshukla 01
3

В этой статье довольно хорошо описывается школьное расписание и подход к алгоритму: « Разработка программы - интерактивного планировщика на основе ограничений для школ и колледжей». [PDF]

Автор сообщает мне, что программное обеспечение SYLLABUS все еще используется / разрабатывается здесь: http://www.scientia.com/uk/

Leftium
источник
3

Я работаю над широко используемым механизмом планирования, который делает именно это. Да, это NP-Complete; лучшие подходы стремятся приблизить оптимальное решение. И, конечно, есть много разных способов сказать, какое из них является «лучшим» - что важнее, чтобы учителя были довольны своим расписанием, или, например, чтобы ученики посещали все свои классы?

Абсолютно самый важный вопрос, который вам нужно решить на раннем этапе, - что делает один способ планирования этой системы лучше другого ? То есть, если у меня есть расписание, в котором миссис Джонс преподает математику в 8 лет, а мистер Смит преподает математику в 9, это лучше или хуже, чем в расписании, когда они оба преподают математику в 10? Это лучше или хуже, чем когда миссис Джонс преподает в 8 лет, а мистер Джонс преподает в 2 года? Зачем?

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

Этап оптимизации локального поиска часто используется для «полировки» конечного ответа и достижения лучших результатов.

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

Том Диббл
источник
2

Как правило, программирование с ограничениями является хорошим подходом к этому типу задач планирования. Поиск по «программированию с ограничениями» и планированию или «планированию на основе ограничений» как в пределах стека, так и в Google даст несколько хороших ссылок. Это не невозможно - просто об этом немного сложно подумать при использовании традиционных методов оптимизации, таких как линейная или целочисленная оптимизация. Один из выходов - существует ли расписание, удовлетворяющее всем требованиям? Это само по себе, очевидно, полезно.

Удачи !

Грембо
источник
2

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

Permaquid
источник
2

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

Есть и другие удачные подходы. Все реализовано в open source проектах:

  • Подход на основе ограничений
    • Реализовано в UniTime (не совсем для школ)
    • Вы также можете пойти дальше и использовать целочисленное программирование. Успешно выполнено в университете Удине, а также в университете Байройта (я был там задействован) с использованием коммерческого программного обеспечения (ILOG CPLEX)
    • Подход на основе правил с эвристикой - см. Планировщик Drools
  • Различная эвристика - FET и моя собственная

См. Здесь список программного обеспечения для расписания

Karussell
источник
0

Я думаю, вам следует использовать генетический алгоритм, потому что:

Также посмотрите: аналогичный вопрос и еще один

Betamoo
источник
0

Я не знаю, что кто-то согласится с этим кодом, но я разработал этот код с помощью своего собственного алгоритма и работает для меня в ruby. Надеюсь, это поможет им, кто ищет его в следующем коде: periodflag, dayflag subjectflag и teacherflag - это хэш с соответствующим идентификатором и значением флага, которое является логическим. По любым вопросам, свяжитесь со мной ....... (-_-)

periodflag.each do | k2, v2 |

            if(TimetableDefinition.find(k2).period.to_i != 0)
                subjectflag.each do |k3,v3|
                    if (v3 == 0)
                        if(getflag_period(periodflag,k2))
                            @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
                            @teacherlists=Employee.find(@teachers)
                            teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] 
                            teacherflag.each do |k4,v4|
                                if(v4 == 0)
                                    if(getflag_subject(subjectflag,k3))
                                        subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
                                        if subjectperiod.blank?
                                            issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
                                            if issubjectpresent.blank?
                                                isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
                                                if isteacherpresent.blank?
                                                    @finaltt=TimetableAssign.new
                                                    @finaltt.timetable_struct_id=@timetable_struct.id
                                                    @finaltt.employee_id=k4
                                                    @finaltt.section_id=section.id
                                                    @finaltt.standard_id=standard.id
                                                    @finaltt.division_id=division.id
                                                    @finaltt.subject_id=k3
                                                    @finaltt.timetable_definition_id=k2
                                                    @finaltt.timetable_day_id=k1
                                                    set_school_id(@finaltt,current_user)
                                                    if(@finaltt.save)

                                                        setflag_sub(subjectflag,k3,1)
                                                        setflag_period(periodflag,k2,1)
                                                        setflag_teacher(teacherflag,k4,1)
                                                    end
                                                end
                                            else
                                                @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
                                                @finaltt=TimetableAssign.new
                                                @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
                                                @finaltt.employee_id=@subjectdetail.employee_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @finaltt.subject_id=@subjectdetail.subject_id
                                                @finaltt.timetable_definition_id=k2
                                                @finaltt.timetable_day_id=k1
                                                set_school_id(@finaltt,current_user)
                                                if(@finaltt.save)

                                                    setflag_sub(subjectflag,k3,1)
                                                    setflag_period(periodflag,k2,1)
                                                    setflag_teacher(teacherflag,k4,1)
                                                end
                                            end
                                        end
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end

источник