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

Федеральное государственное бюджетное учреждение науки ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. Трапезникова Российской академии наук

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

005531202

Сидоренко Александр Михайлович

РАЗРАБОТКА МЕТОДА АГРЕГИРОВАНИЯ ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ РАБОТ НА МАШИНОСТРОИТЕЛЬНЫХ ПРЕДПРИЯТИЯХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

- 4 !;ПП ¿ШЗ

Москва 2013

005531202

Работа выполнена на кафедре компьютерных систем автоматизации производства Московского государственного технического университете имени Н.Э. Баумана.

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

Официальные оппоненты:

доктор технических наук, профессор Хоботов Евгений Николаевич

доктор технических наук, профессор Ицкович Эммануил Львович

кандидат технических наук, доцент Кокуева Жанна Михайловна

Ведущая организация:

Институт системного анализа РАН

Защита состоится 14 октября 2013 года в 14 часов на заседании диссертационного совета Д002.226.01 при Институте проблем управления РАН имени В.А. Трапезникова по адресу: 117997, Москва, ул. Профсоюзная, д. 65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления РАН имени В.А. Трапезникова.

Автореферат разослан «_»_2013 года

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

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

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

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

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

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

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

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

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

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

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

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

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

• Разработан вариант алгоритма построения согласованных планов и расписаний работ, позволяющий распараллеливать вычисления.

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

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

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

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

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

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

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

• определить загрузку обрабатывающего оборудования предприятия и на основе анализа использования оборудования повысить эффективность работы предприятия.

Апробация. Основные положения диссертационной работы докладывались на научно-технических конференциях МГТУ им. Н.Э. Баумана (Москва, 2009 - 2011 г.г.), на 51-й, 54-й и 55-й научно-технических конференциях МФТИ (Москва, 2008, 2011, 2012 г.г.), на шестнадцатой международной научно-технической конференции МЭИ (Москва, 2010 г.), на IV международной конференции «Управление развитием крупномасштабных систем MLSD'2010» (ИПУ РАН, 2010 г.), на V международной конференции «Параллельные вычисления и задачи управления» (ИПУ РАН, 2010 г.), на VI международной конференции «Управление развитием

крупномасштабных систем MLSD'2012» (ИПУ РАН, 2012 г.), на научном семинаре в ИПУ РАН (2012 г.).

Основные результаты исследований были использованы при проектировании компанией «Нью Лайн Инжиниринг» цеха обработки трубопроводов на заводе Воронежского акционерного самолетостроительного общества.

Публикации. Основное результаты диссертационной работы опубликованы в 5 статьях в журналах, рекомендованных ВАК, 10 тезисах докладов на различных российских и международных конференциях, методических указаниях по выполнению лабораторных работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, основных выводов и результатов, списка использованной литературы из 118 наименований, трех приложений. Объем основной части работы составляет 127 страниц, включая 49 рисунков и 11 таблиц.

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

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

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

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

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

Пусть в течение планируемого интервала времени требуется последовательно изготовить Ь изделий. Каждое изделие состоит из К. типов комплектующих деталей (/=1 ,—,Ь). В состав одного изделия /го типа входит пц комплектующих деталей j-го типа (у = 1,..., ).

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

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

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

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

используемом оборудовании и сборки каждого изделия.

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

У = гшп{С1гах},

где Стах = тах{С, }, С1 = А1 +Тп А1 - время начала сборки изделия /, 1] -длительность сборки изделия.

При этом должны быть выполнены следующие ограничения:

1) не нарушаются отношения предшествования между технологическими операциями обработки комплектующих деталей, т.е. 5, + р.[ < Б], если / —> у для г, у е N.

2) не нарушаются отношения предшествования между обработкой комплектующих деталей и сборкой изделия, т.е. 5,. + 7] < А1, где 7* - время изготовления комплектующих деталей для изделия /, 1 = 1,...,/,.

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

данной задачи построения расписания из-за её большой размерности и сложности.

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

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

