автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и методы решения задачи автоматизированного составления расписаний с интеллектуальной поддержкой принятия решений

На правах рукописи

¿Г

Воронин Иван Викторович

МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЗИРОВАННОГО СОСТАВЛЕНИЯ РАСПИСАНИЙ С ИНТЕЛЛЕКТУАЛЬНОЙ ПОДДЕРЖКОЙ ПРИНЯТИЯ РЕШЕНИЙ

Специальность- 05 13 01 - Системный анализ, управление и обработка

информации (технические системы)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

ООЗ17 и

Санкт-Петербург - 2008

003171319

Работа выполнена в Балтийском государственном техническом университете «ВОЕНМЕХ» им. Д Ф Устинова, г Санкт-Петербург

Научный руководитель -

кандидат технических наук, доцент Емельянов В Ю

Официальные оппоненты

доктор технических наук, профессор Копыльцов А В кандидат технических наук, доцент Смирнова Н Н

Ведущая организация - Военно-Морская академия им Н Г Кузнецова (г Санкт-Петербург)

Защита диссертации состоится «ЛЗ» илЭ'ИсЯ 2008г в часов на заседании диссертационного совета Д 212 238 07 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им В И Ульянова (Ленина) по адресу 197376, Санкт-Петербург, ул Проф Попова, 5

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан «0» ЛЛ 2008г

Ученый секретарь диссертационного совета

/ Цехановский В В /

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

С математической точки зрения задача составления расписания является задачей упорядочения и характеризуется очень высокой размерностью Математические методы решения таких задач рассматриваются в рамках теории расписаний (ТР)

Анализ известных математических методов, традиционно применяемых к решению задачи составления расписаний, показал, что они не позволяют с приемлемой трудоемкостью получить решение для задачи высокой размерности с учетом совокупности рассматриваемых на практике ограничений Решение требует поиска нового подхода, что и определяет цель и задачи диссертационного исследования

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

Для достижения поставленной цечи необходимо решить следующие задачи

- построение на основе системного анализа модели для задачи составления расписания с учетом характерных для нее ограничений,

- разработка системы критериев оценки качества решения задачи,

- поиск метода решения,

- разработка алгоритмов, реализующих данный метод,

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

Результаты диссертационного исследования:

1 Предложена модель задачи составления расписания с учетом системы рассматриваемых на практике ограничений

2 Предложены метод и алгоритм составления расписания на основе упорядочения его элементов с использованием гибких приоритетов Разработаны модель, расчетная схема и алгоритм для определения приоритетов элементов расписания

3 Разработаны метод и алгоритм настройки приоритетов в процессе составления расписания на основе нейросетевого подхода

4 Разработана, реализована и внедрена в эксплуатацию автоматизированная система составления расписания занятий Разработана методика составления расписания с помощью автоматизированной системы

5 Разработана система критериев оценки качества расписания и алгоритмы их оценки

Научная новизна результатов диссертации состоит в следующем

1 Предложенная модель обеспечивает учет необходимости выполнения операции несколькими машинами различных классов (специализированные и универсальные), возможности выбора универсальной машины по заданной совокупности признаков, индивидуальных режимов работы машин

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

3 Настройка приоритетов в процессе составления расписания осуществляется на основе нейросетевого подхода с учетом получаемых оценок качества расписания

Достоверность результатов, полученных в работе, определяется

- корректным использованием математического аппарата системного анализа, теории множеств, нечеткой логики и нейронных сетей,

- результатами практического применения автоматизированной системы для составления расписания занятий в БГТУ «ВОЕНМЕХ» им Д Ф Устинова в течение двух лет

Практическая ценность результатов диссертации состоит в следующем

1 На основе полученных в диссертации результатов построена и внедрена в эксплуатацию автоматизированная система составления расписания занятий в высшем учебном заведении

2 Эксплуатация автоматизированной системы в БГТУ «ВОЕНМЕХ» им Д Ф Устинова в течение двух лет подтверждает ее эффективность при составлении расписания на основе учета широкого набора ограничений на режим работы преподавателей, аудиторий и учебных групп

3 Распределенная структура автоматизированной системы и разработанная методика составления расписания обеспечивают параллельную работу большого коллектива пользователей без специальной подготовки

4 Автоматизированная система обеспечивает поддержание расписания занятий в электронной форме и оперативное внесение текущих изменений в расписание с интерактивным контролем их допустимости

Внедрение результатов Результаты диссертационного исследования внедрены в процесс планирования и подготовки учебного процесса в БГТУ «ВОЕНМЕХ» им Д Ф Устинова, а также в учебном процессе при проведении лекционных, практических и лабораторных занятий

Апробация работы Основные результаты диссертационного исследования докладывались и обсуждались на X международной конференции «Региональная информатика - 2006» и на семинарах кафедры «Систем обработки информации и управления» БГТУ «ВОЕНМЕХ» им ДФ Устинова

Публикации. По теме диссертационной работы опубликовано 13 научных работ, из них - 6 статей (1 статья из перечня изданий, рекомендованных ВАК), 2 работы - в материалах международных научно-технических конференций, 5 свидетельств об официальной регистрации программ

Структура и объем работы. Диссертация состоит из введения, пяти разделов, заключения и списка литературы, включающего 123 наименования Основная часть работы изложена на 152 страницах машинописного текста Работа содержит 57 рисунков и 31 таблицу

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулированы пели и задачи исследования Приведены основные результаты и положения диссертационной работы, характеристика их научной новизны и практической ценности

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

Анализ рассматриваемой задачи позволил выделить ее особенности 1) Длительность выполнения каждой операции а>2 задается количеством фиксированных дискретных промежутков времени / = 1.7', разделенных на несколько периодов (дней планирования)

2) Машины можно разделить на 2 класса специализированные (жестко закрепленные) для конкретных операций и универсальные

3) Для выполнения операции могут одновременно требоваться несколько машин различных классов

4) Для каждой операции требуется выбрать время выполнения и назначить по заданным признакам требуемое количество универсальных машин

5) Каждая машина (как специализированная, так и универсальная) может иметь индивидуальный режим работы

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

Допустимый объем решаемой задачи должен быть достаточен для применения автоматизированной системы в крупных учебных заведениях высшего образования

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

При использовании методов математического программирования рассматриваемые ограничения приводят к нелинейной задаче, избежать чего удается введением дополнительных переменных и ограничений, что существенно увеличивает размерность В результате, в рассматриваемой прикладной задаче число переменных и ограничений достигает сотен тысяч На практике с такой высокой размерностью не в состоянии справиться ни один из известных методов Кроме того, рассматриваемая прикладная задача является многокритериальной

