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

На правахрукописи

Тарасов Алексей Геннадьевич

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

Специальность 05.13.06 - «Автоматизация и управление технологическими процессами и производствами (технические системы)»

Автореферат на соискание ученой степени кандидата технических наук

Москва 2004

Работа выполнена в ГОУ Московский государственный технологический университет «Станкин»

Научный руководитель:

доктор технических наук, профессор Фролов Е.Б.

Официальные оппоненты: доктор технических наук, профессор

Саксонов £ А.

кандидат технических наук, Крюков В.В.

Ведущее предприятие:

Институт Машиноведения им. Благонравова Российской Академии Наук

Защита состоится " 25 " ноября 2004 года в 12 часов на заседании Диссертационного Совета К 212.142.01 при Московском Государственном Технологическом Университете "Станкин" по адресу: 127055, ГПС, Москва, К-55, Вадковский пер., д.За.

С диссертацией можно ознакомиться в библиотеке университета за один месяц до защиты.

Автореферат разослан « 22 » октября 2004 г.

Ученый секретарь Диссертационного совета

К 212.142.01, к.т.н. Тарарин И.М.

2 3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

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

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

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

Вопросам оперативного планирования и управления в интегрированных машиностроительных производствах посвящены работы многих отечественных ученых: Белянина П.Н., Блехермана М.Х., Васильева В.Н., Горнева В.Ф., Емельянова В.В., Овсянникова М.В., Колесова И.М., Лещинского Л.Ю., Макарова И.М., Митрофанова В.Г., Первозванского А.А., Петрова В.А., Соломенцева Ю.М., Сосонкина В.Л., Султан-Заде Н.М., Третьякова Э.А., Фролова Е.Б., Чудакова А.Д. и др. Основным результатом работ этих ученых явилось с методологическт»|шрд"^ е м

БИБЛИОТЕКА |

гдаяч з

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

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

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

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

Для достижения поставленной цели в работе решены следующие научные и практические задачи:

^ разработана методика, упрощающая многокритериальную оптимизацию

расписаний, на основе продукционных таблиц; ^ разработан эвристический алгоритм расчета расписания, отвечающий

требованию оперативности; ^ построена имитационная модель с высокой степенью адекватности производственной среде;

получена программная реализация подсистемы, выполняющая расчет расписания на уровне производственного участка

обеспечена открытость разработанной подсистемы для добавления новых критериев и ограничений;

обеспечена интеграция подсистемы с системой оперативного календарного планирования «ФОБОС».

Научная новизна работы заключается в следующем:

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

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

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

Методы исследования. При выполнении теоретических исследований и экспериментальных работ использовались:

• элементы теории множеств;

• теория систем массового обслуживания (СМО);

• графовая трактовка производственных расписаний;

• имитационное моделирование производственной среды;

• приемы эвристического программирования;

• концепции экспертных систем (таблицы принятия решений).

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

Эксплуатация разработанной подсистемы позволяет уменьшить объем незавершенного производства, повысить эффективность работы диспетчерского отдела предприятия и снизить затраты на производство на 5 -15 % за счет комплексного учета множества производственных факторов и ограничений. '

Аппробация работы. Данная подсистема интегрированного внутрицехового календар-ного планирования внедрена в составе системы «ФОБОС» на следующих предприятиях:

1. ОМЧ СПб Метро (г. Санкт-Петербург);

2. АМО «ЗИЛ» (г. Москва);

3. МПО «Машиностроение» (г. Реутов).

Теоретическая и практическая реализация работы докладывалась на следующих конференциях:

1. УП-я научная конференция МГТУ «СТАНКИН» и «Учебно-Научного Центра Математического Моделирования МГТУ "Станкин" - ИММ РАН», 28-29 апреля 2004 г., Москва.

2. Международная научно-практическая конференция «Современное машиностроение: управление эффективным развитием», 27-28 апреля 2004 г., Москва.

Публикации. По теме диссертации опубликовано 3 работы.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы (43 наименований). Работа изложена на 112 страницах машинописного текста, содержит 47 рисунков, 16 таблиц и приложение.

