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

Введение.

Глава 1. Математические модели задачи размещения.

1.1. Математическая формулировка задачи размещения.

1.2. Модель размещения на основе объектного подхода.

1.3. Моделирование объектного подхода на сетях Петри.

1.4. Моделирование маскированного размещения сетями Петри.

Выводы.

Глава 2. Разработка генетических алгоритмов для задачи размещения.

2.1. Генетические алгоритмы на сетях Петри.

2.2. Алгоритм на основе популяции квазиоптимальных решений.

2.3. Алгоритм на основе многоуровневых субпопуляций.

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

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

Выводы.

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

3.1. Задача составления расписания как задача размещения.

3.2. Функция приспособленности для задачи расписания.

3.3. Проведение и анализ результатов эксперимента.

Выводы.

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

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

Исследователями рассмотрены частные виды задачи размещения [48,62]. Для их решения применяются методы, которые можно разделить на три группы: точные, эвристические и диалоговые. В большинстве точных и эвристических методов использованы графовые модели размещений [64., 76, 79, 116, 152, 164, 169] . В них задача размещения сводится к задаче раскраски графа. Различные этапы размещения часто решаются с помощью алгоритмов математического программирования и различных эвристик, моделирующих работу диспетчера [93,97,6]. В последнее десятилетие XX века для решения различных задач стали применять генетические алгоритмы [1,8,111,130,138-151,155,154,168,173, 181]. При поиске решения они реализуют упрощенные модели основных факторов эволюции таких, как: наследственная изменчивость, естественный отбор, дрейф генов. Научный и практический интерес представляют исследования, посвященные возможности использования генетических алгоритмов для решения задачи размещения.

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

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

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

1. Математическая формулировка задачи размещения.

2.Представление генетических алгоритмов и исходных данных задачи размещения сетями Петри.

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

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

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

Математический аппарат. В работе применены методы математического моделирования, теории расписаний, алгоритмов, сетей Петри, генетических алгоритмов.

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

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

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

Реализация и внедрение результатов. Программа применяется для составления расписаний в вузах. Результаты исследований используются в учебном процессе кафедры компьютерных технологий ЧГУ им. И.Н. Ульянова.

Апробация работы. Основные положения работы и ее результаты докладывались и обсуждались на Международной научной конференции студентов, аспирантов и молодых ученых «Ломоно-сов-2002» (Москва, 2002), Всероссийской межвузовской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике» (Чебоксары, 2002), всероссийских научно-технических конференциях «Динамика нелинейных дискретных электротехнических и электронных систем» (Чебоксары, 1999; 2001), на межвузовской научно-практической конференции «Проблемы повышения качества образования» (Чебоксары, 2002), на итоговых научных конференциях в ЧГУ им. И.Н.Ульянова (Чебоксары, 1999; 2001; 2002), на заседаниях и научных семинарах кафедры компьютерных технологий ЧГУ им. И.Н.Ульянова (Чебоксары, 1999; 2000; 2001; 2002).

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка использованной литературы, содержащего 182 источника и приложения. Общий объем работы - 171 страница. Основной текст диссертации изложен на 131 странице и включает 26 таблиц, 20 рисунков.

Выводы

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

2. Математический эксперимент подтвердил теоретические расчеты относительно сложности алгоритмов. Лучшие временные

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

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

132

Заключение

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

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

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

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

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

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

5. Сформированы функция приспособленности, алгоритм контроля за лимитом размещения и алгоритм штрафа за простои в обслуживании требований. На ее основе составлены требова

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

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

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

1. Андреев В.В. Генетические и нейронные алгоритмы: Конспект лекций. Чебоксары: Изд-во Чуваш, ун-та, 2001. 38 с.

2. Анисимов H.A. Формальная модель для разработки и описания протоколов на основе сетей Петри//Автомат. и вычисл. техн. 1988. - №6.- С.3-10.

3. Архангельский С.И. Учебный процесс в высшей школе, его закономерные основы и методы: Учеб.-метод, пособие. М. : Высш. шк., 1980.- 368 с.

4. Баев В.В., Пипенко C.B. Пакет программ моделирования дискретных процессов расширенными сетями Петри//Управл. сист. и машины. -1991. №8. - С.83-87.

5. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы: Пер. с англ. М.: Мир, 1982. - 583 с.

6. Бардадым В.А. Исследование оптимизационных задач, связанных с составлением расписаний учебных занятий: Автореф. дис. канд. физмат. наук. Киев: ИК АН Украины.1991.- 29 с.