В рамках комбинаторного подхода задача составления учебного расписания относится к классу ЫР-полных задач, которые не поддаются эффективному алгоритмическому решению Для алгоритма, корректно решающего №-полную задачу, потребуется в худшем случае экспоненциально возрастающее в зависимости от объема задачи количество времени и, следовательно, его практическое применение возможно лишь для задач малого объема

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

Расписание, операции в котором сильно связаны между собой посредством требуемых специализированных и в меньшей степени универсальных машин существенно зависит от порядка выполнения операций Если по некоторому эвристическому методу удастся определить оптимальную последовательность размещения операций, то количество вариантов перебора сократится в п] раз, где п -количество операций

Второй раздел посвящен формализации задачи составления расписания В терминах линейною целочисленного программирования разработана формальная модель составления расписаний с дискретным временем выполнения операций машинами, которые делятся на 2 класса специализированные (жестко закрепленные) для конкретных операций и универсальные Модель предусматривает обработку операции несколькими машинами различных классов Введем следующие группы булевых переменных

Г1, если операция г назначена на время г, -' [О-впротивном случае,

, если для для операции г назначена универсальная машина а,

У" 111 - в противном стучае,

„ _ /1, если специализированная машина g во время I выполняет операцию г, [О-в противном случае,

д, _ 11, если универсальная машина а во время / занята операцией г, ш [О-в противном стучае,

1, если специализированная машина g во время г выполняет операцию, О-в противном случае,

Г1, если универсальная машина а во время г выполняет операцию, [О-в противном случае,

а,

р

га _ /1, ее

, если у машины g отсутствуют операции в день 3, • в противном случае,

Введем следующую группу булевых констант

_ /1, если операция г выполняется специализированной машиной g,

|0 - в противном случае,

Определим условие выполнения всех операций ^х., = тг, V/ Каждая машина

!

в любое время может выпо зиять только одну операцию

г г

Введем соотношения, определяющие выбор универсальных машин для выполнения операции

у_а = к°, Ч/г, где к° - количество универсальных машин, необходимых для выполне -

а

ния операции г

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

О < ут va - к" < Д°т1Х, Vz, где va - количественная характеристика машины а,

к™ - требуемая для выполнения операции z количественная характеристика машины,

Д°т„ - максимально допустимый запас по количественной характеристике

г, = rz,Vz,rfle т0 - тип машины а, тг - требуемый для выполнения операции z тип машины

Определим количество операций в период (день) 8 для машины g, и зададим на него ограничения

UAXl

= Vg, <5,где MCVj-индекс времени начала дня

t=MIN%

МАХ] - индекс времени окончания дня д

MINf < Q.% < MAXf, Vg, S, где

MIN f - минимальное количество операций в день для машины g,

7С

МАХ¡г - максимальное количество операций в день для машины g,

Введем ограничения на количество занятых дней для машин

± К1 - Ф * MAXf,4g, где

S

MIN™ - минимальное количество занятых дней для машины g, МАХ™' - максимальное количество занятых дней для машины g

Введем следующие группы булевых переменных

0 _ Jl, если в день 6 машина g начинает выполнение операций со времени t, У'» ~ [0 - в противном случае,

а _ fl, если в день 5 машина g заканчивает выполнение операций временем /, / gs> ~ jo - в противном случае,

Недопустимость простоя машины g в день 8 задается условием

МАХ7,

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

В качестве первого этапа решения задачи составления расписания предлагается проведение анализа исходных данных Анализ направлен на достижение двух основных целей

1 Выявление ошибок и противоречий в исходных данных,

2 Локализация «узких» мест и определение оптимальной или близкой к оптимальной последовательности выполнения операций

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

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

Для расчета коэффициентов сложности (КС) операций в рамках анализа

исходных данных предлагается следующая расчетная схема

+ < к%

Ка "

где К* = ]Г —" коэффициент сложности назначения специализированной

г.1 п м

машины g для выполнения операции г,п- количество интервалов времени в пределах допустимого времени выполнения операции, а>1 - длительность выполнения

операции, Н^, = тг° ^—^ - коэффициент сложности выполнения операции /-1

специализированной машиной g в интервал времени /, приоритет интервала времени, заданный для данной машины в исходных данных, т - количество операций, для выполнения которых задействована данная машина, = '¿Г л - сумма приоритетов допустимых промежутков времени выполнения операций машиной g,

5*

К" = со- коэффициент сложности выбора универсальной машины а для занятия

г, количество списков универсальных машин, А^ = \/п^Аа - средняя доля

0-1

универсальных машин в списке 5, п - количество универсальных машин в списке, Аа = ]/п^Н'^ - средний коэффициент сложности универсальной машины а, п -количество интервалов в пределах допустимого времени выполнения операции, Нл„ = < £ - коэффициент сложности назначения универсальной машины на 1-й

интервал времени, л* - приоритет интервала времени, заданный для данной универсальной машины в исходных данных, т - количество операций, для

выполнения которых требуется машина о; = ^тг,^ - сумма приоритетов

ы

допустимых промежутков времени выполнения операций машиной а, , -эмпирические весовые коэффициенты

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

Полученные коэффициенты сложности являются основой для формирования последовательности расстановки занятий

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

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

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

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

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

- подбор наилучшего времени проведения занятия,

- подбор наилучшей аудитории для проведения занятия в конкретное время,

- пересчет приоритетов ячеек расписания

Для решения задачи подбора наилучшего времени проведения занятия и наилучшей аудитории предлагается использовать аппарат нечеткой логики Введены лингвистические переменные резерв аудитории, приоритет преподавателя, количество новых переходов и уверенность отбора Их функции принадлежности

Разработана база правил нечеткого вывода, например

Если (резерв)=(отличная 0,6) и (переходы преподавателей)=(мало 1) и (переходы групп)=(мало 1), то (уверенность отбора) = (полная 0,6),

Если (резерв)=(хорошая 0,4) и (переходы преподавателей)=(мало 1) и

Результатом является четкое значение уверенности отбора конкретной аудитории и конкретного времени, полученное в результате дефазификации результатов нечеткого вывода (рисунок 2)

0 5* (83+100)* 0 6+0 5(62+83)* 0 4 55+29 „„

Центр =- ---=----'—--5---=--= 84

2>№] 06+04 1

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

зависимости времени решения задачи от ее объема Однако при этом сохраняется возможность не обнаружения удовлетворительных вариантов расстановки некоторых занятий

По мнению автора, это может быть вызвано двумя причинами

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

- несовершенство и субъективность правил формирования последовательности расстановки занятий