СОДЕРЖАНИЕ РАБОТЫ

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

Задача нахождения оптимального расписания является КР-трудной. Т.е. для нее не найдено эффективных алгоритмов с полиномиальной сложностью (степенная зависимость вычислительных затрат от размерности задачи). Отыскать наилучшее решение удается лишь для отдельных частных случаев.

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

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

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

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

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

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

Размерность современных производственных задач и количество налагаемых на расписание ограничений уже не допускают ручных методов расчета. Последние десятилетия безоговорочно доминирует концепция CIM -Computer Integrated Manufacture. Без интегрированных систем поддержки производства невозможно как его эффективное планирование, так и оперативное управление.

На сегодняшний день существует ряд программных продуктов, позволяющих достаточно эффективно решать задачи внутрицехового управления (ФОБОС, САПФОР, BAAN Synchronization и др.), но, вместе с тем, остается открытой проблема адекватности постановки задачи реальным условиям производственной среды.

Традиционно, в подобных системах предлагается составление производственного расписания только по одному выбранному критерию (см. рис. 1).

Рис. 1. Система «ФОБОС»: диалог выбора оптимизирующего критерия

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

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

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

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

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

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

1. высокая вычислительная сложность алгоритма решения (КР-трудная задача);

2. практически полное отсутствие необходимого математического аппарата (формальному решению поддаются лишь частные случаи);

3. ОДЗ целевого функционала сильно фрагментирована или распределена;

4. вид целевого функционала слишком сложен для аналитического решения.

Все это делает невозможным применение строгих математических методов. К тому же, размерность реальных практических задач превышает технические возможности современных вычислительных средств, или же искомое решение получается за неприемлемое время (что нарушает требование оперативности).

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

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

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

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

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

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

Основным показателем оптимальности производственного расписания (или предпочтения одного варианта перед другим) является стоимость выполнения данного производственного заказа.

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

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

L = => МАХ, Q, => MIN (1)

где!, - функционал, характеризующий величину прибыли от выполнения

производственного заказа, S — доход от выполнения заказа (абсолютный МАХ функционала L -производство без затрат), 10

£?/ - функционал, характеризующий затраты по определенной статье расходов:

- затраты на материал;