1 1 - 1 1 111

......и 1 - в г 1 г

| - 1 г

н ■■■ 1. И 1 г

Т„ г

Рисунок 1. Диаграмма Гантта для расписания обработки /-й группы деталей в / -м производственном подразделении

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

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

Такое расписание названо «каркасным» и для обработки и сборки комплектующих V -го изделия на предприятии представлено на рисунке 2, где через Т. обозначено затраченное на это время.

ш

Рисунок 2. Диаграмма Гантта «каркасного» расписания для изготовления комплектующих V -го изделия

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

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

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

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

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

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

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

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

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

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

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

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

Тогда при одновременной доступности всех работ «каркасное» расписание, которое минимизирует общее время изготовления всех узлов, таково, что сборка у'-го по порядку изготовления узла предшествует сборке узла у'+/, если гшп(^у,,В[/,^) </+|],В{п) и

4./+1] * Ау+1] ■

Если ^у+1] и имеется к (к = 1,...,п) следующих за ней

работ по изготовлению узлов, для которых также выполняются равенства =В[1+к+ц, то для этих работ кроме выполнения

условий тт(4у+4],5[у+4+1])<тт(4у+А+1],5[у+)1]) для всех к (к = 0,...,п) должно также выполняться условие

тт(4я,й[у+л+1])<шт(4уЧ„+1],5[у]), где через ] + п +1 обозначена первая работа, следующая за работой ] + п, и для которой 1] * ■

Здесь - время изготовления «каркаса» комплектующих деталей /-го по порядку изготовления узла, В[п - время сборки /-го по порядку изготовления узла.

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

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

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

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

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

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

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

После определения величин А] для всех изготавливаемых

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

считаются известными.

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

Обработка комплектующих деталей, сборка узлов высшего и п-1 порядков сборки объединены в «каркас» изготовления комплектующих. Время изготовления этого «каркаса» обозначено через , а время сборки сборочных единиц п-2 порядка через В/.

Мохаиообработка

Сборке узлов п-1 порядка

У1 и!_л 1 ш ш штшшл ттт, шттшт

1 и [а&У 1 ии 1! :1атв

I II )

!А.,

Сборка узлов I п-2 порядка

Рисунок 3. Диаграмма Гантта изготовления сборочных единиц различного порядка сборки

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

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

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

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

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

Процесс изготовления сложного узла или изделия удобно представлять с использованием «каркасного» расписания, в котором предварительное изготовление комплектующих узла или изделия / -го типа представляется «каркасом» длительностью А;, одновременная сборка и продолжение изготовления комплектующих представляется «каркасами», имеющими одинаковую длительность Ц , а завершающая сборка — «каркасом» длительностью В . Такой процесс может быть представлен на диаграмме Гантта, показанной на рисунке 4.

Мех. обр. 4 А 1 а2 °2 А • • • • • •

Сборка > А о2 в2 А в, • • •

Рисунок 4. Диаграмма Гантта для «каркасного» расписания изготовления сложных узлов

Здесь через Х1 обозначено время ожидания комплектующих при сборке изделия ; -го типа, через ¿1 - время ожидания перед началом изготовления комплектующих для сборки изделия / -го типа. Для вычисления величин А, В, и Ц предложены специальные методы, описанные в третьей главе.

Условия, позволяющие определять оптимальный порядок построения «каркасного» расписания изготовления сложных узлов и выпускаемых изделий определяются теоремой 3.2.

Теорема 3.2. Пусть требуется изготовить п типов сложных узлов или изделий, сборка каждого из которых производится по описанной выше схеме. Времена А/, В, и Д для каждого узла или изделия известны. Тогда при одновременной доступности всех работ и оборудования последовательность изготовления узлов или изделий,

которая минимизирует максимальную длительность «каркасного» расписания изготовления всех узлов, такова, что сумма

п-1 ;=1

достигает минимального значения.

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

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

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

