Реферат по теме выпускной работы

Введение

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

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

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

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

Цель и задачи исследования

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

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

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

Актуальность

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

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

Запланированная научная новизна

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

Обзор исследований по теме

Отечественные

    По результатам поиска среди материалов портала магистров ДонНТУ были найдены работы Гливка А. Г., Хаустова Д. А., Сергеева Е. Ю., в которых расматривались проблемы оперативно-календарного планирования в различных отраслях. Из научных работ преподователей нашего университета по данной теме были найдены работы Секирин А. И.

    В целом по Украине было найдено множество работ по смежным областям с разрабатываемой подсистемой. Можно выделить также существующие разработки по данной теме: СПРУТ-ОКП и Zenith SPPS.

Зарубежные

    Основная масса работ по данной теме является зарубежной. Можно сделать вывод, что на западе данная тема намного лучше проработана, вследствии того, что там постоянно совершенствуются средства производства. Из зарубежных авторов можно выделить: M. Dorigo, G. Di Caro, Rong Zhou, Alan S. Manne. Из зарубежных готовых систем можно выделить: LEKIN и TACTIC.

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

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

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

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

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

    

    Для каждой операции есть деталь , которой она принадлежит, станок , на котором она должна быть обработана и продолжительность обработки операции , где - неотрицательное целое число. Каждая деталь - цепь операций, и каждая операция должна быть обработана на данном аппарате в течение данного времени. Задача состоит в том, чтобы найти стартовые времена всех операций таким образом, время завершения самой последней операции было минимально. Для каждой детали должна быть соблюдена последовательность операций и каждый станок может обработать только одну задачу за заданное время. Никакая операция не может быть прерванной; если она началась, то она должна быть закончена. Решение s случая задачи размерности n x m определяет порядок обработки относительно всех задач на каждом станке и неявно определяет время начала и завершения для каждой операции. Максимальное время завершения называют периодом обработки, и большинство исследований сводятся к проблеме минимизация периода обработки.

    Приведенный пример задачи мы можем связать с дизъюнктивным графом G=(V, A, E), где V набор узлов, A - соединительный набор дуг, и E - дизъюнктивный набор дуг. Узлы V соответствуют всем операциям и двум фиктивным узлам, источнику и выходом. Соединительные дуги A представляют отношения предшествования между операциями для каждой детали, а дизъюнктивные дуги E представляют все пары операций, которые будут выполнены на том же самом станке. Всем дугам, исходящих от узла, присваивается продолжительность обработки операции. У источника есть соединительные дуги с нулевой длинной для всех первых операций каждой детали, а у выхода есть соединительные дуги, исходящие из всех последних операций. Выполняемое планирование соответствует выбору одной дуги от каждой дизъюнктивной дуги и соединяется таким образом, чтобы получающийся направленный граф был нециклическим, то есть чтобы в нем не было петель. Проблема уменьшения периода обработки сводится к обнаружения ряда дизъюнктивных дуг которые минимизируют длину критического пути в направленном графе. [2]

Описание муравьиных алгоритмов

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

    В качестве иллюстрации возьмем задачу поиска кратчайшего пути между двумя узлами графа G=(V, E), где V – множество узлов (вершин), а E – матрица, которая представляет связи между узлами. Пусть - число узлов в графе. Обозначим – длину пути в графе, пройденного k-м муравьем, которая равна числу пройденных дуг (скачков между вершинами) от первой до последней вершины пути. Пример графа с выделенным путем представлен на рисунке 1. С каждой дугой, соединяющей вершины (i, j) ассоциируем концентрацию феромона .

Рисунок 1 Пример продвижения по графу (анимация: объем - 36кб, размер - 407Х264, количество кадров - 6, задержка между кадрами - 300 мс, количество циклов повторения - непрерывный цикл повторения).

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

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

(1)

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

(2)

Здесь – длина пути, построенного k-м муравьем в момент времени t. Таким образом, для каждой дуги графа концентрация феромона определяется следующим образом

(3)

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

Cхема работы алгоритма

    Приведем формализованный алгоритм работы данной системы:

1. Формирование графа производственного цеха с учетом необходимости обработки заданного числа деталей;
2. Инициализация параметров алгоритма;
3. Cоздание муравьиной колонии и размещение ее в начальном пункте;
4. Построение схемы переходов между вершинами графа;
5. Выбор наиболее оптимального маршрута (на основании ранее выбранных эвристик);
6. Обновление феромона.

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

    В алгоритме могут быть использованы различные критерии окончания, например:

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

Заключение

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

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

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

1. Система оперативно-календарного планирования автоматизированного механообрабатывающего мелкосерийного производства на основе комплексных моделей : диссертация д-ра техн. наук Загидуллина Равиля Рустэмбековича: 05.13.06 Уфа, 2006 448 с. РГБ ОД, 71:07-5/452.
2. Swarm Intelligence. Focus on Ant and Particle Swarm Optimization, 2007 I-Tech Education and Publishing.
3. Роевые алгоритмы, курс лекций, Скобцов Ю.А, 2009 г.
4. [202] M. Dorigo and G. Di Caro. The Ant Colony Optimization Meta-Heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 11-32. McGraw-Hill, 1999.
5. Donald W. Fogarty, Yohn H. Blackstone, Yr. And Thomas R. Hoffman. Production and Inventory management (Cincinnati: South - Western Publishing, 1991). P. 452 - 453.
6. Штовба С.Д. Муравьиные алгоритмы // Exponental Pro. Математика в приложениях, 2003, №4, с. 70-75
7. Официальный сайт СПРУТ-ОКП. URL: http://sprut.ru/productsandservices/mrpii
8. Официальный сайт Zenith SPPS. URL: http://www.zspps.com/soft.html
9. Личный сайт M. Dorigo. URL: http://iridia.ulb.ac.be/~mdorigo/HomePageDorigo/
10. Перечень научных статей G. Di Caro. URL: http://www.idsia.ch/~gianni/my_publications.html
11. Перечень научных статей Rong Zhou. URL: http://www2.parc.com/isl/members/rzhou/pub-cat.html
12. On the Job Shop Scheduling Problem. URL: http://ideas.repec.org/p/cwl/cwldpp/73.html
13. Официальный сайт LEKIN. URL: http://www.stern.nyu.edu/om/software/lekin/index.htm
14. Официальный сайт TACTIC. URL: http://www.waterloo-software.com/

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

© ДонНТУ 2010, Черный М.С.