42
С помощью точных (классических) методов и алгоритмов целочисленного
программирования возможно получение точной математической модели,
отвечающей всем ограничениям, но в сложного характера задачи составления
расписания эта модель будет громоздкой и сложной. Чтобы избежать этого,
применяется имитационное моделирование. В этом случае алгоритм оперирует
непосредственно расписанием и списком занятий, которые необходимо
включить в расписание (учебным планом). Процесс составления начинается с
пустого расписания, когда все занятия находятся в списке неучтенных занятий.
Далее алгоритм переходит от одного незаконченного расписания к
другому, стремясь наилучшим образом расставить все занятия, включенные в
список.
Процесс продолжается до тех пор, пока не будет сформировано полное
расписание или выполнится фиксированное количество итераций.
При реализации алгоритма, основанного на принципах имитационного
моделирования, особое внимание уделяется разработке эвристических правил
выбора очередного занятия из списка, определения наилучшей для него позиции
в расписании и оценке получаемого расписания.
К положительным чертам такого подхода можно отнести возможность
детального учета специфики решаемой задачи в случае составления расписания
для конкретного вуза. Однако при этом сильно ограничивается возможность
применения разработанной системы в других учебных заведениях. Кроме того,
по-видимому, понадобится вносить существенные изменения в алгоритм при
незначительных внутренних изменениях в ВУЗе.
Так как алгоритм основан на действиях, совершаемых специалистом при
составлении расписания, то существует возможность организации деятельного
диалога между пользователем и системой при поиске оптимального расписания.
Подходы к автоматизации составления расписания.
Во многих университетах расписание формируется в ручном режиме,
составляется оно на картонных планшетах, мелким почерком карандашом на них
наносится сетка расписания. В таком же виде они распространяются по
факультетам и кафедрам. Найти нужную информацию или сделать
определенную выборку в такой ситуации крайне затруднительно. Поэтому как