7. Бардадым В.А. Составление расписаний учебных занятий с помощью ЭВМ//Управл. сист. и машины. 1991. - №8. - С.119-126.

8. Батищев Д. И. Генетические алгоритмы решения экстремальных задач: Учеб. пособие/Под ред. Львовича Я.Е. Воронеж, 1995. 69 с.

9. Баткина И.Б. О гигиене умственного труда студентов//Педагогика высшей школы. Воронеж, 1974. 128 с.

10. Бачериков Н.Е., Воронцов М.П., Добромиль Э.И. Психогигиена умственного труда учащейся молодежи. Киев: Здоровье, 1988. 168 с.

11. Бобровский С. Delphi: учебный курс. СПб: Питер, 2000. - 640 с.

12. Богомолов А.И. Важнейшая задача вуза//Вестник высш. шк. 1967.- №10. С.3-8.

13. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. 13-е изд., исправл. - М.: Наука, 1986. - 544 с.

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

15. Букатова И.Л. Эволюционное моделирование и его приложения. -М.: Наука, 1979. 231 с.

16. Бурлаков M.B. Методология и инструментальная программная система ОСПЛАН оптимизации сетевого и календарного планирования. 1995. №4/5. - С.21-32.

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

18. Верхола А.П. Дидактические основы оптимизации процесса обучения дисциплинам вуза: Автореф. дис. д-ра пед. наук/Киев. гос. пед. инт. Киев, 1989. 49 с.

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

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

21. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М., 1985. - 509 с.

22. Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. М.: Высш. шк., 1986. - 311 с.

23. Григорьев A.B., Желтов В.П. Генетические алгоритмы в развитии творческого начала студентов//Проблемы повышения качества образования: Деп. в НИИ ВО. Тез. докл. I межвузовской науч.-практ. конф. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.25-26.

24. Григорьев A.B., Желтов В. П. Генетический алгоритм на основе многоуровневых субпопуляций//Проблемы повышения качества образования: Деп. в НИИ ВО. Тез. докл. I межвузовской науч.-практ. конф. Чебоксары: Изд-во Чуваш, ун-та, Чебоксары, 2002. С.29-30.

25. Григорьев A.B., Желтов В.П. Генетический алгоритм на основе популяции квазиоптимальных решений//Проблемы повышения качества образования: Деп. в НИИ ВО. Тез. докл. I межвузовской науч.-практ.конф. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.27-28.

26. Григорьев A.B., Желтов В.П. Генетический алгоритм оперирующий субпопуляциями разного уровня//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.205-208.

27. Григорьев A.B., Желтов В.П. Генетический алгоритм с начальной популяцией из квазиоптимальных решений//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.203-205.

28. Григорьев A.B., Желтов В.П. Задача размещения//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2002. -С.185-189.

29. Григорьев A.B., Желтов В.П. Задачи исследования генетических алгоритмов//Проблемы повышения качества образования: Деп. в НИИ ВО. Тез. докл. I межвузовской науч.-практ. конф. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.23-24.

30. Григорьев A.B., Желтов В.П. Метод маскированного составления расписания учебных занятий//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2001. С.202-205.

31. Григорьев A.B., Желтов В.П. Обобщенный генетический алгоритм на сетях Петри//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.197-203.

32. Григорьев A.B., Желтов В.П. Обобщенный генетический алгоритм/ /Математические модели и их приложения: Сб. науч. тр. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.110-113.

33. Григорьев A.B., Желтов В.П. Представление генетических алгоритмов сетями Петри//Информационные технологии в электротехнике и электроэнергетике (ИТЭЭ-2002): Материалы IV Всерос. науч.-техн. конф. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.178-179.

34. Григорьев A.B., Желтов В.П. Представление маскированного подхода решения задачи размещения сетями Петри//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.194-197.

35. Григорьев A.B., Желтов В.П. Представление объектного подхода решения задачи размещения сетями Петри//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2002. С.189-193.

36. Григорьев A.B., Желтов В.П. Применение эволюционных алгоритмов для составления расписания учебных занятий//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2001. С.194-198.

37. Григорьев A.B., Желтов В.П. Решение задачи коммивояжера с помощью генетического алгоритма в визуальной среде программирования Delphi//Tpyflbi молодых ученых и специалистов. Чебоксары: Изд-во Чуваш. ун-та, 2001. С.193-194.

38. Григорьев A.B., Желтов В.П. Стадии работы и операторы генетического алгоритма для составления расписания учебных занятий//Труды молодых ученых и специалистов. Чебоксары: Изд-во Чуваш, ун-та, 2001. С.198-202.

