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

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

004613705

Загороднев Дмитрий Иванович

Моделирование материальных потоков в рамках интегрированной системы управления производством машиностроительного предприятия на основе эвристических алгоритмов

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

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

2 3 ЛЕК 2010

Набережные Челны - 2010 г.

004618705

Работа выполнена на кафедре «Автоматизация и информационные технологии» ГОУ ВПО «Камская государственная инженерно-экономическая академия».

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

доктор техн. наук, профессор Симонова Лариса Анатольевна

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

доктор техн. наук, профессор Дмитриев Сергей Васильевич

доктор техн. наук, профессор Захаров Вячеслав Михайлович

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

Технологический центр ОАО «КАМАЗ»

Защита диссертации состоится «27» декабря 2010 г. в 13— час. на заседании диссертационного совета Д 212.309.01 в Камской государственной инженерно-экономической академии, по адресу: 423810, Республика Татарстан, г. Набережные Челны, пр. Мира, 68/19.

С диссертацией можно ознакомиться в библиотеке Камской государственной инженерно-экономической академии.

Электронный вариант автореферата размещен на сайте Камской государственной инженерно-экономической академии (ш\у\у. ineka.ru).

Автореферат разослан «25» ноября 2010 г.

Ученый секретарь

диссертационного совета Д 212.309.01 доктор технических наук, профессор

Симонова Л А.

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

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

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

Степень разработанности исследуемой проблемы. Большой вклад в вопросах автоматизации подготовки и управления производственными системами внесли Соломенцев Ю.М., Митрофанов В.Г., Павлов В.В., Горнев В.Ф., Черпаков Б.И., Коновал Д.Г., Каяшев А.И., Кожевников Ю.В., Адгамов Р.И., Сиразетдинов Т.К., Султан-заде Н.М, Симонова Л.А. и др.; в области информационных технологий Норенков В.П., , Горанский Г.К., Барабанов

В.В., Судов Е.В., Верник-ов Г.В, Дмитров В.И. и др.; в вопросах организации информационных систем поддержки принятия решений Поспелов Д.А. , Вагин В.Н. , Саати Т., Попов Э.В. , Мамиконов А.Г. и др.; в области моделирования процессов E.W.Dijcstra, Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Ананий В. Левитин; методов моделирования процессов В.В. Псиола, Б.В. Гнеденко, И.Н. Коваленко, Н. Holden, N.H. Risebro, Д. Дрю, L.C. Evance, В.И. Швецов, A.C. Алиев, D. Helbing, А.П. Буслаев, A.B. Новиков, В.М. Приходько, А.Г. Таташев, М.В. Яшина; G. Clarke, J.W. Right, Г.И. Чернов, И.С. Дрогин, Gunter Hans, Rieks Heinz G., А Э. Александров, Л. Форд, Д. Фалкерсон; Кучеренко Е.И., Бодянского Е.В., Михалева А.И., Котова В.Е, Питерсон Дж., Хемди A.Taxa и др.

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

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

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

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

1. Исследовать основные подходы и методы моделирования материальных потоков для применения к условиям машиностроительного предприятия.

2. Предложить структуру модуля моделирования материальных потоков на внутрицеховом и межцеховом уровнях в рамках интегрированной системы управления производством территориально-распределённой системы машиностроительного предприятия.

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

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

5. Разработать методики и алгоритмы моделирования оптимальной 3-х мерной загрузки транспортных средств машиностроительного предприятия.

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

В процессе диссертационного исследования получены следующие результаты, обладающие научной новизной:

1. Методика моделирования материальных потоков на внутрицеховом и межцеховом уровнях в рамках интегрированной системы управления производством машиностроительного предприятия на основе базы прецеден-

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

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

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

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

Практическая полезность работы:

1. Разработана структура модуля моделирования материальных потоков на внутрицеховом и межцеховом уровнях в рамках интегрированной системы управления производством территориально-распределённой системы машиностроительного предприятия.

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

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

4. Разработана методика и алгоритмы моделирования оптимальной 3-х мерной загрузки транспортных средств машиностроительного предприятия.

5. Предложенные методики и алгоритмы реализованы в виде программного комплекса «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010).

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

Реализация и испытание результатов исследований осуществлено на примерах машиностроительного предприятия ОАО «КАМАЗ». Разработанный программный комплекс «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010) и основные положения диссертации используются в учебном процессе в Камской государственной инженерно-

экономической академии. Разработанные методики используются на машиностроительном предприятии ООО ЛинкОр, получен акт об использовании материалов диссертационной работы (Акт №07 от 21 октября 2010 г.).

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

Апробация работы. Основные положения и результаты, полученные в работе, докладывались на международных и межрегиональных научных и научно-практических конференциях: Межрегиональная научно-практическая конференция «Студенческая наука в России на современном этапе» (Наб. Челны, 2008 г.), Международная научно-техническая конференция (Пенза,2008г.), Международная научно-техническая и образовательная конференция (Наб. Челны, 2010 г); II Межрегиональная научно-практическая конференция студентов, аспирантов и молодых ученых (Наб. Челны, 2010 г.), на научных семинарах в Камской государственной инженерно-экономической академии (2007-20 Юг. г.).

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

