Моделирование материальных потоков в рамках интегрированной системы управления производством машиностроительного предприятия на основе эвристических алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат наук Загороднев, Дмитрий Иванович

• Загороднев, Дмитрий Иванович
• кандидат наук
• 2010

Оглавление диссертации кандидат наук Загороднев, Дмитрий Иванович

СОДЕРЖАНИЕ

Введение

Глава 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 Приложение 4

Введение диссертации (часть автореферата) на тему «Моделирование материальных потоков в рамках интегрированной системы управления производством машиностроительного предприятия на основе эвристических алгоритмов»

ВВЕДЕНИЕ

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

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

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

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

В.Н., Саати Т., Попов Э.В., Мамиконов А.Г. и др.; в области моделирования процессов 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. Формирование основных положений и требований к моделированию материальных потоков в рамках интегрированной системы управления производством машиностроительного предприятия

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

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

Системы ERP охватывают все ключевые процессы деятельности предприятия. Применительно к управлению материальными потокам такие системы выполняют ведение конструкторских и технологических спецификаций, определяющих состав материальных ресурсов и операций, необходимых для изготовления производимых изделий; планирование потребностей в материалах и комплектующих, сроков и объёмов поставок для выполнения плана производства продукции; управление запасами и закупками [68].

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

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

Рисунок 1.1. Организационная структура крупного территориально распределенного машиностроительного предприятия

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

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

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

Таблица 1.1 - Сравнительный анализ систем управления машиностроительным предприятием с точки зрения задач управления материальными потоками.

----—Системы Задачи —-——__ Ргеас1ог Фобос ХепНЪ 8РР8

Прямое, обратное и двунаправленное планирование + - -

Планирование с учетом критериев (приоритеты, даты) + + +

Работа с конечными и бесконечными ресурсами, поддержка сменных календарей + + -

Модуль динамического управления доступностью материалов + + +

Сервер управления цепочками поставок + - -

Распределенное межзаводское планирование + - -

Возможность моделирования материальных потоков в условиях различных режимов работы оборудования и различных сроков запуска деталей в обработку - + +

В настоящее время среди машиностроительных предприятий используется достаточно большое количество комплексных интегрированных систем управления на разных уровнях [1, 2, 3]. Был произведен сравнительный анализ используемых на российском рынке систем управления. С точки зрения моделирования материальных потоков для рассмотренных систем были определены их основные функциональные задачи (Таблица 1.1). В качестве анализируемых систем управления были выбраны: MES-системы Фобос [1], Preactor [2]; Zenith SPPS [3].

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

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

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

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

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

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

- интеллектуализацию алгоритмов решения и широкое применение эвристических методов;

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

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

Задачи, решаемые в области моделирования маршрутов, часто отличаются повышенной сложностью и являются так называемыми ЫР-сложными задачами (задача с нелинейной полиномиальной оценкой числа итераций решений) [6]. В связи с этим традиционные методы решения задач, хорошо зарекомендовавшие себя, здесь оказываются бессильны — сказывается повышенная

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

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

- объемно-массовые характеристики планируемых к транспортировке

грузов;

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

- суммарный пробег транспортных средств;

- суммарная продолжительность работы и др.

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

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

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

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

Значительные исходные; размеры задач. Это свойство особенно характерно для крупных ¡промышленных центров, где насчитывается большое число автотранспортных организаций, поставщиков и потребителей. Наличие большого числа существенных ограничений, неучет которых может при вести к недопустимым; вариантам транспортировки: [13]. Это, прежде всего ограничения по времени, работы транспортного1 средства на линии, времени простоя- под: погрузкой и разгрузкой, времени вызова и доставки грузов, зависимости между типом транспортного средства и видом груза и т.д [9, 10, 11,12].

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

обработку информации и приводит к определенным отклонениям от наилучших

результатов [10, 12].

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

В настоящее время используется достаточно большое количество систем

планирования маршрутов. Был произведен сравнительный анализ используемых на российском рынке систем (Таблица 1.2), приведены преимущества и недостатки каждой из рассмотренных систем. В качестве анализируемых систем были выбраны: «БИТ: НОВА Управление транспортной логистикой»[14], <<Кс1п11оЩ:е>>[15], «Деловая карта»[16], «Тор11оШ;е»[17].

Таблица 1.2 Сравнительный анализ используемых на российском рынке систем планирования маршрутов.