39. Григорьев A.B., Малышев A.B., Желтов В.П. Моделирование логических элементов сетями Петри//Наука, творчество, информация: Материалы 33-й науч. студ. конф. Чебоксары: Изд-во Чуваш, ун-та, 1999. С.133-134.

40. Гультяев А. Визуальное моделирование в среде MATLAB: учебный курс. СПб: Питер, 2000. - 432 с.

41. Гуляев Г.В. Генетика. Изд. 2-е, перераб. и доп. М.: Колос, 1977. - 360 с.

42. Гуревич Д.С. Поглощающие сети Петри и их использование при разработке цифровых вычислительных систем с распределенной структу-рой//Автомат. и вычисл. техн. 1990. - №2. - С.80-87.

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

44. Дегтярев Ю.И. Методы оптимизации: Учеб. пособие. М. : Сов. радио, 1980. - 270 с.

45. Десрочерс A.A., Ал-Джар Р. Приложения сетей Петри в производственных системах: Моделирование, управление и анализ производитель-ности/Ин-т электрич. и электрон, техники. Нью-Йорк, 1995. -.270 с.

46. Димитриев А.П. Стохастическая оптимизация в задаче размещения на сетях Петри: Автореф. дис. канд. техн. наук/Чуваш, гос. ун-т. Чебоксары, 2001. 23 с.

47. Димитриев А.П., Желтов В.П. Математическая модель расписания учебных занятий // ИТЭЭ: Материалы II' Всерос. науч.-техн. конф. Чебоксары: Изд-во Чуваш, ун-та, 1998. С. 235-237.

48. Димитриев А.П., Желтов В.П. Моделирование дискретных динамических систем с неоднородными топологическими единицами // Тр. Академии электротехн. наук Чувашской Республики.® 1. Чебоксары: Изд-во Чуваш, ун-та, 2000. С. 81-84.

49. Димитрие в А.П., Желтов В.П. Оптимизация на сетях Петри // Математические модели и их приложения:Сб.науч.тр. Вып. 2. Чебоксары: Изд-во Чуваш, ун-та, 2000. С. 95 98.

50. Димитриев А.П., Желтов В.П. Применение генетических алгоритмов в задаче дискретной оптимизации //На рубеже тысячелетий: Итоги и перспективы: Тр. молодых ученых и спец. / Чуваш, ун-т. Чебоксары, 2000. С.143.

51. Димитриев А.П., Тихонов С. В., Желтов В. П. Составление расписания: Проблемы и качество // Наука, просвещение, цивилизация: Материалы 32-й студ. науч.конф. / Чуваш, ун-т. Чебоксары, 1998. С. 133-134.

52. Доскин В.А., Лаврентьева H.A. Ритм физиологических функций и режим обучения//Вестник высш. шк. 1974. - №5. - С.76-79.

53. Дубинин Н.П. Горизонты генетики: Пособие для учителей. М.: Просвещение, 1970. - 560 с.

54. Желтов В. П., Музыкантов В.И. Теория графов: Конспект лекций. Чебоксары: Изд-во Чуваш, ун-та, 1998. 100 с.

55. Желтов В.П., Желтова Л.В. Моделирование систем и дискретные математические модели: Текст лекций. Чебоксары: Изд-во Чуваш, ун-та, 1995. 124 с.

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

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

58. Зиновьев Э.В. и др. Интегрированная система поддержки и имитационного моделирования сетей Петри на ПЭВМ//Автоматика и ВТ. -1991. №5. - С.10-18.

59. Игошев И.А., Игошев В.И. Работоспособность студента и планирование занятий//Вестник высшей школы. 1973. - №6. - С.16-23.

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

61. Исаев С.А. Разработка и исследование генетических алгоритмов для принятия решений на основе многокритериальных нелинейных моделей: Автореф. дис. канд. техн. наук/Нижегородский гос. ун-т.1. Н.Новгород, 2000. 21 с.

62. Йодан Э. Структурное проектирование и конструирование программ.- М., 1979. 211 с.

63. Каган В.И., Сычеников И.А. Основы оптимизации процесса обучения в высшей школе: Единая методическая система института: теория и практика: Науч.-метод, пособие. М.: Высш. шк., 1987. - 143 с.

64. Карманов В.Г. Математическое программирование. 2-е изд. - М. : Наука, 1980. - 256 с.