Для устранения второй из них и косвенно первой целесообразно корректировать порядок следования отдельных занятий в процессе составления расписания Действительно, в процессе расстановки занятий изменяется их допустимое время проведения, следовательно, необходимо время от времени пересчитывать коэффициенты сложности отдельных занятий и корректировать их расположение в очереди

Расчет КС и их пересчет в процессе составления расписания целесообразно осуществлять с использованием технологии нейронных сетей (НС) Применение НС в данном случае дает возможность ухода от субъективности расчета КС, формирования последовательностей занятий, обеспечивающих традиции преподавания определенных дисциплин, характеризуемых высокой методической эффективностью Появляется возможность гибкого, неформального учета пожеланий преподавателей, настройки на удачные фрагменты расписания, выделение и обобщение типичных ситуаций на основе накопленного сетью опыта В качестве архитектуры НС целесообразно использовать многослойный персептрон с количеством скрытых слоев равным 2 В качестве входов сети будем использовать приоритеты групп, преподавателей и аудиторий на время проведения занятий Для обеспечения обучения сети на каждый нейрон первого слоя необходимо подавать номер специальности, номер дисциплины, номер типа занятия и номер преподавателя Нейроны в слое будут соответствовать занятию

Для первоначального обучения НС предполагается использовать алгоритмы обучения с учителем В качестве обучающей выборки можно использовать наборы реальных исходных данных, накопленные за период эксплуатации первого варианта системы, и коэффициенты сложности, рассчитанные для них по приведенным выше формулам Дальнейшее обучение (корректировка весовых коэффициентов, используемых при расчете коэффициентов сложности) предполагается производить, исходя из корректировок, вносимых диспетчером на основе личного опыта, оценки расписания кафедрами и традиций учебного заведения Подстройка сети позволяет скомпенсировать субъективность эвристического подхода и учесть не формализованные пожелания преподавателей

Четвертый раздел посвящен разработке автоматизированной системы составления расписания занятий, включающей аппаратную, программную и методическую подсистемы

Аппаратная подсистема (рисунок 3) обеспечивает функционирование автоматизированной системы на уровне оборудования, предоставляя коммуникационные и вычислительные возможности, а также средства хранения данных

Отдел расписаний выделен в отдельную сеть, не имеющую доступа во внешнюю сеть, с возможностью обращаться только к серверу и к другим

компьютерам отдела. Это обеспечивает дополнительную безопасность от вирусов и внешних атак и в конечном итоге стабильность подготовки расписания. Например, в БГТУ сеть отдела расписаний состоит из 3-х компьютеров. С сервером взаимодействуют 43 кафедры. Прямой доступ к серверу имеет администратор.

Единая сеть ВУЗа

Кафедры

ПК Кафедры!

ПК Кафедры л

Рисунок 3 - Аппаратная подсистема

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

Архитектура программной подсистемы предусматривает

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

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

На основе технологии «клиент-сервер» разработана база данных, позволяющая вводить, хранить и редактировать исходные данные. Логическая структура базы данных разработана с учетом всех необходимых требований, предъявляемых к системе, и позволяет наращивать функциональные возможности.

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

Рисунок 4 - Общая структура программной подсистемы Реализован модуль корректировки расписания занятий, обеспечивающий расстановку в автоматизированном режиме нерасставленных занятий и устойчивость расписания (сопровождение, текущая корректировка)

Новизна разработанного метода, основных алгоритмов и программных модулей защищена свидетельствами об официальной регистрации Роспатента

Пятый раздел посвящен внедрению автоматизированной системы в эксплуатацию Разработаны критерии (показатели) оценки качества расписания, формируемого автоматизированной системой Приводятся значения оценок показателей дчя расписания занятий в осеннем семестре 2006-2007 учебного года в БГТУ Проведены исследования влияния объема аудиторного фонда на качество расписания Представлены результаты реализации нейросетевого подхода к расчету КС

Для оценки качества расписания предложены характеристики, соответствующие наиболее существенным ¡фактическим требованиям к расписанию

1) Количество нерасставленных занятий

2) Котичество невыполненных пожетаний преподавателей к нежслатечьному времени проведения занятий

3) Количество невыполненных пожеланий преподавателей к максимальному количеству занятий в день

4) Количество невыполненных пожеланий к максимальному количеству занятых дней

5) Количество «окон» в расписании преподавателей

6) Количество «окон» в расписании групп

7) Количество переходов из корпуса в корпус для преподавателей

8) Количество переходов из корпуса в корпус для групп

Разработанная автоматизированная система более двух лет используется для обеспечения планирования учебного процесса В осеннем семестре 2006-2007 учебного года в учебном процессе БГТУ задействовано 775 преподавателей и 443 группы Пожелания на время проведения занятий подали 509 преподавателей, прочие пожелания поступили от 421 преподавателя Учебный план ВУЗа включал в себя 7183 учебные дисциплины, общим объемом аудиторных часов в неделю 13362 При составлении расписания в автоматическом режиме были учтены все требования учебного процесса и пожелания преподавателей Список нерасставленных занятий составил менее двух процентов, кроме тою в расписании групп и преподавателей присутствовали окна и переходы При доводке расписания в автоматизированном режиме были скорректированы некоторые пожелания преподавателей Приведем итоговые значения показателей качества

БГТУ Осень 2007г.

Подано 14016 пожеланий преподавателей к нежелательному времени проведения занятий Не удовлетворено 345, что составляет 2,46% У 53 (6,84%) преподаватетей превышено максимальное количество занятых дней

Следующая таблица отражает количество переходов из корпуса в корпус

Перех Пн Вт Ср Чт Пт Сб Всего

Препод 34/31 31/23 29/25 29/26 37/37 21/26 181/168

Групп 236/237 218/223 208/196 208/203 224/222 166/163 1260/1244

Таким образом, в среднем из пяти преподавателей один вынужден раз в неделю переходить из корпуса в корпус Каждая группа в неделю совершает в среднем два перехода из корпуса в корпус

Следующая таблица отражает количество окон в расписании

Окна Пн Вт Ср Чт Пт Сб Всего

Препод 30/40 25/34 22/27 36/36 27/30 13/10 157/177

Групп 2/1 1/4 6/3 9/6 5/4 3/1 26/19

В среднем из пяти преподавателей у одного и из 33 групп у одной в расписании в течение недели присутствует окно

Приведем сведения о загруженности аудиторного фонда В среднем, наиболее загруженными оказались вузовские аудитории общего назначения (78%) и наименее загруженными кафедральные аудитории специального назначения (19%) Однако некоторые аудитории из последней группы загружены на 100%

Получим зависимости показателей качества от объема наиболее дефицитных вузовских аудиторий общего назначения Для этого будем постепенно добавлять аудитории и получать значения показателей качества Часть полученных результатов представлена на рисунке 5

