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

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

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

МАСЛОВ Михаил Геннадьевич

Москва - 2004

Работа выполнена на кафедре "Компьютерные технологии и системы" Московского государственного университета прикладной биотехнологии

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

■ доктор технических наук, профессор Ивашкин Юрий Алексеевич

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

- доктор технических наук, профессор Бобров Дмитрий Александрович

■ доктор технических наук, профессор Миронова Валентина Александровна

Ведущая организация

■ Московский государственный университет технологий и управления

Защита состоится » июня 2004 г. в 14 час. 15 мин. на заседании диссертационного совета К212.149.03 при Московском государственном университете прикладной биотехнологии по адресу: 109316, г. Москва, ул. Талалихина, 33, конференц-зал.

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

93

Автореферат разослан «.-*- '» мая 2004 г.

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

Потапов А.С.

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

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

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

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

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

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

• разработка алгоритмов построения и рационализации расписаний в соответствии с выбранными критериями;

• синтез состава и структуры автоматизированной информационной системы составления расписаний и графиков выполнения работ.

Научная новизна.

• Сформулирована расширенная постановка задачи составления расписания занятий в вузе и предложена методика её решения на основе формализованных знаний.

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

• Разработаны эвристические и генетические алгоритмы решения поставленных задач составления расписаний.

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

Методы исследования.

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

Практическая значимость работы.

• Разработан программный комплекс «Университетское расписание» для составления расписания учебных занятий. Данная система имеет трёхзвенную архитектуру, позволяющую снизить время на её обслуживание, что особенно актуально для крупных вузов, поддерживает распределённый ввод и обработку информации.

• Разработана информационная модель планирования учебного процесса.

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

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

• На базе объектно-ориентированной методологии разработаны методика и программная реализация для создания автоматизированных систем составления расписаний. Созданы средства автоматической генерации исходного кода для данного типа приложений.

Основные положения, вынесенные на защиту:

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

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

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

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

Внедрение результатов работы.