65. Киколов А.И. Обучение и здоровье: Метод, пособие для студ. и препод, вузов. М.: Высш.шк., 1985. - 104 с.

66. Киндлер Е. Языки моделирования. М. : Энергоатомиздат, 1985. -288 с.

67. Коменкова М.С. Инструментальная система моделирования параллельных процессов, описанных языком сетей Петри/Управляющие системы и машины. 1988. - №5. - С.16-19.

68. Конвей Р.В., Максвелл В.А., Миллер Л.В. Теория расписаний: Пер. с англ. М.: Наука, 1975. - 359 с.

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

70. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.

71. Кофман С.А. Теория расписаний и вычислительная математика. -М.: Наука, 1984. 335 с.

72. Криволуцкая Н.В. Программы составления расписания занятий для образовательных учреждений. М. : Моск. ин-т повышения квалификации работников образования, 1999. ИеЬ-страница: http://ito.bitpro.ru/1999/IV/IV19.html.

73. Кузин Ф.А. Кандидатская диссертация: Методика написания, правила оформления и порядок защиты: Практ. пособие для аспирантов и соискателей ученой степени. 5-е изд. - М. : Ось-89, 2001. - 224 с.

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

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

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

77. Лейбович А.Н. Организационно-педагогические условия повышения эффективности календарного планирования учебного процесса в средних профтехучилищах: Автореф. дис. канд. пед. наук. Казань, 1987.- 18 с.

78. Леонавичюс Ю.И. Как сберечь время студента//Вестник высш. шк. -1987. №8. - С.30-37.

79. Лескин A.A., Мальцев П.А., Спиридонов A.M. Сети Петри в моделировании и управлении. Л.: Наука, 1989. - 133 с.

80. Лобков С.Н., Фатхи В.А., Климович Г.И., Дуднакова О.В. Стохас-тическо-детерминированные временные сети Петри как средство описания моделей многопроцессорных вычислительных систем//Управл. сист. и машины. 1991, - №8. - С.60-68.

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

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

83. Марчук Г.И. Методы вычислительной математики. М. : Наука, 1977. - 456 с.

84. Математическое моделирование технологических процессов и метод обратных задач в машиностроении/А.Н. Тихонов, В.Д. Кальнер, В.Б. Гласко. М.: Машиностроение, 1990. - 264 с.

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

86. Мочалов Б.М. Опыт разработки АСУ-ВУЗ//Вестник высш. шк. 1977.- №12. С.87-89.

87. Мурата Т. Сети Петри: Свойства, анализ, приложения//ТИИЭР. Т.77. 1989. № 4. С.41 - 85.

88. Мургов В.Н. Имитационное моделирование микропроцессорных систем на базе Е-сетей для ПЭВМ//Микропроц. сист. и ср-ва 1990. - №17. - С.36-37.

89. Неверов Г.С. АСРЗ в действии//Вестник высш. шк. 1970. - №5. -С.57-61.

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

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

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

93. Орловская JI.M. Процедуры моделирования учебного процесса в общеобразовательной школе: Автореф. дис. канд. пед. наук/Краснояр. гос. пед. ун-т. Красноярск, 1998. 20 с.

94. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1982. - 510 с.

95. Паукшена Д. Автоматизированные системы управления вузом: Библиограф. указатель. Рига: РПИ, 1984. 16 с.

96. Педагогика и психология высшей школы: Учеб. пособие для ву-зов/Отв. ред. С.И. Самыгин. Ростов-на-Дону: Феникс, 1998. 544 с.

97. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984. - 264 с.

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

99. Приближенные методы решения дискретных задач оптимизации/И.В. Сергиенко, Т.Т. Лебедева, В.А. Рощин. Киев: Наук, думка, 1980. -276 с.

100. Пропой А.И. Элементы теории оптимальных дискретных процессов. -М. : Наука, 1973. 256 с.

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

102. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике:

103. В 2 кн.: Пер. с англ. М.: Мир, 1986. Кн. 1. - 349 с.

104. Риоло Р.Л. Естественный отбор в мире 6HTOB//Scientific American- изд. на русск. языке. 1992. - №9/10. - С.160-163.

105. Розенблюм Л.Я. Сети Петри//Техническая кибернетика. 1983. -№5. - С.12-40.

106. Рубинштейн М.И. Оптимальная группировка взаимосвязанных объектов. М.: Наука, 1989. - 168 с.

107. Рыжов В.А. Динамичные сети Петри/ВЦ АН СССР. М., 1988. 24 с.

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

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