Зависимость кол*ва нерасставленных занятий от объема аудиторного фонда

50 60 70 ВО 90 Количество аудиторий

Зависимость количества окон в расписании групп от объема аудиторного фонда

? 170

8 160 ^ | 150 | ^ 140

I 130 * 120

60 70 60

Количество аудиторий

Рисунок 5 - Зависимость показателей от количества аудиторий общего назначения

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

Рисунок 6 - Динамика изменения количества нерасставленных занятий

В соответствии с предложениями, сформулированными в разделе 3, автоматизированная система была дополнена нейросетевым алгоритмом корректировки коэффициентов сложности Настройка сети осуществлялась на основе

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

В заключении представлены основные выводы по диссертационной работе

1 В теории расписаний отсутствует универсальный метод решения рассматриваемой задачи Высокая размерность реальных задач составления расписаний не позволяет применять на практике существующие методы Целесообразно искать новый эмпирический метод, предусматривающий частичное применение комбинаторного подхода с отказом от полного перебора вариантов за счет упорядочения списка операций

2 В качестве конкретной прикладной задачи для иллюстрации основных положений диссертации выбрана задача составления расписания занятий для высшего учебного заведения, для которой на настоящее время не получено решение с учетом совокупности ограничении, характерных для современного ВУЗа Актуальна разработка методики составления расписания занятий и реализующей ее автоматизированной системы

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

4 Предложены метод и алгоритм составления расписания на основе упорядочения его элементов с использованием гибких приоритетов Разработаны модель, расчетная схема и алгоритм для определения приоритетов элементов расписания

5 Разработаны метод и алгоритм настройки приоритетов в процессе составления расписания на основе нейросетевого подхода

6 Разработана система критериев оценки качества расписания занятий и алгоритмы их оценки

7 На основе полученных результатов построена и внедрена в эксплуатацию автоматизированная система составления расписания занятий в высшем учебном заведении Ее эксплуатация в БГТУ «Военмех» им Устинова Д Ф в течение двух лет подтверждает ее эффективность при составлении расписания на основе учета широкого набора ограничений на режим работы преподавателей, аудиторий и учебных групп Разработана методика составления расписания с помощью автоматизированной системы

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемом журнале из списка ВАК

1 Автоматизация как основа оптимального планирования учебного процесса университета /ИВ Воронин [и др ] // Мехатроника, автоматизация, управление -2007 -№5 -С 45-48

В других изданиях.

2 Воронин И В Автоматизация составления расписания занятий на основе системы управляемых приоритетов // Современные проблемы социально-экономических и правовых наук сб ст студентов и молодых ученых - Томск ТГУ, 2004 - С 83-88

3 Воронин И В Построение информационной системы отдела расписаний БГТУ // Актуальные вопросы управления в организационно-технических системах сб тр студентов, магистрантов, аспирантов и молодых ученых БГ ГУ / Балт гос техн ун-т - СПб, 2005 - С 18-21

4 Воронин И В Подсистема корректировки расписания занятий // Актуальные вопросы ракетно-космической техники и технологий сб тр студентов, магистратов, аспирантов и молодых ученых БГТУ / Балт гос. техн ун-т - СПб, 2006 -С 185188

5 Воронин И В Показатели качества расписания занятий // Актуальные вопросы ракетно-космической техники и технологий сб тр студентов, магистрантов, аспирантов и молодых ученых БГТУ У Балт гос техн ун-т - СПб, 2007 - С 149-152

6 Воронин И В Интеллектуальная автоматизированная подсистема составления расписания занятий /ИВ Воронин, В Ю Емельянов // Региональная информатика - 2006 (РИ - 2006) материалы X междунар конф - СПб СПОИСУ, 2006 - С 196-197

7 Свидетельство об официальной регистрации программ для ЭВМ №2007612151 Клие1ггское приложение для удаленного ввода данных для составления расписания занятий (АРМ Кафедра) / И В Воронин, В Ю Емельянов, А С Зайцев -2007

8 Свидетельство об официальной регистрации программ для ЭВМ №2007612152 Подсистема анализа исходных данных для составления расписания занятий высшего учебного заведения / И В Воронин -2007

9 Свидетельство об официальной регистрации программ для ЭВМ №2007612153 Подсистема составления расписания занятий высшего учебного заведения (ПСРЗ)/ И В Воронин, В Ю Емельянов, А С Зайцев - 2007

10 Свидетельство об официальной регистрации программ для ЭВМ №2007612154 Подсистема корректировки расписания занятий высшего учебного заведения/ И В Воронин, В Ю Емельянов, M С Журавлева - 2007.

11 Свидетельство об официальной регистрации программ для ЭВМ №2007620212 База данных информационной системы учебно-методического управления высшего учебного заведения /ИВ Воронин, А А Жердер, С H Мальцев -2007

12 Воронин ИВ Автоматизированная система составления расписания занятий // Актуальные вопросы управления в технике и экономике сб тр студентов, магистрантов, аспирантов и молодых ученых БГТУ / Балт гос техн ун-т - СПб, 2003 -С 19-22

13 Воронин И В Информационная система учебно-методического управления университета /ИВ Воронин [и др ] // Региональная информатика - 2006 (РИ -2006) материалыXмеждунар конф - СПб СПОИСУ,2006 -С 201-202

Подписано в печать 12 05 08 Формат бумаги 60x84 1/16 Бумага документная Печать трафаретная Уел печ л 1 Тираж 100 экз Заказ №163 Балтийский государственный технический университет

Типография БГТУ 190005, Санкт-Петербург, 1-я Красноармейская ул д 1

ВВЕДЕНИЕ.

1 АНАЛИЗ ЗАДАЧИ И СРЕДСТВ ЕЕ РЕШЕНИЯ.

1.1 Общая характеристика задачи.

1.2 Обзор существующих средств решения.

1.3 Обзор методов решения.

1.3.1 Математическое программирование.

1.3.2 Комбинаторный подход.

1.3.3 Эвристические и вероятностные методы.

1.4 Выводы по разделу.

2 ФОРМАЛИЗАЦИЯ ЗАДАЧИ.

2.1 Общая модель задачи.

2.2 Формализация задачи на основе аппарата теории множеств.

2.3 Формирование элементов расписания.

2.4 Принципы анализа исходных данных.

2.5 Выводы по разделу.

3 РАЗРАБОТКА МЕТОДА РЕШЕНИЯ ЗАДАЧИ.

3.1 Последовательный метод составления расписания.

3.2 Расчет коэффициентов сложности с применением нейронных сетей.

3.3 Выводы по разделу.

4 РАЗРАБОТКА АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ.