Программы/фирмы Преимущества Недостатки

БИТ: НОВА Автоматическое/ручное При осуществлении

Управление планирование маршрутов. мелкопартионных

транспортной Использование систем перевозок

логистикой ред. 3.2. ОР 8 -мониторинга для планирование загрузки

минимизации затрат необходимо определять

(отслеживания маршрутов, вручную.

скорости движения

транспорта, учета расхода

топлива) и безопасности

движения.

КёпЯснйе Позволяет выполнять поиск Варианты построения

возможных вариантов по 6 оптимальных

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

товаров по автомобилям и 6 машин представлены

методам по критерию отдельно друг от друга.

минимума пройденного

пути.

Деловая карта Возможность разбиения Для

маршрутов и добавления к машиностроительных

ним «попутных» заказов. предприятий возникает

Минимизация общего проблема разбиения

времени выполнения зоны обслуживания на

заказов клиентов сектора развозки и

ТорЯо^е Обеспечивает расчет оптимального

средней удельной закрепления этих

стоимости доставки секторов за

единицы груза. распределительными

центрами или

складами.

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

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

маршрутизации [19].

1

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

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

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

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

Результаты анализа, проведенного по методам решения задач маршрутизации сведены в таблицу 1.3 [20, 21, 22, 23, 24, 25, 26]. Поставленная тестовая задача была решена различными методами, результаты оценивались по наиболее значимым характеристикам.

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

Таблица 1.3 - Анализа методов решения задач маршрутизации.

Метод Результаты Протяженность полученного экспериментально го маршрута, км Точность по отношению ко всем методам Точность по отношению к правильному решению

Метод Кларка-Райта Общая протяжённость маршрута - 978 км. Плюсы -простота реализации метода, гибкость (при наличии дополнительных факторов, алгоритм решения можно перестраивать), применим и для большого числа точек. Минус - при решении из маршрутов «выпали» 2 населенных пункта. 1071 47% 41%

Метод имитации отжига Общая протяженность маршрута - 501 км. Плюсы -хорошие результаты при незначительном уменьшении параметра «температура». Минусы - эффективен при небольшом количестве точек, располагающихся последовательно на небольших расстояниях друг от Друга. 640 78% 73%

Алгоритм Прима Общая протяженность маршрута - 500 км.. Плюсы -простота, программная реализуемость, учет всех вершин, определенное количество шагов. Минусы - не обеспечивает цикличность графа; не учитывает двойного прохождения пути, из-за чего происходит выбор неоптимального маршрута. 500 100% 98%

Генетичес кий алгоритм Общая протяженность маршрута - 285 км (решение неверно). Плюсы - программная реализуемость, учет всех вершин. Минусы - не обеспечивает связность графа, а следовательно, получение оптимального пути; не обеспечивает цикличность графа; количество шагов алгоритма неопределенно. 611 82% 86%

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

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах [32, 33, 34, 35, 36]. Алгоритм нахождения кратчайшего пути (кратчайшей цепи) входит в качестве отдельного этапа подзадачи во многие вычислительные схемы оптимизации для экстремальных задач на графах [37, 38, 39]. Поэтому в литературе по этому вопросу можно найти описания алгоритмов, принадлежащих различным авторам: Беллман [27], Дийкста [29, 31, 40], Форд и Фалкерсон [28], Данциг [26], Ен [25]и др.

Сравнительный анализ различных алгоритмов нахождения оптимального маршрута на графе приведен в таблице 1.4[27, 28, 29, 30, 31]

Таблица 1.4 - Сравнительный анализ различных алгоритмов нахождения

оптимального маршрута на графе.

Алгоритм Ограничения Сложность алгоритма Количество итераций алгоритма для нахождения кратчайшего пути в графе из 30 вершн

Дейкстры Граф без ребер с отрицательными весами 0(п2 +'ш); 0(п^п + т^п); 0(п^п + т) 930 88 74

Беллмана -Форда - от Х\Е\) 900

Флойда-Уоршелла - 0(п) 27000

Джонсона Недопустимы циклы в графе с отрицательным весом 0(V2logV+ ГЕ); О(УЕ^У) 39882 1329