(?2 - затраты на оплату труда работников (с учетом простоев и сверхурочных, которые необходимо минимизировать);

0$ - затраты на перерасход фонда заработной платы (из-за несоответствия разрядов работников и работ);

- затраты на амортизацию основных фондов (расходование общего фонда времени оборудования с учетом простоев);

(?5 - затраты на электроэнергию (с учетом штрафов за перерасход лимита);

- затраты на незавершенное производство (хранение межоперационных заделов);

- затраты на компенсацию задержек заказчику (штрафы, если требуемая деталь не будет изготовлена в срок);

08 - затраты на излишнюю переналадку оборудования (при частой смене номенклатуры обрабатываемой партии деталей);

09 - затраты на внутрицеховую транспортировку заготовок (от одного станка к другому);

- затраты на аренду производственных площадей;

- количество учтенных производственных факторов в математической модели производственной среды.

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

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

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

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

Проведенные исследования реальных производственных ситуаций, а также анализ возможных производственных факторов и ограничений позволили выделить следующий набор «узких мест» мелкосерийных производств:

• высокие требования к срочности конкретных деталей;

• высокие требования к точности/качеству отдельных деталей;

• скорейшая загрузка станочного парка (без заделов);

• МИН перерасхода лимита электроэнергии;

• МИН незавершенного производства;

• МИН «пролеживания» деталей;

• МИН простоев / МАХ коэффициент загрузки оборудования;

• МИН переналадок оборудования;

• МИН несоответствие разрядности работы и исполнителя;

• МИН простоев дорогостоящего оборудования;

• МИН мощность внутрицехового грузопотока;

• МИН количество задействованных станков;

• фиксированное количество мастеров на станочную группу;

• связи между отдельными стадиями обработки деталей;

• оптимальное распределении деталеопераций между станками.

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

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

Рис 2 Диаграмма Ганта • календарный график загрузки оборудования

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

Одним из основных ограничений является рабочее время каждой единицы оборудования. Поскольку каждый станок может иметь индивидуальный график работы (1,2,3-сменный режим, плавающее расписание внутри смены), то представляется целесообразным каким-то образом «занять» нерабочие периоды. Это позволит наиболее просто исключить возможность попадания любой операции в «запретную зону».

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

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

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

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

На рис. 3 наглядно показан пример возможного расположения рабочих и нерабочих интервалов времени. В данном случае, единицей времени принята одна смена. Из рисунка видно, что первый станок работает в 2-сменном режиме, третий - в 1-сменном, а в выходные дни для персонала станка № 5 допускается работа сверхурочно.

Рис. 3. Нерабочие интервалы заняты «пустымиработами»

Главной особенностью использования концепции «временная матрица» является то, что любое получаемое с ее учетом расписание является допустимым (т.е. реализуемым в конкретной производственной среде), а алгоритм его составления практически полностью освобождается для решения основной производственной задачи - оптимизации по указанному набору критериев.

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

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

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

N8 1 ■ ■ ■

№2 ■рши

№3 гшИп1

Рис. 4. Начальное состояние производственного плана (содержит в себе все потенциально возможные варианты компоновкирасп исания)

На рис. 5 показано состояние множества элементов расписания после выполнения нескольких шагов. Каждый шаг сопровождается перемещением временного маркера на одну единицу времени вправо. При этом из всех операций, претендующих на выполнение на каждой единице оборудования в каждый момент времени выбирается только одна - лидирующая, а остальные -сдвигаются вместе со своими «потомками» на величину длительности лидирующей.

Рис. 5. Маркер сместился—слева от негообразоваласьупорядоченная область

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

№ 1 ■Й1 > | ■

№ 1

№3 □■■¡ЕПИИ ■п

Рис. 6. Область высокой неопределенности (справа) постепенно сокращается

Когда временной маркер дойдет до предельного значения (все работы окажутся позади - см. рис. 7), расчет прекращается, и полученное расписание записывается в базу данных.

№1 ■Н I ■ ■

№2

№3 ■О 1

Рис. 7. Получен конечныйрезультат — допустимоерасписание

За один проход по неупорядоченному множеству маркер избавляется от всех перекрываний конкурирующих операций путем разрешения конфликтов по каждой единице оборудования в каждый момент времени.

Преимущества данного метода: оперативность расчета и надежность конечного результата. Алгоритм составления расписания достаточно просто реализуем, и затрачивает незначительное время на очередной перерасчет (один проход маркера).

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

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

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

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

Каждый шаг маркера сопровождается разрешением конфликта по каждой единице оборудования - из набора конкурирующих операций необходимо выбрать наиболее подходящую для всех указанных критериев оптимизации расписания (см. рис. 8).

Рис. 8. Конфликтная ситуация

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

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

Ниже приводится перечень эвристик (правил выбора), выявленных при анализе рассмотренного ранее критериального множества для данной расширенной имитационной модели производственной среды:

• при выборе очередной единицы оборудования отдавать предпочтение, в первую очередь, помеченным (приоритетным);

• начинать оптимизацию с МАХ загруженного станка;

• выбрать операцию наиболее долгообрабатываемой детали;

• отклонить операцию, конфликтующую с зафиксированной (уже находящейся в обработке);

• выбрать операцию с более поздней стадией обработки детали;

• выбрать МАХ долгую операцию в начале рабочего цикла;

• выбрать операцию с МАХ временем ожидания своей очереди;

• выбрать операцию с МИН ожиданием ее следующей стадии;

• выбрать операцию, МАХ заполняющую остаток интервала;

• отложить деталь при критической задержке любой ее стадии;

• в «особой зоне» сначала выбирать из помеченных операций;

• выбрать операцию детали с помеченными операциями;

• выбрать операцию с МАХ значением приоритета;

• выбрать операцию детали, обработка которой может быть завершена до конца текущего рабочего периода времени;

• выбрать операцию, наиболее соответствующую плановым затратам определенного вида производственных ресурсов.

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

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

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

• содержать обобщенные характеристики по группам критериев;

• сочетать простоту представления и обработки данных;

• обеспечивать открытость модели для изменения системы ограничений;

• адекватно отражать реальные производственные факторы и ограничения;

Основными объектами имитационной модели являются: станок, деталь, операция, работник; а так же разного рода ограничения: рабочие интервалы и особые временные зоны. Связи между классами объектов показаны на рис. 9.

Рис. 9. Связи между классами объектов имитационной модели

Из рисунка видно, что расширенная модель охватывает такие классы объектов, как деталь, составляющие ее операции, выполняющие их станки, рабочие интервалы для каждой единицы оборудования. Штат сотрудников учитывается лишь косвенно, через задание «особых зон» (в них приоритет отдается соответственно помеченным операциям).

В третьей главе описываются особенности реализации подсистемы интегрированного внутрицехового календарного планирования.

Поскольку в процессе дальнейшей опытно-промышленной эксплуатации планируется интеграция подсистемы с системой «ФОБОС» на программном уровне, в качестве средств реализации была выбрана среда DELPHI 6.

Система «ФОБОС» находится в непрерывном развитии, а данная разработка носит экспериментальный характер, поэтому она реализована, как надстройка над системой, с интеграцией на уровне БД (рис. 10).

Рис. 10. Интеграция с системой «ФОБОС» науровне БД

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

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

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

Процесс совместной эксплуатации разработанной подсистемы интегрированного внутрицехового календарного планирования и системы «ФОБОС» выглядит следующим образом:

1. ввод информации в систему «ФОБОС» (данные о предприятии, задействованных отделах и подразделениях, производственных мощностях, ограничениях производственной среды, заказах, материалах, снабжении);

2. настройка разработанной подсистемы (установление связей с необходимыми таблицами общей БД, считывание имеющихся данных);

3. ввод дополнительной информации в подсистему (заполнение локальной БД недостающей информацией о конкретных особенностях производственной среды при выполнении данного заказа);

4. выполнение расчета расписания с учетом выбранных условий;

5. после получения приемлемого результата составленное расписание записывается в общую БД (при этом часть информации, не используемая системой «ФОБОС», остается в локальной БД);

6. полученное от подсистемы расписание используется системой «ФОБОС» на последующих этапах планирования данного производства.

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

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

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

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

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

Как уже было отмечено ранее, все задачи (по временным затратам на ш-иск их решения) подразделяются на ОТ--трудные и Р-разрешимые. Поскалыс' в разработанной подсистеме использовались эвристические алгоритмы, любая производственная задача автоматически считается Р-разрешимой. ДЛУ таких задач общее время выполнения вычислений определяется по формуле 2.

где Т - длительность выполнениярасчета, К -произвольная константа, N -размерность задачи, п - степень полинома.

Данное утверждение также подтверждается расчетом (см. таблицу 1). Таблица 1. Усредненная оценкавременныхзатрат

Размерность задачи Средняя Коэффициент Средняя степень

(кол-во станков, продолжительность увеличения полинома

детален,операций) поиска решения размерности (число л)

20; 150; 900 15 мин 1 -

20;300; 1800 7.4 мин 2 2,3

20;450;2700 23.4 мин 3 2,5

20;600;3600 41.7 мин 4 2,6

20;750;4500 98.5 мин 5 2,6

Первоначально тесты проводились для относительно небольшой партии запуска (20 станков, 150 деталей, 900 деталеопераций). Обшая длительность выполнения производственного заказа составляла около суток (3 рабочие смены). Затем, после расчета усредненных значений, заносимых в результирующую таблицу, происходил переход к более крупной партии деталей. Для этого номенклатура изделий каждый раз увеличивалась на размер базовой партии. Таким образом, размерность задачи возрастала точно в 2,3,4,5,... раз.

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

Максимальная размерность тестовой задачи, решенной с помощью данной подсистемы, составила 100 станков, 1000 деталей, 6000 операций. Общая длительность выполнения расчета составила 3.5 часа, а горизонт планирования равнялся 2 месяцам.

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

Для определения экономических показателей (себестоимости производства) использовался готовый расчетный модуль, входящий в состав системы "ФОБОС". Оценка экономического эффекта производилась только для задачи, взятой из архива системы (с реальными исходными данными - см. таблицу 2).

Таблица 2. Усредненная оценка экономической эффективности

Размерность задачи (кол-во станков, деталей,операций) Усредненный коэффициент загрузки оборудования (до и после работы подсистемы) Изменение экономических показателей составленного расписания (себестоимость)

20; 150; 900 0.82/0.78 -3%

20; 300; 1800 0.85/0.80 -5%

20 ; 450; 2700 0.81/0.76 -6%

20 ; 600 ; 3600 0.79/0.75 -6%

20;750;4500 0.77/0.74 -7%

В целом, проводя сопоставления с результатами, полученными с помощью системы «ФОБОС», отмечается некоторое снижение среднего коэффициента загрузки оборудования (с 0.8 до 0.77). Это объясняется более жесткими условиями, предъявляемыми к расписаниям в разработанной подсистеме. Тем не менее, за счет одновременного учета множества факторов, достигается значительная экономия материальных и трудовых ресурсов. Себестоимость производства уменьшается в среднем на 5 -15 %.

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

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

2) Создана расширенная имитационная модель производственной среды, обеспечивающая открытость подсистемы для добавления новых оптимизационных критериев и ограничений.

3) Предложенный алгоритм расчета расписаний удовлетворяет требованиям оперативности планирования производства (небольшие вычислительные затраты) и высокой адекватности реальной среде.

