Содержание к диссертации
Введение
ГЛАВА 1. Обзор и анализ существующих подходов и моделей, постановка научной проблемы и основные этапы её решения 17
1.1. Обзор и анализ существующих методов и моделей составления расписаний учебных занятий 17
1.1.1. Основные направления решения задачи составления расписания учебных занятий 17
1.1.2. Точные алгоритмы генерации расписаний 18
1.1.3. Эвристические подходы 25
1.1.4. Диалоговые методы 35
1.2. Общая постановка задачи составления расписания на примере МГУПБ 37
1.2.1. Этапы постановки задачи автоматизации создания расписания учебных занятий 37
1.2.2. Документы, используемые при планировании учебного процесса и составлении расписания 38
1.2.3. Ограничения и пожелания, учитываемые при составлении расписания 41
1.2.4. Требования к разрабатываемой программе 43
Выводы по главе 1 45
ГЛАВА 2. Формализация задачи, математическая модель составления расписания учебных занятий в высшем учебном заведении 46
2.1. Математическая модель задачи составления расписания учебных занятий в вузе 46
2.2. ЛГР-трудность задачи составления расписания учебных занятий 58
2.3. Методика оценки и сравнения различных вариантов расписаний .60
2.4. Иерархическая многоуровневая схема упорядочения критериев по их значимости 62
Выводы по главе 2 64
ГЛАВА 3. Алгоритмы решения задачи составления расписания учебных занятий в высшем учебном заведении 65
3.1. Эвристический алгоритм составления расписания 65
3.1.1. Исследование критичности занятий при формировании расписаний. Разработка алгоритма назначения занятий... 65
3.1.2. Разрешение конфликтных ситуаций возникающих при распределении заявок . 73
3.2. Решение задачи с использованием генетического алгоритма 80
3.2.1. Представление расписания в виде хромосомы (chromosomal representation) .82
3.2.2. Начальное решение (initial population).. 82
3.2.3. Селекция (selection) 82
3.2.4. Система скрещивания 88
3.2.5. Кроссовер (crossover) 88
3.2.6. Мутация (mutation) :...,..90
3.2.7. Естественный отбор 90
3.2.8. Оценка расписания (fitness evaluation) 94
3.2.9. Условия завершения (stopping conditions, termination) 94
Выводы по главе 3 96
ГЛАВА 4. Описание практической реализации автоматизированных систем составления расписаний 97
4.1. Архитектура разработанных систем 97
4.2. Описание программного обеспечения применявшегося для решения задач 100
4.3. Программное обеспечение необходимое для функционирования программ 100
4.4. Автоматизированная система составления расписания учебных занятий 101
4.4.1. Функциональная структура системы составления расписания учебных занятий 101
4.4.2. Сравнительный анализ автоматизированной системы "Университетское расписание" с аналогичными программами 105
4.4.3. База данных автоматизированной системы составления расписания учебных занятий 112
4.5. Автоматизированная система планирования графиков работы сотрудников 116
4.5.1. Функциональное назначение программы 116
4.5.2. Обзор разработанных алгоритмов для решения задачи составления графиков работы персонала 125
Выводы по главе 4 130
Заключение 132
Литература 135
Приложения 164
- Документы, используемые при планировании учебного процесса и составлении расписания
- Иерархическая многоуровневая схема упорядочения критериев по их значимости
- Разрешение конфликтных ситуаций возникающих при распределении заявок
- Функциональная структура системы составления расписания учебных занятий
Введение к работе
Актуальность проблемы
Задачи синтеза расписаний являются предметом широких научных исследований с середины XX века. Область их применения включает в себя такие различные сферы человеческой деятельности, как промышленность, транспортные перевозки, образование, массовое обслуживание и т. д. Практика выдвигает множество задач, которые невозможно эффективно решать путем полного перебора. Для большинства моделей теории расписаний нахождение оптимального расписания является трудноразрешимой задачей, а решение приближенных к реальным условиям задач обладает ещё большей сложностью, т.к. данные решения должны удовлетворять многочисленным, зачастую конфликтующим между собой ограничениям производственного, организационного и психофизиологического характера. Главной проблемой здесь является большая многовариантность, не позволяющая за приемлемое время получать оптимальное решение. Выходом из данного положения является отказ от подхода, когда пригодным считается только самое лучшее решение. Это направление, получило в последние десятилетия широкое развитие в дискретной оптимизации — направление построения эффективных алгоритмов приближенного решения NP-трудных задач, детерминистические методы решения, для которых, неприемлемы или не обеспечивают необходимой степени точности. В данной работе рассмотрены две задачи подобного класса, возникающие в конкретных областях управленческой деятельности — составление расписаний учебных занятий в вузе и планирование графиков работы персонала в организациях с плавающими режимами работы. Данные задачи являются, задачами на размещение требований в ограниченные ресурсы, с нелинейными ограничениями и критериями, в виде формул исчисления предикатов, принимающими дискретные значения. В силу М*-трудности эти задачи, для своего решения требуют разработки эффективных приближённых методов.
Количественный и качественный рост высшей школы требует нового подхода к решению задач управления учебной, научной и хозяйственной деятельностью вузов. Этот подход в последние годы находит свое воплощение в применении современных средств вычислительной техники и математических методов в управлении высшими учебными заведениями. В современном мире всё большее внедрение получают различного рода системы автоматизации тех процессов, которые всегда выполнялись вручную. Например, системы принятия решения в маркетинге, экспертные системы заменяющие опытных специалистов, прогнозирующие системы в самых различных областях науки и техники. К таким же процессам относится и составление расписания, которое до сих пор во многих учебных заведениях составляется вручную, на основе многолетнего опыта. Современная наука располагает средствами, позволяющими наилучшим образом организовать любой процесс, в том числе и учебный.
Задача планирования расписания учебных занятий - это задача на составление расписания комбинаторного типа, характерной особенностью, которой является огромная размерность и наличие большого числа ограничений сложной формы. Фактически, в настоящее время, не существует универсальных методов решения таких задач. Математическая (классическая) теория расписаний [105; 224; 227; 233] охватывает лишь узкий круг хорошо формализуемых проблем, которые обычно сводятся к задачам коммивояжера, транспортной и т.п. Прямое применение каких-либо данных методов к задаче составления расписания учебных занятий не представляется возможным. Тем не менее, есть ряд эвристических и переборных методов, которые вполне поддаются программированию.
Существует мнение [183], что опытный диспетчер может составить расписание так, что оно будет в большей степени отвечать интересам учебного процесса и общественной жизни образовательного учреждения. Однако с этим нельзя согласиться. Ручное решение задачи составления расписания занятий требует наличия больших затрат времени, квалифицированных специалистов, в то время как результат такого решения во многих случаях получается далеко не оптимальным. Речь идёт не о том кто лучше составит расписание компьютер или человек, т.к. в реальности существует не автоматическое, а автоматизированное составление расписания. После ввода исходной информации требуется её согласование, т.к. невозможность получения требуемого расписания может быть определена ещё на этапе анализа. Во время составления расписания возможно возникновение тупиковых ситуаций. Всё это требует изменения исходных данных и ослабления ограничений, здесь без человека не обойтись. Без внесения данных изменений расписание не будет иметь практической ценности. Здесь также следует учесть тот момент, что расписание может изменяться и во время его использования, т.е. после его составления, и здесь весьма важен человеческий фактор. В этом плане важна поддержка данного процесса, путем применения автоматизированных методов и процедур. Основное преимущество состоит в том, что автоматизированное составление убирает массу рутинной работы, такой как поиск возможных вариантов внесения очередных элементов в расписание, проверки выполнения требований, поиска случайных ошибок в готовом расписании, оформления расписания на бумаге в виде различных таблиц (для преподавателей, групп, покабинетного), оставляя человеку больше времени на более интеллектуальные действия. Компьютер, в данном; случае, также, является инструментом, существенно усиливающим способности человека, т.к. человек не в состоянии перебрать и проанализировать такое же количество вариантов расписаний как компьютер.
Изучение опыта создания подобных систем (см. приложение 5), показывает, что в последние годы предпринимались множественные попытки совершенствования планирования учебного процесса, путем построения алгоритмов оптимизации задач планирования учебной работы вуза и последующей их реализацией на вычислительной технике. В первую очередь это попытки решения задачи составления расписаний занятий, являющейся, как известно, самой сложной в подсистеме планирования. Такие исследования в разное время проводились и продолжаются в некоторых вузах [66; 180]. Однако практическое внедрение планирования учебного процесса с использованием компьютерной техники имеет место лишь в немногих вузах. Анализ состояния этих разработок позволяет сделать следующие выводы:
Разработка и внедрение вузами задач АСУ осуществляется в инициативном порядке и эти работы, как правило, направлены на решение отдельных задач. Разобщенность групп исследователей и разработчиков привела к созданию множества систем, направленных на разработку алгоритмов и программ, рассчитанных на обслуживание только конкретного вуза.
Существующие системы не учитывают специфику составления расписаний в нашем университете (ограниченный аудиторный фонд, невозможность задания требуемых ограничений).
Многие системы возлагают на разработчика расписания всю ответственность за учет реальных требований. В частности, учет требований преподавателей, ограничений на количество проводимых занятий в день, в неделю, необходимые переносы и "урезки" занятий в случае нехватки ресурсов - все эти и многие другие рутинные задачи в таких системах приходится решать человеку, чаще всего наугад, методами перебора.
Имеющиеся программы не предполагают многопользовательский режим работы и не поддерживают весь необходимый электронный документооборот. Выходные документы не соответствуют по форме применяемым в нашем вузе. Отсутствуют возможности настройки шаблонов документов.
При планировании не обеспечивается единство информационного и программного обеспечения и технической базы.
Отсутствует системный подход к использованию компьютерной техники в управлении вузом, т.е. задачи разрабатываются при отсутствии технических заданий и технических проектов.
Почти не выполняются работы по разработке типовых унифицированных элементов для создания единой автоматизированной системы для управления высшей школой.
Имеющиеся программы имеют весьма неудобный интерфейс для ввода исходных данных и редактирования полученного расписания.
В связи с расширением работ по совершенствованию системы управления высшей школой путем создания и внедрения в вузах различных автоматизированных систем управления возникла необходимость в унифицировании средств составления учебного расписания на вычислительной технике. Для этого необходимо четко формализовать требования к расписанию и разработать соответствующее алгоритмическое обеспечение.
При разработке алгоритмов автоматизированного составления расписания занятий остро стоит проблема создания универсальных алгоритмов, учитывающих специфику условий каждой конкретной задачи. Такие алгоритмы должны быть достаточно "гибкими" в том смысле, чтобы без существенного их изменения можно было включать и исключать требования из системы требований к расписанию. Однако попытка решать задачу каким-либо одним единственным универсальным алгоритмом, на данный момент не представляется возможным. Алгоритмы позволяющие решать широкий класс задач не дают той эффективности, как более конкретные, адаптированные с учётом конкретных условий, алгоритмы.
Для систем составления расписания занятий характерна сильная зависимость от специфики конкретных учебных заведений уже на уровне математических моделей и представления данных, что затрудняет использование типовых систем. Это усугубляется разобщенностью групп исследователей и разработчиков. Систему созданную в одном вузе обычно без изменения и доработки невозможно эффективно использовать в другом. К тому многие из них создава- лись достаточно давно и с их помощью невозможно эффективно решать поставленную задачу.
Для решения поставленных проблем, требуется построение гибкой и легко адаптируемой системы на основе новых принципов, с использованием современных компьютерных технологий. Необходима система, составляющая расписание в соответствии с выбранными критериями и заданными требованиями, т.е. берущая на себя как можно больше функций человека, чтобы расписание приходилось меньше доводить вручную. Данные возможности должны осуществляться также, без изменения исходного кода системы, чтобы использоваться пользователями-непрограммистами. Для покрытия наиболее типичных случаев, необходимо создание нескольких типовых алгоритмов, реализующих составление расписаний. Нужна система поддержки принятия решений, имеющая возможность настройки, потенциально учитывающая всевозможные ограничения и пожелания. Данная система должна иметь возможность дополнения и изменения существующей базы данных и пользовательского интерфейса, а также обеспечивать возможность самостоятельно подключения дополнительных самостоятельно разработанных алгоритмов, возможно с вызовом некоторых предоставляемых системой типовых алгоритмов. Всё это давало бы возможность задавать в каждом вузе требования, отвечающие его условиям, и, с помощью подбора и настройки подходящего алгоритма, получать требуемое расписание.
Цель работы.
Целью работы является разработка математических моделей, методов и алгоритмов для создания автоматизированной системы составления расписания занятий в вузе, а также системы оптимизации графиков работы персонала в организациях с плавающими режимами работы.
Задачи исследования. исследование прикладной области и систематизация принятой технологии разработки расписаний; формирование и формализация ресурсных, учебно-организационных, формальных ограничений и синтез критериев допустимости и рациональности расписаний; разработка структуры реляционной базы данных для хранения информации необходимой при подготовке и составлении расписания занятий в вузе, а также структура базы данных для задачи составления графиков работы персонала; анализ существующих подходов и моделей к составлению расписаний; разработка математических моделей синтеза расписания занятий в вузе и составления графиков работы персонала; разработка автоматизированных методов, процедур и алгоритмов построения и рационализации расписаний в соответствии с выбранными критериями; синтез состава и структуры автоматизированных систем обработки информации и управления для составления расписаний и их реализация.
Методы исследования.
Основные теоретические результаты диссертационной работы получены с использованием аппарата системного анализа, теории графов, математического моделирования, дискретной математики, теории расписаний, численных методов, теории сложности вычислений, а также современных методов программирования.
Научная новизна и значимость работы.
К научной новизне можно отнести следующие результаты:
Сформулирована расширенная постановка задачи составления расписания занятий в вузе и предложена методика её решения на основе формализованных знаний.
Формализован новый класс задач теории расписаний для составления графиков работы в организациях с плавающей нагрузкой.
Разработаны эвристические и генетические алгоритмы решения поставленных задач составления расписаний.
Предложены алгоритмы типа ветвей и границ для задачи планирования графиков работы в организациях с плавающей нагрузкой.
Практическая ценность работы.
Прикладная значимость выполненных исследований определяется следующими полученными в диссертации результатами:
Разработан программный комплекс «Университетское расписание» для составления расписания учебных занятий. Данная система имеет трёхзвенную архитектуру, позволяющую снизить время на её обслуживание, что особенно актуально для крупных вузов, поддерживает распределённый ввод и обработку информации.
Разработана информационная модель планирования учебного процесса.
Построены логические и физические модели баз данных в нотации IDEF1X для хранения информации при составлении расписаний работы персонала и учебных занятий в вузе. Предложены специальные соглашения и принципы организации баз данных, позволяющие сократить сроки проектирования и повысить качество программного обеспечения.
Разработана программа для составления расписаний в организациях с плавающей нагрузкой, определения оптимальной численности персонала и оптимальной расстановки сотрудников по штатным единицам.
На базе объектно-ориентированной методологии разработаны методика и программная реализация для создания автоматизированных систем состав- ления расписаний. Созданы средства автоматической генерации исходного кода для данного типа приложений.
На защиту выносятся следующие основные положения и результаты:
Математические модели составления расписания учебных занятий в вузе и организациях с плавающей нагрузкой.
Структура автоматизированной системы для составления расписания учебных занятий в вузе, информационная модель формирования расписания занятий, логическая и физическая модели баз данных.
Эвристический и генетический алгоритмы для составления расписания учебных занятий в вузе. Подзадачи, возникающие на различных этапах планирования.
Автоматизированная система планирования графиков работы персонала в организациях с плавающей нагрузкой, и разработанные для неё эвристические алгоритмы и алгоритмы типа ветвей и границ.
Внедрение результатов работы.
Программный комплекс для составления расписания учебных занятий в вузе используется при составлении расписаний в МГУПБ, что подтверждается актом внедрения. Программа "Университетское расписание" ("UniSched") и база данных "Расписание учебных занятий в вузе" ("UniSched DB") зарегистрированы в Роспатент РФ. Свидетельства № 2004610313 и № 2004620036.
Разработанная подсистема для планирования графиков работы персонала в организациях с плавающей нагрузкой использована в программном комплексе "АиТ:\Управление персоналом", что подтверждается актом внедрения, и применяется широким числом пользователей данного комплекса.
Апробация работы.
Основные положения и результаты данной работы изложены и обсуждены на:
Учебно-методической конференции "Применение информационных технологий в учебном процессе" (Москва, 1999 г.);
Четвёртой международной научно-технической конференции "Пища, Экология, Человек" (Москва, 2001 г.);
Второй всероссийской научно-технической конференции "Теория конфликта и её приложения" (Воронеж, 2002 г.);
Пятом международном симпозиуме "Интеллектуальные системы" (Калуга,
2002 г.); XV Международной научной конференции "Математические методы в технике и технологиях" (Тамбов, 2002 г.);
Всероссийской научной конференции "Современные проблемы математики, механики, информатики" (Тула, 2002 г.); XI международной научно-технической конференции "Математические методы и информационные технологии в экономике, социологии и образовании" (Пенза, 2003 г.); VII международной научно-методической конференции "Университетское образование" (Пенза, 2003 г.);
Международной научно-методической конференции "Компьютеризация обучения и проблемы гуманизации образования в техническом вузе" (Пенза,
2003 г.); XIV Международной конференции "Применение новых технологий в образовании " (Троицк, 2003 г.);
Третьем украино-российском научно-техническом и методическом симпозиуме "Современные информационные технологии в науке, производстве, образовании и управлении" (Хмельницкий, 2003 г.);
Международной научной конференции "Инновации в науке и образовании -2003" (Калининград, 2003 г.)
Публикации. По теме диссертации опубликовано 17 печатных работ, в том числе 11 докладов в материалах и трудах Международных и Всероссийских конференций и 4 публикации в тезисах докладов, 2 свидетельства об официальной регистрации.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав с выводами, заключения, библиографии и 8 приложений. Объем работы 217 страниц основного текста, включая 15 рисунков и 3 таблицы. Список использованных источников содержит 302 наименования.
Документы, используемые при планировании учебного процесса и составлении расписания
Эвристические методы не гарантируют построения допустимых или оптимальных расписаний. Во многих системах предусматривается возможность в случае тупиковой ситуации начать следующую попытку построения расписания с самого начала с измененными исходными данными. Также предлагается достройка частично сгенерированного расписания вручную. Необходимость корректировки данных возникает также из-за нарушения требований, в связи с неполнотой применяемой математической модели, или при диспетчировании, для замен в расписании в ходе учебного процесса. Средства для такой корректировки баз данных, содержащих исходную информацию и расписания, предусматривались в довольно ранних разработках. Очевидно, они не имели развитой диалоговой поддержки.
С появлением персональных компьютеров и мощных программных средств обработки информации (электронных таблиц, систем управления базами данных) возникли новые возможности для применения диалога при автоматизации составления расписаний. Многие учебные заведения применяют редакторы текстов, электронные таблицы и специализированные программы для подготовки различных документов и оформления расписаний.
Появились программы, предназначенные для расчета распределения нагрузки среди преподавателей кафедры, распределения штатов преподавателей по подразделениям, управления аудиторным фондом, автоматизации составления рабочих документов учебного отдела и выполнения других функций, связанных с подготовкой информации для составления расписания (см. приложе-ние5:[3],[4],[31]).
Возникли программы, поддерживающие составление расписания только вручную (см. приложение 5: [35, 36]). Данные диалоговые программы предоставляют составителю возможность ввода и редактирования исходных данных и элементов расписания с помощью форм и таблиц, проверяют выполнение требований в ходе ввода и не допускают их нарушения или сообщают о возникших конфликтах. Для диагностирования используются известные методы проверки непротиворечивости и целостности баз данных. Для обеспечения минимального времени ответа при диалоге важную роль играет проектирование структур данных (см. приложение 5: [36]). Системы также могут сообщать составителю по запросам необходимую в ходе составления информацию (незанятые уроки у преподавателей и классов, свободные аудитории, неспланированные занятия определенных типов). Многие специалисты высказываются в пользу этого подхода, из-за избыточного числа критериев, учитываемых на практике, отвергая какие-либо средства автоматической генерации. Но проблема в том, что в этом случае эти критерии приходится учитывать вручную, а в результате — стохастически сверстанное расписание, которое потом перекочевывает с небольшими вариациями из года в год. Пользователь не имеет возможности получить совет от системы в плане оптимизации подготовленного расписания. Если не автоматизировать этот процесс, то от субъективизма и случайности никуда не уйти. Кроме того, во многих системах производятся разработки в рамках концепции систем поддержки принятия решений - автоматическая генерация расписания в сочетании с диалоговым вводом и редактированием.
Расписание должно удовлетворять многочисленным требованиям организационного, методического и психолого-физиологического характера, имеющим различные степени обязательности, часто взаимно противоречивым или даже взаимоисключающим. Наиболее общие требования к расписаниям сформулированы в нормативных документах и методической литературе [183,263].
Рассмотренные выше модели и системы не учитывают специфику составления расписаний в нашем университете. В каждой из моделей опускается ряд существенных условий. Актуально привести в соответствие современные требования к расписанию занятий и ограниченность имеющихся ресурсов вузов. Необходимо явно сформулировать наиболее важные требования и формализовать их, поставить задачу синтеза реального, а не абстрактного, учебного расписания. Таким образом, для преодоления недостатков имеющихся систем должен быть использован следующий подход. На первом этапе проводится исследование прикладной области, синтезируется информационная модель процесса и систематизируется список требований к расписанию занятий. Информационная модель отражает шаги процесса, исходные данные, участвующие стороны и особенности документооборота (рис. 1.1). Сущность модели заключается в пошаговой подготовке исходных данных для генерации расписания с периодической коррекцией результатов предыдущих шагов. На основе этой модели и сформированного списка требований на втором этапе разрабатывается математическая модель задачи синтеза расписания занятии и реализуется в виде автоматизированных методов и алгоритмов. На третьем этапе с учетом построенных моделей определяется структура автоматизированной системы обработки информации и управления планированием расписания. Подобный подход позволяет в полной мере учесть специфику процесса, гарантировать практическую значимость результатов планирования и эффективное использование возможностей автоматизации.
Приведем определения основных документов, составляемых при планировании учебного процесса в МГУПБ. В разных учебных заведениях используются различные наименования и содержание описанных ниже документов, поэтому представляется уместным привести определения того, что конкретно подразумевается под названием документа.
Учебный план — документ, устанавливающий общее направление и главное содержание обучения и определяющий организационные и учебно-методические виды и формы процесса обучения. Учебные планы разрабатываются применительно к конкретным специальностям в соответствии с установленным профилем подготовки. Учебный план включает перечень дисциплин, их объем и распределение по семестрам и видам занятий (включая практики, стажировки, курсовые проекты и работы, домашние задания), а также формы и сроки отчетности и контроля знаний. Направление и характер учебного плана конкретизируется в учебных программах.
Иерархическая многоуровневая схема упорядочения критериев по их значимости
Таким образом, составление расписания занятий в вузе формализуется в виде задачи нелинейного булева программирования с ограничениями и критериями в виде формул исчисления предикатов.
В данном случае, можно сказать, что представлена модель, определяющая класс математических моделей составления расписаний занятий в вузе. Конкретная форма математической модели, с заданным числом требований (ограничений и критериев), может быть определена (на практике), только после ввода всей необходимой информации (тогда возможно определение конкретных используемых ограничений, т.к. только одних перечислительных ограничений можно сконструировать несколько тысяч) и задания параметров составления расписания (после этого возможно определение критериев для поиска решения). В конкретном случае нет необходимости учитывать все возможные требования.
Существующие модели фрагментарно охватывают, те или иные группы ограничений и критериев. В данной модели мы попытались охватить весь комплекс необходимых требований, путём их систематизации и указания методики их построения. Использование же какой-либо конкретной формы модели с фиксированными ограничениями и критериями приводит к той или иной степени искажения и упрощения реальной задачи (это особенно характерно для многих ранних работ [194, 220, 251, 261]). К тому же, возможно возникновение дополнительных ограничений - всевозможные сочетания объектов, определяющих требования, и ресурсов (аудитории и/или время) или логических условий, задают различные ограничения и пожелания.
В программном комплексе имеется возможность учета данных ограничений в реляционной модели, путём выбора или конструирования необходимых ограничений и критериев. В алгоритмах полностью учитываются требования перечислительного типа. Для задания логических ограничений, в общем случае, требуется построение достаточно громоздких предикатов, либо описание алгоритма выполняющего проверку. Алгоритмы реализующие их и оформленные в виде плагинов, дают возможность учёта данных ограничений при составлении расписания, т.к. сторонние разработчики могут добавить или заменить некоторые процедуры алгоритма разработанные нами (проверки в данном случае), на свои. Такая доработка, не составит большого труда, по сравнению с полной самостоятельной реализацией.
Математически адекватное описание задачи составления расписания занятий в вузах, к сожалению, не является настолько простым, чтобы его можно было корректно представить какой-либо конкретной фиксированной моделью. Данное представление математической модели отвечает практической реализации задачи в программном комплексе и для решения данной задачи используются соответствующие подходы (см. главу 3).
Доказательства Р-трудности задач данного класса приведены во многих работах. В [189] задача о потоке минимальной стоимости на сети, интерпретирована для задачи составления учебного расписания с нарушением одного условия: в результате решения может оказаться, что один и тот же преподаватель будет одновременно задействован на двух или более уроках. Показано, что добавление условия, обеспечивающего проведение преподавателем в момент времени не более одного урока приводит к переходу задачи в категорию NP-трудных.
В [123], для приведённой в данной работе модели, методом локальной замены [69], выделяя две ./VP-полных подзадачи, показана NP-полнота рассматриваемой задачи.
Задачи составления расписания с запретами для некоторых преподавателей на проведение занятий на определенных парах и реберной раскраски двудольного мультиграфа с фиксированными раскрасками некоторых ребер оказываются взаимно полиномиально сводимыми.
Задача составления расписания с запретами на проведение занятий на определенных уроках для некоторых преподавателей, а также для некоторых классов, полиномиально сводима к задаче с запретами только для преподавателей.
Задача составления учебного расписания с учетом разбиения и объединения классов iVP-полна. Для доказательства #Р-полноты задачи достаточно показать, что к ней полиномиально сводится JVP-полная задача составления расписания с запрещенными для преподавателей занятиями, а сама исходная задача полиномиально сводима к АГР-полной задаче целочисленного линейного программирования в форме задачи распознавания [69].
Задача составления расписания на один урок с учетом разбиения и объединения классов и максимизацией количества занятий в течение урока NP-полна. К этой задаче полиномиально сводима ЛГР-полная задача о максимальном внутренне устойчивом (независимом) множестве графа [69].
Разрешение конфликтных ситуаций возникающих при распределении заявок
При занесении значений используется следующий принцип - если присваивается значение отличающееся от нейтрального, то при сравнении с нейтральным оно имеет приоритет, если сравниваются два отличающихся от нейтрального значения, то менее желательное требование имеет приоритет.
Все требования перечислительного типа хранятся в одной таблице. Стоит отметить, что многие разработчики, обычно, используют в этом случае несколько таблиц, отражающих только наиболее характерные требования, что делает невозможным самостоятельное задание пользователем требований других типов. Используемый же нами подход позволяет пользователю самому выбирать или конструировать необходимые ему требования.
Для выделения требований текущей заявки и их объединения используется следующий алгоритм: 1. Цикл по имеющимся объектам задающим офаничения и формирование фильтра для отбора требований текущей заявки — для каждого поля, соответ ствующего объекту задающему ограничения, производится подстановка зна чения поля из заявки в следующий фрагмент: Если значение поля равно NULL, это значит, что требование распространяется для всех значений объекта задающего офаничения. 2. Накладывается фильтр на таблицу содержащую офаничения и отсеиваются офаничения не нужные для данной заявки. 3. Цикл по записям таблицы содержащей офаничения и занесение требований в компонент типа TMResourceCube, в котором реализуется объединение офа-ничений в соответствии с описанными выше принципами. После ввода, сортировки заявок по некритичности и согласования исходных данных с имеющимися ресурсами, производится распределение заявок в соответствии с их некритичностью и статусами преподавателей. При распределении конкретной заявки в зависимости от её параметров и требований возможны различные отклонения от распределения в соответствии с некритичностью, например, при необходимости назначения подряд нескольких однотипных заявок, или при первоначальном назначении преподавателей с наивысшим статусом, но, в общем, схема остаётся: такой. На рис. 3.2 представлена блок-схема подпрофаммы "Распределение заявок". Распределение заявки начинается с определения допустимых для неё ресурсов. Далее в зависимости от распределения количества пар по неделям производится выбор соответствующей процедуры планирования. Сущность поиска назначения заявки заключается в просмотре по убыванию предпочтительности сначала наилучших вариантов (оптимизация), т.е. наиболее желательных пар и аудиторий, и попытке назначения в них заявки, затем менее желательных и т.д. Если не удаётся найти назначение, то в зависимости от параметров производится либо перестановка уже назначенных заявок и попытка записи на их место текущей, либо откладывание заявки и распределение её после назначения всех заявок. Перестановки производятся до определённой заданной глубины в соответствии с принципом убывания предпочтительности (предусмотрено задание приоритетов преподавателей). В подпрограммах в зависимости от критериев и глубины поиска реализованы различные варианты расчёта с возможностью учёта дополнительных условий, т.е. возможна настройка алгоритма.
Поиск назначения заявки. По своему принципу поиск требуемых ресурсов для назначения заявки можно разделить на два основных типа — поиск назначения для мигающих и еженедельных занятий (занятий, а не заявок). Мигающим называется занятие, которое требуется провести один раз в две недели. Еженедельным, соответственно то, которое проводится на обеих неделях.
Суть поиска назначения для занятий с мигающим распределением состоит в следующем: Сначала просматриваются частично занятые учебные дни групп потока. Перебираются варианты назначения в порядке уменьшения их предпочтительности: С целью рационального распределения временного ресурса потока в первую очередь просматриваются мигающие интервалы, свободные и допустимые относительно логических ограничений, наиболее желательные (в смысле заданных требований). При этом предпочтение отдаётся интервалам с мигающими аудиториями. Мигающей считается аудитория, в которую назначено одномигающее занятие. Это необходимо для рационального распределения аудиторного фонда. Затем переходят к произвольным допустимым интервалам и аудиториям, и т.д.
При поиске назначения для занятий с еженедельным распределением просматриваются наиболее желательные и допустимые на обеих неделях интервалы требуемой длины. После нахождения требуемого интервала в нём производится поиск аудитории (или минимального числа аудиторий) свободных на обеих неделях в течение требуемого интервала. Затем просматриваются остальные менее желательные и т.п. интервалы и аудитории.
Поиск аудиторий осуществляется с учётом заданных максимальных допустимых отклонений на вместимость. Предпочтение отдаётся наиболее желательным в данном случае, для данной заявки, аудиториям, а среди них с минимальными отклонениями от численности потока. На рис 3.3 представлена блок-схема подпрограммы осуществляющей проверку возможности назначения за-явки в единицу времени и поиск допустимой аудитории.
Функциональная структура системы составления расписания учебных занятий
Классические многопользовательские системы, как правило, содержат на рабочих станциях приложения, содержащие презентационную логику, а также средства доступа к данным. Из этого следует, что такие рабочие станции должны предоставлять для самих себя весь требующийся для этого набор сервисов и содержать соответствующее программное обеспечение для их функционирования. Это нередко усложняет технические требования, предъявляемые к аппаратной части клиентской рабочей станции, и в конечном итоге приводит к по-вышению стоимости эксплуатации и сопровождения такой информационной системы. Весьма существенным является то, что значительная часть бизнес-логики таких информационных систем содержится в клиентских приложениях, что повышает требования, предъявляемые к рабочим станциям. Казалось бы, с этой задачей вполне могут справиться и приложения клиент/сервер, однако при большом числе клиентов вся вычислительная нагрузка ложится на сервер БД, который обладает довольно скудным набором для реализации сложной бизнес-логики (хранимые процедуры, триггеры, представления и т.д.). И разработчики вынуждены существенно усложнять программный код клиентского ПО, а это крайне нежелательно при наличии большого числа удаленных клиентских компьютеров. Ведь с усложнением клиентского ПО возрастает вероятность ошибок и обслуживание программного обеспечения затруднено.
Следует отметить, что подобное программное обеспечение требует проведения работ по его настройке и поддержанию этих настроек в рабочем состоянии. Так, пользовательское приложение должно, как минимум "знать" о том, какого типа СУБД используется, где расположены используемые им данные, с помощью какого сетевого протокола они доступны, каков поддерживаемый базой данных язык, определяющий порядок алфавитной сортировки и индексирования данных, иметь установленные драйвера и библиотеки доступа к данным, и "знать" каковы соответствующие настройки библиотек. Подобная работа нередко является весьма трудоёмким процессом, особенно при большем количестве и неоднородном парке рабочих станций. Отметим, что далеко не все компоненты подобного программного обеспечения могут быть включены в состав дистрибутива пользовательского приложения, так как многие из них являются предметом лицензирования и продажи. Трехзвенная архитектура предназначена для того, чтобы внести расширяемость и масштабируемость в информационные системы. Системы, которым нужны эти качества, могут никогда не быть полностью завершены, и в течение жизненного цикла всегда подвергаются изменениям. Тонкие клиенты могут не заменяться в течение жизненного цикла системы, но если клиентские приложения также подвергаются изменениям с изменениями системы и, аналогично клиентским приложениям в клиент-серверной архитектуре, должны время от времени заменяться новыми, более модифицированными версиями, то такая замена происходит несравненно легче, чем в случае клиент-серверного подхода.
Есть и еще один немаловажный фактор: чем сложнее конфигурация, обеспечивающая доступ к данным рабочей станции, тем чаще происходят нарушения в ее работе. По данным некоторых западных источников,,повторное конфигурирование и сопровождение программного обеспечения, предоставляющего доступ рабочих станций к данным, приводит в среднем к четырём дням простоя рабочей станции в год.
Итак, используя стандартные архитектуры создания многопользовательских информационных систем, можно столкнуться с серьезными проблемами, требующими материальных затрат — все более повышающимися требованиями к аппаратному обеспечению рабочих станций и необходимостью обеспечения поддержки настроек доступа к данным. Отметим, что список возможных проблем этим не исчерпывается. Мы не рассматривали проблемы, связанные с перегрузкой сети при росте объема данных (частично они могут быть решены заменой сетевых СУБД серверными, хотя далеко не всегда такой переход полностью решает эти проблемы), проблемы, связанные с эксплуатацией всеми пользователями каких-либо общих ресурсов, а также проблемы, возникающие при территориальной разбросанности предприятия или низком качестве линий связи, а также связанные с безопасностью данных.
Многозвенная архитектура приложений БД призвана устранить перечисленные недостатки. Появление многозвенной архитектуры приложений баз данных обусловлено необходимостью обрабатывать на стороне сервера запросы от большого числа удаленных клиентов. В разработанных системах реализована трёхзвенная архитектура, состоящая из: Клиентских приложений, обеспечивающих пользовательский интерфейс; Сервера приложений, отвечающего за доступ к данным и безопасность. Сервер приложений может быть запущен на компьютере, либо как сервис (только в операционных системах на базе ядра NT, т.е. Windows NT, 2000, ХР), либо как программа. При этом он остается доступен через System Tray; Сервера БД (Oracle, Microsoft SQL Server или MSDE, Interbase), поддерживающего функционирование базы данных и обрабатывающего запросы. В рамках этой архитектуры, клиентские приложения обеспечивают передачу данных, их локальное кэширование, отображение средствами пользовательского интерфейса и редактирование. При этом приложения обращаются не к серверу БД напрямую, а используют сервер приложений.
