Введение к работе
Актуальность темы. Вопросам повышения эффективности функционирования систем неизменно уделяется значительное внимание. С середины 50-х годов XX века (после опубликования результатов исследований С. Джонсона и Р. Беллмана по планированию работы сборочных линий) для решения задач оптимизации работы дискретных систем активно используют модели и методы теории расписаний.
Исследования в теории расписаний имеют как теоретическую, так и практическую значимость. Они проводятся с целью уменьшения длительности производственного цикла, уменьшения запаздывания работ относительно установленных сроков и т. п., то есть в конечном итоге направлены на совершенствование механизмов планирования и управления производственными процессами. Этим объясняется неослабевающий интерес к задаче Беллмана-Джонсона и ее обобщениям - классу задач теории расписаний, связанных с решением проблемы составления оптимального плана работы систем последовательного типа (дискретных многостадийных систем). Задачи этого класса являются предметом диссертационного исследования.
Задачи теории расписаний в большинстве своем оказываются трудно решаемыми (Garey М. R., Johnson R. S.). Задача Беллмана-Джонсона является М'-трудной. Первоначально для ее решения предлагались точные подходы, а также метод случайного поиска (Heller J., Nugent С. Е.). Аналитические результаты получены в основном средствами комбинаторного анализа. Комбинаторные исследования проводились при рассмотрении частных случаев, для выявления условий элиминации и доминирования (Белов И. С, Бурдюк В. Я., Столин Я. Н., Johnson S. М., Gupta J. N. D., Nabeshima I., Szwarc W.).
Как точные методы решения задачи Беллхмана-Джонсона и ее обобщений предлагались схемы ветвей и границ (Schrage L., Ignal Е., Dudek R. A., Campbell Н. G., Lawler E. L., Lenstra J. K., Rin-nooy Kan A. H. G.), динамического программирования (Беллман P., Карп P., Якимов P. M.), целочисленного программирования (Мап-ne A. S., Story А. Е., Wagner Н. М.). Однако точные методы можно
POC НАЦИОНАЛЬНА» { БИБЛИОТЕКА |
использовать лишь для решения задач небольшой размерности.
После того, как была установлена ЛГР-трудность задачи Беллма-на-Джонсона (Garey М. R., Johnson R. S., Sethi Ravi), исследования в основном проводятся в области приближенных подходов и связаны с построением эффективных приближенных алгоритмов. Наиболее интенсивные разработки ведутся в области алгоритмов с гарантированными оценками точности и алгоритмов локального поиска.
Одним из основных направлений в современной дискретной оптимизации и, в частности, в теории расписаний является разработка р-приближающих алгоритмов (Севастьянов С. В., Спесивцев А. В., Hall L. A., Potts С. N.). Препятствием к построению алгоритмов с хорошими оценками точности является сложность получения качественных нижних оценок оптимума.
Другим перспективным направлением исследований является локальный поиск. На базе схем последовательного улучшения развились новые мощные средства - алгоритмы имитации отжига, поиск с запретами, генетические алгоритмы (Aarts Е. Н. L., Brucker P., Werner F., Lenstra J. К., Taillard Е., Glover F., Gupta J. N. D., Laguna M., Reeves С R., Nowicki E., Smutnicki С). Интерес к поиску в локальной окрестности носит не только практический, но и теоретический характер: исследуются сложностные аспекты и асимптотическое поведение алгоритмов. Проблемы в области локального поиска связаны с выбором окрестности и направления движения на множестве допустимых решений, со сложностью оценки качества решения.
Описанные проблемы обусловливают необходимость проведения дальнейших исследований в области теории расписаний, касающихся разработки эффективных алгоритмов и методологии поиска приближенно оптимальных решений. Тесная взаимосвязь теории расписаний с реальными задачами оптимизации процессов обработки в дискретных системах является основой для практического использования результатов этих исследований. Практика, в свою очередь, ставит задачи совершенствования используемых моделей, повышения степени их адекватности реальным условиям, разработки новых моделей и методов исследования дискретных многостадийных систем. Очерченный круг вопросов (совершенствование методологии локального поиска, разработка приближенных подходов, а также мето-
дов решения задач и эффективных алгоритмов планирования, совершенствование существующих и построение новых моделей) определяет направление диссертационного исследования. Решение этих вопросов позволит существенно повысить эффективность и качество управления дискретными системами и поэтому является актуальной задачей.
Цель работы состоит в разработке теоретических основ и методов оптимизации процессов обработки заданий в дискретных многостадийных системах и построении эффективных алгоритмов для решения практических задач планирования и управления производственными процессами.
Основные задачи исследования.
Построение математических моделей дискретных многостадийных систем.
Разработка концепции j-оптимальности и приближенного подхода к решению задач теории расписаний.
Разработка и теоретическое обоснование методов построения л-оптимальных расписаний.
Решение на основе разработанных подхода и методов задачи Беллмана-Джонсона и ее обобщений: задачи минимизации максимального запаздывания работ и задачи с повторным обслуживанием.
Разработка эффективных алгоритмов для планирования работы систем последовательного типа.
Решение практических задач по оптимизации работы дискретных многостадийных систем и разработка специализированных технических средств для планирования и управления функционированием таких систем.
Методы исследования. В работе использовались методы теории расписаний, теории сложности, теории алгоритмов, комбинаторного анализа, функционального анализа, теории множеств, теории графов, математического программирования, статистического моделирования.
Научная новизна работы.
Дана новая формализация задачи Беллмана-Джонсона. Построена математическая модель системы последовательной обработки с повторным обслуживанием.
Разработана концепция s-оптимальности, определяющая принцип формирования окрестности решения и методы поиска локально оптимальных решений. Введен оператор преобразования расписания и доказана замкнутость множества допустимых расписаний относительно оператора преобразования. На множестве расписаний введена метрика, даны формальные определения s-окрестнос-ти расписания и s-оптимального решения задачи.
Предложен приближенный подход к решению задач комбинаторной оптимизации, основанный на концепции s-оптимальности. Разработаны методы решения задач об оптимальном перестановочном расписании, Беллмана-Джонсона, минимизации максимального запаздывания и с повторным обслуживанием, реализующие этот подход и использующие преобразования расписаний.
Разработаны методы исследований систем последовательной обработки, основанные на анализе матричных моделей этих систем. Развит аппарат критических путей. Введены понятия меры эффективности преобразования и композиции преобразований. Построена система оценок эффективности преобразований и семейств преобразований.
Получены необходимые условия эффективности преобразований и их семейств. Определены достаточные условия 1-оптималь-ности расписаний и предложены методы построения 1-оптимальных расписаний.
Получены оценки эффективности преобразований, составляющих композицию, и условия согласованности оценок эффективности композиции и преобразований, входящих в ее состав. Доказаны необходимые условия эффективности композиции преобразований и предложены способы построения эффективных композиций. Разработан метод построения s-оптимальных расписаний (s > 2), основанный на проведении эффективных композиций преобразований.
Показано, что разработанные подход и методы применимы для решения таких обобщений задачи Беллмана-Джонсона, как задачи с неодновременным поступлением работ, с заданными отношениями предшествования работ и с разными маршрутами.
Разработаны эффективные алгоритмы поиска «-оптимальных расписаний (s > 1), определена их сложность и доказана сходимость.
Практическая ценность. Использование теоретических и практических результатов, полученных в диссертации, позволяет существенно повысить качество и эффективность планирования и управления в дискретных многостадийных системах. Это подтверждается приведенными в диссертации примерами решения практических задач.
Аналитические результаты, представленные в работе, дают возможность строить легко реализуемые на ЭВМ эффективные алгоритмы синтеза приближенно оптимальных расписаний. Разработанные алгоритмы применимы для оптимального планирования работы различного рода систем последовательного типа, например, при планировании производственных процессов в сборочных, инструментальных цехах предприятий машиностроения и т. п. Использование алгоритмического обеспечения в АСУТП позволяет улучшить ряд показателей эффективности работы предприятий, в том числе увеличить объем производства на планируемый период, уменьшить длительность простоев оборудования по организационным причинам, снизить энергозатраты в расчете на единицу выпускаемой продукции, уменьшить штрафы, связанные с несвоевременным выполнением заказов.
Реализация и внедрение результатов. Результаты диссертационной работы в виде алгоритмов и пакетов программ внедрены в системах технологической подготовки производства Волжского подшипникового завода ОАО «ВПЗ-15», г. Волжский Волгоградской обл., и ОАО «Волжский трубный завод», г. Волжский Волгоградской обл.
Материалы диссертации используются в учебном процессе кафедры прикладной математики и информатики Волжского гуманитарного института (филиала) Волгоградского государственного университета при проведении курса «Теория расписаний».
Основные положения, выносимые на защиту:
Концепция ^-оптимальности.
Матричное представление и математическая модель процесса обработки заданий в системах конвейерного типа.
Математическая модель системы последовательной обработки с повторным обслуживанием.
Метод анализа матричных моделей дискретных многостадийных систем с помощью аппарата критических путей и их образов (развитие метода критических путей).
Метод преобразований при построении приближенно оптимальных расписаний, операторы преобразования расписаний и их свойства.
Способ оценивания эффективности преобразований, необходимые условия эффективности преобразований, достаточные условия 1-оптимальности расписаний, метод построения 1-оптимальных расписаний.
Способ оценивания эффективности композиции преобразований по оценкам эффективности преобразований, составляющих композицию, а также необходимые условия эффективности композиции преобразований.
Метод построения ^-оптимальных расписаний (s > 2) с использованием композиций преобразований и их семейств.
Алгоритмы синтеза s-оптимальных расписаний (s > 1).
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на научно-техническом семинаре «Проблемы создания интеллектуальных САПР» (Геленджик, 1988), VIII Всесоюзной конференции «Проблемы теоретической кибернетики» (Горький, 1988), международных научных и научно-технических конференциях «Непрерывно-логические методы и модели в науке, технике и экономике» (Пенза, 1995), «Математические методы и компьютеры в экономике» (Пенза, 1996, 1997, 1999), «Логико-математические методы в технике, экономике и социологии» (Пенза, 1998, 1999), «Математические методы в технике и технологиях» - ММТТ-12 (Великий Новгород, 1999), «Математические методы и информационные технологии в экономике» (Пенза, 2000, 2001), «Математические методы
и информационные технологии в экономике, социологии и образовании» (Пенза, 2001), «Математические методы в технике и технологиях» - ММТТ-2000 (Санкт-Петербург, 2000), Четвертом сибирском конгрессе по прикладной и индустриальной математике - ИНПРИМ-2000 (Новосибирск, 2000), Российской конференции «Дискретный анализ и исследование операций» - DAOR 2002 (Новосибирск, 2002), семинарах по дискретной математике и теории информации (Пенза, завод-втуз, 1987-1992), ежегодных конференциях профессорско-преподавательского состава Волжского гуманитарного института (филиала) Волгоградского государственного университета (1996-2003).
Публикации. По теме диссертации опубликована 51 научная работа, включая монографию, 22 статьи, 26 тезисов докладов и 2 изобретения.
Структура и объем работы. Диссертация состоит из введения, четырех частей, включающих 8 глав, заключения, библиографии из 190 наименований и приложений. Объем работы составляет 337 страниц основного машинописного текста и 26 страниц приложений; в диссертации 22 рисунка и 15 таблиц.