4) Программный комплекс реализован как дополнение к системе «ФОБОС» с интеграцией на уровне БД.

5) Внедрение подсистемы в опытно-промышленную эксплуатацию позволило повысить эффективность диспетчерского контроля, снизить объем незавершенного производства на 10%, добиться экономии материальных и трудовых ресурсов (себестоимости производства) до 15%.

Основные положения диссертации представлены в следующих публикациях:

1. Тарасов А.Г. «Многокритериальная оптимизация в задачах календарного планирования» // Материалы УП-й научной конференции МГТУ «СТАН-КИН» и «Учебно-Научного Центра Математического Моделирования МГТУ "Станкин" -ИММ РАН», 28-29 апреля 2004 г., Москва, стр. 125-127.

2. Тарасов А.Г. «Экономические аспекты и подходы к оперативному управлению производством» // Материалы международной научно-практической конференции «Современное машиностроение: управление эффективным развитием», Москва, 27-28 апреля 2004 г., стр. 200-201.

3. Тарасов А.Г., Фролов Е.Б. «Составление производственных расписаний в задачах календарного планирования» // Москва, «Научтехлитиздат», журнал "Промышленные АСУ и контроллеры" № 10,2004, стр. 45-47.

Автореферат диссертации на соискание ученой степени кандидата технических наук