110. Сивриков Б.Е. Оптимизация планирования учебного процесса с применением персональных ЭВМ: Автореф. дис. канд. пед.наук/Ин-т развития проф.образования. М., 1995.-17 с.

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

112. Смирнов С.М., Постникова Н. В. Подсистема «Расписание» действуем/Вестник высш. шк. 1974. - №7. - С.16-19.

113. Сотсков Ю.Н., Струсевич В.А., Танаев B.C. Математические модели и методы календарного планирования: Учеб. пособие. Минск: Университетское, 1994. 232 с.

114. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986. - 325 с.

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

116. Тихонов А.Н., Уфимцев М.В. Статистическая обработка результатов экспериментов: Учеб. пособие. М.: Изд-во МГУ, 1988. - 174 с .

117. Трахтенгерц Э.А. Программное обеспечение автоматизированных систем управления. М.: Статистика, 1975. - 288 с.

118. Тюкачев Н.А, Свиридов Ю.Т. Delphi 5. Создание мультимедийных приложений. М.: Нолидж, 2000. - 384 с.

119. Федотов A.B. Моделирование в управлении вузом. J1. : ЛГУ, 1985.- 120 с.

120. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М. : Мир, 1984. - 496 с.

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

122. Харыбина Т. Р. Математическая модель оптимизации учебного процесса на базе современных информационных технологий: Автореф. дис. канд. физ.-мат. наук/Рос. гос. пед. ун-т. СПб., 1994. - 21 с.

123. Холланд Д.Х. Генетические алгоритмы/ZScientific American изд. на русск. языке. - 1992. - №9/10. - С.32-40.

124. Цетлин M.J1. Исследования по теории автоматов и моделирование биологических систем. М.: Наука, 1969. - 116 с.

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

126. Чучалин И.П., Ямпольский В.З., Чудинов В.Н. и др. Модели управления учебным процессом вуза. Томск: Изд-во Том. ун-та, 1992. -180 с.

127. Ширяев В.Д. Основы алгоритмизации: Учеб. пособие. Саранск,1993. 171 с.

128. Шкурба В.В. Задача трех станков. М.: Наука, 1976. - 96 с.

129. Шураков В.В., Венецкий И.Г., Дуброво И.Г. Автоматизированная система управления вуза: Учебно-метод. пособие. М. : Высшая школа, 1976. - 184 с.

130. Яглом И.М. Булева структура и ее модели. М. : Сов. радио,1980. 192 с.

131. Aubin J., Ferland J.A. A large scale timetabling prob-lem//Comput. and Operat. Res. 1989. - vol.16, - №1. - P.67-77.

132. Brindle A. Genetic algorithms for function optimization. Unpublished doctoral dissertation, University of Alberta. Edmonton,1981. 135 p.

133. Burke E.K., Elliman D.G. and Weare R.F. A Genetic Algorithm for University Timetabling//Proceedings of the AISB Workshop on Evolutionary Computing (University of Leeds, UK, llth-13th April 1994),1994.

134. Burke E.K., Elliman D.G. and Weare R.F. A University Timetabling System based on Graph Colouring and Constraint Manipulation// Journal of Research on Computing in Education. 1994. vol.27, №1. - P.1-18.

135. Burke E.K., Elliman D.G. and Weare R.F. Automated Scheduling of University Exams//Proceedings of the IEE Colloquium on Resource Scheduling for Large Scale Planning Systems (10th June 1993) -1993. digest №144, section 3.

136. Burke E.K., Elliman D.G. and Weare R.F. Extensions to a University Exam Timetabling System//Proceedings of the IJCAI-93 Workshop on Knowledge-Based Production, Planning, Scheduling and Control (Chambery, France, 29th Aug 1993). P.42-48. IJCAI

137. Burke E.K., Elliman D.G. and Weare R.F. The Automation of the Timetabling Process in Higher Education//Journal of Educational Technology Systems. 1995. vol.23, - №4. - P.257-266. Baywood Publishing Company.

138. Burke E.K., Elliman D.G., Ford P.H. and Weare R.F. Examination Timetabling in British Universities A Survey//The Practice and Theory of Automated Timetabling (eds EK Burke and P Ross), Springer, 1995.

139. Burke E.K., Elliman D.G., Newall J.P., and Weare R.F. A Memetic Algorithm for University Exam Timetabling//The Practice and Theory of Automated Timetabling (eds EK Burke and P Ross), Springer, 1995.

140. Cavicchio D.J., Jr. Adaptive search using simulated evolution. Unpublished doctoral dissertation, University of Michigan, Ann Arbor. 1970.