Структура и объем диссертации: Диссертационная работа состоит из введения, пяти глав, заключения, библиографического списка использованной литературы, включающего 87 наименований. Работа изложена на 123 страницах машинописного текста, содержит 30 рисунков и 15 таблиц, 4 приложения.

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

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

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

Такие крупные машиностроительные предприятия, как ОАО «КАМАЗ», ОАО «ГАЗ» и т.п. на современном этапе широко внедряют MRP/ERP/MES системы. На мировом рынке сейчас предлагаются и успешно внедрены на предприятиях с территориально - распределенной системой, свыше 500 систем класса MRP 11 - ERP. Среди всех предложенных решений можно выделить около десятка проектов, которые достаточно полно отражают потребности производственно-промышленного комплекса. Особенность управления материальными потоками в данных системах заключается в системном рассмотрении совокупности всех звеньев производственного процесса как единое целое, сокращение ресурсных и временных затрат достигается

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

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

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

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

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

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

МвДиШ

Преобразование векторных карт; в маршрутный граф I

прецвдв!

.Моделирование оптимальных маршрутов на дородном графе

1 '

1 маршрутов доставки р

Моделирование внутрицеховых маршрутов доставки

Моделирование загрузки транспорта

Накопление данных

Формирование прецедентов

Формирование правил

Накопление знаний

Вьщача результатов работы

Рисунок 1 -Моделирование материальных потоков в рамках интегрированной системы управления производством машиностроительного предприятия

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

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

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

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

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

'И-И-»0 (1)

• К = ъ\Т

где

Ъ Множество допустимых решений;

Т Множество тар подлежащих укладке;

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

|г, | Количество элементов входящих во множество;

К Множество, содержащее элементы, входящие в г,, но не входящие в Т;

Мц Номер слоя укладки (0 - верхний слой).

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

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

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

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

Правила для получения нового прецедента (вывода решения) записаны в форме предикатов. Например:

Правило для формирования маршрутов:

1. (УА)(УВ)( НЕСУЩМАРШ (А, В)-* ПОЛМАРШ {А, В)

2. (УА)(\/В)(НЕСУЩШРШ(А, В) -> ПОЛАЛТМАРШ(А,В)

3. {\/А)(\/В)(НЕСУЩМАРШ(А,В) -» ПОСГРМАРШ (А,В)

где

БЗСОДМАРШ(А,В)

ПОЛМАРШ(А,В)

НЕСУЩМАРШ(А,В)

ПОЛАЛТМАРШ(А,В)

ПОСТРМАРШ(А,В)

В базе содержится маршрут; Получить маршрут из базы; Не существует маршрута из пункта А в пункт В; Получить альтернативный маршрут; Построить маршрут.

Правило для получения расположения тар:

1. <уХ)(СПУКЛНЕСОД (X) -> УДЛ(Х)

2. (УХ){НИЖГРНЕСТ (X) УДЛ(X)

3. (\/Х)(ВСЕГРНЕСТ (X) -> УДЛ (X)

где

СПУКЛНЕСОД(Х) НИЖГРНЕСТ(Х) ВСЕГРНЕСТ(Х) УДЛ(Х)

Список не содержит ящик заданного типа; Нижняя грань ящика не имеет опоры; Все грани не соприкасаются; Удалить ящик заданного типа из списка;

Новый набор для : укладки :

Исходные данные

■ Формирование : альтернативных : способов | загрузки

Приоритеты предприятия

Определение зкспергами

[.коэффициентов;

Набор альтернативных способов загрузки

База прецедентов

т

>анен :цед«

!

Сохраненный прецедент

п^гцедекта

Значение — весовых — коэффицие нтов

| Шжйрова^ е I списка : аяьтеризти'еных загрузок

Показатели способов зафузки

Значения показателей

Ранжированный список способов . загрузки

Рисунок 2 - Процесс наполнения базы прецедентов на примере способа загрузки

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

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

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

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

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

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

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

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

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

Структура составного многокритериального веса ребра представлена

Рисунок 3 - Составной многокритериальный вес ребра дорожного графа

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

0 = е\х ~х Е1, £"=11. +£зх /IX, * ьх ^х (2)

где

и- число участков составляющих маршрут;

V, - скорость движения на ¡-м участке маршрута;

1] - длина ¡-го участка маршрута;

(:. - тип дороги на участке 1 маршрута;

Метод Кларка-Райта относится к числу приближенных, итерационных методов и предназначается для компьютерного решения задачи развозки. Погрешность решения не превосходит в среднем 5-10%.Недостатками данного алгоритма является его недоработка с точки зрения загрузки транспорта, при расчете загрузки рассматривается лишь суммарный вес грузов и грузоподъемность одинаковых машин.

Начало

Пункты доставки, информация по

транспорту, информация по грузам

Ранжирование транспортных средств на основе расчета целевой _______функции_______

Построение матрицы расстояний и километровых выигрышей

Построение нового маршрута

<\~ Все маршруты построены?

да

/ Вывод

/ построенных

/ маршрутов и /

способов укладки '

грузов

Конец

/

Добавление пункта к маршруту

Выбор транспортного средства

3-х мерная загрузка транспортного средства

Загрузка прошла успешно?

Рисунок 4 - Модифицированный алгоритм Кларка-Райта

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

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

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

Задачи об упаковке и рюкзаке, как в одномерном, так и в двух - или в трехмерном случаях, относятся к классу №-полных задач.

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

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

2. Учитывать допустимую грузоподъемность транспортного средства и равномерность распределения нагрузки в кузове.

На основе сформулированных требований был построен модифицированный алгоритм.

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

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

« = Kl • » + у2 ■ -Js + Кз • ^ г, + Г4 ■ I, • 12 + п ■ 1тЫ + Гй ■ ¡тау + Г? • Ml^UcT") +

ie<V ie\i;2

+ К8 -Mi,(.teNxt > xui) +Y4 • Hi^^UT) + Kl0 ■ a^^ieT) + ylt ■ Mmin(l„^¿(.ieT) +

+ П2 • "ш1пО,Л»:)(£еГ) + • ¿,lmin(lI.l,^:>-t1.1|(ifr) + Kn ' ®|mina..W-<n.,l (i<?r) + ßj

_ 1_

min :f-ZicN »CO ;sCO)

58 - значение функционала качества двумерного предмета, после установки которого образована данная область;

Б - площадь двумерного предмета, после установки которого

образована данная область;

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

Т - множество вершин внутренней ломаной, которые вместе с тремя

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

1; -длина отрезка (х! ,х5+1 ) внутренней ломаной;

1тш - минимальное расстояние между внутренней и внешней границами области;

1пах - максимальное расстояние между внутренней и внешней границами области;

[IX (У) - математическое ожидание функции х по всем элементам множества У;

ах(У) - среднеквадратичное отклонение функции х по всем элементам множества У ;

- значение функционала качества областей укладки Псиола

в - грузоподъемность транспортного средства;

5г - площадь занимаемая грузом;

Ба - площадь кузова транспортного средства;

Х„„ МО - сумма весов ящиков установленных друг на друга;

8(0 ■ грузоподъемность ящика, верхняя грань которого образует плоскость укладки;

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

Таблица 1. Характеристики погрузчиков

Наименование Модель Грузоподъемность, G Скорость, V

Электропогрузчик ЕВ735 3 10

Электропогрузчик ЕВ717 2 10

Дизельный погрузчик ДВ1661 1 12

Дизельный погрузчик ДВ1788 3 12

Дизельный погрузчик ДВ1792 3 12

Дизельный погрузчик СРСДЗОФА 3 12

Автопогрузчик 4066 5 12

Автопогрузчик 4081 5 12

Автопогрузчик ДВНМ 5022 5 12

Таблица 2. Рабочие центра цеха

Рабо-бо-чий центр Наименование Модель Мощность Сварочная толщина Серий-рий-ный номер Координаты оборудования

и. В i, Ka

РЦ 1.1 Машина рельефной сварки МТ 1607 70 - 59.01.0 1 У/115

РЦ 1.2 Машина рельефной сварки МТ 1607 70 5 58.01.0 3 Ф1 / 114/113

РЦ2 Автоматическая линия SPM 200 Т1/ 113

РЦЗ Автоматическая линия SPM 201 У1 /113

РЦ4 Автоматическая линия SPM 101 У/У1 / 118/117

РЦ 5.1 Машина для точечной сварки МРТ 1613 38 0 16 4 58.01.0 2 Ф/Ф1 / 114/113

РЦ 5.2 Машина для точечной сварки МРТ 1613 38 0 16 4 58.01.0 4 Ф1 / 114

РЦ6 Автоматическая линия SPM 108 У/У1 / 118/117

РЦ7 Спец. Сварочная машина SPM 113 6 У1/Ф/ 118

На внутрицеховом уровне апробация проводилась на примере цеха сварки-сборки кабин и кузовов Камского прессово-рамного завода

машиностроительного предприятия ОАО «КАМАЗ», где ,ча данный момент на балансе предприятия находится 129 погрузчиков, модели которых приведены в таблице 1.

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

Следующим этапом по координатам транспортных средств формируются матрицы положения транспортных средств (матрица смежности) между точками рабочих центров (РЦ) на примере участка сборки-сварки боковин (таблица 3).

Таблица 3. Матрица положения участка сборки-сварки боковин

Матрица положения между точками Связные точки участка сборки-сварки боковин

РЦ 1.1 РЦ 1.2 РЦ2 РЦЗ РЦ 5.1 РЦ 5.2

Связные точки участка сборки-сварки боковин РЦ 1.1 X 42 72 66 48 36

РЦ 1.2 42 X 36 30 18 6

РЦ2 72 36 X 12 |_ 30 42

РЦЗ 66 30 12 X 15 30

РЦ5.1 48 18 30 15 X 15

РЦ 5.2 36 6 42 30 15 X

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

На межцеховом уровне ОАО «КамАЗ», в состав которого входит более 40 территориально распределенных предприятий, в качестве примера моделирования межпроизводственных маршрутов была рассмотрена доставка группы товаров с центрального

Таблица 4. Информация о транспортных средствах

склада.

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

Марка /77 S, к ti/ч С кг V, N Д л/100 кп

Соболь 70 1500 7 И. 7

Г1зель 60 1500 6 155

Фермер 70 1500 s 6 j 15.3

Волдан 60_ 1800 7 Ю

КАМАЗ 43118 Г~ 90 7000 18 i 6.6

КАМАЗ 5320 80 10000 15 15 25

AVIA 90 11000 11

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

Таблица 5. Результат ранжиро- Таблица 6. Результаты построения меж-

вания списка транспортных производственных маршрутов

средств

Марка Целебая ф-я F Кол-до

ГЪэель -0,0% 76 2

Фермер 0.020708 2

Валдан 0,024082 2

Соболь 0.055126 2

Камаз 1*3118 0.602506 2

Камаз 5320 0,664-160 2

AVIA 0,785882 2

п Маршрут S. км т Загрузка. % а. л/ЮОкн

1 0-9-2-20-0 169 КамАЗ 76.6 78.83

2 0-14-10-0 16S Кам43 61.1 76.69

3 0-19-3-0 181 Гцель 50 28

i 0-12-1-0 158 Кам53 69 39.5

5 0-6-17-7-0 127 Кам53 78 31.75

6 0-16-18-15-0 90 AVIA 63 9.9

»Шыбор аагрумюа

Vй : "" I«1 , ■"■».¿гг. * *

8»я» üít ' ifesfesa

««asÉsaíj te i. 5<:hK9»5ra4 Шэфа

** 3?! ■ ^ тщ ^

............!..";.......:..

í .. 'ibUr-í.-Á;

|iT| Ée : i íbssa

ЦЧ

.......... s

.-J f у -г J i J -Й

ж ®

Г '¡оф. i

!> ттъ •:

I* i

\í i

. KVshMíSredvcheniy,,

t*** *| ÍDMarshryS ( ®PL TTsepochkaPeredazheriiya ¡í

; ► 1 1РЦ 5-РЦ4 |

IDVtemeni j VremyaHsMare

| 08.04.2010

ш (Счетчик)

i * (Счетчик; 0

Ямим Щ5 > j§¡ J|H w i

r ш"e

Рисунок 6 - «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010)

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

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

1. Исследованы основные подходы и методы построения систем управления и моделирования материальных потоков на машиностроительном предприятии.

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

3. Исследованы основные подходы и методы построения оптимальных маршрутов на графах. Предложена методика построения оптимальных маршрутов, обеспечивающая сокращение времени работы алгоритмов без снижения их качественных показателей, что позволило применить их для построения оптимальных маршрутов на больших маршрутных графах на разных этапах с учетом вместимости, использования различных типов транспортных средств и загрузки. Апробация разработанных алгоритмов была проведена на конкретных примерах и показала, что можно сократить время работы алгоритмов в 7... 10 раз. Например, длительность работы на 12 точках составляла 120 минут, после проведенных модификаций время работы составило 10.. 12 минут.

4. Предложены методики и алгоритмы моделирования оптимальной 3-х мерной загрузки транспортных средств машиностроительного предприятия. Погрешность решения не превосходит в среднем 5-10%.

5. Предложенные методики и алгоритмы реализованы в виде программного комплекса «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010). Осуществлена проверка эффективности программного комплекса на межцеховом уровне на ОАО «КАМАЗ» и внутрицеховом уровне на примере цеха кабин и кузовов Камского прессово-рамного завода машиностроительного предприятия ОАО «КАМАЗ», разработанные методики используются на машиностроительном предприятии ООО «ЛинкОр».

Основное содержание работы отражено в следующих публикациях: Научные статьи, опубликованные в журналах, рекомендованных ВАК:

1. Загороднев, Д.И. Оптимизация материальных потоков в распределенной системе управления машиностроительного предприятия на основе эвристических алгоритмов / Д.И. Загороднев, Л.А. Санакулова, Л.А. Симонова // Научно-технические ведомости СПбГПУ, Серия «Наука и образование» -2010. № 3(106). - С. 101-107

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

2. Загороднев, Д.И. Организационная структура крупного и малого предприятия и принципы организации производства / Д.И. Загороднев // Проектирование и исследование технических систем: межвузовский научный сборник. Вып. 13. - Набережные Челны: ИНЭКА, 2009. - С. 91-95.

3. Загороднев, Д.И. Применение методов решения транспортной задачи для автоматического управления транспортными потоками предприятия / Д.И. Загороднев, Л.А. Симонова // Проектирование и исследование технических систем: межвузовский научный сборник. Вып. 14. - Набережные Челны: ИНЭКА, 2009. - С. 56-65.

4. Загороднев, Д.И. Исследование методов решения транспортных задач при управлении материальными потоками предприятия / Л.А. Санаку-лова, Д.И. Загороднев, А.И. Салахеева // Социально - экономические и технические системы. - 2009. -№4. - URL: http://feets.rn

5. Загороднев, Д.И. Унификация форм заявки в автоматизированной системе планирования грузоперевозок на машиностроительном предприятии / Д.И. Загороднев, Л.Т. Шарифянова // Сборник трудов Международной научно-технической и образовательной конференции (28-31 марта 2010 года) Часть 1. Книга 1. - Набережные Челны: 2010. - С. 191-193.

6. Загороднев, Д.И. Алгоритм принятия решения при организации многономенклатурных поставок / Г.Э. Гиниятуллина, Д.И. Загороднев, Л.А. Санакулова // «Камские чтения»: сборник материалов. 1 межрегиональная научно-практическая конференция. В 3-х ч. Часть 3. - Набережные Челны: ИНЭКА, 2010.-С. 77-80.

7. Загороднев, Д.И. Свидетельство о государственной регистрации программы для ЭВМ №2010614058. Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов / Д.И. Загороднев, Л.А. Симонова М.: Роспатент, 2010.

8. Загороднев, Д.И. Исследование показателей систем управления сварочного оборудования / Д.И. Загороднев // Социально - экономические и технические системы. - 2010. - Jfe 3. - URL: http://Kts.ru

Подписано в печать 24.11.10 г. Формат 60x84/16 Бумага офсетная Печать ризографическая Уч.-изд.л. 1,3 Усл.-печ.л. 1,3 Тираж 100 экз.

Заказ 1964 Издательско-полиграфический центр Камской государственной инженерно-экономической академии

423810, г. Набережные Челны, Новый город, проспект Мира, 68/19 тел./факс (8552) 39-65-99 e-mail: ic@ineka.ru

Введение

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

1.1 Анализ систем управления машиностроительного предприятия с точки зрения задач управления материальными потоками

1.2 Анализ существующих решений оптимального планирования материальных потоков

1.2.1 Особенности задач оптимизации при моделировании маршрутов

1.2.2 Анализ существующих автоматизированных ИС планирования маршрутов

1.2.3 Исследование методов решения задачи маршрутизации

1.2.4 Исследование и анализ методов нахождения кратчайших расстояний на маршрутном графе

1.3 Анализ решения задачи загрузки транспортных средств

1.3.1 Анализ существующих автоматизированных информационных систем планирования загрузки транспортных средств

1.4 Методы формирования базы прецедентов применительно к построению системы моделирования материальных потоков

1.5 Постановка задач исследования

Глава 2. Методика формирования базы прецедентов системы моделирования материальных потоков

2.1 Разработка структуры системы моделирования материальных потоков

2.2 Рассуждения по прецедентам

2.3 Способ хранения прецедентов моделей загрузки транспорта

2.4 Методика формирования прецедентов загрузки транспорта

2.5 Контроль увеличения размеров базы прецедентов

2.6 Методика формирования прецедентов при моделировании маршрутов

2.7 Структура прецедента

2.8 Организационные правила хранения данных в базе прецедентов

2.9 Выводы

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

3.1 Структура интегрированного алгоритма поиска оптимальных маршрутов

3.2 Алгоритм построения оптимальных маршрутов на дорожном графе на основе модифицированного алгоритма Дейкстры

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

3.4 Структура составного многокритериального веса ребер дорожного графа

3.5 Функционал качества альтернативных маршрутов

3.6 Алгоритм построения кольцевых маршрутов на основе модифицированного алгоритма Кларка-Райта

3.7 Алгоритм выбора транспортного средства

3.8 Выводы

Глава 4. Методика моделирования оптимальной загрузки транспортных средств на основе алгоритма Псиола с использованием модифицированных эвристик

4.1 Формирование исходных данных задачи загрузки транспортных средств

4.2 Общая структура модифицированного алгоритма Псиола

4.3 Модифицированный функционал качества областей укладки

4.4 Выводы

Глава 5. Апробация программного комплекса «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» на примере машиностроительного предприятия с распределенной системой управления.

5.1 Описание структуры машиностроительного предприятия с распределенной системой на примере ОАО «КамАЗ»

5.2 Моделирование материальных потоков на внутрицеховом уровне на примере Камского прессово-рамного завода

5.3 Моделирование материальных потоков на межцеховом уровне на примере ОАО «КамАЗ»

5.4 Выводы 108 Заключение 110 Список использованной литературы 113 Приложение 1 121 Приложение 2 122 Приложение 3 123 Приложение

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

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

Степень разработанности исследуемой проблемы. Большой вклад в вопросах автоматизации подготовки и управления производственными системами внесли Соломенцев Ю.М., Митрофанов В.Г., Павлов В.В., Горнев В.Ф., Черпаков Б.И., Коновал Д.Г., Каяшев А.И., Кожевников Ю.В., Адгамов Р.И., Сиразетдинов Т.К., Султан-заде Н.М, Симонова Л.А. и др.; в области информационных технологий Норенков В.П.,, Горанский Г.К., Барабанов В.В., Судов Е.В., Верников Г.В, Дмитров В.И. и др.; в вопросах организации информационных систем поддержки принятия решений Поспелов Д.А., Вагин

В.Н., Саати Т., Попов Э.В., Мамиконов А.Г. и др.; в области моделирования процессов E.W.Dijkstra, Томас X. Кормен, Чарльз И. Лейзерсон, Рональд JI. Ривест, Клиффорд Штайн, Ананий В. Левитин; методов моделирования процессов В.В. Псиола, Б.В. Гнеденко, И.Н. Коваленко, Н. Holden, N.H. Risebro, Д. Дрю, L.C. Evance, В.И. Швецов, A.C. Алиев, D. Helbing, А.П. Буслаев, A.B. Новиков, В.М. Приходько, А.Г. Таташев, М.В. Яшина; G. Clarke, J.W. Right, Г.И. Чернов, И.С. Дрогин, Gunter Hans, Rieks Heinz G., А Э. Александров, Л. Форд, Д. Фалкерсон; Кучеренко Е.И., Бодянского Е.В., Михалева А.И., Котова В.Е, Питерсон Дж., Хемди A.Taxa и др.

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

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

Цель исследования: повышение эффективности процесса управления материальными потоками на внутрицеховом и межцеховом уровнях машиностроительного предприятия!

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

1. Исследовать' основные подходы и методы моделирования материальных потоков для применения к условиям машиностроительного предприятия.

2. Предложить структуру модуля моделирования материальных потоков на внутрицеховом и межцеховом уровнях в рамках интегрированной системы управления производством территориально-распределённой системы машиностроительного предприятия.

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

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

5. Разработать методики и алгоритмы моделирования оптимальной 3-х мерной загрузки транспортных средств машиностроительного предприятия.

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

В процессе диссертационного исследования получены следующие результаты, обладающие научной новизной:

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

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

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

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

Практическая полезность работы:

1. Разработана структура модуля моделирования материальных потоков на внутрицеховом и межцеховом уровнях в рамках интегрированной системы управления производством территориально-распределённой системы машиностроительного предприятия.

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

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

4. Разработана методика и алгоритмы моделирования оптимальной 3-х мерной загрузки транспортных средств машиностроительного предприятия.

5. Предложенные методики и алгоритмы реализованы в виде программного комплекса «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010).

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

Реализация и испытание результатов исследований осуществлено на примерах машиностроительного предприятия ОАО «КАМАЗ». Разработанный программный комплекс «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010) и основные положения диссертации используются в учебном процессе, в Камской государственной инженерно-экономической академии. Разработанные методики используются на машиностроительном предприятии ООО ЛинкОр, получен акт об использовании материалов диссертационной работы (Акт №07 от 21 октября 2010 г.).

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

Апробация работы. Основные положения и результаты, полученные в работе, докладывались на международных и межрегиональных научных и научно-практических конференциях: Межрегиональная научно-практическая конференция «Студенческая наука в России на современном этапе» (Наб. Челны, 2008 г.), Международная научно-техническая конференция (Пенза,2008г.), Международная научно-техническая и образовательная конференция (Наб. Челны, 2010 г); II Межрегиональная научно-практическая конференция студентов, аспирантов и молодых ученых (Наб. Челны, 2010 г.), на научных семинарах в Камской государственной инженерно-экономической академии (2007-20Юг.г.).

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

Основные результаты работы:

1. Исследованы основные подходы и методы построения систем управления и моделирования материальных потоков на машиностроительном предприятии.

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

3. Исследованы основные подходы и методы построения оптимальных маршрутов на графах. Предложена методика построения оптимальных маршрутов, обеспечивающая сокращение времени работы алгоритмов без снижения их качественных показателей, что позволило применить их для построения оптимальных маршрутов на больших маршрутных графах на разных этапах с учетом вместимости, использования различных типов транспортных средств и загрузки. Апробация .разработанных алгоритмов была проведена на конкретных примерах и показала, что можно сократить время работы алгоритмов в 7. 10 раз. Например, длительность работы на 12 точках составляла 120 минут, после проведенных модификаций время работы составило 10. 12 минут.

4. Предложены методики и алгоритмы моделирования оптимальной 3-х мерной загрузки транспортных средств машиностроительного предприятия. Погрешность решения не превосходит в среднем 5-10%.

5. Предложенные методики и алгоритмы реализованы в виде программного комплекса «Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010). Осуществлена проверка эффективности программного комплекса на межцеховом уровне на ОАО «КАМАЗ» и внутрицеховом уровне на примере цеха кабин и кузовов Камского прессово-рамного завода машиностроительного предприятия ОАО «КАМАЗ», разработанные методики используются на машиностроительном предприятии ООО «ЛинкОр».

Заключение

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

Результатом исследования явилась разработка программного комплекса «Автоматизированная система управления • материальными потоками предприятия на основе эвристических алгоритмов» (Свидетельство государственной регистрации программ для ЭВМ №2010614058 от 31 мая 2010). .

1. MES система «ФОБОС» / FOBOS-MES. — URL: http://www.fobos-mes.ru (дата обращения 27.11.2009).

2. Preactor Production Planning and Scheduling Software / Preactor International Ltd. — URL: http://www.preactor.com (дата обращения 25.11.2009).

3. Zenith SPPS Автоматизация производства. — URL: http://www.zspps.com/ (дата обращения 25.11.2009).

4. Системы автоматизации. Нет предела совершенству», Д. Любовина, издание "Логинфо", №4-5, 2007 г.

5. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах: Учебное пособие. — 2-е изд., исправл. М: Высш. шк., 2005 - 544 е.: ил.

6. Лебедев Г.И., «Математические модели в транспортных системах (конспект лекций», Минск, 2009 г.

7. R. L. Graham and P. Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1): 43-57, 1985.

8. S. Chung, A. Condon. Parallel implementation of Boruvka's minimum spanning tree algorithm. In Proc. 10th Int'l Parallel Processing Symp. (IPPS'96), pages 302-315, April 1996.

9. Пакер ЗД. URL: http://www.packer3d.ru/

10. CHUL-YOUNG BYUN Lower Bounds for . Large-Scale Set Partitioning Problems, ZIB-Report 01-06 (January 2001)

11. OPTIMA, Mathematical Programming Society Newsletter, March 2008

12. Necessary Condition for Path Partitioning Constraints, Nicolas Beldiceanu and Xavier Lorca, 2004

13. A Technical Review of Column Generation in Integer Programming, Wilbert E. Wilhelm, Department of Industrial Engineering Texas A&M University, July 10, 2001

14. БИТ: НОВА Управление транспортной логистикой. URL: http://www.lcbit.ru (дата обращения 12.03.2009)

15. KdnRoute. URL: http://www.torgrus.com (дата обращения 18.03.2009)16.«Деловая карта». URL: http://rus-analit.ru/index.php7option- comcontent& task=view&id= 14&Itemid=l (дата обращения 02.04.2009)

16. Алголист. URL: http://algolist.manual.ru/ai/ga/dioph.php (дата обращения 12.04.2009)'

17. David R. Karger, Philip N. Klein, and Robert'E. Tarjan. A randomized lineartime algorithm to find minimum spanning trees. Journal of the ACM, 42(2): 321-328, March 1995.

18. V. King. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263-270. 1997.

19. Алгоритм Прима. URL: http://ru.wikipedia.org/wiki/ %D0%90%D0 %BB%D0%B3%D0%BE%D 1 %80%D0%B8%D 1 %82%D0%BC

20. D0%9F%D 1 %80%D0%B 8 %D0%BC%D0%B0 (дата обращения 8.05:2009)

21. Open Vehicle Routing Problem with Time Deadlines: Solution Methods and an Application! URL: http://masters.donntu.edu.ua/2009/ kita/aleksandrova/ library/article02 eng.pdf(дата обращения 12.05.2009)

22. Aarts E. H. L., Korst J. H. M., Laarhoven van P. J. M. Simulated annealing, in Aarts E., LenstraJ.K. (Eds) Local search in combinatorial optimization. Chichester: Wiley, 1997. pp 91-120.

23. Aarts E. H. L., Korst J. H. M. Simulated annealing and Boltzmann machines. Chichester: Wiley, 1989.

24. Hajek В., Sasaki G. Simulated annealing: to cool it or not. Sys. Contr. Lett. vl2 (1989), pp 443-447.

25. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing. Science. v220 (1983), pp 671-680.

26. Binder K. Monte Carlo methods in statistical physics. Berlin: Springer, 1978.j

27. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. l.C. 87-90, 1958.

28. L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.

29. E. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), P. 269-271

30. Томас X. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильяме», 2007. — С. 1296.

31. Ъ2.Басакер Р., Саати 71 Конечные графы и сети. М.: Наука, 1974. 368с.

32. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа, 1976. —С. 392.

33. ЪЛ.Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320с.

34. Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429с.38Юре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С. 336.

35. Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997.

36. Ананий В. ■ Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — M.: «Вильяме», 2006. — С. 189—195.

37. Евстигнеев,В.А., Мельников Л.С. Задачи и упражнения по теории графов и комбинаторике. Новосибирск: НГУ, 1981. - 88 с.

38. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. Нижегородская область: Изд-во Нижегородского гос. университета им. Н.И.Лобачевского. 2004

39. Искусственный интеллект. Кн. 2: Модели и методы: Справочник / Под ред. Э.В. Попова. М.: Радио и связь, 1990. 303 с.

40. Левйн Р., Дранг Д., Эделсон Б. Практическое введение в технологию искусственного интеллекта и экспертных систем с иллюстрациями на Бейсике. М.: Финансы и статистика, 1990. 239 с.

41. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь. 1990. 376с.

42. Кофман Л. Введение в теорию нечетких множеств. М.: Радио и связь, 1982.

43. Задача об упаковке. URL: http://works.tarefer.ru/69/100865/index.html (дата обращения 2.06.2009)

44. Алгоритмы: введение в разработку и анализ, : Пер. с англ. М. : Издательский дом «Вильяме», 2006. - 576 с.

45. Donald Knuth; James Н. Morris, Jr, Vaughan Pratt (1977). «Fast pattern matching in strings». SIAM Journal on Computing 6 (2): 323-350.

46. LoadPlaner. URL: http://www.loadplanner.com/ (дата обращения 23.07.2009)

47. Answer Logistic. URL: http://www.answer-logistic.ru/ (дата обращения 25.07.2009)

48. ГОСТ Р ИСО 10303-1-99. Системы автоматизации производства и их интеграция. Представление данных об изделии и обмен этими данными.

49. М.: ИПК Изд-во стандартов, 1999. — 16 с

50. Симонова JI. А. Методология построения интегрированного информационного обеспечения гибких производственных систем механической обработки на машиностроительных предприятиях: монография / Л.А.Симонова. — СПб.: Изд-во Инфо-Да, 2004. —198 с.

51. Куликов Г.Г. Интеллектуальные информационные системы: учебное пособие / Г. Г. Куликов, Т. В. Брейкин, В. Ю. Арьков. — Уфа: УГАТУ, 1999.— 129 с.

52. Mason F. Computerized Cutting Tool Management / F. Mason // American Machinist & Automated Manufacturing, Special Report 786. — 1986. — P. 106— 120.

53. Zheng Y. Integration of computerized Tool Management System and Tool Condition Tracking at All Levels / Y. Zheng, A. Bilberg, L. Alting // Flexible Automation and Integrated Manufacturing. — 1993. — P. 439—447.

54. Veeramani D. Integration of cutting-tool management with shop-floor control in flexible machining systems / D. Veeramani // Computer control of flexible manufacturing systems: research and development. — 1994. — P. 405—423.

55. Narang R.V. A computer model for tool management information system / R.V. Narang // Computer applications in production and engineering. — 1997.1. P. 208—216.

56. Marczinski G. Tool Management Systems / Goetz Marczinski // Manufacturing engineering handbook. — 2004. —P. 16.1—16.17.

57. Gray A.E. A synthesis of decision models for tool management in automated manufacturing / A.E. Gray, A. Seidman, K.E. Stecke // Manag. Sci. — 1993.

58. Vol. 39. — № 5. — P. 549—567.

59. Turkcan A. Due date and cost-based FMS loading, scheduling and tool management / A. Turkcan, M. S. Akturk, R. Storer // Int. J. Prod. Res. — 2007.

60. Vol. 45. —№5. —P. 1183—1213.

61. Локтев A. Tool Management / А. Локтев, Д. Локтев // Стружка — 2006. — №3 (14). —С. 28—29.

62. Локтев A. Tool Management. Организационные и технические меры по организации системы инструментообеспечения / А. Локтев // Стружка. — 2006. — №4 (15). — С. 32—34.

63. Graver Т. W. A tool provisioning problem in FMS / Т. W. Graver, L. F. McGinnis // Int-1 J. of FMS. — 1989. — № 1. — P. 239—254.

64. Описание ERP систем. URL: http://ru.wikipedia.org/wiki/ERP (дата обращения 28.11.2009)

65. MRP II планирование производственных ресурсов. URL: http://itc.ua/articles/mrp ii planirovanie proizvodstvennyh resursov 2346 (дата обращения 28.11.2009)

66. Modell Martin E. A Professional's Guide to Systems Analysis, Second Edition / Martin E. Modell. — New York: McGraw-Hill Book Company, 1996.

67. ТПУ 21.20.1-87. «Организация и ведение кодирования инструментария. Основное производство». — Набережные Челны: ОАО «КАМАЗ», 1987.

68. Люгер Д.Ф. Искусственный интеллект 2003. Стр. 307

69. Коффман А. Сетевые методы планирования и их применение / А. Коффман, Г. Дебазей. — М.: Прогресс, 1968. — 182 с.

70. Саати Т. Принятие решений. Метод анализа иерархий (1993)

71. В.В.Псиола О приближенном решении 3-х мерной задачи об упаковке на основе эвристик. URL: htQ3://www.intsys.msu.ru/magazine/archive/vll(l-4ypsiola-083-100.pdf (дата обращения 12.11.2009)

72. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.

73. М. Липский Комбинаторика для программистов. М.: Мир, 1988.

74. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

75. Загороднев, Д.И. Исследование методов решения транспортных задач при управлении материальными потоками предприятия / Л.А. Санакулова, Д.И. Загороднев, А.И. Салахеева // Социально экономические и технические системы. - 2009. — № 4. - URL: http://sets.ru

76. Загороднев, Д.И. Унификация форм заявки в автоматизированной системе планирования грузоперевозок на машиностроительном предприятии / Д.И. Загороднев, Л.Т. Шарйфянова // Сборник трудов

77. Международной научно-технической и образовательной конференции (28-31 марта 2010 года) Часть 1. Книга 1. Набережные Челны: 2010. - С. 191-193.

78. Загороднев, Д.И. Исследование показателей систем управления сварочного оборудования / Д.И. Загороднев // Социально -экономические и технические системы. 2010. - № 3. - URL: http://sets.ru

79. ООО ЛИНКОР423822 РФ РТ пр.Московский 51/38-13 тел/факс (8552) 70-65-95 Официальный эксклюзивный представитель LINCOLN GmbH and Co.KG в Поволжье РАЗРАБОТКА ПОСТАВКА МОНТАЖ СЕРВИСНОЕ ОБСЛУЖИВАНИЕ ЦЕНТРАЛИЗОВАННЫХ СИСТЕМ СМАЗКИ

80. УТВЕРЖДАЮ льный директор ООО ЛинкОр В.АОбухов ября 2010 г.

81. Акт №07 от 21 октября 2010 г. об использовании материалов диссертационной работы на соискание ученой степени кандидата технических наук Загороднева Дмитрия Ивановича

82. Методика построения оптимальных маршрутов на основе модифицированных алгоритмов Кларка-Райта и Дейкстры с использованием эвристических критериев;

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

84. Председатель комиссии: Технический директор

85. Члены комиссии:1 Нач. производства1. Зам.нач.производства1. А.К.Фазлыев1. Д.Д.Ханов М.А.БряндинтоегайкожАж фвдизращшшо государственной регистрации программы для ЭВМ2010614058

86. Автоматизированная система управления материальными потоками предприятия на основе эвристических алгоритмов

87. Правообладатель(ли): Загороднев Дмитрий Иванович (Ни) Симонова Лариса Анатольевна (Ш1)

88. Автор(ы): Загороднев Дмитрий Иванович Симонова Лариса Анатольевна (1111)1. Заявка № 2010613066

89. Дата поступления 31 мая 2010 Г. Зарегистрировано в Реестре программ для ЭВМ23 июня 2010 г.

90. UINT DejkstraGetMinVertex(void) {

91. UINT min = 0; // индекс вершины с минимальной меткой bool blnitOK = false;assert(NULL != VertexList);