Тарасов Алексей Геннадьевич

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

Лицензия на издательскую деятельность ЛР №01741 от 11.05.2000 Подписано в печать 22.10.2004. Формат 60x90 /16 Уч.изд. л. 1,5. Тираж 50 экз. Заказ № 200

Отпечатано в Издательском Центре МГТУ «СТАНКИН» 103055, Москва, Вадковский пер., д.3а

»234 fin

РНБ Русский фонд

2005-4 23113

Введение.

ГЛАВА 1. Исследование предметной области

1.1. Постановка проблемы.

1.2. Обзор средств и методов решения.

1.3. Обзор существующих систем.

1.4. Анализ традиционного подхода решения задач календарного планирования.

1.4.1. Диаграмма Гантта.

1.4.2. Правила выбора из очереди.

1.4.3. Система приоритетов.

1.4.4. PERT-анализ.

1.5. Формулировка ТЗ.

ГЛАВА 2. Построение имитационной модели

2.1. Проблемы многокритериальной оптимизации.

2.2. Затратный подход к календарному планированию.

2.3. Анализ производственных факторов.

2.4. Классификация оптимизационных критериев.

2.5. Временная матрица для диаграммы Гантта.

2.6. Алгоритм составления расписаний.

2.7. Эвристики (правила разрешения конфликта).