Разработанные прототипы системы имеют модульную структуру, реализованы на языке программирования С# и платформе Microsoft.Net с использованием и Parallel Extensions для Microsoft .Net Framework. В состав системы входят следующие основные модули: модуль просмотра и редактирования технологической информации, модуль работы с заказами, модуль отображения расписаний, модуль формирования «каркасных» расписаний, модуль расчета и построения подетальных расписаний, модуль сбора и обработки статистики, модуль формирования отчетов. В качестве хранилища данных в первых версиях программы использовалась СУБД Microsoft SQL Server 2008, а для доступа к данным - подсистема платформы .Net Entity Framework.

Даже несмотря на то, что в первых вариантах реализации программы прототипа он показал хорошие результаты, как по качеству, так и по времени решения, результаты профилирования программы показали, что на обмен данными с СУБД тратится очень большое количество времени, которое в некоторых случаях доходило до 35% времени выполнения программы. В поисках более быстрой альтернативы была найдена и успешно интегрирована документо-ориентированная база данных Моп§оБВ, использование которой позволило увеличить скорость доступа к данным в среднем в 3 раза.

Внедрение результатов диссертационной работы при проектировании цеха обработки трубопроводов на заводе Воронежского акционерного самолетостроительного общества позволило выбрать оптимальное количество оборудования с нужной степенью автоматизации, а также оптимизировать расписание работ на выбранном оборудовании и сократить время изготовления одного самолетокомплекта труб с 15 до 7 дней. При этом стоимость проекта уменьшилась на 15% (~19,6 млн. рублей).

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

Таблица 1

Изделий Деталей Операций Время расчета без распараллеливания Время расчета с распараллеливанием Прирост производительности

1 4795 32084 3 мин. 05 сек. 1 мин. 36 сек. 48%

2 9874 65181 5 мин. 54 сек. 3 мин. 09 сек. 47%

3 14236 101075 9 мин. 47 сек. 5 мин. 16 сек. 46%

4 19862 135368 14 мин. 12 сек. 7 мин. 51 сек. 45%

6 31866 209374 19 мин. 53 сек. 11 мин. 57 сек. 40%

8 37428 253119 25 мин. 11 сек. 15 мин. 48 сек. 37%

Таблица 2

Изделий Деталей Операций Время расчета Условия

30 148257 =1 млн. 29 мин. 47 сек. 2-х ядерный процессор

64 259187 =1,9 млн. 55 мин. 34 сек. 4-х ядерный процессор

Из таблицы 1 становится видно, что распараллеливание вычислений позволяет получить существенное сокращение времени расчетов (данные вычисления проводились на ноутбуке с двухъядерным процессором Intel Core2 Duo 2.4ГГц и объемом оперативной памяти 2Гб).

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

Таблица 3

Изделий Деталей Операций Время расчета Вычислительная система

16 82638 641742 11 мин. 9 сек. Core i5 3,3 ГГц (4 ядра), 8 Гб RAM

20 105058 815906 17 мин. 59 сек. Core i5 3,3 ГГц (4 ядра), 8 Гб RAM

42 216258 1678685 39 мин. 14 сек. Соге ¡5 3,3 ГГц (4 ядра), 8 Гб НАМ

60 315174 2447718 1 час 51 мин. Соге ¡5 3,3 ГГц (4 ядра), 8 Гб ЯАМ

Одной из самых «больших по размерности» задач, решавшихся в рамках экспериментов, стала задача построения расписания, в которой изготавливается 60 изделий, состоящих из 252 узлов первого порядка, 762 узлов второго порядка, 2364 узлов третьего порядка и 7062 узлов высшего порядка сборки, с общим количеством комплектующих деталей 315174 единицы. Время расчета на компьютере с 4-х ядерным процессором составило 1 час 51 минуту. При этом было рассчитано 2447718 операций обработки и сборки.

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

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

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

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

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

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

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

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

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

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

10. Основные результаты исследований были использованы при проектировании компанией «Нью Лайн Инжиниринг» трубогибочного цеха на заводе Воронежского акционерного самолетостроительного общества.

