Реферат

Содержание

1.   1.     Общая постановка проблемы
2.   2.     Описание объекта исследования
3.   3.     Аналитическая постановка задачи
4.   4.     Математическая постановка задачи
5.   5.     Обзор методов и алгоритмов
6. 5.1     Теория расписаний
7. 5.2     Метод ветвей и границ
8. 5.3     Диаграмма Гантта
9. 5.4     Муравьиные алгоритмы
10. 5.5     Генетические алгоритмы
11.   Выводы
12.   Список литературы

1. Общая постановка проблемы

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

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

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

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

– Многочисленность номенклатуры изделий;
– Нестабильность объёмов производства;
– Различные отклонения производственного процесса от заданного ритма.

2. Описание объекта исследования

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

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

– Организация сбора данных о работе обрабатывающих станков и другого производственного оборудования;
– Распределение выполнения производственных заказов по оборудованию и отслеживание выполнения заказов;
– Формирование электронных паспортов партий, содержащие данные о том, кто, когда, на каком оборудовании и из каких материалов сделал то или иное изделие;
– Выполнение мониторинга работы станков, обрабатывающих центров, промышленных роботов, оснастки для подсчёта времени наработки и контроля значений технологических параметров (температура, давление, время цикла и т.д.);
– Отображение текущего состояния оборудования на рабочих местах пользователей или на больших экранах, расположенных в цехах;
– Ведение централизованной базы технической документации и управляющих программ, а также пересылка управляющих программ в системы управления станками. [2]

Используя язык UML, можно представить функции компьютеризированной системы в следующем виде (см.рис.1):

Рисунок 1 – Функции компьютеризированной системы

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

Система СПУ охватывает три стадии организации производства:

– предварительную (исходную) стадию;

– стадию разработки и оптимизации сетевого графика;

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

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

Стадия разработки и оптимизации включает:

– расчленение всего комплекса работ на этапы и выдача заданий исполнителям на составление фрагментов сетевой модели по каждому этапу;

– составление перечня работ с описанием их содержания;

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

– определение последовательности и параллельности выполнения работ;

– построение локальных сетевых графиков (фрагментов) по этапам;

– построение («сшивание») локальных графиков в комплексную (сводную) сетевую модель;

– расчет основных параметров сетевой модели и ее оптимизация;

– оформление документов и доведение заданий и сроков выполнения работ до исполнителей.

В большинстве случаев в качестве решающего фактора принимается фактор времени. В этом случае основными параметрами сетевого графика являются:

– продолжительность работ;

– ранние и поздние сроки наступления событий;

– критический путь;

– резервы времени по событиям. [3]

3. Аналитическая постановка задачи

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

Для решения этой задачи используется следующая входная информация:

– состав конструкций изделий;

– наличие и возможности обрабатывающего оборудования и персонала;

– заказанное количество изделий;

– директивные сроки изготовления.

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

Рисунок 2 – Технологический процесс

(анимация: 4 кадра, циклов повторения - цикличный , размер 148.034 Кб)

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

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

4. Математическая постановка задачи

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

Пусть:

n – количество станков, которые задействованы в технологическом процессе,
tпij, tфij – плановое, фактическое время обработки i-детали на j-ом станке, где i=(1,2,…,k), j=(1,2,…,n),
Δtпр – время простоя j-го станка.

Тогда целевая функция будет иметь следующий вид:

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

На вышеописанную целевую функцию влияет ряд ограничений.

Пусть Тдi, Тфi – директивный и фактический срок изготовления i-детали,
Nнi, Nфi – необходимое и фактическое количество обработанных деталей,
i – партий деталей,
tlk – длительность технологической операции k над деталью l,
ml – общее количество операций над деталями,
тогда все ограничения будут иметь следующий вид:

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

– изготовление детали должно быть выполнено в срок, т.е. фактический срок изготовления детали не должен превышать директивный;

– работа должна быть выполнена в полном объёме, т.е. количество фактически обработанных деталей должно быть равно необходимому;

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

Кроме этого, имеются дополнительные ограничения, которые заранее не всегда возможно учесть:

– капитальный ремонт оборудования;

– плановый осмотр оборудования;

– отсутствие персонала.

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

5. Обзор методов и алгоритмов

5.1 Теория расписаний

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

Задачи расписания (планирования) обработки n деталей на m станках, известная как задача Джонсона, по имени автора, предложившего простой алгоритм поиска оптимальной последовательности запуска деталей в обработку для двух и, в частном случае, трех станков, относится к классу экстремально - комбинаторных задач и является одной из сложнейших оптимизационных задач. Суть задачи в том, что имеется деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом -ая деталь обрабатывается на первом станке за времени, а на втором — за времени. Каждый станок в каждый момент времени может работать только с одной деталью. Требуется составить такой порядок подачи деталей на станки, чтобы итоговое время обработки всех деталей было бы минимальным.

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

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

5.2 Метод ветвей и границ

Метод ветвей и границ – один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи. [5]

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

5.3 Диаграмма Гантта

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

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

5.4 Муравьиные алгоритмы

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

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

Рисунок 3 – Логика муравьиных алгоритмов [9]

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

5.5 Генетические алгоритмы

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

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

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

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

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

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

Выводы

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

Список литературы

1. Тюленев Л.В. Организация и планирование машиностроительного производства: Учебное пособие / Л.В. Тюленев. – СПб: Бизнес-пресса, 2001. – 304 с.
2. Михайлова Л.В. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме / Л.В. Михайлова, Ф.И. Парамонов, А.В. Чудин. – М.: ИТЦ МАТИ, 2002. – 60 с
3. Календарное планирование и оперативное управление производством и процессами. программирования [Электронный ресурс] – Режим доступа: https://studfiles.net/preview/404204/page:10/#18
4. Методы оптимизации расписаний параллельных обслуживающих систем [Электронный ресурс] – Режим доступа: http://www.swsys.ru/index.php?page=article&id=108
5. Комбинаторные методы [Электронный ресурс] – Режим доступа: http://studbooks.net/2274360/informatika/kombinatornye_metody
6. Штовба С.Д. Муравьиные алгоритмы // Научно-практический журнал Exponenta Pro. Математика в приложениях. – 2003. – № 4. – С. 70-75.
7. Генетический алгоритм [Электронный ресурс] – Режим доступа: http://mirznanii.com/a/313173/geneticheskiy-algoritm
8. Anna Ławrynowicz Genetic Algorithms for Solving Scheduling Problems in Manufacturing Systems [Электронный ресурс] – Режим доступа: https://content.sciendo.com/view/journals/fman/3/2/article-p7.xml
9. Ошурков В.А., Макашова В.Н. Оперативное планирование производства в MES-системах с использованием методов и алгоритмов искусственного интеллекта [Электронный ресурс] – Режим доступа: https://cyberleninka.ru/article/v/operativnoe-planirovanie-proizvodstva-v-mes-sistemah-s-ispolzovaniem-metodov-i-algoritmov-iskusstvennogo-intellekta
10. Стрельников Е.А., Светличная В.А. Анализ методов сетевого планирования для АСУ загрузкой механического оборудования. / Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2018) / Материалы IX международной научно-технической конференции – Донецк: ДонНТУ, 2018г. – с. 11-15. Режим доступа: http://iuskm.donntu.ru/electronic/iusmkm2018.pdf