2.8. Расширенная имитационная модель.

ГЛАВА 3. Реализация программного комплекса

3.1. Выбор средств реализации - среда Delphi 6.

3.2. Интерфейс и диалоги.

3.3. Модули и алгоритмы.

3.4. Формат таблиц БД.

3.4.1. Внешнее представление данных.

3.4.2. Внутреннее представление данных.

3.5. Интеграция с системой «ФОБОС».

ГЛАВА 4. Оценка эффективности ПК

4.1. Оценка сложности алгоритма.

4.2. Оценка экономического эффекта от внедрения ПК.

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

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

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

На Российском рынке уже более 10 лет одно из первых мест занимает интегрированная системы технологической подготовки производства, оперативного календарного планирования и диспетчерского контроля «ФОБОС». С 1985 года ее развитие происходило с привлечением заводских специалистов, что позволило учитывать накопленный опыт в области отечественного машиностроения. В настоящее время система успешно внедрена на ряде отечественных и зарубежных (Германия, Китай) предприятий.

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

ЗАКЛЮЧЕНИЕ

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

В ходе работы над темой, автором были получены следующие научно-практические результаты:

1) выполнена классификация производственных факторов по признаку качественной неоднородности характеристических показателей;

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

3) разработана методика, упрощающая многокритериальную оптимизацию расписаний, на основе таблиц принятия решений (ТПР);

4) разработан эвристический алгоритм расчета расписания, отвечающий требованию оперативности;

5) получена программная реализация подсистемы, выполняющая расчет расписания на уровне производственного участка (цеха);

6) обеспечена открытость разработанной подсистемы для добавления новых критериев и ограничений;

7) обеспечена интеграция подсистемы с системой оперативного календарного планирования «ФОБОС».

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

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

Усредненная оценка вычислительной сложности алгоритма составления расписаний указывает на степень п = 2,5 (не экспоненциальный, а полиномиальный рост временных затрат при увеличении размерности задачи).

Экономия материальных и трудовых ресурсов, достигаемая за счет составления производственных расписаний, косвенно оптимизированных сразу по целому ряду критериев, составляет 5-15% (зависит от значимости производственных факторов и количества заданных ограничений). Кроме того, достигается снижение объема незавершенного производства до 10 %.

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

1. Toomey J. W. MRP 1.: Planning for Manufacturing Excellence. - Chapman & Hall, 1996.

2. Wiest J.D., Levy F.K. A management guide to PERT/CPM. Englewood Cliffs, N.J.: Prentice Hall, Co., 1969.

3. Wight O.W. The executive's guide to successful MRP II. Englewood Cliffs, N.J.: Prentice-Hall, 1982.

4. Особенности использования и внедрения ERP систем в России. -www.citforum.ru

5. Функции ERP- и MES-систем. www.mesa.ru

6. Составление скользящих графиков работы. www.mnogosmenka.ru

7. Азимина Е.В. Адаптивные методы календарного планирования серийных машиностроительных производств: автореферат к.э.н. по спец. 08.00.28 организация производства, СПб 1995.

8. Архангельский А .Я. Программирование в Delphi 6, Москва: ЗАО "Издательство БИНОМ", 2002. 1120 с.

9. Березовский Б.А., Борзенко В.И., Кемпнер JI.M. Бинарные отношения в многокритериальной оптимизации, Москва: Наука, 1981.

10. Ю.Вольский В.И. Правила выбора лучших вариантов на ориентированных графах и графах-турнирах // Автоматика и Телемеханика, 1988, № 3, 3-17.

11. Горшков А.Ф. Метод замещений, Москва, 2004.

12. Гэлловэй JI. Операционный менеджмент. СПб: Питер, 2002, 213-214.

13. Каширина Н.В., Маран М.М. Технология программирования в среде Delphi, Москва 1999. 128 с.

