Содержание к диссертации
Введение
Глава 1. Исследование предметной области
1.1. Постановка проблемы 4
1.2. Обзор средств и методов решения 5
1.3. Обзор существующих систем 15
1.4. Анализ традиционного подхода решения задач календарного планирования 22
1.4.1. Диаграмма Гантта 23
1.4.2. Правила выбора из очереди 25
1.4.3. Система приоритетов 26
1.4.4. PERT-анализ 28
1.5. Формулировка ТЗ 30
Глава 2. Построение имитационной модели
2.1. Проблемы многокритериальной оптимизации 31
2.2. Затратный подход к календарному планированию 34
2.3. Анализ производственных факторов 36
2.4. Классификация оптимизационных критериев 45
2.5. Временная матрица для диаграммы Гантта 50
2.6. Алгоритм составления расписаний 52
2.7. Эвристики (правила разрешения конфликта) 55
2.8. Расширенная имитационная модель 62
Глава 3. Реализация программного комплекса
3.1. Выбор средств реализации - среда Delphi 6 67
3.2. Интерфейс и диалоги 68
3.3. Модули и алгоритмы 84
3.4. Формат таблиц БД 96
3.4.1. Внешнее представление данных 96
3.4.2. Внутреннее представление данных 98
3.5. Интеграция с системой «ФОБОС» 102
Глава 4. Оценка эффективности ПК
4.1. Оценка сложности алгоритма 105
4.2. Оценка экономического эффекта от внедрения ПК 107
Заключение 107
Литература 109
Приложение
- Постановка проблемы
- Проблемы многокритериальной оптимизации
- Выбор средств реализации - среда Delphi
- Оценка сложности алгоритма
Введение к работе
В условиях современной экономической ситуации, связанной с реальным переходом к рынку, важнейшими задачами для предприятий стали быстрое реагирование на требования рынка, повышение эффективности производства, снижение стоимости и сокращение времени выхода конкурентоспособной продукции на рынок с требуемым уровнем качества.
На машиностроительных предприятиях становится все более широко распространенным позаказный способ организации работ, который сопоставим с мелкосерийным и единичным производством. Поэтому особенно актуальной становится проблема оперативного календарного планирования на уровне цеха.
Каждая конкретная производственная среда характеризуется своим набором производственных факторов. Этот набор задает систему ограничений (критериев), которым должно удовлетворять производственное расписание. Многие из них весьма и весьма специфичны, другие -сложноформализуемы. При этом критериальное множество со временем изменяется (решаются старые проблемы, появляются, новые ограничения). Поэтому на первый план выходит задача разработки оптимизационных алгоритмов, способных учитывать множество производственных факторов одновременно, эффективно решающих задачи календарного планирования, и отвечающие требованию оперативности.
На Российском рынке уже более 10 лет одно из первых мест занимает интегрированная системы технологической подготовки производства, оперативного календарного планирования и диспетчерского контроля «ФОБОС». С 1985 года ее развитие происходило с привлечением заводских специалистов, что позволило учитывать накопленный опыт в области отечественного машиностроения. В настоящее время система успешно внедрена на ряде отечественных и зарубежных (Германия, Китай) предприятий.
Данная работа посвящена проблеме многокритериальной оптимизации производственных расписаний, и выполнена с целью расширить функциональные возможности расчетного модуля оперативного внутрицехового календарного планирования системы «ФОБОС».
Постановка проблемы
Каждая конкретная производственная среда характеризуется своим набором производственных факторов. Необходимо разработать алгоритм, эффективно решающий задачу оперативного календарного планирования -составление технологического расписания для конкретного производственного участка (цеха).
При этом необходимо учитывать систему ограничений, налагаемую как производственными факторами среды («узкие места» производства), так и условиями выполнения конкретного производственного заказа. Особенно эти ограничения актуальны для мелкосерийных и единичных производств, где нет и не может быть уже отлаженного календарного плана выпуска продукции.
Поскольку размерности реальных производственных задач достаточно велики (десятки-сотни станков, тысячи единиц деталей, десятки тысяч операций их обработки), применение точных математических методов для получения оптимального расписания становится практически невозможным.
Задача нахождения оптимального расписания является NP-трудной. Т.е. для нее не найдено эффективных алгоритмов с полиномиальной сложностью (степенная зависимость вычислительных затрат от размерности задачи). Отыскать наилучшее решение удается лишь для частных случаев.
Выходом из создавшейся ситуации является применение альтернативных (приближенных) методов оптимизации. Наиболее распространенный в системах оперативного управления производством -эвристические алгоритмы. На необходимость их применения с целью соблюдения оперативности расчета также указывает ряд авторов [7], [28], [38].
Эвристики - правила, обобщающие опыт человека-эксперта в различных проблемных ситуациях. Простота формализации каждого правила и обоснованный выбор их активного набора позволяет получать удовлетворительный результат за приемлемое время. Т.е. изначально NP-трудная задача сводится к Р-разрешимой. Расписание, рассчитанное таким образом, является уже не оптимальным, а допустимым. Оно учитывает основные ограничения производственной среды, и может быть непосредственно выполнено в реальных производственных условиях [34].
Основной задачей становится автоматизация процесса расчета расписаний, учитывающего наибольшее количество выявленных производственных ограничений. Для ее решения потребуется пересмотреть традиционный подход к решению задач календарного планирования и доработать имитационную модель производственной среды.
Применительно к производственным расписаниям, данный метод носит скорее оценочный характер, позволяя, наряду с параметром общей длительности выполнения производственного заказа, сравнивать между собой различные варианты компоновки элементов расписания.
Его суть заключается в определении суммарного квадратичного отклонения полученного решения от абсолютно идеального. Критерием качества является сумма квадратов отклонений по двум показателям: времени ожидания обработки деталью и величине вынужденного простоя оборудования. Предполагается, что оба показателя равнозначны по своей негативности, но возможен вариант наличия весовых коэффициентов при подсчете.
К сожалению, применимость данного метода в теории расписаний существенно ограничена по сравнению с его более простым математическим аналогом для определения коэффициентов в функциях общего вида. Так, при решении оптимизационных уравнений размерность задачи часто становится чрезмерной из-за громоздкости формализации основных ограничений в производственных расписаниях: 1) задание жестких последовательностей следования операций обработки для каждой детали 2) необходимость предусмотреть отсутствие временных наложений для операций разных деталей в пределах каждой единицы оборудования 3) наличие групп взаимозаменяемого оборудования, что обеспечивает отдельным операциям дополнительную мобильность Главный недостаток метода - невозможность учитывать качественную составляющую отдельных элементов расписания, т.к. состав самих операций не подвергается дальнейшей детализации.
Тем не менее, метод наименьших квадратов может быть с успехом применен при составлении технологических расписаний в производственных средах, где доминируют типовые операции без специфических требований. В этом случае стратегия построения решения заключается в последовательном выборе из множества возможных операций той, которая обеспечивает наименьший прирост штрафной функции.
В данной работе решено использовать отдельные элементы метода в комбинации со средствами, позволяющими учитывать технологическую специфику производственной среды. Так условие минимального отклонения результата от абсолютного реализовано в виде двух независимых эвристик (№ 9 и № 14 - см. параграф 2.7).
Метод блочной оптимизации Суть данного подхода заключается в разделении одной большой задачи на ряд более мелких, размерность которых допускает поиск оптимального решения внутри каждого блока. Окончательный ответ формируется путем согласования полученных блоков между собой. Таким образом, задача оптимизации решается на двух уровнях иерархии: 1) оптимизация каждого блока в отдельности 2) оптимизация взаимного расположения блоков Данный метод удобен тем, что достигается снижение вычислительных затрат на поиск решения за счет снижения размерности рассматриваемых подзадач. Обычно он применяется совместно с другими математическими методами, отвечающими за оптимизацию отдельных фрагментов.
Дополнительного внимания заслуживает стратегия разбиения большой производственной задачи на более мелкие подзадачи. Однозначного ответа здесь не существует. Решающую роль играет специфика конкретной производственной среды и номенклатура изделий (однотипные детали, близкие технологические операции, потребность в специфических материальных ресурсах, т.д.).
Проблемы многокритериальной оптимизации
Процесс нахождения экстремумов целевого функционала в задачах с несколькими критериями и ограничениями принципиально отличается от своего более простого аналога. Он характеризуется следующими особенностями (см. рис. 7): 1) Высокая вычислит, сложность алгоритма решения (NP-трудная задача) 2) Практически полное отсутствие необходимого математического аппарата (формальному решению поддаются лишь частные случаи) 3) ОДЗ целевого функционала сильно фрагментирована или распределена 4) Вид целевого функционала сложен для аналитического решения Рис. 7. Поиск экстремума целевого функционала специального вида в задаче со сплошной ОДЗ (слева) и сильно фрагментированной (справа)
Все это делает невозможным применение строгих математических методов, К тому же, размерность реальных практических задач превышает технические возможности современных вычислительных средств, или же искомое решение получается за неприемлемое время (что нарушает требование оперативности).
Вопрос многокритериальной оптимизации уже много раз поднимался в прессе и литературе, причем не только в производственной, но и в научно-практической, экономической сферах [9], [26]. Делались многочисленные попытки реализовать теоретические изыскания на практике (с разной степенью успешности), но все они, в большинстве своем, "разбивались" о необходимость формализации задачи. В данной работе используется подход, не требующий проведение оптимизации в явном виде.
В теории расписаний различают два термина: оптимальное расписание и допустимое расписание [34]. Первый термин связан с нахождением решения, удовлетворяющего всем выдвинутым условиям, и обеспечивающего глобальный экстремум целевого функционала. Данные задачи относят к классу NP-трудных. Сложность алгоритма оценивается экспоненциальной функцией от размерности. Т.е. при увеличении количества элементов на единицу, общее время решения возрастает в разы!
С допустимым расписанием ситуация обстоит иначе. Оно также удовлетворяет всем выдвинутым условиям, но не обеспечивает экстремум целевого функционала. Однако, вычислительные затраты на его поиск значительно меньше. Такие задачи относят к классу Р-разрешимых. Сложность их алгоритма оценивается полиномиальной функцией от размерности. Т.е. при увеличении количества элементов в несколько раз, общее время их решения возрастает в квадрате, кубе, 4-й степени...
Диспетчеру, следящему за выполнением производственного плана, крайне важно оперативно реагировать на любое отклонение от расчетного графика. Поскольку сбор информации о состоянии станочного парка и оповещения о возникающих сбоях выполняются автоматически подсистемой контроля, от оператора требуется как можно быстрее компенсировать отклонение от первоначального плана. В этом ему помогает подсистема оперативного планирования.
Наиболее критическим фактором в этом случае является время, затрачиваемое на поиск решения проблемы [36]. Все исходные данные о выполняемом заказе уже находятся в системе, но их полная обработка и перерасчет расписания потребуют слишком больших вычислительных (временных) затрат. Кроме того, сбои могут возникать в произвольные моменты времени, много раз за одну смену.
Таким образом, использование алгоритмов, дающих приемлемое решение за приемлемое время (допустимое расписание - Р-разрешимая задача), является обоснованным с точки зрения оперативности принятия решений и, в конечном итоге, с позиции экономической эффективности планирования производства.
Другой момент - каким образом связать между собой набор критериев, указанных оператором? Первоначально планировалось выявлять критические пути - «узкие места» производства по одному из критериев и, как-то фиксируя их, запустить процедуру оптимизации по следующему критерию. После последовательных проходов по всему перечню, было бы получено расписание, учитывающее особенности всех ограничений.
Но такой подход был отвергнут в силу большой громоздкости (поиск критических путей) и больших вычислительных затрат (многопроходный метод - по всему списку критериев). Кроме того, он потребовал бы введения нового понятия - «фактор подвижности», чтобы отличать фиксированные операции от свободных. К тому же он не дает полной гарантии строгого соответствия всем налагаемым ограничениям (очередной критерий может свести на нет все положительные результаты, достигнутые предыдущими).
Было выдвинуто требование - все используемые оптимизационные критерии и ограничения производственной среды должны учитываться одновременно, прямо в процессе составления расписания. В этом случае будет соблюдаться требование оперативности (однопроходный метод) и гарантируется получение расписания, учитывающего все ограничения. Для выполнения данного требования была построена расширенная имитационная модель производственной среды, содержащая в себе дополнительно необходимую информацию для алгоритма расчета расписания. За счет этого сам алгоритм получился достаточно простым и быстрым. Алгоритм расчета и расширенная имитационная модель подробно описаны в параграфах 2.6 и 2.8 соответственно.
Выбор средств реализации - среда Delphi
Delphi 6 - высокоэффективный инструмент визуализированной разработки приложений, но в то же время - весьма сложная объектно-ориентированная среда программирования. Используемый в ней язык Object Pascal является фундаментом для создания приложений любой сложности, предназначенных для работы как на отдельных компьютерах, так и в различных компьютерных сетях. Данный язык наследует большинство возможностей и правил своего предшественника (Borland Turbo Pascal), по-прежнему сочетая в себе простоту грамматики и строгость формализации синтаксиса [8], [13], [22].
Большинство приложений, создаваемых с помощью среды Delphi, направлены на решение прикладных задач, связанных с производством и бизнесом. Это значит, что организация взаимодействия с базами данных, имитационное и математическое моделирование, поиск и формирование оптимальных управленческих стратегий, а также создание отчетов и документирование будут наиболее часто встречающимися типовыми программируемыми операциями [37]. Для их реализации среда Delphi предоставляет весьма широкий спектр библиотек готовых компонентов, а также средств для разработки индивидуальных решений.
В данной работе в качестве средства реализации была выбрана среда Delphi 6 главным образом с целью обеспечения будущей совместимости с интегрированной системой «ФОБОС» на программном уровне. На текущий момент данная разработка выполнена и сдана в опытно-промышленную эксплуатацию, как дополнение к системе. В дальнейшем же планируется провести полную интеграцию всех программных модулей и интерфейсов.
Основными чертами полученного программного комплекса являются невысокие требования к аппаратному обеспечению (система «ФОБОС» способна эффективно функционировать даже на персональном компьютере Intel Pentium 100 MHz с 16 Мб ОЗУ под управлением ОС WINDOWS 98), а также легкость настройки и модификации для конкретных предприятий.
Как было сказано ранее, данный программный продукт разрабатывался в виде надстройки над интегрированной системой «ФОБОС», что предполагает их совместное использование в опытно-промышленной эксплуатации.
Подсистема интегрированного внутрицехового календарного планирования реализована как самостоятельный программный комплекс, способный считывать требуемую информацию о производственном расписании непосредственно из БД системы «ФОБОС», но имеющий собственный интерфейс и независимые алгоритмы обработки данных.
На рис. 23 изображено основное рабочее окно программы. В нем приводится общая информация о текущем расписании. Все необходимые данные заносятся черед диалоги, вызываемые при выборе соответствующего пункта в главном меню. По мере выполнений требуемой последовательности действий становится доступным все новая информация.
Так первоначально данные полностью отсутствуют - сначала необходимо загрузить файл с расписанием. После этого подсчитывается и выводится размер задачи: количество станков, деталей, операций. Теперь можно изменить параметры отдельных элементов (станков, деталей, операций), задать требуемые опции расчета, а также выбрать значимые критерии из списка, и т.д.
Пункт меню "Расписание Предв. оценка" позволяет получить приблизительные сведения о конечном расписании: время его расчета, временные рамки, МАХ возможный коэффициент загрузки оборудования (как приоритетного, так и обычного). На данном этапе пользователь имеет возможность скорректировать любые параметры, если приведенные оценки его почему-либо не устраивают.
Завершающий шаг - запуск процедуры расчета расписания (пункт меню "Расписание Начать расчет"). Процесс расчета занимает некоторое время, зависящее от размера задачи и указанных параметров. Индикатор внизу окна показывает прогресс, а прошедшее и оценка оставшегося времени выводится в главном окне программы.
После завершении расчета окончательные результаты (полученные временные характеристики и показатели загрузки оборудования) также выводятся на форму, а рассчитанный вариант расписания может быть сохранен в виде отдельного файла локальной БД. При необходимости, расчет может быть повторен с другими исходными данными.
Важную роль в процессе формирования конечного расписания играют параметры его расчета. Необходимо обеспечить не только полноту информации, но и удобство, простоту ввода для пользователя программного продукта. Диспетчеру в первую очередь требуется оперативно отреагировать на возникшее отклонение от плана. Т.е. быстро задать новую информацию, и запустить перерасчет с текущего момента.
Для этих целей все необходимые функции сосредоточены в главном меню, сгруппированные по смысловой нагрузке. Кроме того, поскольку фактор времени может быть особенно критичным, предусмотрена возможность быстрого сохранения и загрузки настроек в виде файлов профиля (пункт меню "Профили"). В этом случае диспетчеру требуется лишь загрузить соответствующее расписание и профиль к нему, внести единичное изменение в данные (информация о произошедшем отклонении от плана), и запустить расчет с текущего момента.
К подобным нештатным ситуациям можно отнести следующие события: поломка оборудования, неявка значимого исполнителя, непредвиденная задержка выполнения какой-либо технологической операции, внешний фактор (срыв сроков поставок спец. оснастки, внеплановое ограничение энергоснабжения).
Перераспределять работы по станкам - если при расчете расписания для каждой операции указан не номер станка, а только номер группы взаимозаменяемого оборудования, то результат, как правило, оказывается лучше, т.к. присутствует большее количество альтернатив при выборе. Данная опция, в случае перерасчета расписания, разрешает переназначать детали на другие единицы технологического оборудования согласно текущему графику загрузки.
Разрешить минимальные простои — возможно, добровольно согласившись на единичные простои оборудования, мы начнем получать лучшие по своим характеристикам расписания за счет расширения конкурирующего множества: под рассмотрение попадут не только те операции, которые могут быть реализованы в текущий момент, но и те, которые будут готовы в следующую единицу времени. Таким образом, оборудование будет минимальное время ожидать наиболее подходящую деталь, не "отвлекаясь" на менее существенные.
Оценка сложности алгоритма
Как уже было отмечено в параграфе 1.1, все задачи (по временным затратам на поиск решения) подразделяются на NP-трудные и Р-разрешимые. Поскольку в разработанном ПК использовались эвристические алгоритмы, любая производственная задача автоматически считается Р-разрешимой. Для таких задач общее время выполнения вычислений определяется по формуле 2. Это утверждение подтверждено расчетом (см. таблицу 15) и наглядно показано на графике (см. рис. 47 — по оси ординат отложен натуральный логарифм от времени поиска). T = K-Nn (2) где Т - длительность выполнения расчета, К - произвольная константа, N- размерность задачи, п - степень полинома. Первоначально тесты проводились для относительно небольшой партии запуска (20 станков, 150 деталей, 900 операций). Общая длительность выполнения производственного заказа составляла около суток (3 рабочие смены). Затем, после расчета усредненных значений, заносимых в результирующую таблицу, происходил переход к более крупной партии деталей. Для этого номенклатура изделий каждый раз увеличивалась на размер базовой партии. Таким образом, размерность задачи возрастала точно в 2, 3,4, 5,... раз.
Для определения степени полиномиальной сложности алгоритма (число п) требуется лишь прологарифмировать соотношение длительности решения текущей и базовой задач по соответствующему основанию. Как видно из таблицы, это число всегда находится в отрезке (2;3). По усредненным данным было принято значение п = 2,5. Полученный результат полностью удовлетворяет требованию оперативности (при увеличении размерности задачи вдвое, временные затраты возрастают в 5-6 раз).
Максимальная размерность тестовой задачи, решенной с помощью данного ПК, составила 100 станков, 1000 деталей, 6000 операций. Общая длительность выполнения расчета составила 3,5 часа, а горизонт планирования равнялся 2 месяцам. В современной практике мелкосерийного производства с позаказным способом организации работ, задачи подобной размерности встречаются довольно редко. Поэтому можно считать, что разработанный ПК полностью решил все поставленные перед ним задачи. Для определения экономических показателей (себестоимости производства) использовался готовый расчетный модуль, входящий в состав системы «ФОБОС». Оценка экономического эффекта производилась только для задачи, взятой из архива системы (с реальными исходными данными см. таблицу 16).
В целом, проводя сопоставления с результатами, полученными с помощью системы «ФОБОС», отмечается некоторое снижение среднего коэффициента загрузки оборудования (с 0,8 до 0,77). Это объясняется более жесткими условиями, предъявляемыми к расписаниям в разработанной подсистеме. Тем не менее, за счет одновременного учета множества факторов, достигается значительная экономия материальных и трудовых ресурсов. Себестоимость производства уменьшается в среднем на 5 - 15 %.
В данной работе была предпринята попытка создания подсистемы интегрированного внутрицехового календарного планирования, эффективно решающей практическую задачу составления производственных расписаний с учетом сразу целого ряда критериев и ограничений, налагаемых технологическими особенностями производственной среды.
В ходе работы над темой, автором были получены следующие научно-практические результаты: 1) выполнена классификация производственных факторов по признаку качественной неоднородности характеристических показателей; 2) получена имитационная модель производственной среды, с высокой степенью адекватности отражающая ее специфические технологические особенности; 3) разработана методика, упрощающая многокритериальную оптимизацию расписаний, на основе таблиц принятия решений (ТПР); 4) разработан эвристический алгоритм расчета расписания, отвечающий требованию оперативности; 5) получена программная реализация подсистемы, выполняющая расчет расписания на уровне производственного участка (цеха); 6) обеспечена открытость разработанной подсистемы для добавления новых критериев и ограничений; 7) обеспечена интеграция подсистемы с системой оперативного календарного планирования «ФОБОС». Разработанная подсистема предназначена, в первую очередь, для сотрудников планово-диспетчерской службы предприятия. Областью ее применения является составление календарного графика производства конкретной партии запуска на всем плановом периоде (на этапе предварительного планирования), а также оперативная коррекция отклонений от уже реализуемого плана (при осуществлении диспетчерского контроля производства).
Проведенная оценка эффективности функционирования подсистемы, показывает достаточно высокую результативность как с точки зрения экономических показателей, так и с позиции временных затрат на поиск решения.
Усредненная оценка вычислительной сложности алгоритма составления расписаний указывает на степень п = 2,5 (не экспоненциальный, а полиномиальный рост временных затрат при увеличении размерности задачи).
Экономия материальных и трудовых ресурсов, достигаемая за счет составления производственных расписаний, косвенно оптимизированных сразу по целому ряду критериев, составляет 5-15% (зависит от значимости производственных факторов и количества заданных ограничений). Кроме того, достигается снижение объема незавершенного производства до 10%.
Работа выполнена в полном объеме, указанном в техническом задании, и удовлетворяет основным требованиям, предъявляемым к расчетным модулям АСУ. Программная часть реализована таким образом, что обеспечивает легкость модификации при изменениях в составе сопутствующей системы, а также при появлении новых, неучтенных ранее производственных факторов.