4.1 Разработка структуры автоматизированной системы составления расписания занятий.

4.2 Аппаратная подсистема.

4.3 Программная подсистема.

4.4 Разработка логической структуры базы данных.

4.5 Разработка алгоритма составления расписания.

4.6 Разработка модуля анализа исходных данных.

4.7 Разработка модуля корректировки расписания.

4.8 Методическая подсистема.

4.9 Выводы по разделу.

5 АНАЛИЗ РЕЗУЛЬТАТОВ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ.

5.1 Разработка критериев оценки качества расписания занятий.

5.2 Результаты внедрения автоматизированной системы.

5.3 Исследование влияния объема аудиторного фонда на качество расписания.

5.4 Реализация нейросетевого подхода подсчета КС.

5.5 Выводы по разделу.

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

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

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

В последние 10-15 лет для высшего образования в России характерен процесс постоянных изменений, причем наиболее существенных изменений можно ожидать при планируемом переходе к двухступенчатой кредитно-модульной системе высшего образования. Высшие учебные заведения должны иметь возможность быстрого и гибкого реагирования на возможные изменения. Такую возможность дает автоматизация планирования учебного процесса ВУЗа. В условиях роста разнообразия образовательных программ, острой нехватки бюджетного финансирования и аудиторного фонда задачи рационального распределения ресурсов приобретают первостепенное значение. Составление расписания занятий в новых условиях без автоматизации этого процесса не представляется возможным [31]. Составление расписания в ВУЗе характеризуется рядом проблем, которые перечислены ниже на примере Балтийского государственного технического университета «Военмех» им. Устинова Д.Ф. (БГТУ).

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

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

Растет разнообразие форм обучения, с различными требованиями к ограничениям на время проведения занятий, как для форм обучения, так и для групп.

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

Для обеспечения гибкости учебного процесса вводится нечетное количество аудиторных часов по дисциплинам учебного плана, что ведет к необходимости планирования двухнедельного расписания.

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

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

Сформулированные проблемы, а также наличие большого количества разнообразных специфических требований к организации учебного процесса, предъявляемых администрацией учебного заведения и выпускающими кафедрами, делают невозможным применение старых подходов и методов к процессу составления расписания, основанных на ручном труде. Огромное разнообразие учебных планов и требований, а также значительно возросший объем задачи и ограниченный объем аудиторного фонда, делают задачу составления расписания слишком сложной и недоступной для коллектива диспетчеров. Вследствие увеличения разнообразия и возросшей связанности расписания групп различных специальностей и форм обучения, увеличение количества сотрудников-диспетчеров не принесет результата, так как всем диспетчерам необходимо координировать действия между собой во избежание ошибок и накладок. Человек больше не в состоянии удержать в голове огромный объем информации и выполнять множество рутинных операций и проверок. В такой ситуации обеспечить своевременное и гибкое планирование учебного процесса в состоянии лишь автоматизированная система, осуществляющая централизованную работу со всеми данными, выполняющая огромное количество трудоемких рутинных операций и предоставляющая пользователю лишь сервисы высшего уровня абстракции. Задача автоматизации составления расписания занятий в современном ВУЗе актуальна как никогда раньше.

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

С математической точки зрения задача составления расписания является задачей упорядочения и характеризуется очень высокой размерностью [29]. Математические методы решения таких задач рассматриваются в рамках теории расписаний (ТР). «Временной» характер задач теории расписаний выделяет их в особый класс, существенно отличающийся от «объемных» экономических задач. Если в последних требуется ответить на вопрос, что и сколько производить, то в задачах ТР необходимо определить, когда и в какой последовательности выполнять работы. Это различие в существе задач определяет различие в методах и возможностях их решения. Для задач объемного характера развит достаточно мощный аппарат, главным образом математического программирования, позволяющий, с успехом добиваться их решения. Для задач ТР решающий аппарат развит в гораздо меньшей степени [35].

Поиск оптимального или близкого к оптимальному расписания осуществляется с помощью одного из 3 подходов:

- математического программирования [1,23];

- комбинаторного [35,62,75];

- эвристического [35].

Задача составления расписания может быть сформулирована в терминах линейного целочисленного программирования. Описывается система из работ, состоящих из операций, и машин, выполняющих конкретные операции. В виде неравенств представлена система ограничений. Также вводятся дополнительные целочисленные переменные для описания ограничений типа «или-или», которые нельзя описать в рамках обычного линейного программирования. Далее записывается сама система и формируется целевая функция. Целевые функции могут быть различными. Конкретный вид целевой функции зависит от того, что нам необходимо минимизировать [45].

При применении методов математического программирования для решения рассматриваемой задачи ТР неизбежно показательное возрастание времени решения задачи в зависимости от ее размерности в силу неизбежного использования приемов перебора вариантов:

Т = С-ктп, где С-некоторая константа, ^-количество пар в неделю, /«-среднее количество типов занятий проводимых преподавателем, «-количество преподавателей.

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

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

При комбинаторный подходе используются такие понятия, как задачи класса Р, эффективные алгоритмы и ТУР-полные задачи[82].

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

Класс ТУР-задач обладает следующими свойствами:

- никакую УУР-полную задачу нельзя решить никакими известными полиномиальными алгоритмами;

- если существует полиномиальный алгоритм для какой-нибудь УУР-полной задачи, то существуют полиномиальные алгоритмы для всех ТУР-полных задач.

Практическое значение понятия ТУР-полноты состоит в следующем: такие задачи по существу трудно решаемы с вычислительной точки зрения, они не поддаются эффективному алгоритмическому решению и для алгоритма, корректно решающего ^УР-полную задачу, потребуется в худшем случае экспоненциальное количество времени и, следовательно, он не будет применим на практике ни к каким, за исключением очень малых, задачам [75].

Неудовлетворительное состояние развития точных методов решения задач ТР обусловило разработку приближенных методов, позволяющих получать приемлемые решения при сравнительно небольших затратах времени и средств. Условно приближенные методы делятся на эвристические и вероятностные [75].

Эвристические алгоритмы основаны на приеме, который называется приемом снижения требований. Он заключается в отказе от поиска оптимального решения за приемлемое время. Эвристические алгоритмы используют различные разумные соображения без строгих обоснований.

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

Еще одно из направлений эвристических методов решения задач ТР состоит в формировании правил или функций предпочтения (приоритетов). Для каждой /-й работы из множества ожидающих выполнения работ, вычисляется значение функции /. предпочтения и выбирается та работа, для которой /. достигает максимума или минимума.