Программный комплекс для составления расписания учебных занятий в вузе используется при составлении расписаний в МГУПБ, что подтверждается актом внедрения. Программа "Университетское расписание" ("UшSched") и база данных "Расписание учебных занятий в вузе" ("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 свидетельства об официальной регистрации.

Структура и объем диссертации.

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

текста, включая 21 рисунок 3 таблицы. Список использованных источников содержит 303 наименования.

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

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

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

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

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

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

Таблица 1

1 ГРУППЫ (7={g: g= I..|G|}

2 ПРЕПОДАВАТЕЛИ Р={р:р= l..|P|}

3 ДИСЦИПЛИНЫ D={d-.d= l..|£>|}

4 ВИДЫ ЗАНЯТИЙ V= {v: v= 1 ..|F1>

5 АУДИТОРИИ A = {a: a = l..\A\}

6 НЕДЕЛИ N={n: «= l..|iV|}

7 ДНИ 5={s: s= l..|5|}

8 ПАРЫ Г={г. t= l..|7]}

9 КОРПУСА

|jV| = 2. Я= {A: h = 1..|#1} единица времени h = h(n,s,t)=(n-\)\S\+(s-\)\1\ +1.

||СМст || |C|x|JW| ~ соответствие между группами и потоками; ||С1с/1| |С|х|1|- соответствие между группами и подгруппами;

aeKk, К= |J Кь 0, к(а) - корпус аудитории а;

Гц: / = 1 = 1 - длительности перехода между корпусами;

Xgpdvanst ~ Л если в g-й группе по d-й дисциплине назначен v-й вид занятия у р-го преподавателя в а-й аудитории в 5-й день на t-й паре м-ой недели, и 0 в противном случае;

8 (массив, индекс элемента^ - функция, возвращающая TRUE, если элемент массива представляет собой обязательное требование и FALSE,

если требование желательно;

¡\Qg II |(7| - вектор численности групп;

II |Л| - вектор вместимости аудиторий;

И^глИ |С|*№|ЛТ| - количество пар по занятию г у £-ОЙ группы в неделю п

||Я ^Ц |С|х|Д:с|.М| - число занятий 7 на неделе п у группы с (с учётом потоков и подгрупп в которые она входит);

Щс,к) - функция, возвращающая 1, если в единицу времени к в группе с или в каком-либо потоке или подгруппе, в которые она входит, проходит занятие, 0 в противном случае:

Я(е,п,я) - функция, возвращающая 1, если на неделе п в дне 5 существует хотя бы одно занятие у группы с или в каком-либо потоке или подгруппе,

в которые она входит;

Ц Рр 0К0К|| - требование преподавателя р о проведении его занятий без окон: 0 - означает наличие, 1 - допустимость наличия или отсутствия, 2 -отсутствие окон;

|| || |с|- максимальное число пар в день у учебной группы с;

\\Р№рП1!таХ ПаР || - максимальное количество пар занятий в день 5 на

неделе п у преподавателяр\

Р2(пу8,е) - предикат, отражающий требование проведения занятий в группе с, а также в сформированных из неё подгруппах и потоках на неделе п в день 5 в одном и том же корпусе;

- множество групп состоящее из учебной группы с, а также из формируемых из неё подгрупп и потоков:

Р2(п, = ф (3 Ь к)-. (I е ¥с &.Х1ргат{ = 1 & аеКк) =>

¿V г)(П / е уу: (Хщатг= 1 => аеку Ограничения

1. По нормам проведения занятий.

1.1. В единицу времени у группы, преподавателя и в аудитории должно проходить не больше чем одно занятие:

1.2. Учёт наличия потоков и подгрупп:

(1К с): К(ф й 1

1.3. На вместимость аудиторий:

(V К ё, а): ^вм * * ^

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

2.1. В каждой группе g необходимо провести требуемое количество пар по каждому занятию г, за период планирования:

2.2. Должно выполняться указанное в С2%гп распределение по неделям:

3. Ограничения, задаваемые перечислением допустимыхресурсов.

В обозначениях массивов ограничений сначала записываются обозначения множеств ограничений О^^Ь^У^^, а затем обозначения

временных и (или) материальных ресурсов с ограничениями A,K,N,S,T,H. Различные сочетания элементов, задающих ограничения на ресурсы, определяют множество ограничений перечислимого типа. Каждый элемент получаемого таким образом массива представляет собой число [0..Л] - лингвистическую переменную (например, 0 - означает невозможность, 1 - допустимость, 2 - желательность, занимать данный ресурс). Таким образом, можно сконструировать необходимые, в нашем случае, обозначения, массивов, определяющих ограничения:

- допустимое или желательное время проведения занятий

преподавателем;

У^GDV_Hgctvtf\ |б|х|.0|х|1/|х|.Н| - допустимое или желательное время проведения занятий по дисциплине-виду у группы;

\\DV_A ¿Ыа\( \D\x\V\x\A\ - допустимая или желательная аудитория для проведения занятий по дисциплине-виду;

- допустимый или желательный корпус для проведения занятий по дисциплине-виду;

\\GDVPgdvp ц \g\x\D\x\ У\х\Р\ - преподаватель р, занимающийся с g-ой. группой по d-ой дисциплине у-му виду занятий;

Занятия должны назначаться в допустимое время, допустимой аудитории и корпусе, и проводиться установленными преподавателями:

Х&сЫапй * СПУРфр*Р_НрНМ* СОУ_Нфю1 * ОУ_А ¿уа*

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

4. Ограничения, задаваемыелогическимиусловиями.

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

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

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

Примеры построения ограничений логического типа приведены ниже.

4.1. Требование отсутствия окон у преподавателя:

Р1(р,п,з•) = (V 1,еТ, ¡2еТ, // <

(Х&гаю*! = 1&<Г^=1 .. Ц -1) (V В,г,а): Хёргат( = 0) V (ц = \))) & (Ххргат1! = 1 & = (2+ 1.. 7У (V Х?ргат( = 0)\ (12 = Т))) =>(№ =

11.л2у.С*№) = I) (У р,п,зу. (8(Р безокон, р) & (Рр безокон> I) о Р1(р, п, 8))

л_/ 1 /с /п без окон . „ без окон . ., , ,,

(Уры): (5 (Р ,р)& (Рр < 1; => -1 И,

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

(V с,п,з): (5(С тахпар, с) => X <Сстахпар)

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

V (р.п.з): (5(Р№ тахтр,р,п,з) => ЪХцргам <Р№рттах"ар)

Критерии

1. Критерии требований перечислительного типа.

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

X Р-Н рк * Х№хак тах

Аналогичным образом могут быть построены и остальные критерии данного типа.

2. Критерии требований логического типа.

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

2.1. Минимизация интервала времени между первым и последним занятием группы в день (минимизация окон):

X ('max (t* R(c,h(n,s,t))) - min (t* R(c,h(n,s,t)))) ->min

2.2. Минимизация интервала времени между первым и последним занятием в день у преподавателя:

£ ( max. 0*Xgpzanst)) ~ min^(t*Xgpzanst))min

2.3. Равномерное число занятий в день у группы:

2.4. Минимизация количества неиспользованных мест в занятых аудито-

риях:

Z Xgpzah * (Wa - Qg * X№Zah ) -> min (Vg,p,z,a,h)

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

]Г sign (Р2(п, s,c))-± max

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

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

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

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

Рис. 1. Блок-схема процесса составления расписания учебных занятий в вузе.

Предлагается следующая формула для вычисления степени некритичности заявки

где V— количество допустимых временных ресурсов;

А - количество допустимых аудиторных ресурсов;

D - общая длительность занятия;

R - размер потока;

F- длительность непрерывного занятия; - коэффициенты.

Чем больше значение 8, получаемое для заявки по данной формуле, тем она менее критична. Далее следует распределение заявок в соответствии с их некритичностью и статусами (степень обязательности выполнения требований) преподавателей. При распределении конкретной заявки в зависимости от её

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

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

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

Представление расписания в виде хромосомы (chromosomal representation). Хромосома представляет набор из И1*1.Н1 генов, которые удобно представить в виде матрицы, по строкам которой идут временные, а по столбцам аудиторные ресурсы. В ячейках данной матрицы находятся гены. Геном в данном случае является заявка. В локусе (местоположение определённого гена в хромосоме), которым является ячейка может

находиться только одна заявка, либо ничего (т.е. нулевой указатель).

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

Г Начало ^

X

Создание начальной популяции

Вычисление фиттнеса (функции приспособленности)

Переход к следующему поколению

Выбор системы скрещивания

Кроссовер

■Ь

Коррекция генов

и— —Ь»пД»чнм|Ц ЧИСЛО ПОТОМКОВ гфпрмиппияип

-1 Выбор типа мутации

Мутация

--- '—""^^^^Щобходимое число потомков сформированд_^Д^

Вычисление фиттнеса

Выбор схемы отбора

Отбор

—«^^^^Условия окончания эволюции т-™™»— ■

Получение решения

С Стоп )

Рис. 2 Блок-схема работы генетического алгоритма.

Начальное решение (initial population) может быть получено при помощи эвристического алгоритма, рассмотренного ранее.

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

Кроссовер (crossover). Для данной задачи было разработано два специализированных вида операторов кроссовера (crossover).

Первый вид кроссовера осуществляется путём скрещивания двух хромосом по следующей схеме:

1. Выбор двух особей (т.е. расписаний).

2. Определение числа точек кроссовера (случайно, от 1 до 3).

3. Определение (случайным образом) точек кроссовера, приходящихся на один из интервалов между днями.

4. Формирование двух рекомбинантных гамет потомков.

5. Проверка на допустимость потомков и возможная коррекция.

Второй вид кроссовера осуществляется путём повторения заданного числа раз скрещивания в самой хромосоме каких-либо двух временных интервалов (пар) следующим образом.:

1. Случайный выбор двух интервалов (пары).

2. Скрещивание (используется многоточечный кроссовер).

3. Проверка и коррекция.

4. Запись в потомка.

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

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

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

В качестве условий завершения (stopping conditions, termination) используются следующие функции завершения: количество поколений (number of generations), сходимость по потери разнообразия (diversity converged), сходимость функции пригодности (fitness converged), значение функции пригодности (fitness target). В последнем случае процесс завершается, если достигнуты уровни выполнения задаваемых требований.

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

В разработанных системах реализована трёхзвенная архитектура. В качестве сервера БД, могут быть использованы Oracle, Microsoft SQL Server и Interbase. Co стороны клиента не требуется никакой инсталляции, что является преимуществом использования трёхзвенной архитектуры.

Автоматизированная система составлениярасписанияучебныхзанятий в вузе "Университетское расписание" состоит из следующих основных подсистем:

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

"Кафедра" - для формирования выписок и распределений-лекционных потоков на кафедрах на основе графиков занятий составленных в деканатах;

"Расписание" - для построения и коррекции расписания в ручном и автоматическом режимах, включая просмотр полученного варианта с возможностью комментариев по поводу неувязок.

На рис. 3 представлен интерфейс программы с примером составленного расписания.

Рис. 3 Пример составленного расписания учебных занятий.

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

В приложениях представлены: документы, подтверждающие внедрение результатов диссертационной работы, свидетельства об официальной регистрации, обзор существующих программных систем для составления расписаний учебных занятий, выходные формы и результаты решения задач, структуры баз данных автоматизированных систем в нотации ГОЕИХ (Чена-Баркера), фрагменты исходного кода.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

5. Разработана математическая модель составления графиков работы персонала в организациях с плавающим режимом работы. Данная задача является новой и не сводится к известным типовым моделям теории расписаний или дискретного программирования.

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

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

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

9. На основе проведенного моделирования информационной среды вуза создана структура базы данных для распределённого многопользовательского сбора и хранения информации при подготовке и

составлении расписания занятий в вузах и других учебных заведениях аналогичного типа.

10. Разработана структура базы данных для задачи составления графиков работы персонала, совместимая и интегрируемая с программным комплексом "АиТ:Управление персоналом".

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

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

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

Список публикаций:

1. Маслов М.Г. Система поддержки принятия решений в составлении расписания занятий в вузе // Пища, Экология, Человек: Труды четвёртой международной научно-технической конференции - М., 2001. - С.269-273.

2. Ивашкин Ю.А Маслов М.Г. Система поддержки принятия решений при составлении расписания занятий в вузе // Новые информационные технологии в региональной инфраструктуре и образовании: Труды международной научно-технической конференции. - Астрахань, 2001. -С.169-171.

3. Ивашкин Ю.А., Дзюбко СИ., Маслов М.Г. Экспертная система построения расписания работы сотрудников // Интеллектуальные системы (ИН-ТЕЛС2002): Труды пятого международного симпозиума. 2-4 июля 2002 г. - Калуга, 2002. - С.275-277.

4. Маслов М.Г. Эвристический алгоритм решения задачи составления расписания учебных занятий в вузе // Математические методы в технике и техно-

логиях: Сб. трудов XV Международной научной конференции. В 10-и т. 2 -4 июня 2002 г. - Тамбов, 2002. - Т. 9. - С.86-88.

5. Маслов М.Г. Система построения расписания работы сотрудников // Теория конфликта и её приложения: Труды второй всероссийской научно-технической конференции. 30 сентября - 4 октября 2002 г. - Воронеж, 2002. -С.209-211.

6. Маслов М.Г. Алгоритм решения задачи составления расписания учебных занятий в вузе // Теория конфликта и её приложения: Труды второй всероссийской научно-технической конференции 30 сентября - 4 октября 2002 г. -Воронеж, 2002. - С.216-217.

7. Маслов М.Г. Генетический алгоритм для задачи составления расписания занятий в вузе // Современные проблемы математики, механики, информатики: Тезисы докладов Всероссийской научной конференции. 20 -22 ноября 2002 г. - Тула: ТулГУ. 2002. - С. 214-218.

8. Маслов М.Г. Автоматизированная система построения графиков работы персонала для организаций с плавающим режимом работы // Современные проблемы математики, механики, информатики: Тезисы докладов Всероссийской научной конференции. 20 - 22 ноября 2002 г. - Тула: ТулГУ. 2002.-С.218-222.

9. Маслов М.Г. Автоматизированная система составления расписания учебных занятий в вузе // Математические методы и информационные технологии в экономике, социологии и образовании: Труды XI международной научно-технической конференции. 22 - 23 мая 2003 г. -Пенза, 2003.-С.303-305.

10. Маслов М.Г. Применение генетического алгоритма для решения задачи составления расписания занятий в вузе // Компьютеризация обучения и проблемы гуманизации образования в техническом вузе: Труды международной научно-методической конференции. 15-18 апреля 2003 г. - Пенза, 2003. - С.296-298.

11. Маслов М.Г. Применение эвристического подхода для разработки алгоритма составления расписания занятий в вузе // Университетское образование: Труды VII международной научно-методической конференции. 10-11 апреля 2003 г. - Пенза, 2003. - С. 165-166.

12. Маслов М.Г. Автоматизированная система планирования работы сотрудников Современные информационные технологии в науке, производстве, образовании и управлении // Труды третьего украино-

российского научно-технического и методического симпозиума. 16-19 апреля 2003 г. - Хмельницкий, 2003. - С.156-158.

13. Маслов М.Г. Эвристический подход при автоматизированном составлении расписания учебных занятий в вузе // Применение новых технологий в образовании: Материалы XIV международной научной конференции. 26 -27 июня 2003 г. - Троицк, 2003. - С.324-326.

14. Маслов М.Г. Решение задачи составления плавающего графика работы персонала для организаций с изменяющейся по времени потребностью в нём // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта : Труды 2-й международной научно-технической конференции. 25 - 27 июня 2003 г. - Вологда, 2003 - С. 146-149.

15. Маслов М.Г. Компьютерная система для подготовки расписания занятий в вузе // Инновации в науке и образовании - 2003: Труды международной научной конференции, посвященной 90-летию высшего рыбохозяйственного образования в России. 13-15 октября 2003 г. -Калининград, 2003. - С.257.

16. Свидетельство об официальной регистрации программы для ЭВМ № 2004610313. "Университетское расписание" ("UшSched"). /Ивашкин Ю.А., Маслов М.Г./ - М.: Роспатент, 2004.

17. Свидетельство об официальной регистрации базы данных № 2004620036. "Расписание учебных занятий в вузе" ("UniSched DB"). /Ивашкин Ю.А., Маслов М.Г./ - М.: Роспатент, 2004.

Отпечатано в типографии ООО "Франтэра" ПД № 1-0097 от 30.08.2001г. Москва, Талалихина, 33

Подписано к печати 25.05.2004г. Формат 60x90/8. Бумага "Офсетная № 1" 80г/м2. Печать трафаретная. Усл.печл. 1,50. Тираж 100 Заказ 096 МГУПБ. 109316, Москва, ул. Талалихина, 33

WWW. РКАЭТЕЯЛ. ЯИ

- 1 40 45

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР И АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ И МОДЕЛЕЙ, ПОСТАНОВКА НАУЧНОЙ ПРОБЛЕМЫ И ОСНОВНЫЕ ЭТАПЫ ЕЁ РЕШЕНИЯ.

1.1. Обзор и анализ существующих методов и моделей составления расписаний учебных занятий.

1.1.1. Основные направления решения задачи составления расписания учебных занятий.

1.1.2. Точные алгоритмы генерации расписаний.

1.1.3. Эвристические подходы.

1.1.4. Диалоговые методы.

1.2. Общая постановка задачи составления расписания на примере МГУПБ.

1.2.1. Этапы постановки задачи автоматизации создания расписания учебных занятий.

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

1.2.3. Ограничения и пожелания, учитываемые при составлении расписания.

1.2.4. Требования к разрабатываемой программе.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ, МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СОСТАВЛЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ.

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

2.2. АТМтудность задачи составления расписания учебных занятий.

2.3. Методика оценки и сравнения различных вариантов расписаний

2.4. Иерархическая многоуровневая схема упорядочения критериев по их значимости.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ.

3.1. Эвристический алгоритм составления расписания.

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

3.1.2. Разрешение конфликтных ситуаций возникающих при распределении заявок.

3.2. Решение задачи с использованием генетического алгоритма.

3.2.1. Представление расписания в виде хромосомы (chromosomal representation).

3.2.2. Начальное решение (initial population).

3.2.3. Селекция (selection).

3.2.4. Система скрещивания.

3.2.5. Кроссовер (crossover).

3.2.6. Мутация (mutation).

3.2.7. Естественный отбор.

3.2.8. Оценка расписания (fitness evaluation).

3.2.9. Условия завершения (stopping conditions, termination).

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4. ОПИСАНИЕ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ АВТОМАТИЗИРОВАННЫХ СИСТЕМ СОСТАВЛЕНИЯ РАСПИСАНИЙ

4.1. Архитектура разработанных систем.

4.2. Описание программного обеспечения применявшегося для решения задач.

4.3. Программное обеспечение необходимое для функционирования программ.

4.4. Автоматизированная система составления расписания учебных занятий.

4.4.1. Функциональная структура системы составления расписания учебных занятий.

4.4.2. Сравнительный анализ автоматизированной системы "Университетское расписание" с аналогичными программами.

4.4.3. База данных автоматизированной системы составления расписания учебных занятий.

4.5. Автоматизированная система планирования графиков работы сотрудников.

4.5.1. Функциональное назначение программы.

4.5.2. Обзор разработанных алгоритмов для решения задачи составления графиков работы персонала.

ВЫВОДЫ ПО ГЛАВЕ 4.

Актуальность проблемы

Задачи синтеза расписаний являются предметом широких научных исследований с середины 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 наименования.

Выводы по главе 4

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

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

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

4. На базе объектно-ориентированной методологии разработаны методика и программная реализация создания автоматизированных систем составления расписаний учебных занятий.

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

6. Разработана структура и принципы работы распределённого программного комплекса для составления расписаний. Создана открытая для интеграции и включения дополнительных модулей, распределённая система с интерфейсом на основе СОМ-технологий.

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

В заключение можно сделать выводы о том, что:

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

2. Выполнен анализ информационных потоков и построена информационная модель формирования расписания. На основе информационной модели реализована структура автоматизированной системы составления расписаний.

3. Сформированы и формализованы ресурсные, учебно-организационные, формальные ограничения, проведён синтез критериев допустимости и рациональности расписаний.

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

5. Разработана математическая модель составления графиков работы персонала в организациях с плавающим режимом работы. Данная задача является новой и не сводится к известным типовым моделям теории расписаний или дискретного программирования.

6. На основе анализа разработанных математических моделей можно сделать вывод, что указанные задачи обладают характерными свойствами известных NP - полных задач составления расписаний, и являются NP - полными.

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

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

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

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

10. Разработана структура базы данных для задачи составления графиков работы персонала, совместимая и интегрируемая с программным комплексом "АиТ:\Управление персоналом".

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

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

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

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

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

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

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

1. Авербах И.Л., Цурков В.И. Оптимизация в блочных задачах с целочисленными переменными. — М.: Наука, 1995. — 228 с.

2. Автоматизация принятия решений и обработки данных в высшей школе / Под ред. Т.Н. Рахимова. Ташкент: 1980.

3. Автоматизация составления расписаний в вузе. — Киев: КПИ, 1972. — 144 с.

4. Автоматизация управления вузом. — М: Радио и связь, 1984. — 176 с.

5. Автоматизированные системы управления вузом / Под ред. Н.Г. Загоруй-ко. Новосибирск: НГУ, 1980.

6. Автоматизированные системы управления МАИ.— М: МАИ. 1976.

7. Автоматизированные системы управления учебным процессом / Под ред. У.А. Фрейналиса Рига: Рижский политехнический ин—т, 1979.

8. Акиндинов В.В. Относительная эффективность оптимальных алгоритмов многоэтапного поиска // Прикладные задачи технической кибернетики. — М., 1966.

9. Альтшуллер Г. С. Алгоритм изобретения. — М.: Наука, 1973.

10. Альтшуллер Г.С. Найти идею. Новосибирск: Наука, 1986.

11. Алыиарайда А. Оптимизация мультизадачного графика по временному критерию: Автореф. дис. . канд. техн. наук: 05.13.16 / Дагестанский государственный университет. — Махачкала, 2000. — 115 с.

12. Анисимов Б.В., Власов В.П. Анализ решающих правил машинных методов пошагового составления расписания учебных занятий // Математические и информационные проблемы прогнозирования и управления наукой. — Киев: Институт кибернетики АН УССР, 1971. С.113-122.

13. Анисимов Б.В., Власов В.П. Проблема автоматизации диспетчерской службы вуза // Применение ЭВМ в учебном процессе. М., 1969.

14. Анисимов Б.В., Власов В.П., Савельев А.Я. Метод решения задач составления расписания учебных занятий // Всесоюзный семинар по применению ЭВМ в организации и планировании учебного процесса: Тез. докл. — М., 1969

15. Анисимов Б.В., Власов В.П., Савельев А.Я. Разработка машинного алгоритма составления расписания учебных занятий // Применение ЭВМ в учебном процессе. М., 1969. - С.85-95.

16. Анисимов Б.В., Савельев А.Я., Карпов В.М. Разработка машинных алгоритмов составления учебного плана // Применения ЭВМ в учебном процессе. М., 1969. - С.32-40.

17. Анисимов Б.В., Сазонов Б.А., Власов В.П. Основные направления развития подсистемы "Расписания" АСУ МВТУ. // Создание и развитие подсистемы "Расписание" АСУ МВТУ. М., 1976. - С.62-79.

18. Анисимов Б.В., Соломагин Н. И., Власов В.П. Об автоматизации оперативной работы диспетчерской службы вуза // Программированное обучение и методы автоматизации учебного процесса / МВТУ. — 1968.

19. Антонюк Б.Д. Информационные системы в управлении. М.: Радио и связь, 1986.

20. Аоки М. Введение в методы оптимизации. — М.: Наука, 1977.

21. Архангельский С.И. Лекции по научной организации учебного процесса в высшей школе. М.: Высшая школа, 1976. 200 с.

22. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.-288 с.

23. АСУ Московского института нефтехимической и газовой промышленности им. И. М. Губкина. -М: НИИВШ, 1976.

24. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ. — М.: Мир, 1979. — 536 с.

25. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ. М.: Издательский дом "Вильяме", 2001. - 384 с.

26. Бабич В.М. Раецкий Л.И. Модели и результаты автоматизации решения задач расписаний учебного процесса // Методы и системы технической диагностики. Саратов: СПУ, 1991. - С.99-102.

27. Бабкин В.Ф. Разработка и реализация оптимизационных моделей и механизмов управления высшим учебным заведением: Автореф. дис докт.техн. наук: 05.13.10 / Воронежский гос. архитектурно-строительный университет. — Воронеж, 2001. — 330 с.

28. Бардадым В.А. Исследование оптимизационных задач, связанных с составлением расписаний учебных занятий: Дисс. . канд. техн. наук. — Киев, 1991.- 120 с.

29. Баркан С.А., Танаев B.C. О построении расписаний учебных занятий // Весщ акадэмп навук БССР, серыя ф!зша-матэматычных навук. — 1970. № 1. - С.76-82.

30. Барраклоу Э. Применение электронно-цифровых вычислительных машин для составления расписания учебных занятий // Кибернетика и проблемы обучения: Пер. с англ. A.M. Довгяло. — М.: Прогресс, 1970. С.323-349.

31. Баталин Г.А. Эмпирико-статистическое моделирование психологических типов в задачах управления персоналом: Автореф. дис. . канд. техн. наук:. 05.13.01 / Санкт-Петербургский институт информатики и автоматизации РАН. Санкт-Петербург, 2001. - 136 с.

32. Белёнова Н.К. Равномерное распределение потока по стоковым дугам сети // Автоматика и телемеханика. — 1987. № 11. — С. 144—154.

33. Беллман Р. Динамическое программирование: Пер. с англ. — М.: Издательство иностранной литературы, 1960. — 400 с.

34. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования: Пер. с англ. / Под ред. А.А. Первозванского. — М.: Наука, 1965. — 460 с.

35. Белова Н.Б., Краснер Н.Я. Модели и методы построения расписаний учебных занятий. — Воронеж: ВГУ, 1984. — С.43-55.

36. Белый Б.М. Разработка и исследование некоторых приёмов и методов решения дискретных задач принятия решений (на примере задач теории расписаний). — Киев, 1987.

37. Бердж К. Теория графов и её применения. — М., 1962.

38. Беркинблит М.Б. Нейронные сети — М.: МИРОС, 1993.

39. Бондаренко В.Ф., Кирпичников М.В., Шкляр В.Б. Методы оптимального планирования и диспетчирования вычислительных систем. Обзорная информация. Минск: БелНИИНТИ. 1976, с.26-30.

40. Брахман Т. Р. Многокритериальность и выбор альтернативы в технике. — М.: Радио и связь, 1984.

41. Бугаев В.Н., Савинков В.М., Пестерев В.Ф. Составление расписания занятий в вузе с применением ЭЦВМ // Тезисы докладов Всесоюзной межвузовской научно-технической конференции по проблемам научной организации труда в вузах / МИЭИ. 1969. — Вып. 2.

42. Бузунов Ю.А., Корчака Н.М. Алгоритм понедельного распределения занятий // Вестник высшей школы. — 1968. № 10. — С.42-46.

43. Бузунов Ю.А., Корчака Н.М. Применение ЭЦВМ для составления расписания занятий вуза // Применение ЭВМ в учебном процессе: Сб. науч. тр. — М., 1969.

44. Бузунов Ю.А., Корчака Н.М. Что такое хорошее расписание // Вестник высшей школы. — 1968. — № 10.

45. Быков В.Е. Автоматизация управления в системе просвещения. — Томск: Томский университет, 1984.

46. Василенко С.И. Некоторые задачи теории расписаний. — М.: ВЦ АН СССР, 1986.

47. Вахания Н. Н. Шафранский В. В. Алгоритмы решения обобщенных задач теории расписаний. М: ВЦ РАН, 1991.

48. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. Д.Б. Подшивалова. -М.: Мир, 1989.-360 с.

49. Власов В.П. Автоматизированная подсистема учета, контроля и анализа состояния разработки АСУ высшей школы. АКР АСУВ. М.: Отд. науч. информ., 1977.-31 с.

50. Власов В.П. Применение ЭВМ для решения задач планирования учебного процесса в вузе: Автореф. . канд. техн. наук. — М., 1970. — 16 с.

51. Власов В.П., Петров В.Я. Об автоматизации составления учебных расписаний для вуза. //Программированное обучение и методы автоматизации учебного процесса. М.: МВТУ им. Н.Э.Баумана, 1968. С.34—43.

52. Власов В.П., Савельев А.Д. Алгоритм составления расписания // Научная организация учебного процесса /МВТУ. — 1969. — Вып. 2.

53. Волков Ю.В. Решение задач управления в АСУ с использованием функциональных моделей // Автоматизация управления вузом: Темат. сб. науч. тр. М: НИИВШ, 1985. - С.54-65

54. Вопросы планирования высшего образования / Под ред. Е.Н. Жильцова. — М.: Изд-во Моск. ун-та., 1972. — 152 с.

55. Всесоюзная научная конференция по разработке автоматизированных систем высшей школы. М., 1970. С. 46, 54, 58.

56. Гарипов В.Р. Многокритериальная оптимизация систем управления сложными объектами методами эволюционного поиска: Дис. . канд. техн. наук: 05.13.01.-Красноярск, 1999. 166 с.

57. Гендин H.JI. Мосьпан В.И. Алгоритм решения задачи составления учебного расписания. Научная организация учебного процесса. Выпуск ДПИ, 1969.

58. Гене Г.В., Левнер Е.В. Приближенные алгоритмы для некоторых универсальных задач теории расписаний // Изв. АН СССР, Техническая кибернетика. 1978. - № 6. - С.38-43.

59. Герман Э.И., Макаров И.П. Об использовании элементов метода ветвей и границ в схемах динамического программирования // Изв. Том. политехи, ин-та. 1976., С. 17-21.

60. Герман Э.И., Пак Л. В., Чудинов В.Н. Решение задачи распределения аудиторного фонда в вузе. Новосибирск: НГУ, 1978. - С. 138-142.

61. Гермейер Ю. Б. Введение в теорию исследования операций — М.: 1971.

62. Глушков В.М. Основные проблемы использования вычислительной техники в учебном процессе // Применение ЭВМ в учебном процессе. — М., 1969.

63. Горбаченко И. М. Методы моделирования процесса обучения и разработка интерактивных обучающих курсов: Автореф. дис. . канд. техн. наук: 05.13.01 / Сибирский гос. технологический университет. — Красноярск, 2001.-176 с.

64. Горская Г.И., Чуракова Р.Г. Организация учебно-воспитательного процесса в школе. — М.: Просвещение, 1986. — 208 с.

65. Григоришина И.А. Инструментальная поддержка учебного процесса в условиях применения автоматизированных учебных курсов: Дис. . канд. техн. наук. Киев, 1984. - 209 с.

66. Григорьев А. В. Представление генетических алгоритмов сетями Петри в задаче размещения: Дис. . канд. техн. наук: 05.13.18 / Чувашский государственный университет имени И.Н. Ульянова. — Казань, 2002. — 171 с.

67. Гурин Л. С. Дымарский Я. С., Меркулов А. Д. Задачи оптимального распределения ресурсов — М.: Сов. радио, 1968.

68. Гусев И.Т., Мухин Э.В., Сумароков Л.Н. О методологических принципах применения количественных методов при исследовании учебного процесса в ВУЗе // Программированное обучение / КГУ. — Киев., 1969. — № 4,5.

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

70. Демидович А.К., Прокопенко Г.К. Компьютерные технологии построения тарификационного плана и составления расписания занятий: Учебное пособие/ Акад. последиплом. образования. Мн., 2002 — 52 с.

71. Дерябина P.M. Моделирование и оптимизация синхронизирующих расписаний: Автореф. дис. . канд. техн. наук: 05.13.16 / Институт угля и угле-химии СО РАН. Кемерово, 2000. - 22 с.

72. Джофрион А. Дайер Дж., Файнберг А. Решение задач оптимизации при многих критериях на основе человеко-машинных процедур // Вопросы анализа и процедуры принятия решений. — М.г Мир, 1976.

73. Дзюбко С.И. Разработка и исследование алгоритмов составления расписаний в задачах планирования и оперативного управления: Дисс. . канд. техн. наук: 05.13.10 / ИПУ. -М., 1986. 132 с.

74. Довгялло A.M., Мехтиев Г. Б., Петрушин Р.А. Экспертная система по составлению учебных программ //Методы и системы технической диагностики. Часть 1 . Экспертные обучающие системы. — Саратов: СГУ, 1989. — С.98-101.

75. Домбровский P.JI., Здрок В.В. Задача оптимального управления процессом проектирования АСУ // Автоматизированные системы управления высшим учебным заведением: Изв. при Львов, ун-те. — Львов: Вища школа, 1979. С.51—58.

76. Домбровский Р.Л., Здрок В.В. Подсистема автоматизированного составления расписания занятий в АИС вуза // Исследование операций и АСУ: Межведомственный научный сборник. Киев, 1976. Вып №7. — С.49-61.

77. Дубов К.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука. Главная редакция физ.-мат. лит., 1986.

78. Есипов Б.А., Бородин Н.Б. Оптимальное планирование и управление учебным процессом студентов // Проблемы создания автоматизированной системы управления ВУЗом. Томск: Изд-во. Том. гос. ин-та, 1978. С.153-161.

79. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума.-М.: Наука, 1991.

80. Зайцева Е.Н. Станкевич Ю.А. Некоторые современные методы решения оптимизационных задач // Материалы Второй международной конференции "Новые информационные технологии в образовании". — 1996.

81. Зарубицкая Т.Ф. Самойленко А.Т. О подсистеме автоматизированного составления расписаний учебных занятий //Опыт разработки и внедрении АСУ ВШ в Киевском государственном университете. — М.: НИИВШ, 1976. -С.35^0.

82. Здрок В.В. Математическое обеспечение типовой подсистемы системы планирования учебного процесса // Автоматизированные системы управления высшим учебным заведением. — Львов: "Вища школа", Изд-во при Львов.ун-те, 1979. С. 16-29.

83. Здрок В.В. Об автоматизации составления расписаний занятии // Автоматизированные системы управления высшим учебным заведением. — Львов: "Вища школа", Изд-во при Львов.ун-те, 1977. С.30-39.

84. Здрок В.В. Подсистема "Расписание" в АСУ Вуз "Сигма" // Автоматизированные системы управления высшим учебным заведением. — Львов: "Вища школа", Изд-во при Львов, ун-те, 1979. — С.8-16.

85. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. — М.: Лаборатория Базовых Знаний, 2001 — 288 с.

86. Ивахненко А.Г. Системы эвристической самоорганизации в технической кибернетике Киев: Техника, 1971.

87. Ивашкин Ю.А. Маслов М.Г. Система поддержки принятия решений при составлении расписания занятий в вузе // НИТРИО-2001. — Астрахань, 2001.

88. Ивашкин Ю.А., Дзюбко С.И., Маслов М.Г. Экспертная система построения расписания работы сотрудников // Интеллектуальные системы (ИН-TEJIC'2002): Труды пятого международного симпозиума. 2 — 4 июля 2002 г. Калуга, 2002. - С.275-277.

89. Ильина Т.Р. Модели и алгоритмы оптимизации загрузки ресурсов в условиях мелкосерийного производства: Автореф. дис. . канд. техн. наук: 05.13.06 / НИИ систем управления, волновых процессов и технологий. — Красноярск, 2001. — 23 с.

90. Индюшкин B.J1., Лысенко В.И., Тарасов С.Б. Принципы построения математического обеспечении АСУ ВШ. — М.: НИИВШ, 1977. — 83 с.

91. Использование ЭВМ в организации и планировании учебного процесса. — М.: "Высшая школа", 1972, С. 127-196.

92. Истомин А.Л. Оптимизация учебного плана в вузе в условиях ограниченных ресурсов // Математические методы в технике и технологиях: Сб. трудов XV Международ, науч. конф. В 10-и т. 2 — 4 июня 2002 г. — Тамбов, 2002.-Т. 9. — С.82-86.

93. Канцедал С.А. Вычислительные алгоритмы решения задач теории расписаний // Изд. АН СССР. Техническая кибернетика. 1982. -№ 3, С.42-51.

94. Кибернетика и исследование операций в управлении учебным процессом: Под. ред. И.Н. Ильина Рига: Рижский политехнический ин-т, 1984.

95. Климов А.А. Задачи анализа и синтеза типовых структур локальных и распределённых баз данных АИУС в сфере образования: Автореф. дис.канд. техн. наук: 05.13.10 / Институт проблем управления им. В.А.Трапезникова. Москва, 2002. - 207 с.

96. Кнут Д.Э. Искусство программирования для ЭВМ. — 2-е изд.: Пер. с англ.: Уч. пос. — М.: Издательский дом "Вильяме", 2000. Т. 3: Сортировка и поиск. — 832 с.

97. Колоколов А.А. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. — Омск: ОмГУ, 1992. С.67—93.

98. Конвей Р.В., Масквелл B.JL, Миллер JI.B. Теория расписаний: Пер. с англ. -М.: Наука, 1975.-360 с.

99. Концепция создания интегрированной автоматизированной информационной системы Минобразования России. М., 2000.

100. Корбут А. А., Финкельштейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969.-368 с.

101. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.

102. Корнюшко В.Ф., Кулыгина М.М., Андронова С.А. Расчёт материально-технической базы вуза на ЭВМ // Автоматизация управления вузом: Темат. сб. науч. тр. -М: НИИВШ, 1985.-С.176-181.

103. Королев М.А. Автоматизированная система управления Московского экономико-статистического института // Использование ЭВМ в организации и планировании учебного процесса. — 1972. С.69-84.

104. Королев М.А. О математическом обеспечении АСУ вуза. // Опыт разработки и внедрения элементов автоматизированной информационной системы управления вузом: Тезисы докладов Всесоюзного межвузовского семинара.-М.: МЭИ, 1971.

105. Костюк В.И., Мартинес Х.О., Зорин В.В. Использование алгоритмов последовательной обработки для составления расписаний // Вопросы создания АСУ ВУЗ. М.: НИИВШ, 1976. - С.3-5.

106. Кофман А. Введение в прикладную комбинаторику: Пер с франц. / Под. ред. Б.А. Севастьянова. М.: Наука, 1975. — 480 с.

107. Кравцов М.К., Шермак А. X. О решении комбинаторных задач оптимизации с минимаксными критериями // Кибернетика. — 1989. № 3. - С.71-77.

108. Краковская Т.А. Разработка методов анализа и обработки данных для исследования рынка образовательных услуг: Автореф. дис. . канд. техн. наук: 05.13.01 / Иркутская государственная экономическая академия. Иркутск, 2002. -126 с.

109. Краснекер JI.C. Об адаптивном подходе к задаче принятия решений при нескольких критериях // Вопросы оптимального программирования в производственных задачах — Воронеж: Изд. Воронежского ун-та, 1972.

110. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. 2-е изд., перераб. и доп. — М.: Энергоатомиздат, 1988. — 480 с.

111. Кузьмина Е.А. Модели и оптимизация учебных планов в образовательных системах: Автореф. дис. . канд. техн. наук: 05.13.10 / Уфимский гос. авиационный технический университет. — Уфа, 2002. — 136 с.

112. Кузьмина Е.А. Модели и оптимизация учебных планов в образовательных системах: Автореф. дис. . канд. техн. наук: 05.13.10 / Уфимский гос. авиационный технический университет. — Уфа, 2002. — 136 с.

113. Кулыгина М.М. Применение ЦВМ при составлении расписаний // ЭВМ в учебном процессе и управлении вузами. — Рига: РПИ, 1974. — С. 166-122.

114. Кумагина Е.А. Задачи распределения ресурсов и упорядочения работ в сетевых канонических структурах: Автореф. дис. . канд. техн. наук: 05.13.01 / Нижегородский государственный университет им. Н.И. Лобачевского. — Н.Новгород, 2001. — 15 с.

115. Курейчик В.В. Разработка теории и исследование эволюционных, синерге-тических и гомеостатических методов принятия решений: Дис. . докт. техн. наук: 05.13.18. Таганрог, 2001, - 390 с.

116. Ларионова С.Л. Автоматизация планирования расписания занятий в образовательных учреждениях Министерства обороны и оборонных отраслей промышленности: Дисс. . канд. тех. наук. — М., 1994. — 167 с.

117. Лащенков А.В. Разработка математического и программного обеспечений оптимизации проектных решений на основе раскраски вершин графа: Автореф. дисс. канд. техн. наук. -М., 1999.

118. Левин Г.М., Танаев B.C. Декомпозиционные методы оптимизации проектных решений. Минск: Наука и техника, 1978. - 240 с.

119. Лейбович А.Н. Применение ЭВМ для календарного планирования учебного процесса в ПТУ, школах и техникумах. М: Высш. школа, 1991.

120. Лимонова Т.И. Состояние разработок АСУ в вузах страны: Сб. науч. тр. НИИВШ.-М., 1976.-41 с.

121. Литвин У.О. Вопросы проектирования вычислительной техники в организации труда и управлении учебным процессом в ВУЗе: Дисс. . канд. экон. наук. -Киев, 1971.-281 с.

122. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросо-четаний в математике, физике, химии: Пер. с англ. — М.: Мир, 1998. 653 с.

123. Логвинов И. И. Имитационное моделирование учебных процессов. — М.: Педагогика, 1980. 127 с.

124. Лоскутов С.И. О построении расписания занятий в учебном заведении // Математические методы управления и обработки информации. — М.: МФТИ, 1983.-С.151-157.

125. Лукьянец Н.Б. Составление и изменение расписания учебных занятий в школе с помощью ЭВМ // Вопросы совершенствования системы управления в просвещении на основании использования вычислительной техники. М.: НИИ общей педагогики, 1980. - С.70-82.

126. Лыщинский Г.П. О возможности применения математической теории оптимальных решений в некоторых задачах планирования работы учебных заведений // Научная организация учебного процесса. Новосибирск, 1968.-№2.

127. Лыщинский Г.П. Управление развитием вуза — основа планирования его главных количественных показателей // Научная организация учебного процесса. Новосибирск, 1968. - № 1.

128. Магомедов A.M. Связное расписание: Учеб. пособие. Даг. гос. ун-т им. В. И. Ленина. Махачкала: Изд-во ДГУ, 1994. - 72 с.

129. Макаров И. П. Постановка и решение некоторых задач управления организационными системами (на примере высшего учебного заведения): Дис. . канд. техн. наук. — Томск, 1971. — 170 с.

130. Максименко В.Ф. Ляшенко Т.М. Один алгоритм составления некоторых схем массового обслуживания // Вычислительная математика и техника. АН УССР.-Киев, 1963.

131. Маслов М.Г. Алгоритм решения задачи составления расписания учебных занятий в вузе // Теория конфликта и её приложения: Труды второй всероссийской научно-технической конференции 30 сентября — 4 октября 2002 г.- Воронеж, 2002. С.216-217.

132. Маслов М.Г. Генетический алгоритм для задачи составления расписания занятий в вузе // Современные проблемы математики, механики, информатики: Тезисы докладов Всероссийской научной конференции. 20 — 22 ноября 2002 г. Тула: ТулГУ. 2002. - С. 214-218.

133. Маслов М.Г. Применение эвристического подхода для разработки алгоритма составления расписания занятий в вузе // Университетское образование: Труды VII международной научно-методической конференции. 1011 апреля 2003 г. Пенза, 2003. - С. 165-166.

134. Маслов М.Г. Система поддержки принятия решений в составлении расписания занятий в вузе // Пища, Экология, Человек: Труды четвёртой международной научно-технической конференции — М., 2001. — С.269—273.

135. Маслов М.Г. Система построения расписания работы сотрудников // Теория конфликта и её приложения: Труды второй всероссийской научно-технической конференции. 30 сентября — 4 октября 2002 г. — Воронеж, 2002. С.209-211.

136. Маслов М.Г. Эвристический подход при автоматизированном составлении расписания учебных занятий в вузе // Применение новых технологий в образовании: Материалы XIV международной научной конференции. 26 — 27 июня 2003 г. Троицк, 2003. - С.324-326.

137. Математические методы и модели решения задач в подсистеме "Расписание" АСУ ВУЗ / Б.А. Сазонова, П.В.Беспалов и др. М.:НИИВШ, 1978.

138. Математические модели и вычислительная техника в управлении учебным процессом высшей школы. — Рига: Рижский политехнический ин-т, 1986.

139. Математические разработки по созданию АСУ вуза. — М.: Московский горный институт, 1974.

140. Математическое и информационное обеспечение АСУ вуза. — Киев: Общество "Знание" УССР, 1976.

141. Медведский М.В. Рационализировать составление расписания // Вестник высшей школы. 1970. — № 5. — С. 53-57.

142. Медведский М.В., Неверов Г.С. Разработка семестровых расписаний занятий в вузе с помощью ЭЦВМ "Минск-77" // Использование ЭВМ в организации и планировании учебного процесса. М.: Изд. ВШ, 1972, С. 196217.

143. Методы и средства кибернетики в управлении учебным процессом высшей школы. — Рига: Рижский политехнический инс-т, 1985.

144. Мехтиев Г.Б. Разработка алгоритма проектирования учебных программ // Методы и средства управления учебным процессом высшей школы. — Рига: РГУ, 1990.-С. 66-69.

145. Минаков И.А. Разработка инструментальных средств для исследования и конструирования генетических алгоритмов: Дисс. . канд. тех. наук: 05.13.16-Самара, 2000.- 181 с.

146. Митюшин Ф.Ф., Нагорнова В.Ф. Составление расписания проведения занятий в ВУЗе // Труды ВЦ ВГУ. Воронеж, 1969. - Вып. 4.

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

148. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. — М. Наука, 1986. — 260 с.

149. Мишенин Ю.Н. Вопросы разработки автоматизированной системы управления высшим учебным заведением: Дисс. . канд. тех. наук. — М., 1971. — 198 с.

150. Молибог А.Г. Основы разработки семестрового расписания учебных занятий с помощью ЭВМ // НИИВШ. М., 1976. С.3-17.

151. Мухин Э.В., Низаметдинов Ш.У., Евланова В.П. Применение ЭЦВМ для составления расписания в вузе // Всесоюзный семинар по применению ЭВМ в организации и планировании учебного процесса: Тезисы докладов. М., 1969.-С.248.

152. Мухин Э.В., Романенко А.Г., Сумароков JI.H. О задачах составления оптимального учебного плана по критерию минимума функции потерь // Программированное обучение / КГУ. — Киев., 1969. — № 4,5.

153. Мухин Э.В., Романенко А.Г., Сумароков Л.Н. Применение ЭВМ для оптимизации учебных планов ВУЗа // Вестник высшей школы. — М., 1968. № 9.

154. Мухин Э.В., Романенко А.Г., Сумароков Л.Н. Сетевое моделирование учебного процесса в вузе // Вестник высшей школы. — М., 1968. № 9.

155. Мухин Э.В., Сумароков Л.Н. Алгоритмы решения задачи составления расписания в вузе // Экономические науки. — М., 1969. — № 1.

156. Наац Н.Э. , Тарусин Г.Н. Система автоматизированного составления расписания // Кибернетика и вуз. — Томск, 1969. — Вып. 2.

157. Нагорнова В.Ф. Использование ЦВМ для автоматизации составления расписания в вузе: Дисс. . канд. техн. наук/ МАИ. -М., 1971. 163 с.

158. Научная организация учебного процесса. Вопросы проектирования АСУ вузом / Под ред. Ю.Н. Малнева Куйбышев, 1976.

159. Неверов Г. С. АСРЗ в действии // Вестник высшей школы. 1970. — № 5. — С. 53-611

160. Неверов Г.С., Медведский М.В. Методика составления расписания занятий на ЭЦВМ. Минск, 1970.

161. Никитин Ю.Б. Сложность алгоритмов сортировки на частично упорядоченных множествах: Автореф. дис. . канд. физ.-мат. наук: 01.01.09 / МГУ им. М.В. Ломоносова. Красноярск, 2001. - 14 с.

162. Овчинников А.А., Путинский B.C. Сетевые методы планирования и организация учебного процесса. — М.: ВВИА им. Жуковского, 1965.

163. Овчинников А.А., Путинский B.C., Петров Г.Ф. Сетевые методы планирования и организация учебного процесса. — М.: Высшая школа, 1972. — 156 с.

164. Оре О. Теория графов. 2-е изд. — М.: Наука, 1980, - 336 с.

165. Орехов Э.Ю. Синтез расписаний на основе точного и вероятностного алгоритмов: Автореф. дис. . канд. физ.-мат. наук: 05.13.18 / Уфимский государственный авиационный технический университет. — Уфа, 2002. — 90 с.

166. Орлов В.Н. Анализ автоматизированных систем по составлению расписания учебных занятий // АСУ высшая школа. Чебоксары: ЧТУ, 1976. — С.68-74.

167. Осипова Е.М. Разработка объектных моделей для автоматизации анализа и проектирования систем дистанционного обучения: Автореф. дис. . канд. техн. наук: 05.13.16 / Санкт-Петербургский гос. университет. Санкт-Петербург, 2002. - 120 с.

168. Пайкес В. Г. Методика составления расписания в образовательном учреждении. М.: АРКТИ, 1999. - 47 с.

169. Пак JI.B., Чудинов В.Н. Решение задачи распределения аудиторного фонда в ВУЗе // Автоматизированные системы управления в ВУЗе. — Новосибирск: НГУ, 1978.— С. 138-142.

170. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. — М.: Мир, 1985. — 512 с.

171. Петров В.Я., Власов В. П. Задача оптимального распределения учебных групп в потоки // Применение ЭВМ в учебном процессе. М., 1969. С.29— 33.

172. Петров В.Я., Власов В.П. Об автоматизации составления учебного расписания для вуза // Программированное обучение и методы автоматизации учебного процесса / МВТУ. — 1968.

173. Пичко С.П., Яшунин А.Е. Применение рандомизированных функций предпочтения при составлении учебных расписаний // Проблемы создания, внедрения и эксплуатации АСУ высшей школы. — Киев: Знание, 1976. — С. 15— 17

174. Плахотишин A.M. Моделирование производственных возможностей и расписаний М.: ABF, 1997. — 177 с.

175. Подиновский В.В., Гаврилой В.М. Оптимизация по последовательно применяемым критериям. — М.: Советское радио, 1975.

176. Подчасова Т.П. и др. Эвристические методы календарного планирования. — Киев: Техника, 1980.

177. Портной Г.П. Математический аппарат оптимизации учебных планов с использованием ЭЦВМ // Применение ЭВМ в учебном процессе. — М., 1969.

178. Португал В.М. Применение комбинаторного метода для решения задачи составления расписания // Кибернетика. — Киев, 1967. — № 4.

179. Постникова Н. В. Разработка методов составления расписания учебных занятий в вузе на типовую неделю с использованием ЭЦВМ применительно к МТИЛП: Дисс. канд. техн. наук. — М., 1973. 160 с.

180. Поташник В.Я. Пичко О.П. Рандомизированная схема составления учебного расписания г ВУЗе // Эффективность автоматизированных систем управления высшей школы. Киев: Знание, 1977. - С.23-27.

181. Применение ЭВМ в учебном процессе //Сб. докл. науч.-техн. семинара / Под. ред. А.И. Берга. М.: 1969.

182. Применение ЭЦВМ для автоматизации процессов составления учебных планов и расписаний / Б.В. Анисимов, А.Я. Савельев, В.П. Власов, В.П. Карпов // Использование ЭВМ в организации и планировании учебного процесса М., 1972. - С. 191-192.

183. Пяткин В.А. NP-полнота задачи о назначениях с двумя критериями. М.: Наука, 2001.

184. Разработка и внедрение АСУ ВУЗ: Сб. статей. М., 1976, С. 14-19.

185. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. — 376 с.

186. Решение задач управления высшей школы с использованием математических моделей / Под ред. Коваленко В.Е. М.: НИИВШ, 1990.

187. Савинков В.М. Применение ЭВМ в учебном процессе // Программированное обучение и обучающие машины. Киев, 1967.

188. Савкин А.Н., Целовальников Е.П. Вопросы построения автоматизированных систем управления учебным процессом // Автоматизированные системы управления и обучения / Моск. энерг. ин-т. -М., 1976. — Вып. 298. — С. 17-26.

189. Самофалов К.Г., Симоненко В.П. Автоматизация составления расписания в вузе. Методические разработки. Киев: КПИ, 1972. - 144 с.

190. Самофалов К.Г., Симоненко В.П. Автоматизация подготовки данных к учебному процессу // Проблемы высшей школы. — 1972. — Вып. 2.

191. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: Мир, 1984.-455 с.

192. Свидетельство об официальной регистрации базы данных № 2004620036. "Расписание учебных занятий в вузе" ("UniSched DB"). /Ивашкин Ю.А., Маслов М.Г./ М.: Роспатент, 2004.

193. Свидетельство об официальной регистрации программы для ЭВМ № 2004610313. "Университетское расписание" ("UniSched"). /Ивашкин Ю.А., Маслов М.Г./ М.: Роспатент, 2004.

194. Севидж Д.Э. Сложность вычислений: Пер. с англ. — М.: Факториал, 1998. — 368 с.

195. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. — 2-е изд. Киев: Наук, думка, 1988. — 472 с.

196. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. — М.: ФИЗ-МАТЛИТ, 2002.-240 с.

197. Силуков Ю.Д. НОТ и расписание занятий // Вестник высшей школы. -1968. — № 3. С.21-27.

198. Смагина И.А. Разработка программного инструментария построения сценариев диалога при оценке квалификации сотрудников фирмы: Автореф. дис. . канд. техн. наук: 05.13.12 /Московский государственный горный университет. М., 2000. - 24 с.

199. Собенина О.В. Оптимизация функционирования информационной системы административного управления на основе теории расписаний: Автореф. дис. . канд. техн. наук: 05.13.10 / Воронежский государственный технический университет. Воронеж, 2001. - 16 с.

200. Создание автоматизированной системы управления в Московском институте электронной техники. Подсистема "Расписание". М: НИИВШ, 1973. -32 с.

201. Создание и развитие подсистемы "Расписание" АСУ МВТУ. М: Отдел научной информации НИИВШ, 1976.

202. Состояние работ по созданию ОАСУ Минвуза СССР. М.:НИИВШ, 1977.-48 с.

203. Степин Ю.П. Исследование и разработка методов решения многокритериальных задач теории расписаний в АСУ организационного типа (па примере вуза): Дисс. канд. тех. наук: В 2-х т. М, 1976. Т. 1-2.

204. Сумароков JL, Мухин Э. Применение ЭВМ для планирования учебного процесса // Экономические науки. 1969. — № 1.

205. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т.: Пер. с англ. М.: Мир, 1991. — Т. 1-2.

206. Танаев B.C. Декомпозиция и агрегирование в задачах математического программирования / Под. ред. А.Д. Закревского. — Минск: Наука и техника, 1987.-183 с.

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

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

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

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

211. Тарусин Г.Н. Алгоритм выбора в задачах расписания // Кибернетика и вуз. Томск: Изд-во Томского ун-та, 1970. - Вып. 3. - С.38-46.

212. Тарусин Г.Н., Наац И.Э. Алгоритм составления расписания // Кибернетика и вуз. Томск: ТПИ, 1969. - Вып. 2. - С. 19-23.

213. Таха X. Введение в исследование операций: в 2-х книгах, перев. с англ., -М.: Мир, 1985.

214. Тащев А.К., Ушаков Г.И. К вопросу о методике определения штатной структуры вуза // Научная организация учебного процесса в вузе. — Челябинск, 1970.

215. Темников Ф.Е. Принципы построения АСУ // Всесоюзная научная конференция по разработке АИС. М., 1970. - С.46,54,58.

216. Теория расписаний и вычислительные машины / X.JI. Бруно, Э.Г. Кофф-ман, P.JI. Грехем и др.; под. ред. Э.Г. Коффмана: Пер. с англ. — М.: Наука, 1984.-333 с.

217. Теория систем и методы системного анализа в управлении и связи / В.Н. Волкова, В.А. Воронков, А.А. Денисов и др. М.: Наука, 1983. — 248 с.

218. Технический отчёт по научно-исследовательской теме: "Автоматизация процесса составления расписания в ВУЗе". — М.: МАИ, 1968. — ч.2.

219. Технический отчёт по научно-исследовательской теме: "Автоматизация процесса составления расписания в ВУЗе". — М.: МАИ, 1969. — ч.З.

220. Тонг Ф. Эвристические методы балансирования работы сборочного конвейера // Вычислительные машины и мышление. М., 1967.

221. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. — М.: СИНТЕГ, 1998.-376 с.

222. Третьяк В.А. Проектирование и реализация проблемно-ориентированных языковых средств для создания программ учебного назначения: Дисс. . канд. физ.-мат. наук. Киев, 1990. - 121 с.

223. Управление в иерархических производственных структурах / Подчасова Т.П., Лагода А.П., Рудницкий В.Ф.; Отв. ред. Шкурба В.В.; АН УССР. Инт киберн. Киев: Наук, думка, 1989. - 184 с.

224. Управление персоналом организации / Под ред. А.Я. Кибанова. — 2-е изд., доп. и перераб. М.: ИНФРА-М, 2002. - 638 с.

225. Учебно-организационная работа в ВУЗе / Под ред. Л.В. Федотова, Н.Н. Трунова. Л.: ЛПИ, 1980. - 112 с.

226. Федотов А.В. Моделирование в управлении вузом. Л.: ЛГУ, 1985. - 120 с.

227. Финкельштейн Ю.Ю. Прикладные методы и прикладные задачи дискретного программирования: Отв. ред. Корбут А.А. — М.: Наука, 1976. — 264 с.

228. Фишер Ф.Н. Проблемы идентификации в эконометрии. — М.: Финансы и статистика, 1978.

229. Фогель Л., Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. М: Мир, 1969 г.

230. Хакен Г. Информация и самоорганизация: Макроскопический подход к сложным системам. М.: Мир, 1991. — 240 с.

231. Холл М. Комбинаторика: Пер. с англ. — М.: Мир, 1970. — 424 с.

232. Ципина Н.В. Разработка моделей алгоритмов и средств процесса автоматизированного обучения: Автореф. дис. . канд. техн. наук: 05.13.10 / Воронежский государственный технический университет. — Воронеж, 2002. — 135 с.

233. Чахирева Т.Н. Разработка методики персонального оценивания государственных служащих: Автореф. дис. . канд. техн. наук: 05.13.10 / Северо

234. Западная академия государственной службы. — Санкт-Петербург, 2002. -163 с.

235. Черединов М. Н. Применение ЭВМ для решения ряда задач проектирования и управления высшей школой: Дис. . канд. техн. наук. — Челябинск,1971.-162 с.

236. Черединов М.Н. Методика составления учебных занятий с помощью ЭВМ // Научная организация учебного процесса. Челябинск: ЧПИ, 1970.

237. Чернов В.М. ЭЦВМ составляет расписание // Вестник высшей школы. -1968. -№ 10. -С.46-49.

238. Чесноков А.В. Составление расписания занятий в условиях конфликта между вариантами распределений // Теория конфликта и её приложения: Труды второй всероссийской науч.-техн. конф. 30 сентября — 4 октября 2002 г. Воронеж, 2002. - С.26-27.

239. Шалунова М.Г. Система поддержки принятия решений по управлению структурой предложения образовательных услуг: Автореф. дис. . канд. техн. наук: 05.13.10 / Тверской государственный технический университет. -Тверь, 2002.-238 с.

240. Шеннон Р. Имитационное моделирование систем — искусство и наука. -М.: Мир, 1978.

241. Шкатулла В.И. Настольная книга менеджера по кадрам. М.: ИНФРА-М, 1998. - 527 с.

242. Шкурба В.В. Имитационное моделирование и оптимизация // Кибернетика.- 1981. -№ 1. -С.91-96.

243. Щёлоков В.А. Организация управления кадровыми ресурсами высших учебных заведений МЧС России: Дис. . канд. техн. наук: 05.13.10 / Санкт-Петербургский университет МВД России. Санкт-Петербург, 2002.- 144 с.

244. Экономико-математические методы и модели территориального распределения капиталовложений на развитие сети школ и дошкольных учреждений. ВЦ Госплана УССР / Ю.И. Саенко и др. Киев, 1967.

245. Эстрада С. В. Структуры, алгоритмы и программное обеспечение подсистемы планирования учебного процесса в вузах: Дис. . канд. техн. наук. — Киев, 1986.-190 с.

246. Юрасов В.Г. Моделирование и синтез развивающихся телекоммуникационных сетей и компьютерных систем управления вузом: Автореф. дис. . докт. техн. наук: 05.13.10 / Воронежский государственный технический университет. Воронеж, 1999. — 290 с.

247. Ямпольский В.З. Автоматизация управления высшей школой. — Воронеж: Воронежский ун-т, 1987.

248. Ямпольский В.З., Герман Э.И., Пак Л.В. Автоматизированное составление расписания учебных занятий в крупном многопрофильном вузе. Томский политехнический институт // НИИВШ. М., 1976. С.6-7.

249. Ямпольский В.З., Матлис Б.С. Определение весовых коэффициентов на основе экспертных оценок // Кибернетика и вуз. Томск: ТПИ, 1969.— Вып. 1.-106 с.

250. Ямпольский В.З., Матлис Б.С. Применение метода ранговой корреляции для определения весовых коэффициентов показателей деятельности вуза // Кибернетика и вуз. Томск, 1969. - Вып. 2.

251. Abramson D.A. Constructing School Timetables Using Simulated Annealing: Parallel and Sequential Solutions // Management Science. — Jan 1991. p.98-113.

252. Akkoyunll E.A. Algorithm for the optimum university time-table, in the computer // J. Operation Res. England. 1976. Vol. 16. - № 4. - p.347-350.

253. Appleby J.S., Blake D.V., Newman E.A. Techniques for producing school timetables on a computer and their application to other scheduling problems // The Computer Journal, -1961. Vol. 3. - № 4. - p.237.

254. Arora S., Lund С. Hardness of approximation // Approximation Algorithms for NP-Hard Problems / Ed. by S.D.Hochbaum. PWS Publishing Company, 1995.1. P.399—446.

255. Back Т., Hoffmeister F., Schwefel H.P. A Survey of Evolution Strategies // Proceedings of the 4th International Conference on Genetic Algorithms (ICCA IV), ed. R.K. Belew and L.B. Booker, Morgan Kaufman Publishers, Inc., San Diego, -1991.

256. Beasley David, Bull David R., Martin Ralph R. An Overview of Genetic Algorithms, in 2 parts. University Computing. 1993. - 15(2). - p.58-69.

257. Berghius J. La composition des horaires scolaires // Vorirag auf dom 23 Kon-gress der Benutrer von Gamma-Magnettrommelechnern. — Bologna. — 1961.

258. Bondarenko V.A., Mustard J., Pokrovskii A.V. Combinatorial Problem Connected with Stabilization of Systems with Quasichaotic Behaviour // Deakin University. Geelong. AU. Cadsem Report 97-009. 1997. p. 1-23.

259. Chen В., Potts C.N., Woeginger G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization.- Boston, MA: Kluwer Acad. Publ., 1998. Vol. 3. - p.21-169.

260. Davis L. Job shop scheduling with genetic algorithms // J.J. Grefenstette, editor, Proceedings of the First International; Conference on Genetic Algorithms. Lawrence Erlbaum Associates, 1985. -p.136-140.

261. Durbin R., Szeliski R., Yuille A. An Analysis of the Elastic Net Approach to the Travelling Salesman Problem // Neural Computation. 1989. - Vol. 1, -p. 348358.

262. Fogel D.B. Applying evolutionary programming to selected traveling salesman problem // Cybernetics and Systems. 1993. - 24(1).

263. Forrest S., Mayer-Kress G. Genetic algorithms, nonlinear dynamical systems, and models of international security // In L. Davis, editor, Handbook of Genetic Algorithms. Van Nostrand Reinhold; 1991. chapter 13. - p. 166-185.

264. Freisleben В., Sculte M. Combinatorial Optimization with Parallel Adaptive Threshold Accepting I I Proc. 1992 European Workshop on Parallel Computing, Barcelona. 10S Press, 1992. - p.176-179.

265. Galil Z. Efficient algorithms for finding maximal matching in graphs, preprint, 1983-C.54,460.

266. Gambardella L.M., Dorigo M. // Ant-Q: A Reinforcement Learning Approach to the Travelling Salesman Problem // Proc. 12th Int. Conf. on Machine Learning. Morgan Kaufmann, 1995. - p.252-260.

267. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

268. Gosselin K., Truchon M. Allocation of classrooms by linear programming // Journal of Operations Research. 1986. - 37. - № 6. - p.561-569.

269. Gotlieb C.C. The construction of class-teacher timetables // Information Processing. -1963. p.73-77.

270. Gsima J. Gotlieb C.C. Tests on a computer method for constructing school timetables // Communications of the Assoc. Comput. Math. 1964. - 7. - № 3. -p. 160.

271. Gunzenhauser R., Janginger W. Uber eine Methode zur Erstellung von Schulstunden planen mit Helte einer Ziffernrechenanlage // Rechentechn. und Automat. 1964, - 11. - № 3.

272. Harp S.A., Samad T. Genetic synthesis of neural network architecture. // In L. Davis, editor, Handbook of Genetic Algorithms. Van Nostrand Reinhold, -1991.

273. IT-образование: факультет ВМиК МГУ // Программист. 2001. — № 12. -С.80.

274. Jule А.Р. Estensions to the heuristic algorithm for University time-table // Computer Journal. 1968. - v.10.

275. Knowlesk, Tagg R.M., Thompson P.N. A heuristic treesearch method of selecting face schedules at a colliery // Operat. Res. Quatr. 1962. - 18. — № 2.

276. Lasak D. Die Berichungen des Kollisionsindex verfahrens zum Gotlieb-Verfahren // Electronische Datenverarbeitung. 1968. - 10. - № 2.

277. Lasak D. Ein mathematische Modell Zur Erstellung von Studenplanen // Electronische Datenverarbeitung. —1966. 8. - № 3.

278. Lawrie N.L. Linear programming as an aid to school timetabling // British Joint Computer Conference. London, 1966. — p.16-22.

279. Mihos C.H., Balas E. The problem of optimal time-tables // Rev. Roum. Math. Rures at Appl. 1965. - 17. - № 4. - p.474-484.

280. Newell A., Simon H.A. Heuristic problem-solving: The next advance in operation research // J. Operation Res. Soc. America. 1958. - 6. - № 1.

281. Rutenbar R.A. Simulated annealing algorithms: An overview. IEEE Circuits and Devices Magazine, January. 1989.

282. Sherman G.R. A combinatorial Problems, arising from Scheduling University Classes // Journal of the Tennese Academy of Sciences, 1963. - p.116-117.

283. Stahlknecht P. Zur elektronischen Berechnung von Stundenplanen // Elektron-ische Datenverarbeitung. -1964. № 2.

284. Wolpert D.H., Macready W.G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation. — 1997. — Vol. 1. — № 1.

285. Wood D.C. A technique for colouring a graph

286. Zade L. Fuzzy Sets // Information and Control. 1973.