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

ВВЕДЕНИЕ

ГЛАВА I. ЗАДАЧА СИНХРОНИЗАЦИИ ДШ ОБЪЕКТОВ СЛОЖНОЙ СТ1УКГУРЫ С ЗАРЪЙРУЕШМ ПОРЯДКОМ ВЫПОЛНЕНИЯ ЗАДАНИЙ

1.1. Анализ методов решения задач составления расписаний

1.2. Анализ методов решения многокритериальных задач

1.3. Особенности решения комбинаторных задач большой размерности

1.4-. Постановка задачи синхронизации функционирования сложной системы

1.5. Методика назначения приоритетов

1.5.1. Анализ параметров сложных систем и критериев качества их функционирования

1.5.2. Связь критериев и приоритетов

1.5.3. Методика определения предпочтения параметров

1.5.4. Методика назначения приоритетов

1.6. Синтез алгоритма синхронизации по характеристикам объекта

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

ГЛАВА 2. РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПРОЦЕДУР ПОИСКА

РЕШЕНИЯ ШОГОКРИТЕРИАЛЬШХ ЗАДАЧ СИНХРОНИЗАЦИИ

И ПРОГНОЗИРОВАНИЕ КАЧЕСТВА РАСПИСАНИЙ

2.1. Блоковый алгоритм

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

2.3. Организация процедур поиска решения с помощью непараметрических критериев

2.4. Определение оценки качества эвристических алгоритмов синхронизации

2.5. Прогнозирование оценки качества расписаний

2.6. Исследование возможностей блокового алгоритма

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

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

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

3.1. ППП для решения задач синхронизации ^

3.2. Задачи синхронизации в ВУЗе ^

3.2.1. Параметры и параметрические ограничения ^

3.2.2. Функции и функциональные ограничения

3.2.3. Критерии и критериальные ограничения

3.2.4. Выходные переменные для составления расписаний занятий

3.2.5. Назначение приоритетов

3.2.6. Синтез блокового алгоритма

3.2.7. Ограничения и критерии для составления расписания экзаменов

3.2.8. Блоковый алгоритм для составления расписания экзаменов

3.3. Особенности решения задач синхронизации 108 учебного процесса в ВУЗе

3.4. Задача планирования процесса испытаний III систем летательных аппаратов

3.5. Автоматизированное определение нормативов при составлении расписаний

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

В Основных направлениях экономического и социального развития СССР на 1981-1985 гг. и на период до 1990 года отмечается, что "для решения задач интенсификации экономики и повышения ее эффективности предусматривается развивать производство, обеспечивать широкое применение автоматизированных систем управления, создавать автоматизированные цехи и заводы, улучшать использование производственных мощностей - машин, оборудования, транспортных средств, наиболее рационально использовать материальные, трудовые и финансовые ресурсы" [92].

Все. эти важнейшие направления сконцентрированы в появившейся в последние годы концепции гибких автоматизированных производств (ГАП) и гибких производственных систем (ГПС). В материалах июньского (1983 г.) пленума ЦК КПСС эта концепция изложена в конкретных директивах по развитию гибких технологий, которым должно придаваться первостепенное значение [76]. Под ними понимается адаптивная производственная система, способная менять свою конфигурацию, состав и цели функционирования в зависимости от меняющейся производственной ситуации.

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

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

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

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

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

Обычно задачи составления расписаний изучаются в теории расписаний [10,55,112,129], многокритериальные задачи - в разделах методов оптимизации [25,103] и в теории принятия решений [75,100, 130], проблемы, связанные с большой размерностью - в теории вычислительной сложности [26,106,137]. Пересечение этих самостоятельных областей исследования порождает задачи с новыми свойствами (рис.1).

В теории расписаний исследуются модели задач составления расписаний, разрабатываются математические методы получения решений и анализируется их оптимальность. В большинстве своем эти задачи исключительно трудоемкие результаты обширных исследований, приведенных в последние годы скорее выявляют сложность проблемы, чем намечают конструктивные пути ее решения [129]. Точное решение удается найти лишь для частных случаев, таких, например, как задача Джонсона для одного и двух станков [29], различные варианты задач упорядочения с ограничениями на отношения предшествования, количество станков, работ и др. Доказательства их оптимальности область исследования: -теория принятия решений,

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

-теория расписаний.

Рис.1. К определению объекта исследования.

1 - область многокритериальных задач составления расписаний (МКСР).

2 - область МКСР большой размерности. в основном проводятся для каждого случая и почти не подлежат обобщению. Наличие множества различных ограничений, заданных правил использования ресурсов, различных вариантов отношения предшествования и других принципиальных особенностей приводит к выводу, что сама постановка вопроса о получении оптимального решения для задач практических размерностей вообще не правомерна (10,135]. Кроме того, при составлении расписаний часто возникает необходимость в использовании более одного показателя эффективности. Этот вопрос практически не рассматривается в классической теории расписаний.