Задачу составления расписания* можно представить в виде задачи упорядочивания, где дисциплины из учебного плана являются операциями, а группы, преподаватели и аудитории - обслуживающие приборы [66]. Модель в этом случае удобно представлять в виде сети, дуги которой представляют операции. Каждой дуге соответствует некоторый весовой коэффициент, который является значением целевой функции, определяющей степень предпочтения выполнения данной операции. Вершины сети, называемые событиями и обозначаемые Е„ могут интерпретироваться как результаты выполнения отдельных частных работ. Таким образом, задача составления расписания сводится к построению сети с учетом всех требуемых условий. В случае, когда сетей можно построить несколько, необходимо рассчитать для каждой из них критический путь, и выбрать сеть с наименьшим критическим путем. Данный метод хорошо подходит для классической задачи упорядочения, а для решения задачи составления учебного расписания, его применение проблематично, так как в учебном расписании надо не просто упорядочить операции, а выбрать еще и время их проведения, что не предусматривается данной моделью и приведет к необходимости построения дискретной уровневой сети с запрещенными состояниями.

При применении всех этих методов также неизбежно возрастание по экспоненте времени работы программы при увеличении объема задачи [27].

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

- построение на основе системного анализа модели для задачи составления расписания с учетом характерных для нее ограничений,

- разработка системы критериев оценки качества решения задачи,

- поиск метода решения,

- разработка алгоритмов, реализующих данный метод,

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

Диссертация состоит из введения, пяти разделов и заключения. Содержит 159 страниц сквозной нумерации, в том числе 152 основного текста, список использованных источников из 123 наименований на 7 страницах и иллюстрирована 57 рисунками.

5.5 Выводы по разделу

1. Предложены критерии оценки показателей качества расписания занятий, формируемого автоматизированной системой. Разработаны алгоритмы получения оценок. Полученные оценки на примере осеннего семестра 2006/2007 учебного года позволяют сделать вывод о его высоком качестве.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

4. Предложены метод и алгоритм составления расписания на основе упорядочения его элементов с использованием гибких приоритетов. Разработаны модель, расчетная схема и алгоритм для определения приоритетов элементов расписания.

5. Разработаны метод и алгоритм настройки приоритетов в процессе составления расписания на основе нейросетевого подхода.

6. Разработана система критериев оценки качества расписания занятий и алгоритмы их оценки.

7. На основе полученных результатов построена и внедрена в эксплуатацию автоматизированная система составления расписания занятий в высшем учебном заведении. Ее эксплуатация в БГТУ «Военмех» им. Устинова Д.Ф. в течение двух лет подтверждает ее эффективность при составлении расписания на основе учета широкого набора ограничений на режим работы преподавателей, аудиторий и учебных групп. Разработана методика составления расписания с помощью автоматизированной системы.

1. Банди Б. Основы линейного программирования — М.: Радио и связь, 1989. 176с.

2. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения -М.: Наука. Гл. ред. физ.-мат. лит., 1989. 160 с.

3. Береснев B.JI. Дискретные задачи размещения и полиномы от булевых переменных -Новосибирск.: Изд-во Инст. математики, 2005. — 408 с.

4. Бондарев В.М., Рубелинецкий В.И., Качко Е.Г. Основы программирования Харьков: Фолио, 1997.-386 с.

5. Буч Г. Объектно-ориентированный анализ и проектирование СПб.: Невский диалект, 1999.-560 с.

6. Воронин И.В. Автоматизированная система составления расписания занятий // Актуальные вопросы управления в технике и экономике: сб. тр. студентов, магистрантов, аспирантов и молодых ученых БГТУ / Балт. гос. техн. ун-т. — СПб, 2003. — С. 19-22.

7. Воронин И.В. Автоматизация составления расписания занятий на основе системы управляемых приоритетов // Современные проблемы социально-экономических и правовых наук: сб. ст. студентов и молодых ученых. Томск: ТГУ, 2004. - С. 83-88.

8. Воронин И.В. Построение информационной системы отдела расписаний БГТУ // Актуальные вопросы управления в организационно-технических системах: сб. тр. студентов, магистрантов, аспирантов и молодых ученых БГТУ / Балт. гос. техн. ун-т.-СПб, 2005.-С. 18-21.

9. Воронин И.В. Подсистема корректировки расписания занятий // Актуальные вопросы ракетно-космической техники и технологий: сб. тр. студентов, магистрантов, аспирантов и молодых ученых БГТУ / Балт. гос. техн. ун-т. — СПб, 2006. С. 185-188.

10. Ю.Воронин И.В. Показатели качества расписания занятий // Актуальные вопросы ракетно-космической техники и технологий: сб. тр. студентов, магистрантов, аспирантов и молодых ученых БГТУ / Балт. гос. техн. ун-т. СПб, 2007. - С. 149-152.

11. П.Воронин И.В. Интеллектуальная автоматизированная подсистема составления расписания занятий / И.В. Воронин, В.Ю. Емельянов // Региональная информатика 2006 (РИ - 2006): материалы X междунар. конф. - СПб: СПОИСУ, 2006. - С. 196-197

12. Свидетельство об официальной регистрации программ для ЭВМ №2007612151. Клиентское приложение для удаленного ввода данных для составления расписания занятий (АРМ Кафедра) / И.В. Воронин, В.Ю. Емельянов, A.C. Зайцев. 2007.

13. Свидетельство об официальной регистрации программ для ЭВМ №2007612152. Подсистема анализа исходных данных для составления расписания занятий высшего учебного заведения / И.В. Воронин. — 2007.

14. Свидетельство об официальной регистрации программ для ЭВМ №2007612153. Подсистема составления расписания занятий высшего учебного заведения (ПСРЗ)/И.В. Воронин, В.Ю. Емельянов, А.С. Зайцев. 2007.

15. Свидетельство об официальной регистрации программ для ЭВМ №2007612154. Подсистема корректировки расписания занятий высшего учебного заведения/ И.В. Воронин, В.Ю. Емельянов, М.С. Журавлева. 2007.

16. Свидетельство об официальной регистрации баз данных №2007620212. База данных информационной системы учебно-методического управления высшего учебного заведения / И.В. Воронин, А.А. Жердер, С.Н. Мальцев -2007.

17. Воронин ИВ. Информационная поддержка управления БГТУ «Военмех» / Итоговый отчет по НИР, 2006.

18. Винкоп, Стефан Использование Microsoft SQL Server 7.0. Специальное издание. : Пер. с англ. СПб.: Издательский дом «Вильяме», 2001. — 816с., ил.

19. Гаврилова Т.А. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф. Хорошевский- СПб.: Питер, 2001. 384 е.: ил.

20. Галузин К.С. Математическая модель оптимального учебного расписания с учетом нечетких предпочтений: Дис. канд. техн. наук: 05.13.18 / Пермь, 2004.