ОСНОВНЫЕ ТРУДЫ ПО ТЕМЕ ДИССЕРТАЦИИ В изданиях, рекомендованных ВАК:

1. Сидоренко A.M., Хоботов E.H. Планирование производств с параллельной сборкой изделий // Вестник МГТУ им. Н.Э. Баумана. Машиностроение. - 2009. — №3. - С. 100-109.

2. Дудников E.H., Сидоренко A.M., Хоботов E.H. Система планирования проведения анализов в лабораториях на промышленных предприятиях // Автоматизация в промышленности.-2011. - № 10.-С. 10-13

3. Мелкишев В.Н., Сидоренко A.M., Хоботов E.H. Система планирования для производств с параллельной сборкой изделий // Программные продукты и системы. - 2012. №3. - С. 213-217

4. Сидоренко A.M., Хоботов E.H. Планирование и построение расписаний работ с учетом сборки узлов и изделий // Автоматизация в промышленности. - 2012. - №10. - С. 21-25

5. Сидоренко A.M., Хоботов E.H. Параллельные вычисления в задачах построения расписаний работ на предприятиях с учетом промежуточных сборок // Известия Вузов. Машиностроение. -2012. - Спец. выпуск: Фундаментальные проблемы создания и поддержки высокотехнологичных производств. - С. 43-51

В прочих изданиях:

6. Сидоренко A.M., Хоботов E.H. Модели планирования и построения расписаний работ на предприятиях с дискретным характером производства. // Управление развитием крупномасштабных систем (MLSD'2010): материалы четвертой международной конференции. - Москва, 2010. - Т.1. — С. 359361.

7. Сидоренко A.M., Хоботов E.H. Использование параллельных вычислений при решении задач планирования и построения работ на предприятиях. // Параллельные вычисления и задачи управления: труды пятой международной конференции. -М.: Москва, 2010. -С. 315-322.

8. Мелкишев В.Н., Сидоренко A.M., Хоботов E.H. Использование методов агрегирования для построения расписаний работ на машиностроительных предприятиях // Проблемы

фундаментальных и прикладных естественных и технических наук в современном информационном обществе: труды 54-й Всероссийской научной конференции. Аэрофизика и космические исследования. - Москва, 2011. - С. 217-218.

Московский Государственный Технический Университет им. Н.Э. Баумана

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

04201362435

СИДОРЕНКО АЛЕКСАНДР МИХАИЛОВИЧ

РАЗРАБОТКА МЕТОДА АГРЕГИРОВАНИЯ ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ РАБОТ НА МАШИНОСТРОИТЕЛЬНЫХ

ПРЕДПРИЯТИЯХ.

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук, профессор Хоботов Е. Н.

Москва 2013

Содержание Стр.

Введение.....................................................................................................................4

Глава 1. Обзор методов, моделей и систем планирования работ....................9

1.1. Обзор существующих методов построения расписаний.............................9

1.2. Обзор существующих систем планирования работ на предприятиях.................................................................................................21

1.3. Постановка задачи.........................................................................................33

Глава 2. Разработка методов построения согласованных расписаний

работ на машиностроительных предприятиях.........................................39

2.1. Разработка методов агрегирования и использования «каркасных» расписаний.....................................................................................................41

2.2. Разработка алгоритмов построения согласованных планов работ

и «склейки» «каркасных» расписаний........................................................48

2.3. Использование параллельных вычислений для задачи построения согласованных планов работ на уровне предприятия...............................52

2.4. Планирование работ на предприятиях с параллельной сборкой изделий...........................................................................................................57

2.5. Разработка алгоритма построения согласованных расписаний для производства с параллельной сборкой изделий.........................................64

2.6. Группировка изделий для параллельной сборки.......................................67

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

Глава 3. Разработка методов, учитывающих наличие

промежуточных сборок..............................................................................72

3.1. Постановка задачи построения расписаний с учетом промежуточных сборок.................................................................................72

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

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

