Оперативное построение расписаний с древовидной структурой требований

• Автор: Янков, Игорь Александрович
• Шифр специальности: 05.13.01, 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Пенза
• Количество страниц: 200 с. : ил.

ОГЛАВЛЕНИЕ
Введение.

Глава I. Анализ современных моделей, методов и средств построения расписаний

1.1 Актуальность и проблематика разработки систем автоматического построения расписаний

1.1.1 Анализ существующих систем автоматического планирования.

1.1.2 Специфика предметных областей с древовидной структурой обслуживания требований.

.2 Теоретические основы построения расписаний

1.2.1 Одностадийные расписания.

1.2.2 Многостадийные расписания

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

1.3 Расписания с древовидной структурой связей.

1.4 Выводы по главе 1
Глава 2. Модель и методы оперативного построения и перестроения расписаний с древовидной структурой требований.
2.1 Модель расписаний с древовидной структурой.
2.1.1 Требования к модели и ее предназначение
2.1.2 Представление модели расписания в виде смешанного графа
2.1.3 Операции над графом расписания создание, отмена, перепланирование задачи.
2.1.4 Принципы построения дерева задач ветвление задач.
2.2 Алгоритм построения расписаний с древовидной структурой связей
2.2.1 Постановка задачи
2.2.2 Формирование целевой функции.
2.2.3 Общая схема построения расписаний
4.3.2 Целевая функция и ее компоненты
4.3.3 Логика агентского взаимодействия
4.4 Особенности архитектуры и программной реализации комплекса построения расписаний
4.5 Экспериментальная оценка эффективности программного комплекса на основе тестовой эксплуатации системы планирования компанией VI .
4.5.1 Условия проведения тестовой эксплуатации.
4.5.2 Основные характеристики функционирования системы автоматического планирования в ходе проведения тестовой эксплуатации программного комплекса. 1
4.5.3 Анализ эффективности предложенных моделей и методов на основе сравнения автоматического и ручного типа построения расписаний
Заключение.
Литература


Это повысило эффективность работы всего порта и позволило сократить расходы за счет отказа от ручного планирования. В году этой компанией была внедрена система автоматического построения расписания поставок готовой продукции клиентам для крупного типографского комплекса. В автономно генерируемом расписании отражается план работы многих подразделений, а также порядок и сроки обслуживания клиентов. Такая автоматизация позволила компании-заказчику существенно увеличить объем выпускаемой продукции при сохранении того же уровня постоянных издержек. К наиболее часто встречающимся решениям по автоматизации процесса составления планов можно отнести многочисленные комплексы поддержки учебного процесса, а точнее их модули построения расписаний. Например, современная система «АВТОРасписание» компании «ММиИС» может подготавливать расписания для общеобразовательных школ, техникумов и вузов. Несмотря па то, что это одна из самых сложных задач прикладной математики, благодаря удачно подобранным эвристикам, решение, как правило, удовлетворяет пользователей. Это доказывается большим количеством поставленных готовых решений в самых разных регионах России []. Анализ приведенных выше успешных внедрений выявляет следующие закономерности. Все представленные системы планирования работают в пакетном режиме. Это означает, что они загружают исходные данные (ресурсы, заказы, критерии целеполагания и т. Т.е. Почти всегда в вышеприведенных системах не предусматривается «обратная связь», т. Фиксированные «горизонты планирования» позволяют уменьшить объем вычислительных итераций, но сильно ограничивают гибкость перестроения расписаний, т. Как правило; расписания представляют собой однородные последовательности действий (операций), которые необходимо выполнить однотипным ресурсам, что с одной стороны превращает задачу генерации расписания в классическую задачу упорядочивания теории расписаний, но с другой стороны не отражает многообразия проблем стоящих перед процессом автоматизации процесса составлсния*расписаний []. Описанные системы имеют архитектуру, не позволяющую быстро вносить изменения в логику планирования, дорабатывать отдельные эвристики и добавлять новый функционал. Это вызвано, прежде всего, высокой-связанностью компонентов системы, отвечающих за составление расписания, когда логика планирования распределена среди нескольких модулей и для того, чтобы добавить новую функцию требуется внести изменения в каждый из них. Рассмотрим предметные области, которые предъявляют более высокие требования* к возможности оперативного построения расписаний, предполагающих древовидную структуру обслуживания требований. Очень часто в практических задачах природа структуры расписаний носит сложный характер, когда итоговый план представляет собой составной объект, связывающий множество участников и операций, которые они выполняют на разных стадиях бизнес-процесса с учетом логической последовательности места и времени. Т.е. Зачастую в этом случае построить допустимое расписание, учитывающее множество связей, отражающих порядок следования* и согласования задач, уже является довольно сложной задачей. Тем более она усложняется, если требуется найти оптимальный вариант расписание. Рассмотрим несколько примеров предметных областей, показывающих специфику внутренних связей расписания. Хорошим примером является расписание школьных занятий, когда каждая операция (урок) должна хранить данные о несколько участниках: преподаватель, аудитория, класс [,]. Многие эвристические алгоритмы решают задачу построения такого расписания с помощью разбиения задачи на две независимые подзадачи, например, поиска соответствия, преподаватель-класс и класс-аудитория. Т.к. Но в общем случае операция должна содержать три неизбыточных индекса, указывающих на вышеперечисленные ресурсы. Более сложным случаем является расписание работы водителей и машин в компаниях сдающих автомобили в аренду(геШ-а-саг companies) потому что, в каждый момент времени водитель как ресурс, выполняя передвижения по доставке/забору машин и подвозу пассажиров, выполняет несколько задач [1,2].