141. Cole R., Hopcroft J. On edge coloring bipartite graphs//SIAM J. Comput. 1982. - vol.11, - №3. - P.540-546.

142. Corne D., Ross P., and Fang H-L.: Fast Practical Evolutionary Timetabling. Proceedings of the AISB Workshop on Evolutionary Computation, Springer Verlag, 1994.

143. De Werra D. An introduction to timetabling//Europ. J. Opcrat. Res. 1985. - vol.19, - №2. - P.151-162.

144. De Werra D. On a particular conference scheduling prob-lem//INFOR. 1975. - vol.13, - №3.- P.308-315.

145. De Werra D. Some models of graphs for scheduling sports compe-titions//Discr. Appl. Mathem. 1988. - vol.21, - №1. - P.47-65.

146. DeJong K. Adaptive system design: a genetic approach. IEE Trans SMC, 1980. vol.10. P.566-574.

147. DeJong K. The Analysis and behaviour of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan, 1975.

148. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems II SIAM J. of Comput. 1975. - 5, -№ 4. - P.691-703.

149. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA, 1989. 412 p.

150. Goldberg D.E., Deb K. A comparative analysis of selection schemes used in genetic algorithms. In G.J.E. Rawlins, editor, Foundations of Genetic Algorithms. San Mateo, CA, Morgan Kaufmann. 1991. vol.1. - P.69-93.

151. Gosselin K., Truchon M. Allocation of classrooms by linear programming/ /Europ. J. of Operat. Res. 1986. - vol.37, - №6. -P.561-569.

152. Gotlieb C.C. The construction of class-teacher time-tables//Inform. Proc. 1962. Proc. IFIP Congr. 62. Amsterdam: North-Holland, 1963. - P.73-77.

153. Grefenstette J.J. Genetic algorithms and their applications. In A. Kent and J.G. Williams, editors, Encyclopaedia of Computer Science and Technology. Marcel Dekker, 1990. P.139-152.

154. Grefenstette J.J. Optimization of control parameters for genetic algorithms. IEEE Transactions on- Systems, Man and Cybernetics, 1986. vol.16, - №1. - P.122-128.

155. Hilton A.J.W. School timetables//Annals of Discr. Mathem. -1981. vol.11. - P.177-188.

156. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975. 183 p.

157. Kitagawa F., Ikeda H. An existential problem of a weight-controlled subset and its application to school timetable con-struction//Discrete Mathem. 1988. - vol.72. - P.195-211.

158. Lotfi V., Sarin S. A graph-coloring algorithm for large-scale scheduling problems//Comput. and Operat. Res. 1986. - vol.13, -№1. - P.27-32.

159. Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.

160. Mulvey J.M. A Classroom/Time Assignment Model//Ibid. 1982. -vol.9, - №1. - P.64-70.

161. Ross P., Corne D., and Fang H-L. Improving Evolutionary Timetabling with Evaluation and Directed Mutation.: Proceedings of PPSN III, Jerusalem, October 1994, Springer Verlag.

162. Schmidt G., Strohlein T. Timetable construction an annotated bibliography//Comput. J. - 1980. - vol.23, - №4. - P.307-316.

163. Schniederjans M.J., Kim G.C. A goal programming model to optimize departmental preference in course assignments//Comput. and Operat. Res. 1987. - vol.14, - №2. - P.87-96.148

164. Selim S.M. Split vertices in vertex•colouring and their application in developing a solution to the faculty timetable prob-lem//Comput. J. 1988. - vol.31, - №1. - P.76-82.

165. Smith W.E. Efficiency of a university timetable an application of entropy of choice//Bulletin of the Australian Mathematical Society. - 1984. - vol.30, - №1. - P.19-26.

166. Syswerda G. Schedule optimization using genetic algorithms. In L. Davis, editor, Handbook of Genetic Algorithms, chapter 21, -P.332-349. Van Nostrand Reinhold, 1991.

167. Syswerda G. Uniform crossover in genetic algorithms. In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, 1989, P.2-9. Morgan Kaufmann.

168. Tripathy A. School timetabling a case in large binary integer linear programming//Manag. Sci. - 1984. - vol.30, - P12. - P.1473-1489.

169. Weare R.F. Automated Examination Timetabling//PhD Thesis, Department of Computer Science, University of Nottingham, UK, June 1995.

170. Wood D.C. A technique for colouring a graph applicable to large scale timetabling problems//Comput. J. 1969. - vol.12, - №4. -P.317-319.