Введение к работе
Актуальность работы. Задачи составления расписаний имеют постоянно расширяющуюся сферу приложения, в том числе в области календарного планирования предприятий, организации учебного процесса, построения графиков движения транспорта и планирования информационно- вычислительных процессов.
Методическую основу перечисленных задач составляет теория расписаний, которая использует модельный подход к анализу реальных процессов. Исследования в данной области математического программирования ведутся достаточно давно, при этом разнообразие используемых моделей и степень их универсальности постоянно увеличиваются. Важное место в разработке теории И методов решения задач составления расписаний занимают работы Канторовича Л.В., Конвея РЛ., Парамонова ФЛ, Португала В.М., Танеева B.C. и многих других исследователей. Однако целый круг актуальных вопросов по-прежнему остается открытым, поскольку совершенствование методов теории расписаний проходило, в'основном, без кардинальных изменений анализируемых моделей.
В первую очередь - это снятие ограничений, в рамках которых решаются типовые задачи, исследование методов повышения эффективности вычислительных процедур для задач большой размерности, а также построение моделей задач в условиях неопределенности. При этом разрабатываемое расписание должно удовлетворять целому ряду требований, обуславливающих характер выполнения запланированных производственных операций. В этих условиях ориентация на специализированные модели составления расписаний в различных предметных областях препятствуют разработке универсальных вычислительных алгоритмов и инструментальных средств оптимизации расписаний по заданной совокупности оценочных функций.
Кроме того, любое планирование в нестабильных условиях производственной, экономической и социальной обстановки связано с высоким риском разного рода нарушений, что существенно сказывается на эффективности разработанного расписания.
В связи с этим важное значение приобретает задача разработки универсальных математических моделей составления расписаний^лозволяющих алгоритмизировать процедуру составления расписаний для различных предметных областей с учетом перечисленных выше особенностей.
Цель диссертационной работы состоит в создании методики составления гетерогенных расписаний как болыперазмерных, многокритериальных задач, которые позволяют учитывать неопределенные факторы и использовать разнородные по составу множества требований и приборов, устраняющих существующие ограничения на стратегию обслуживания; а также в разработке на этой основе автоматизированных инструментальных средств поддержки при-
пятня решений при составлении расписаний функционирования производственных систем.
Задачи исследования. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:
предложена математическая модель гетерогенной задачи составления расписаний;
разработана методика формирования оптимального по условным и безусловным критериям предпочтения варианта расписания;
предложен способ декомпозиции и оптимальной композиции задачи составления расписаний по функциональным и временным признакам;
исследованы методы повышения разрабатываемых расписаний с учетом неопределенных факторов производственной обстановки;
разработана интеллектуальная подсистема поддержки принятия решения для диспетчера промышленного предприятия.
Методика исследований. Результаты исследований, выполненных в работе базируются на методах теории расписаний, теории графов, теории принятия решений, методах векторной оптимизации, системного анализа, методологии разработки алгоритмического и программного обеспечения АСУ, анализа данных и инженерии знаний.
Научная новизна работы заключается в следующем:
введено понятие гетерогенной задачи теории расписаний, обобщающее существующие подходы к составлению расписаний, позволяющее сиять огра-шгчения типовых задач за счет использования новых элементов расписания, таких как многофункциональные приборы и комплексные требования;
сформулирована конструктивная математическая модель для гетерогенной задачи составления расписаний, логическая и алгебраическая структуры, которой позволяют объединить большинство существующих форм математического описания задачи, обеспечивают декомпозицию основных элементов расписания и формализуют неопределенные факторы, свойственные реальным задачам теории расписаний;
разработана методология направленного формирования вариантов построения оптимальных расписаний по заданной совокупности требований;
предложен способ декомпозиции исходной задачи составления расписаний, позволяющий формировать допустимые варианты из субоптимальных фрагментов;
- разработан метод построения оптимального расписания в условиях
стохастической и нестохастической неопределенности.
Практическая ценность. Разработана интеллектуальная подсистема поддержки принятия решений, содержащая функционально полный набор модулей для решения гетерогенных задач составления расписаний, в том числе модули одностадийных и многостадийных задач, типовой решающий модуль, модуль структуризации, модули принятия решений и оптимизации. Программная система позволяет упорядочить множество требований в соответст-
вий с имеющимися ограничениями на приборы и ресурсы, сформировать оптимальное по критериям равномерности, количеству переходов, а также эргономическим' показателям расписания с учетом возможных нарушений, связанных с ремонтом, заменами и простоями.
Результаты диссертационной работы в составе: - методики составления оптимального плана загрузки механического цеха; - методики формирования - расписаний для большеразмерных, многокритериальных задач оперативно-календарного планирования; - программного модуля, реализующего подсистему поддержки принятия решений для диспетчера промышленного предприятия, внедрены в производственную деятельность АО УМПО.
Результаты внедрения свидетельствуют о высокой эффективности методов, разработанных в диссертационной работе.
Тематика работы связана с планами госбюджетных научно-исследовательских работ № АП-ПЭ-35-95-03 и № АП-ПЭ-35-96-03 по разработке архитектуры алгоритмического и программного обеспечения многопроцессорных и управляющих систем с элементами искусственного интеллекта.
На защиту выносятся:
- математическая модель гетерогенной задачи составления расписаний;
методика формирования оптимального по условным и безусловным критериям предпочтения варианта расписания, базирующаяся на методе реберной раскраски мультиграфа;
способ декомпозиции и оптимальной композиции задачи составления расписаний по функциональным и временным признакам;
метод формирования расписания в условиях неопределенности с использованием субъективных вероятностей, нечетких и интервальных множеств;
интеллектуальная подсистема поддержки принятия решений для диспетчера промышленного предприятия.
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на : международной научно-методической конференции "Проблемы качества высшего образования" (Уфа, 1994 г.); региональной конференции "Реализация многоступенчатой подготовки специалистов в вузах Башкортостана" (Уфа, 1994 г.); всероссийском совещании "Базы данных и информационные технологии в системах непрерывного образования" (Уфа, 1995 г.).
Публикации. По материалам диссертации опубликовано 7 печатных работ.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографии и приложения. Работа содержит страниц машинописного текста и 121 наименование библиографических источников.