Глава 4. Разработка и внедрение программного прототипа системы

планирования работ на уровне предприятия..........................................102

4.1. Описание программы..................................................................................102

4.2. Оптимизация системы для использования в крупномасштабных системах........................................................................................................105

4.3. Результаты численных экспериментов.....................................................108

4.4. Результаты внедрения.................................................................................113

Основные выводы и результаты..........................................................................116

Список используемых источников......................................................................118

ПРИЛОЖЕНИЯ.....................................................................................................129

Приложение А......................................................................................................129

Приложение Б......................................................................................................140

Приложение В......................................................................................................148

Введение

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

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

Однако для сложных производств и комплексов, в состав которых входит несколько производственных систем и участков, решение задач планирования и построения расписания обработки и сборки деталей, узлов и выпускаемой продукции вызывает уже весьма значительные затруднения из-за большой размерности и сложности структуры возникающих задач. Так, например, количество различных типов деталей, которые обрабатываются на некоторых машиностроительных предприятиях, может достигать нескольких сотен тысяч и даже миллионов. Попытки получения решений таких задач на основе решений задач планирования для отдельных производственных систем и участков, как правило, не приводят к удовлетворительным результатам [38,56,68,69].

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

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

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

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

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

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

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

• провести анализ существующих методов построения расписаний на машиностроительных предприятиях;

• разработать метод, позволяющий строить согласованные планы работ на уровне всего предприятия;

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

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

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

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

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

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

• Разработан вариант алгоритма построения согласованных планов и расписаний работ, позволяющий распараллеливать вычисления.

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

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

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

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

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

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

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

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

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

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

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

Глава 1. Обзор методов, моделей и систем планирования работ

1.1. Обзор существующих методов построения расписаний

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

Для планирования деятельности предприятий используются модели и методы объемного, календарного планирования и модели оперативного планирования [41].

Календарное планирование осуществляется на срок от 1 и до 3 месяцев и, как правило, такие планы пересчитываются через каждые 1-4 недели. В процессе формирования календарных планов строится расписание сборки производимой продукции и обработки ее комплектующих деталей. Исходной информацией для построения календарных планов являются результаты проведения объемного планирования, т. е. состав и объемы работ в привязке к укрупненным отрезкам планируемого периода - месяцам, кварталам. Модели и методы календарного планирования достаточно подробно изучались в работах [4,21,48,67].

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

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

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

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

С моделями, методами и этапами развития теории расписаний можно ознакомиться в трудах как отечественных авторов [18,24,28,32,64-66], так и зарубежных [73,77,78,89,94,102,108]. В работе [94] приведена одна из возможных классификаций существующих методов теории расписаний, обобщенный вид которой приведен на рисунке 1.1, согласно которой их можно разделить на две большие группы в зависимости от точности полученного решения: точные и приближенные.

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

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

Методы решения задач теории расписании

Приближенные

)

^ Гибридные

Г Эвристические методы

Локальный поиск

Нейронные Экспертные ( Нечеткая \ Муравьиных

сети системы 1 логика } колонии

Ун.......N................... 111111И

Решающие правила

7Т\

( Линеиное с

Нелинейное булевыми

переменными

Рисунок 1.1 - Методы решения задач теории расписаний

В блоке «Целочисленное программирование» (рисунок 1.1) представлены методы, позволяющие сводить построение расписаний обработки к решению задач математического программирования. Математическая формулировка задачи линейного программирования выглядит следующим образом. Нужно определить максимум линейной целевой функции (линейной формы)

— Сл Хл I С ■■) Хл +... + сх

7=1

при условиях

YJa.JXJ - Ь,> ПРИ ¿ = 1,2,...,т,

7=1

где вектор с - это вектор коэффициентов линейной формы, а вектор Ь — вектор ограничений.

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

Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ [98,35,63], предложенный в 1960 г.

Лэндом, Дойгом и Литтлом. Он может быть использован как для за