Проведенный анализ показал, что эффективность некоторых алгоритмов можно улучшить за счет применения специализированных методов [41, 31]. Среди рассмотренных алгоритмов, наиболее приемлемым по скорости работы оказался алгоритм предложенный Дейкстрой. Для нахождения кратчайшего маршрута в дорожном графе размерностью 500000 вершин; алгоритму потребуется 3 миллиона машинных операций, что неприемлемо для систем моделирования материальных потоков, т.к. динамические корректировки маршрутов могут производиться очень часто из-за изменяющихся условий, а размерность дорожного графа является большой.

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Загороднев, Дмитрий Иванович

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

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

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

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

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

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

Заключение

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

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

Список литературы диссертационного исследования кандидат наук Загороднев, Дмитрий Иванович, 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- com_content& task=view&id= 14&Itemid=l (дата обращения 02.04.2009)

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

18.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.

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

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

%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.Ананий В. Левитин Глава 8. Динамическое программирование: Алгоритм Флойда поиска кратчайших путей между всеми парами вершин // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — M.: «Вильяме», 2006. — С. 349 — 353

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

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

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

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

Ъ5.Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)

3б.Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664. (М.: Наука, 1987. 383с.)

37.Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429с.

38Юре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.

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

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

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

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

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

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

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

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

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

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

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

50.Роберт Седжвик. Фундаментальные алгоритмы на С++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in С++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688.

51 .Ананий В. Левитин Глава 3. Метод грубой силы: Задача о рюкзаке// Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — M.: «Вильяме», 2006. — С. 160-163.

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

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

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

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

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

56.Симонова Л. А. Интегрированное информационное обеспечение процесса управления технологическими маршрутами в рамках ERP-системы: монография / Л. А. Симонова, М. П. Руднев. — М.: Изд-во Academia ( при участии редакции журнала « Вестник РАН»). — 2005. — 282 с.

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

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

59.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.

60.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.

61.Narang R.V. A computer model for tool management information system / R.V.. Narang // Computer applications in production and engineering. — 1997.

— P. 208—216.

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

63.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.

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

64.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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

79.Robert de Souza Tool Handling Strategies for flexible manufacturing systems / Robert de Souza // Flexible automation and integrated manufacturing. — 1993. — P. 403—414.

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

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

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

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

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

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

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

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

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

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

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

______

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

Комиссия в составе председателя комиссии - технического директора ООО ЛинкОр Фазлыева А.К. и членов комиссии - начальника производства Ханова Д.Д., замначальника произвоства Бряндина М.А,, констатирует, что диссертационная работа Загороднева Дмитрия Ивановича «Моделирование материальных потоков в* рамках интегрированной системы управления производством машиностроительного предприятия на основе эвристических алгоритмов» по своему содержанию рассматривает вопросы производственного характера, свойственные нашему предприятию, в диссертационной работе разработаны методики:

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

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

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

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

Члены комиссии:1 Нач. производства

Зам.нач.производства

А.К.Фазлыев

Д.Д.Ханов М.А.Бряндин

тоегайкожАж фвдизращшш

о государственной регистрации программы для ЭВМ

№ 2010614058

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

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

Автор(ы): Загороднев Дмитрий Иванович Симонова Лариса Анатольевна (1111)

Заявка № 2010613066

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

23 июня 2010 г.

Руководитель Федеральной службы по интеллектуальной собственности, патентам и товарным знакам

Б.П. Симонов

жГ ш ж ж

шшшшш ш

СВИДЕТЕЛЬСТВО

Промежуточная матрица

Общий вес: 17020

Промежуточная матрица

Промежуточная матрица

V- узд»-

UINTi;

for(i = 0; i < uiVertexCount+1; i++) // инициализация if(VertexList[i].bVisited = false) { min = i; blnitOK = true; break; };

if(bInitOK = true) for (; i < uiVertexCount+1; i++) if(VertexList[i] .bVisited = false &&

(VertexList[i].VertexVeight < VertexList[min].VertexVeight)) min = i;

return min; };

//---------------------------------------------------------------------------

//bool Dejkstra_GetNoVisitedPresent(void)

//{

// assert(NULL != VertexList); // // for (int i = 0; i < uiVertexCount; i++) // if(VertexList[i] .bVisited = false)

// return true; //

// return false; //};

//.--------------------------------------------------------------------------

//-------------------------------------------------------------------------

UINT Dejkstra_GetMinVertex(void) {

UINT min = 0; // индекс вершины с минимальной меткой bool blnitOK = false;

assert(NULL != VertexList);