Эвристика в составлении расписания занятий

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

В недалеком 2002 году, заканчивая ВУЗ (Ярославский филиал МЭСИ), специальность «Прикладная информатика в экономике», стояла задача выбора дипломной работы. Предложенный список тем удручил, в основном скучные разработки БД. В принципе мог бы какой-нибудь из моих имеющихся наработок взять за основу, как предлагал зав. кафедры, но кровь бурлила, хотелось сделать что-нибудь интересное и новое для себя. Предложил руководителю тему составления расписания, тем более что работал в ИТ-службе ВУЗа, и в моем ведении была система КИС УЗ (Комплексная информационная система управления учебным заведением), продукт ярославской компании. КИС УЗ была хороша, но составлять расписание сама не могла. Также, этим я преследовал цель сделать что-то полезное, но вышло так, что не было попыток внедрения в жизнь, может хоть публикация на хабре даст кому-нибудь пользу.

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

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



Что касается аудиторий, то я пошел на упрощение, убрал его из расписания, сделав ограничением, при поиске количество свободных аудиторий на конкретное время учитывалась. После генерации расписания во времени – расставлялись аудитории. В общем, вот такую простую модель я и очертил. Поэкспериментировал немножко с генетическим алгоритмом, на основе библиотеки в течение дня набросал программку, однако результат не понравился, и я, недолго думая, переключился на другие алгоритмы. Думаю, нехороший результат получился из-за моего неосновательного подхода, скорее всего, неудачно закодировал модель в терминах ГА. Начал думать о методе ветвей и границ. Пространство поиска представляет собой дерево, где уровень означает занятие, а ветвь – элемент сетки времени. Расписание считается путь от корня дерева до одной из висячих вершин. В пути, в процессе ветвления, проверяется возможность и целесообразность обхода по разным признакам: занятость преподавателя, группы, оценка. Обход дерева, естественно, вглубь. На каждом уровне находятся свободные ячейки сетки для текущего задания. Если постановщик «жестко» закрепил данное задание на определенное время, то строится одна ветвь, соответствующая определенному времени. Далее, проходя по ветви, находится оценка верхней границы (плюс к этому ведется контроль на наличие свободных аудиторий данного типа), и если оценка верхней границы выше оценки найденного лучшего на текущий момент расписания (и если есть свободная аудитория данного типа), то проходим по ветви, иначе переходим на следующую ветвь. В методе ветвей и границ ключевым и важным моментом является алгоритм нахождения оценки верхней границы. Не мудрствуя лукаво, оценивал текущее неполное расписание, и сравнивал с текущим лучшим найденным расписанием. Так как, погружаясь далее, оценка неполного расписания будет становиться хуже, то если она уже хуже оценки лучшего расписания, то ветвь бракуется. И так, запрограммировав все это дело, подготовив данные (брал из системы на основе реальных данных) запустил вечером и ушел домой. Утром, придя на работу, загрузил в КИС УЗ полученное лучшее из миллиарда найденных расписаний, однако без слез нельзя было на это смотреть. Я был разочарован, удручен и не знал, что дальше делать. Вечером пошли с друзьями попить пивка, и вот стою на остановке под хмелем и жду последний трамвай, а в голове одни деревья, ветви, границы, оценки… и тут до меня доходит, что надо каким то образом на каждом уровне, при определении ветвей, их сортировать, сделать так, чтобы сначала шли те варианты, которые вероятнее других были бы в составе лучшего расписания. Но каким образом это сделать? Мысль пришла, когда уже докуривал вторую сигарету. Надо, предварительно, строить для каждого субъекта расписания свои идеальные расписания, и для каждой ветви вычислять степень попадания в эти расписания, и сортировать по ней. Утром на работу шел быстрее обычного, по дороге рисуя в голове технические детали, к обеду эвристика была встроена, результат выглядел в КИС УЗ вполне достойно, и оставшиеся полрабочего дня я улыбался.

PS. Позднее, когда услышал о PageRank, подумал, что есть в нем нечто схожее с этой эвристикой.

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 7

    0
    внедрили?
    что делаете с тем, что преподаватель преподает только по вторникам и четвергам строго первые 2 пары, потому что он уже 20 лет так работает?
    с аудиториями я бы предложил следующее упрощение — у каждой кафедры N аудиторий, среди них и распределять занятия группы.
      +2
      предлагал нечто похожее. на этапе составления критериев составления расписания. (вместе с учебным отделом составляли — я на ноуте, они вручную) выяснилось, что критериев так много, что вручную сделать проще.
        0
        нет, даже попыток не было. Модель, которую реализовал, конечно, упрощенная, и предполагал, что есть много нюансов, которые только при внедрении раскрылись бы. И все эти нюансы надо было бы в 2 методах отобразить:
        — процедура построения ветвей, здесь все ограничения и вводятся, и строятся только валидные ветки; например, была возможность ручного определения конкретного занятия в сетке, и на уровне дерева, соотетствующей данному занятию была бы построена только одна ветвь.
        — процедура построение идеальных частных расписаний.

        И да, найденное расписание выгружалось в КИС УЗ не как готовое расписание. Там была область для составления предварительного расписания, которую потом закрепляли, и выгрузка шла туда, и была возможность ручного редактирования сотрудником учебного отдела. По моим предположениям, такой процесс мог бы и найти место в жизни, но предположения так и остались предположениями…
          0
          >с аудиториями я бы предложил следующее упрощение — у каждой кафедры N аудиторий, среди них и распределять занятия группы.

          учитывались тип аудитории и количество мест, эта информация была в БД, с которой брались исходные данные.
          0
          Странно, что я тебя молодой человек не знаю. И предложения свои видимо ты высказывал не туда :) Я как раз там начальником отдела ИТ работаю.
            0
            ничего странного, если учесть, что ты не обратил внимание на то, что история десятилетней давности. А тогда ты не работал. Я уволился из института в самом конце 2003-го и еще несколько лет захаживал постоянно, сейчас уже несколько раз обновился состав службы ИТО, и поэтому незнакомы.
              0
              :) Ясно. Я посмотрел на дату поста, а про 2002 год в содержании не учел :)
              Я думал у нас сейчас такие интересные личности учатся, ан нет, оказалось прошлое :)

          Only users with full accounts can post comments. Log in, please.