14. Когаловский В.М. Происхождение ERP // Computer World Россия. Директору Информационной Службы, 2000а, (Май).

15. Когаловский В.М. Производственное планирование: особенности внедрения западных методов // ComputerWorld Россия. Директору Информационной Службы, 2000с, № 10, (Октябрь), 23-30.

16. Когаловский В.М. Системы планирования производства: отечественные компромиссы развития // ComputerWorld Россия. Директору Информационной Службы, 2000b, № 9, (Сентябрь).

17. Колесов И.М. Основы технологии машиностроения, М.: Высшая школа, 2001.

18. Митрофанов В.Г., Петров В.М. Интегрированная автоматизированная система управления интегрированным компьютеризированным производством // Станки и инструмент, 1992, №6, 2-4.

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

20. Ногин В.Д. Перспективы и направления развития количественной теории относительной важности критериев.

21. Овсянников М.В., П.С.Шильников. Состояние, проблемы и перспективы развития CALS-технологий в России. www.bmstu.ru22.под редакцией В. Озерова Delphi. Советы программистов, СПб:Символ-Плюс, 2002. 912 с.

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

23. Петров В.А. Групповое производство и автоматизированное оперативное управление, Д.: Машиностроение, 1975.

24. Плахотишин A.M. Моделирование производственных возможностей и расписаний, ABF, Москва, 1997.

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

26. Поспелов Д.А. Логико-лингвистические модели в системах управления, Москва: Энергоиздат, 1981.

27. Рубцов С.В. Эвристические особенности систем управления предприятиями // Бизнес: организация, стратегии, системы, 2000, № 7-8 (Июль-Август), 56-58.

28. Саати Т.Л. Математические модели конфликтных ситуаций, Москва: Сов. Радио, 1977 г.

29. Под ред. Соломенцева Ю.М., Митрофанова В.Г. Автоматизированное проектирование и производство в машиностроении, М.: Машиностроение, 1986.

30. Соломенцев Ю.М., Фролов Е.Б. Математическая модель участка гибкой производственной системы // Проблемы управления и теории информации, 17, № 2, 1988, 53-71.

31. Соломенцев Ю.М., Диденко В.П., Митрофанов В.Г., Прохоров А.Ф. Основы построения систем автоматизированного проектирования гибких производств, М.: Высш. шк., 1986.

32. Султан-Заде Н.М., Тимковский В.Г. Метод оптимизации структуры однопоточной автоматической линии // Система управления станками и автоматические линии, М.: ВЗМИ, 1983, 93-95.

33. Танаев B.C., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии, Минск: Институт технической кибернетики НАН Белоруссии, 1998.

34. Трошин А.В. Автоматизированная система оперативного управления производством на машиностроительном предприятии, М.: Статистика, 1978.

35. Файнгольд M.JL, Кузнецов Д.В., Проблемы совершенствования оперативно-календарного планирования на машиностроительных предприятиях / Под ред. Файнгольд M.JL / Владимир, ВГПУ, 2003.

36. Фридман A.JI. Основы объектно-ориентированной разработки программных систем, Москва: Финансы и статистика, 2000.- 192 с.

37. Фролов Е.Б. Минимизация материальных и трудовых затрат в условиях мелкосерийных и единичных механообрабатывающих производств путем создания интегрированной системы оперативного управления, М: «СТАНКИН», 1993.

38. Фролов Е.Б. Моделирование материальных потоков в интегрированных машиностроительных производствах // Вопросы моделирования гибких производственных систем, М.: МИЭМ, 1989, 92-103.

39. Черныш Е.А., Молчанова Н.П., Новикова А.А., Салтанова Т.А., Прогнозирование и планирование, Учеб. Пособие, Москва: ПРИОР, 1999.

40. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении, Москва: Дело, 2000.

41. Экк К.Д. Знание как новая парадигма управления // Проблемы Теории и Практики Управления, 1998 г, № 2, 2-14.

42. Единая система технологической подготовки производства. Государственные стандарты СССР, М.: Издательство стандартов, 1984.