Решение задач со многими критериями качества обычно рассматривается в двух аспектах. Во-первых, это-разработка алгоритмов поиска оптимальных в каком-либо смысле решений (задача проектирования [119]), во-вторых - процедуры выбора из множества решений наиболее предпочтительного (задача выбора [751). Первое направление 'разрабатывается в методах векторной или многокритериальной оптимизации. Решение таких задач находят с помощью введения различных схем компромиссов [25,103], а также различными вариациями зондирования пространства параметров [П7,П9]. Во втором направлении основным вопросом является не то, как найти оптимальное решение, а что именно следует понимать под оптимальным решением, т.е. исследуются трудности не технического, а концептуального характера [98,99,130]. Решение определяется путем сравнения альтернатив .

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

Одним из важнейших в теории расписаний является вопрос оценки близости построенного расписания к искомому оптимальному. Естественно, что он приобретает особую сложность, если оценка качества должна производиться по нескольким показателям качества (область I рис Л).

Развивающаяся в настоящее время прикладная теория вычислительной сложности относит задачи теории расписаний к классу Ж У - полных задач [26,80]. Основным свойством задач этого класса является то, что их нельзя решить быстрее, чем за экспоненциальное (в зависимости от размерности задачи) число шагов. Выводом из этого факта является полнейшая неэффективность использования точных математических методов для решения такой задачи, особенно для задач немалой размерности [137]. Эффективные (полиномиальные) алгоритмы для новых задач большой размерности, являются скорее результатом искусства разработчика и математика-программиста, их умения использовать особенности задач в целях ускорения вычислений, чем следствием хороших Нормальных процедур. В связи с высокой трудоемкостью оптимизации в строгом смысле определенный интерес представляют методы приближенной оптимизации и, в частности, методы эвристического типа. Согласно [оО] они, как правило, имеют полиномиальную оценку трудоемкости.

Б процессе разработки темы П.б.о.1.1 "Создание алгоритмов и программ для составления расписаний занятий, экзаменов и консультаций" Координационного плана работ Минвуза СССР по проблемам высшей школы на 1976-ЬО гг. и в дальнейших исследованиях по теме были выявлены особенности практических требований к расписаниям, которые не позволяют непосредственно использовать результаты, полученные ни как в теории расписаний, ни в теории решения многокритериальных задач.

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

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

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

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

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

3. Оценка значимости и прогнозирование значений частных критериев качества в зависимости от исходных параметров задачи.

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

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

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

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

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

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

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

В третьей главе описываются результаты практической реализации разработанных методик и процедур. На примерах решения ряда задач показывается, что путем вариации последовательности БдЦ, а также приоритетов исходных заданий пользователь (постановщик задачи и математик-оптимизатор) может в широком диапазоне управлять процессом поиска наилучшего решения задачи составления расписания. Для этой цели разработан пакет прикладных программ для составления расписаний (ШП СР), включающий 10000 операторов языка ПЛ/1. Структура пакета приведена в главе.

Исследованы требования к конкретным применениям ШШ СР и структура программного обеспечения, созданного на основе ШШ СР для решения задач составления расписаний в ВУЗе и для диспетчеризации процесса испытаний систем летательных аппаратов. Проанализирован опыт эксплуатации разработанного программного обеспечения в Казанском и Уфимском авиационном институтах, особенности внедрения в других ВУЗах и организациях. Приведены рекомендации по преодолению ряда трудностей, связанных с особенностями конкретного применения .

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

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

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

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

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

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

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

6. Разработан пакет прикладных программ (10000 операторов языка ПЛ/1), реализующий в диалоговом режиме решение многоцелевой задачи с использованием блокового алгоритма. Исследованы особенности применения пакета для решения задач составления расписаний занятий и экзаменов для крупных многопрофильных ВУЗов и для планирования процесса проведения прочностных испытаний систем летательных аппаратов.

7. Результаты проведенных исследований, машинные реализации разработанных процедур и алгоритмов переданы в Г'осФАП СССР, демонстрировались на ВДНХ СССР, практически реализованы на КАПО имени С.П.Горбунова (экономический эффект 22 тыс.рублей), в ряде ВУЗов Минвуза РСФСР.

ЗАКЛЮЧЕНИЕ

Пакет прикладных программ для составления расписаний, разработанный с использованием подхода, изложенного в настоящей диссертации и в работах [58,65,67,69,70,87,122], отличается от предыдущих разработок по данной тематике следующим:

1. Удобством в адаптации алгоритма к постоянно изменяющимся требованиям пользователей к расписаниям.

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

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

4. Наличием блока накопления опыта, обеспечивающего формирование наилучшей последовательности заданий (в рамках последовательности, установленной с помощью системы приоритетов). Как установлено выше (п.3.2) для составления расписаний в ВУЗе система приоритетов не является полной и последовательность внутри приоритетной группы устанавливается не случайно, а с учетом последовательности, сформированной для одноименного семестра (сессии) прошлого года и в которой учтено большинство замечаний пользователей расписания. Такая возможность обеспечивается тем, что изменение исходной информации от года к году производится в среднем на 74-10% - по специальностям (по дисциплинам, номерам учебных групп) и на 20-25% -по преподавателям.

1. Автоматизированные системы управления. Под ред.Шорина В.Г.1. М.: Знание, 1973, 318 с.

2. Анисимов Б.В., Власов В.П., Сазонов Б.А. Математическая модель задачи вузовских расписаний учебных занятий на основе геометрической интерпретации. В сб. "Вычислительная техника", вып.7, Пенза; ППИ, 1977, с.126-134.

3. Арасланова Л.Ф., Курбатов Б.К. Составление расписания, улучшающего загрузку оборудования, по методу антипода.-ЦФАП НПО "Центрпрограммсистем", Калинин, 1976, регистр. № 702.

4. Бабаев А.А., Друганов Б.Н. Метод ветвей и границ в задаче составления недельного расписания занятий. Кибернетика, 1981, № I, с.63-67.

5. Бабаев А.А. Процедуры кодирования и декодирования перестановок.- Кибернетика, 1984, № 6, с.75-76.

6. Белецкий С.А., Левенталь В.Ц., Глущенко О.Н. Программа решенияобщей задачи календарного планирования (ПЛАН). Описание применения. № П006951 Гос.МП, М.: ВНТИЦ, 1984, 11с.

7. Белкина М.В., Трахтенгерц Э.А. 0 выделении модулей в системепрограмм. Автоматика и телемеханика, 1977, № 7.

8. Березовский Б.А., Кеминер Л.Н. Об одном способе упорядочениякритериев по важности. Автоматика и телемеханика, 1979, № 4, с.67-70.

9. Бродский И.Л. Оптимальная реакция на единичное возмущение расписания. Экономика и математические методы, т.ХП, 1976, Р 6.

10. Бруно Д.Л., Грехем Р.Л., Коглер В.Г., Коффман Э.Г. и др. Теория расписаний и вычислительные машины. М.: Наука, 1984, 336 с.

11. Бурдюк В.Я., Шкурба В.В. Теория расписаний. Задачи и методырешений. Кибернетика, 1971, № I, с.81-102.

12. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных задачкомбинаторного типа. Автоматика и телемеханика, 1968, № II, с.68-93.

13. Быков В.Н., Сергиенко Н.В. Один метод приближенного решениязадач дискретного программирования. Кибернетика, 1978, № 3, с.75-80.

14. Вазинг В.Г., Клипкер И.А. Полиномиальный алгоритм решения задачи Гэри-Джонсона о составлении расписания. Со-общ. АН ГССР, 1981, т.102, № I, с.29-32.

15. Васильев В.В., Додонов А.Г., Левина А.И. Об одном методе решения задачи коммивояжера. Тр.семинара по методам математического моделирования и теории электрических цепей. Ин-т кибернетики АН УССР, вып.9, 1971, с.58-67.

16. Ватник П.А. Статистические методы оперативного управленияпроизводством. М.: Статистика, 1978, 240 с.

17. Вентцель Б.С. Теория вероятностей. М.: Наука, 1969, 376 с.

18. Воденин Д.Р. Диалоговый режим корректирования эвристическихрасписаний. ДР № 2647-79 ДЕП. ВИНИТИ, 1979, 17с.

19. Вьюн А.Ф., Вьюн В.И., Донченко А.Г. Оперативная корректировка план-графика. Механизация и автоматизация управления, 1969, № 3, с.16-19.

20. Гаек Я., Шидак 3. Теория ранговых критериев. М.: Наука,1971, 376 с.

21. Глотов В.А., Павельев В.В. Экспертные методы определения весовых коэффициентов. Автоматика и телемеханика, 1976, № 12, с.95-107.

22. Гордийлук А.Р., Подгасова Т.П. Построение календарного план-графика работы цеха (участка). Механизация и автоматизация управления, 1969, № 3, с.14-16.

23. Григорьева Н.С., Романовский Н.В. Задачи составления циклических расписаний. Кибернетика, 1978, № I, с. 75-79.

24. Гуляницкий А.Ф., Каспитцкая М.Ф., Сергиенко Н.В. и др. 0проблемно-ориентированном пакете программ для решения задач комбинаторной оптимизации. Управляющие системы и машины, 1978, № б, с.43-47.

25. Гуткин JI.C. Оптимизация радиоэлектронных устройств. М.:

26. Советское радио, 1975, 368 с.

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

28. Демин В.К., Чеботарев A.C. Оптимальное обслуживание детерминированного потока требований. Известия АН СССР, Техническая кибернетика, 1976, № 4, с.193-199.

29. Дкейсуол Н. Очереди с приоритетом. М.: Мир, 1973, 280 с.

30. Джонсон С.М. Оптимальные двух- и трехоперационные календарныепланы производства с учетом подготовительно-заключительного времени. Сб. Календарное планирование. -М.: Прогресс, 1966, с.33-41.

31. Дубов Ю.А. Последовательная процедура принятия решений примногих критериях. Автоматика и телемеханика, 1978, № 10, с.104-109.

32. Думлер С.А. Управление производством и кибернетика. М.:

33. Машиностроение, 1969, 420 с.

34. Дюк В. Приложения дискретного программирования. В сб.: Применение исследования операций в экономике. Пер. с венг. М.: Экономика, 1977, с.70-94.

35. Елисеева И.И., Рукавишников В.О. Группировка, корреляция,распознавание образов (Статистические методы классификации и измерения связей). М.: Статистика, 1977, 144 с.

36. Ермольев Ю.М. Методы стохастического программирования. М.:1. Наука, 1976, 240 с.

37. Журавлев Ю.И., Филькенштейн Ю.Ю. Сфера применения методовдискретного программирования. В сб.: Применение исследования операций в экономике. Пер. с венг. М.: Экономика, 1977, с.29-69.

38. Зак Ю.А. Обобщенная задача коммивояжера и ее прикладные аспекты. Автоматика и телемеханика, 1976, № 10, с.120-132.

39. Зак Ю.А. Некоторые свойства задач теории расписаний. Автоматика и телемеханика, 1978, № I, с.123-132.

40. Зиндер Я.А., Шкурба В.В. Эффективные, итеративные алгоритмытеории расписаний. Кибернетика, 1985, № I, с.72-75.

41. Зиновьев С.И. Учебный процесс в современной высшей школе.1. М.: Высшая школа, 1968.

42. Исаченко А.Н., Емеличева Е.В. Многогранник одной задачи теории расписаний. В сб.: Вопросы планирования и экономико-математического моделирования. Минск, 1980, с.117-119.

43. Калюжный Б.И., Солдатов B.C., Шабунин М.И. Об одном способеоценки критерия в задачах теории расписаний. Автоматика и телемеханика, 1976, № 12, с.108-113.

44. Касти Д. Большие системы. Связность, сложность и катастрофы.1. М.: Мир, 1982, 216 с.

45. Канторович Л.В., Романовский И.В. Оптимизационные методы вэкономике: результаты, трудности, перспективы. -Кибернетика, 1977, № 2, с.68-72.

46. Каплинский А.И., Чернышева Г.Д. Об одном способе построенияадаптивных алгоритмов решения задач оптимизации с булевыми переменными. Автоматика и телемеханика, 1976, № Ю, с.66-77.

47. Канцедал С.А., Малых О.А. 0 классах расписаний. Кибернетика, 1981, № 6, с.66-74.

48. Канцедал С.А. Вычислительные алгоритмы решения задач теориирасписаний. Изв. АН СССР, Техническая кибернетика, 1982, № 2, с.221-224.

49. Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная системапрограммирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981, 158 с.

50. Кендел М. Ранговые корреляции. М.: Статистика, 1975, 216 с.

51. Князева Т.А. Опыт применения эвристических методов для решения задачи теории расписаний. В сб.: Математические модели в автоматизированных системах управленияпроизводством. М., ЦЭМИ АН СССР, 1971, с.36-43.

52. Коваленко В.Е., Ремизова Е.А. Задачи анализа, планированияи оптимизации в АСУ-ВУЗ. М.: НИИВШ, 1980, 40 с.

53. Коган Д.И., Лиогонький М.И. Задача о назначениях с учетоминдивидуальных предпочтений. Кибернетика, 1983, № 6, с.80-84.

54. Кожевников Ю.В., Моисеев B.C., Мелузов Ю.В., Хайруллин А.Х.

55. Аналитическое и машинное проектирование автоматизированных систем испытаний авиационных двигателей. М.: Машиностроение, 1980, 272 с.

56. Кожевников Ю.В., Адгамов Р.И., Хайруллин А.Х. К проектированию алгоритма диспетчеризации автоматизированных стендовых испытаний ГТД. В сб.: Труды КАИ, вып.180, 1975, с.18-26.

57. Р.У., Максвелл У.Л. Календарное планирование в условиях сети очередей с дисциплиной по кратчайшей операции. Сб. Календарное планирование. М.: Прогресс, 1966, с.321-334.

58. Р.У., Максвелл У.Л., Миллер П.В. Теория расписаний. -М.: Мир, 1975, 360 с.

59. A.A., Филькенштейн Ю.Ю. Дискретное программирование.-М.: Наука, 1969.

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

61. Кривоногов B.C., Курбатов Б.К., Сытник A.C. ППП для решениязадач синхронизации учебного процесса. Тезисы докл. межреспубликанского семинара "Кибернетика и исследование операций в управлении учебным процессом". Рига: РПИ, 1984, с.16.

62. Кривоногов B.C., Курбатов Б.К., Сытник A.C. Определение коэффициентов ранговой корреляции случайных последовательностей, заданных на перестановках. № П007222 ГосФАП. Инф.бюлл. ВНТИЦ "Алгоритмы и программы", 1984, № 3, с.41.

63. Кристофидес Н. Теория графов. Алгоритмический подход. М.:1. Мир, 1978, 432 с.54. Конвей55. Конвей56. Корбут57. Кофман

64. Круподеров Р.И. Математическая модель и критерии оптимизации

65. АСУ на примере подсистемы "Расписание занятий". -Сб.: Эффективность и моделирование АСУ. Киев: Препринт-80-38, ИК АН УССР, 1980, с.31-43.

66. Кукса А.И., Лаптин Ю.Д. Динамическое программирование в сетевой задаче теории расписаний. Кибернетика, 1978, № I, c.III-II3.

67. Курбатов Б.К. Статистическая оценка продолжительности выполнения комплекса работ. ДЕГ1 ЦНШТЭИприборострое-ния, ДР 814, 1977, 15 с.

68. Курбатов Б.К., Сытник A.C. Использование стратегии дляоперативного регулирования дискретного производства. В сб. тезисов докл. Респ.семинара "Пути совершенствования оперативного управления производством в условиях АСУП", Казань, 1981, с.98.

69. Курбатов Б.К., Сытник A.C. Опыт и особенности составлениярасписания экзаменов в ВУЗе. В сб.: Теория и практика совершенствования системы управления ВУЗом, Томск, ТГУ, 1982, с.143-147.

70. Курбатов Б.К., Сытник A.C. Определение календарных нормативов при автоматизированном составлении расписаний в ВУЗе. В сб.: Тезисы докл. научно-методич.конф. "Управление качеством подготовки специалистов", Казань: КИСИ, 1983, с.13-14.

71. Курбатов Б.К., Ожиганов Л.И., Сытник A.C. Комплекс программдля составления расписаний в ВУЗе в режиме диалога с ЭВМ. Пристендовый листок ВДНХ СССР, М.: ВИМИ, 1982, 4 с.

72. Курбатов Б.К., Ожиганов Л.И., Сытник A.C. Составление расписания экзаменов в ВУЗе. № П007223 ГосФАП. Инф. бюлл. ВНТИЦ "Алгоритмы и программы", 1984, № 3, о • 21 •

73. Курбатова З.Н., Курбатов Б.К. Генератор допустимых расписаний, настраиваемый на выполнение заданного локального правила. ЦФАП НПО "Центрпрограммсистем", Калинин, 1978, per. № 803.

74. Ларичев О.И., Поляков O.A. Человеко-машинные процедуры решения многокритериальных задач математического программирования. (Обзор). Экономика и математические методы, 1980, т.16, № I, с.130-150.

75. Леонтьев Л.П., Гохман О.Г. Проблемы управления учебным процессом: Математические модели. Рига, Зинатне, 1984, 239 с.

76. Лиштенштейн B.C. Дискретность и случайность в экономико-математических задачах. М.: Наука, 1973, 376 с.

77. Макаров И.М., Виноградская Т.М., Рубчинский A.A., Соколов В.Б.

78. Теория выбора и принятия решений. Учебное пособие.-М.: Наука, 1982, 328 с.

79. Материалы Пленума Центрального Комитета КПСС, 14-15 июня1983 г. М.: Политиздат, 1983, 80 с.

80. Меркурьев В.В., Молдавский М.А. Методы решения задач многокритериальной оптимизации. В сб.: Автоматизация поискового конструирования. Искусственный интеллект в машинном проектировании. Йошкар-Ола: МПИ, 1981, вып.12, с.208-231.

81. Методический материал. АСУП. Индивидуальное проектирование.

82. Методика и алгоритм формирования оптимизированных календарных расписаний в цехах серийного производства машиностроительного предприятия. Калинин: НПО "Центрпрограммсистем", 1981, ПО с.

83. Михалевич B.C., Волкович В.JI. Вычислительные методы исследования и проектирования сложных систем. М.: Наука, 1982, 286 с.

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

85. Михалевич B.C., Шор Н.З., Сергиенко Н.В. и др. Пакет прикладных программ для решения оптимизационных задач производственно-транспортного типа большой размерности (ППП ПЛАНЕР). Описание применения. -№ 11006770 ГосМП, М.: ВНТИЦ, 1984 , 80 с.

86. Мут Д. Влияние случайного рассеяния оценок длительности работ на оптимальные календарные планы. В сб.: Календарное планирование. М.: Прогресс, 1966, с.348-356.

87. Мюллер И. Эвристические методы в инженерных разработках.

88. М.: Радио и связь, 1984, 144 с.

89. Мясников В.А., Игнатьев М.Б., Перовская Е.И. Методы планирования и управления производством. М.: Экономика, 1982, 232 с.

90. Ногин В.Д. Новый способ сужения области компромиссов. Техническая кибернетика, 1976, № 5, с.10-14.

91. Норинский Л.Ю. Устойчивость решений задачи теории расписанийпри изменении длительности операций. ДР № 4804-80 ДЕЛ. ВИНИТИ, 1980, 20 с.

92. Ожиганов Л.И., Курбатов Б.К., Сытник А.С. Программа составления расписания экзаменов в ВУЗе с использованием Дос ЕС. № П006440 ГосФАП. Инф.бюлл.ВНТИЦ "Алгоритмы и программы", 1983, № 5, с.21.

93. Озерный В.М., Рябов Л.П. Эвристический метод оптимизации последовательности выполнения операций. Автоматика и телемеханика, 1967, № 12, с.169-172.

94. Озерный В.М., Гафт М.Г. Методология решения дискретных многокритериальных задач. В сб.: Многокритериальные задачи принятия решений, М.: Наука, 1978, с.14-47.

95. Осколков И.О. Одновременное ветвление по нескольким переменным в методе ветвей и границ. Автоматика и телемеханика, 1975, № 8, с.75-81.

96. Осколкова С.Е., Осколков И.О. Применение некоторых эвристических методов к решению задач календарного планирования. Автоматика и телемеханика, 1968, № 2, с.177-184.

97. Основные направления экономического и социального развития

98. СССР на I98I-I985 гг. и на период до 1990 года. -М.: Политиздат, 1981, 95 с.

99. Основы управления технологическими процессами. Под ред.

100. Райбмана Н.С. М.: Наука, 1978, 440 с.

101. Пак Л.В. Разработка моделей и алгоритмов оптимизации и автоматизации процесса планирования учебной работы ВУЗа. Автореферат канд.дисс., Томск; ТШ, 1981, 16 с.

102. Первозванский A.A. Математические модели в управлении производством. М.: Наука, 1975, 617 с.

103. Петров В.В. Суммы независимых случайных величин. М.: Наука,1972, 416 с.

104. Планирование дискретного производства в условиях АСУ. Подред. Глушкова В.М. Киев:, Техника, 1975,

105. Подиновский В.В. Многокритериальные задачи с упорядоченнымипо важности однородными критериями. Автоматика и телемеханика, 1976, № II, с.I18-127.

106. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений. В сб.: Многокритериальные задачи принятия решений, М.: Машиностроение, 1978, с.48-82.

107. Подиновский В.В., Ножин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982, 256 с.

108. Подчасова Т.П. Об оценках в выборе правил предпочтения в задачах календарного планирования. В сб.: Автоматизированные системы управления предприятиями. Тр. семинара, вып.1, Киев, 1968, с.5-46.

109. Португал В.М. Решение задачи календарного планирования с помощью правил предпочтения. В сб.: Прикладная математика и кибернетика. Материалы к Всес.межвуз. симпозиуму по прикл.мат. и киберн., Горький,1967, с.254-258.

110. Пшеничный 13.Н- Необходимые условия экстремума. М.: Наука,1982, 143 с.

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

112. Растригин JI.A., Зйдук Я.Ю. Адаптивные методы многокритериальной оптимизации. Автоматика и телемеханика, 1985, № I, с.5-26.

113. Рейнгольд Э., Нивергельт Ю., Дсо Н. Комбинаторные алгоритмы.

114. Теория и практика. М.: Мир, 1980, 476 с.

115. Романовский И.В. Алгоритмы решения экстремальных задач.1. М.: Наука, 1977, 352 с.

116. Рыбников К.А. Введение в комбинаторный анализ. Изд. Моск.ун-та, 1972, 255 с.

117. Савельев А.Я., Зубарев Ю.Б., Коваленко В.Е., Колоскова Т.А.

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

119. Садыков И.Х. Решение одной задачи оптимального закрепленияисполнителей за работами по векторным критериям.-В сб.: Исследование операций и аналитическое проектирование в технике, вып.2, Казань: КАИ, 1979, с.9-14.

120. Сафонова Т.Е. 0 внесении изменений в оптимальное структурное расписание. Записки научных семинаров ЛОМИ АН СССР, т.Ш, 1981, с.151-161.

121. Семенов А.И., Португал В.М. Задачи теории расписаний в календарном планировании. М.: Наука, 1972.

122. Сергиенко И.В., Каспишцкая М.Ф. Модели и методы решения на

123. ЭВМ комбинаторных задач оптимизации. Киев: Нау-кова Думка, 1981, 288 с.

124. Скворцов В.В. Методы экспертных оценок и их приложение взадачах теории фильтрации. Казань: Тат.кн.изд.,1976, 215 с.

125. Скворцов В.В., Нуриев Н.К. Постановка и подходы к решениюмногоэкстремальной задачи оптимизации работы поточной линии в изменяющихся условиях. В сб.: Теория оптимальных решений, вып.5, Вильнюс: ИМК АН Лит.ССР, 1979, с.55-59.

126. Смоляр Л.И. Модели планирования в дискретном производстве.1. М.: Наука, 1978, 320 с.

127. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров взадачах со многими критериями. М.: Наука, 1981, 112 с.

128. Солодовников В.В., Бирюков В.Ф., Тумаркин В.И. Принцип сложности в теории управления. М.: Наука, 1977,344с.

129. Солодовников В.В., Зверев В.Ю. Применение теории автоматического управления и многокритериальной оптимизации для автоматизации проектирования.АСУ ТП. М.: Машиностроение, 1984, 48 с.

130. Справочник проектировщика АСУ ТП. Под ред. Смилянского Г.Л.

131. М.: Машиностроение, 1983, 527 с.

132. Степин Ю.П. Исследование и разработка методов решения многокритериальных задач теории расписаний в АСУ организационного типа (на примере ВУЗа). Автореферат канд.дисс., М., 1976, 16 с.

133. Сытник A.C. Использование ЭВМ для планирования экзаменационной сессии в ВУЗе. Информационный листок ТатЦНТИ № 10-80, 1980, 4 с.

134. Сытник A.C. Определение длительности подготовки к экзаменув автоматизированной системе составления расписаний. В сб.: Тезисы докл. юбилейной научно-метод. конф. Казань: КАИ, 1982, с.103-104.

135. Сытник A.C. Решение задачи многоцелевой оптимизации в диалоговом режиме. В сб.: Вычислительные и управляющие системы летательных аппаратов. Казань: КАИ, 1983, с.10-12.

136. Сытник A.C. Календарное планирование задач с нефиксированным технологическим маршрутом. В сб.: Тезисы докл. научно-практ. конф. "Новое в технологии и управлении гальванических производств", Казань: КХТИ, 1984, с.60-62.

137. Сытник A.C., Долотова Т.Р. Генератор перестановок. № П007221

138. ГосШАП, Инф.бюлл.ВНТИЦ "Алгоритмы и программы", 1984, № 3, с.40.

139. Тамулинас Б. Обучаемые программные модели поиска оптимальных расписаний. В сб.: Статистические проблемы управления, вып.23, Вильнюс, 1977, с.105-109.

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

141. Теория прогнозирования и принятия решений. Под ред. Саркисяна С.А. М.: Высшая школа, 1977, 352 с.

142. Фейгин JI.И. Общая задача теории расписаний при неполнойинформации. Автоматика и телемеханика, 1972, № 3, c.II0-II6.

143. Хайруллин А.Х., Адгамов Р.И. К оценке временных характеристик автоматизированных испытаний ГТД. В сб.: Совершенствование технологии производства. Казань: НИАТ, 1975, с.16.

144. Цыпкин Я.З. Адаптация и обучение в автоматических системах.1. М.: Наука, 1968, 156 с.

145. Шкурба В.В., Подчасова Т.П., Пишчук А.Н., Тур Л.П. Задачикалендарного планирования и методы их решения. -Киев: Наукова думка, 1966, 155 с.

146. Шкурба В.В., Селивончик В.М. Расписания, имитационное моделирование и оптимизации. Кибернетика, 1981, № I, с.91-96.

147. Эрлих И.И. О возможностях использования одного класса методов выпуклого программирования в диалоговых процессах планирования. Техническая кибернетика, 1981, № 4, с.44-49.

148. Юдин Д.В., Горяшко А.П., Немировский А.С. Математическиеметоды оптимизации устройств и алгоритмов АСУ. -М.: Радио и связь, 1982, 288 с.

149. Baum S., Terry W. Random Sampling Approach To MCDM. Подходк решению многокритериальных задач принятия решений методом случайного поиска. "Lect.Notes Eeon. and Math. Systems", 1981, v.190, p.10-27.

150. Cerny M., Gliickoufora D. Приложение расплывчатых множествв многокритериальных задачах принятия решений. Ekon.-mat. obz., 1978, v.14, No.1, p.1-25.

151. Davis jj., Jaffe I, Algorithm for scheduling tasks on unrelated processors. Построение расписаний для системы независимых процессоров.- I.Assoc.

152. Comput. Llach., 1981, v.28, No.4, p.721-736.

153. Friesz T.L. Multiobyective Optimization in Transportation:

154. The Case of Eduilibrium Netwokk Design. Многоцелевая оптимизация в-транспортировке. Случай проектирования равновесной сети. . Lect. Notes Economics and Mathematical Systems, 1981, v.190, p.116-127.

155. Generalized Academic Simulation Programs (360 GASP). Обобщенный имитационный язык составления расписаний (ГАСП-Ш/360).- Computation Center, Cambridge, Massachusetts: Mass Ihstitute of Technology, 1977, 280 p.

156. Hinxman A. A problem of scheduling conference accomodation.

157. Задача размещения делегатов конференции.- Combinatorial Optimiz., Co 79 Conference, Norwich, 1980, p.53-57.145* Jeffrey В. Optimal Single-Machine Sheduling With Earliness

158. And Tardiness penalties. Составление расписания для одной машины при наличии штрафов за раннее и позднее окончание работу . Oper. Res., 1977, v.25, Nо.1, р.62-69.

159. Karla К., Bansal S., Bagga P. Minimization of Weighted Sumof Completion Times with Due Dates in Permutation

160. Kolar J. A'new possibility in Bi-directional search. Новыйалгоритм эвристического поиска . Kybernetika, 1977, v.13, No.1, p.11-22.

161. Копуa I., Somogyi P., Srabagos T. A Method Of Timetable

162. Construction By Computer. Метод составления расписаний С помощью компьютераJ . Period. Politechn. Elec. End., 1978, v.22, No.2-3, p.171-181.

163. Martelli A. On the complexity of admissible search algorithms. О сложности допустимых алгоритмов поиска!.- Artific. Intellegenz, 1977, v.8, No.1, p.1-13.

164. Miller H., Pierskalla Y7., Rath G. Nurse Shcedulind Using

165. Mathematical Programming.^Составление расписания работы младшего медицинского персонала с помощью математического программированияJ.- Oper. Res., 1976, v.24, No.5, p.857-870.

166. Shigeji Miyazaki. One machine scheduling problem with dualcriteria. L Задача построения расписания для одного прибора с двойным критерием . . J.of the Oper. Res. Soc. of Japan. 1981, v.24, No.1, p.37-51.

167. Spronk J., Telgen J. An ellipsoidal interactive multiplegoal programming method. Эллипсоидальный алгоритм для интерактивного многоцелевого объектного программирования J . Lect. Notes in Economics and Mathematical Systems, 1981, v.190, p.380-387.

168. V/erra D. On a Multi-Peviod Assigment Problem. Задача 0назначениях на период.- Adv. Oper. Res., 1978, 17o.7, p. 129-134.жение 1,

169. Копии актов о внедрении и практическом использовании результатов диссертационной работы1. УТВЕРЖДАЮ0

170. Ректор Казанского авиационного института ии. А.Н.Туполева1. Ю.В.Кожевников" 1979 г.1. АКТ ВНЕДРЕНИЯзадачи " Составление расписания экзаменов в ВУЗе на базе ЕС ЭВМ" в Казанской авиационном институте им.А.Н.Туполева

171. Работа выполнена в соответствии с Координационным планом Минвуза СССР от 9 июля 1976 г. (п. П.6*5.1.1.) на кафедре АСУ Казанского авиационного института им. А.Н.Туполева

172. Объем работы: обследование существующей системы диспегче-ризашга учебного процесса; математическая постановка задачи составления расписания экзаменов; разработка алгоритмов и программ; опытная эксплуатация задачи.

173. Вид внедренных результатов программа ЭВМ.

174. Область и форма внедрения планирование учебного процесса»

175. ОБЪЕМ И КАЧЕСТВО ВЫПОЛНЕННОЙ РАБОТЫ по теме "Исследование автоматизированной системы управления нагружением при статических и повторно-статических прочностных испытаниях".

176. Цроректор по УР Казанского авиационного института ям* А*Н* Туполева1. СЛШавняш»1983г

177. АКТ В Н Е Д?ЕН И Я комплекса пробами для оперативно-календарного пла*» шфоваяия стендовых: испытаний систем ДА в составе учвбно-ясследовательскюс работ в Казанском авиаци «* онном институте имени А. Н» Туполева

178. E. Комплекс програш используемся в учебном процессе при про» ъелении практических и лабораторных: занятий по курсам "Основы проектирования АСУ", "Проектирование подсистем и звеньев АСУ,

179. ХУ, Эффективность от эксплуатации комплекса црограш достигав1**» ся за счёт повшения качества подготовки иннекеров-сиетемотехни «• ков, направляемых на предприятия Минавиапрома* х