21. Гимади. Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации. Труды Института математики. Новосибирск. Наука. Сиб. Отд-ние. 1988. с. 89-115.

22. Гуз Д.С., Фуругян М.Г. Планирование вычислений в многопроцессорных АСУ реального времени с ограничениями на память процессоров // Журнал Автоматика и телемеханика, №2,2005.

23. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. -М.: Мир, 1982.-416с., ил.

24. Дубов В.М., Капустянская Т.И., Попов С.А., Шаров А.А. Проблематика сложных систем СПб.: Элмор, 2006. - 184с.

25. Методы робастного, нейро-нечеткого и адаптивного управления: Учебник / Под ред. Н.Д. Егупова. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 744 е., ил.

26. Емельянов В.Ю., Кругликов В.К. Теория принятия решений: базовые методы СПб.: БГТУ, 2006.-160с.

27. Емельянов В.Ю. Методы моделирования стохастических систем управления СПб.: БГТУ, 2004.-152с.

28. Заде JI. Понятие лингвистической переменной и его применение к принятию приближенных решений -М.: Мир, 1976.

29. Автоматизация как основа оптимального планирования учебного процесса университета / A.C. Зайцев и др. // Мехатроника, автоматизация, управление. -2007.- №5. -С. 45-48.

30. Информационная система учебно-методического управления университета / A.C. Зайцев и др. // Региональная информатика 2006 (РИ - 2006): материалы X ме-ждунар. конф. - СПб: СПОИСУ, 2006. - С. 201-202.

31. Заславский A.A. Использование стратегии расслоения переменных в общих задачах целочисленного линейного программирования // Экономика и мат. методы. 1997. Т. 33. Вып. 2.

32. Заславский A.A. Комбинированный метод решения задач о рюкзаке // Экономика и мат. методы. 1999. Т. 35. Вып. 1.

33. Жданова Е.Г. Теория расписаний М.: - 2000.

34. Карманов В.Г. Математическое программирование Л.: ЛГУ, 1986. - 286с.

35. Карпов Б., Баранова Т. С++: специальный справочник — СПб.: Питер, 2003. 480с. ил.

36. Карпов Ю.Г. Теория и технология программирования СПб.: БХВ-Петербург, 2005. - 272с., ил.

37. Рейсдорф К., Хепдерсон К. Borland C++Builder: Освой самостоятельно / Пер. с англ. — М.: «Издательство БИНОМ», 1998г. 704с.: ил.

38. Командровский В.Г. О планировании в вычислительной системе // Журнал Автоматика и телемеханика, №12,2005.

39. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975. -282с.

40. Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. 2002. №3.

41. Костин С.А. Модели и методы многокритериальной оптимизации начального расписания занятий: Дис. канд. техн. наук: 05.13.18 / Саратов, 2005.

42. Кофман А. Введение в теорию нечетких множеств М.: Радио и связь, 1982. - 432с.

43. Коффман Э.Г., Бруно Дж.Л. Теория расписаний и вычислительные машины. М.: Наука, 1984.-336с.

44. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. — М.: Мир, 1977.-432с.

45. Лагоша Б.А., Петропавловская A.B. Комплекс моделей и методов оптимизации расписания занятий в вузе // Экономика и мат. методы. 1993. Т. 29. Вып. 4.

46. Лазарев A.A. Паретно-оптимальное множество NP-трудной задачи минимизации максимального временного смещения // Изв. РАН. ТиСУ. 2006. №6. с. 103-110.

47. Лебедев С.С. Модификация метода Бендерса частично целочисленного линейного программирования // Экономика и мат. методы. 1994. Т. 30. Вып. 2.

48. Лебедев С.С., Заславский A.A. Использование специального метода ветвей и границ для решения целочисленной обобщенной транспортной задачи // Экономика и мат. методы. 1995. Т. 31. Вып. 2.

49. Лебедев С.С. О методе упорядочивающей индексации целочисленного линейного программирования // Экономика и мат. методы. 1997. Т. 33. Вып. 2.

50. Лебедев С.С., Заславский A.A. Модифицированный метод пометок для задач булева программирования // Экономика и мат. методы. 1998. Т. 34. Вып. 4.

51. Левин В.И. Уточнение задачи Беллмана-Джонсона // Изв. РАН. ТиСУ. 2004. №5 с. 109-112.

52. Левин В.И. Оптимизация расписаний в конвейерных системах с переменным порядком выполнения работ // Журнал Автоматика и телемеханика, №3, 2005.

53. Левин Р. Практическое введение в технологию искусственного интеллекта и экспертных систем с иллюстрациями на Бейсике: Пер. с англ. — М.: Финансы и статистика, 1990.-239с.: ил.

54. Липский В. Комбинаторика для программистов : Пер. с польск. М.: Мир, 1988. — 213с.: ил.

55. Лопатеева О.Н. Система автоматизированного формирования учебного расписания в высшем учебном заведении на основе эвристических алгоритмов : Дис. . канд. техн. наук : 05.13.01 / Красноярск, 2006. 200 с.

56. Лосев С.А., Толмачев С.Г. Системы искусственного интеллекта СПб.: БГТУ 2005. -84с.

57. Макарцова Е.А. Средства моделирования и численные методы в задаче формирования начального расписания занятий: Дис. канд. техн. наук: 05.13.18 / Саратов 2006.

58. Макконнел С. Совершенный код. Мастер-класс: Пер. с англ. Спб.: Питер, 2005. -896с.: ил.

59. Маклаков С.В. BPwin и ERwin. Case-средства разработки информационных систем -М.: ДИАЛОГ-МИФИ, 2000 256с.

60. Марков A.A. Комбинаторно-алгебраические методы в прикладной математике — Горький: ГТУ, 1981. 164с.

61. Маслов М.Г. Разработка моделей и алгоритмов составления расписаний в системах административно-организационного управления: Дис. . канд. техн. наук: 05.13.18 / Москва, 2004.

62. Мину M. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.-488с.

63. Мирецкий И.Ю. Субоптимальные решения задачи об M станках // Изв. РАН. ТиСУ. 2004. №1.

64. Михайлевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. — М.: Наука, 1983. — 207с.

65. Москвин П.В. Азбука STL — М.: Горячая линия-Телеком, 2003. 262с.:ил.

66. Э. Мулен. Кооперативное принятие решений: Аксиомы и модели. — М.: Мир, 1991. -463с.

67. Насибов Э.Н. Методы обработки нечеткой информации в задачах принятия решений -Баку: Элм, 2000. -260с.

68. Насибов Э.Н. Алгоритм построения допустимого решения в задаче упаковки в контейнеры с нечеткими ограничениями // Изв. РАН. ТиСУ. 2004. №2. с. 50-57

69. Низамова Г.Ф. Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов: Дис. . канд. техн. наук: 05.13.01 / Уфа, 2006.

70. Новиков С.А. Дискретная математика для программистов СПб.: Питер, 2003. -304с.: ил.

71. Орлов С.А. Технологии разработки программного обеспечения — СПб.: Питер, 2002. -464 с.

72. Поспелов Д.А. Нечеткие множества в моделях управления и искусственного интеллекта / Под ред. Д.А. Поспелова М.: Мир, 1976. - 311с.

73. Рейнгольд Э., Нивергельт Ю., Део H Комбинаторные алгоритмы теория и практика: Пер. с англ. М. Мир, 1980. - 476с.

74. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений с учетом специфики 64 разрядной версии Windows: Пер. с англ. 4-е изд. — СПб.: Питер, 2003.-752с.:ил.

75. Сакович В.А. Исследование операций (детерминированные методы и модели) — Минск, 1985.-256с.

76. Сачков В.Н. Введение в комбинаторные методы дискретной математики — М.: Наука. Главная редакция физико-математической литературы, 1982. — 384 с.

77. Севастьянов C.B. Введение в теорию расписаний — Новосибирск, 2003. — 173с.

78. Сивохина Н.П., Родинов В.Б., Горбунов Н.М. Логистика: Учебное пособие М.: ООО «Издательство ACT», 2000. - 224с. :ил.

79. Стенли Р. Перечислительная комбинаторика: Пер. с англ. — М.: Мир, 1990. 440 е.: ил.

80. Страуструп Б. Язык программирования С++. Специальное издание. Пер. с англ. М.: ООО «Бином-Пресс», 2005. - 1104с.

81. Танаев В.С, Шкруба В.В. Введение в теорию расписаний — М.: Наука, 1975. 256с.

82. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний: Одностадийные системы М.: Наука, 1984. - 381с.

83. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний: Многостадийные системы М.: Наука, 1989. - 328с.

84. Танаев В.С, Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии Минск: Ин-т техн. Кибернетики НАН Беларуси, 1998. - 290с.

85. Taxa X. Введение в исследование операций: В 2 кн. Кн. 1. — М.: Мир, 1985. -496с.

86. Тихомиров Ю.В. Microsoft SQL Server 7.0. СПб.: БХВ-Петербург, 2001. - 720с.: ил.

87. Топорков В.В. Оптимизация распределения ресурсов в системах жесткого реального времени //Изв. РАН. ТиСУ. 2004. №3 с. 61-71.

88. Уоссерман Ф. Нейрокомпьютерная техника. Теория и практика. М.: Мир, 1992 г. 250 с.

89. Уэллин С. Как не надо программировать на С++ Спб.: Питер, 2004. - 240с. ил.

90. Фаулер М., Скотт К. UML в кратком изложении. Применение стандартного языка объектного моделирования: Пер. с англ. -М.:Мир, 1999. — 191 е., ил.

91. Хоролич Г.Б. Решение задачи составления расписания посадок самолетов адаптивными поисковыми алгоритмами // Математические основы кибернетики: Сб. статей, 1992.-239.

92. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1979. - 519с.

93. Черноруцкий И.Г. Методы оптимизации и принятия решений: Учебное пособие. —

94. СПб.: Издательство «Лань», 2001. 384 с.

95. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. СПб.: БХВ-Петербург, 2006. - 400 е.: ил.

96. Шульгина О.Н. Общая схема решения одной NP-трудной в сильном смысле задачи теории расписаний // Журнал Автоматика и телемеханика, №3, 2004.

97. Шумаков П.В., Фаронов В.В. Delphi 5. Руководство разработчика баз данных М.: Нолидж, 2000. - 640с.

98. Even, S., A. Itai, AND A Shamir 1976., "On the complexity of timetable and multi-commodity flow problems," SIAM J: Comput. 5, 691-703.

99. Johnson S.M. Optimal two and three stage production schedules with set-up times included //Nav. Res. Log. Quart. 1954. V.l.№ 1 P. 61-68.

100. Программа для автоматического составления расписания уроков "АРМ XXIм -http://www.raspisanie.msk.ru/about/about.htm

101. Бесплатная программа составления расписания http://www.nnvinf.narod.ru/

102. АСТРА Программа для составления расписания занятий http://www.sama.ru/~vmf/

103. Составитель расписания http://www.timetabler.narod.ru/

104. Каталог ПО Пантелеева B.JI. http://panvladislav. 1 gb.ru/univercity.aspx

105. РАСПИСАНИЕ УРОКОВ Пррограмма по составлению школьного расписания уроков-ШКОЛЬНЫЙ ДИСПЕТЧЕР http://www.dispet.narod.ru/l 1 l.htm

106. Орловский региональный КЦ Главная страница - http://www.psbatishev.narod.ru/

107. Дискретная математика алгоритмы Алгоритмы теории расписаний http://rain.ifimo.iTi/cat/view.php/vis/schedule-theorv/schedule-theory-2003

108. Дискретная математика алгоритмы Задача о расписаниях http://rain.ifino.ru/cat/view.php/vis/schedule-theory/greedy-2001 -2

109. Дискретная математика алгоритмы Жадный алгоритм выбора заявок -http://rain.ifhio.ru/cat/view.php/vis/schedule-theory/greedy-2001-1

110. Дискретная математика алгоритмы Жадный алгоритм решения задачи о выборе заявок http://rain.ifmo.ru/cat/view.php/vis/schedule-theory/greedv-2006

111. Дискретная математика алгоритмы Задача Джексона о двух станках -http://rain.ifino.ru/cat/view.php/vis/schedule-theory/iackson-2002

112. Теория принятия решений http://www.math.nsc.ru/LBRT/k5/or.html

113. List of NP-complete problems Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/Listof NP-completeproblems#Multiprocessorscheduling

114. Ассоциация программистов России «Интеллект 21 век». E-mail: INTELLECT-21 @MAIL.RU

115. Компания «DigSee Ltd» http://www.digsee.com/rus/timetable

116. ООО «Хронобус» http://infoschool.at.tut.by/hronograf.html

117. ООО «НИКА-soft» (Москва) http://infoschool.at.tut.by/nika.html120. http://infoschool.at.tut.by/rector.html121. http://infoschool.at.tut.by/raspisanie2000.html

118. CyberMatrix Corporation Inc. http://www.cyber-matrix.com/csched.html

119. AVTOR-2+ программа для составления учебного расписания школ, колледжей, ВУЗов. http://avtor-2.narod.ru/