БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра менеджмента
РЕФЕРАТ
на тему:
«ОПТИМИЗАЦИЯ МОДЕЛЕЙ ПРОЦЕССОВ ПРОИЗВОДСТВА»
МИНСК, 2008
В условиях оживления и развития отечественной промышленности существенно возрастает интерес к проблемам организации производства, и в частности, к задачам оперативно-календарного планирования.
Календарные планы работы отдельных производственных ячеек предприятия представляют собой расписания изготовления всех изделий, загрузки оборудования и рабочих мест. Производственная ячейка - часть производственного пространства (станки, участок), на котором соответствующим образом организованы производственные ресурсы и процессы.
Основными параметрами календарных графиков являются: приоритетность работ (очередность запуска изделий в обработку), размер партий запуска и время опережения начала обработки изделий на связанных рабочих местах, размер незавершенного производства. Результатом составления оптимального календарного графика является определение наименьшей длительности производственного цикла, оказывающей существенное влияние на улучшение экономических результатов деятельности предприятия. В этом случае происходит снижение объема оборотных средств в незавершенном производстве, уменьшаются простои оборудования и рабочих.
В производственных подразделениях машиностроительных предприятий календарное планирование в настоящее время основано главным образом на моделировании, позволяющем обеспечить пропорциональность, непрерывность, устранить «узкие места» и правильно установить приоритеты работ. Следует отметить, что установление очередности запуска изделий в производство является одной из основных задач, которую необходимо решить при составлении оптимального календарного графика.
В силу этого, в качестве критерия оптимальности моделей целесообразно использовать минимизацию длительности совокупного производственного цикла. Под моделью производственного процесса понимается его пространственное построение, отражающее технолого-организационную суть последнего через организационную структуру. Под моделью плана производства - количественно-временная организация предметов труда в ходе производственного процесса. Под моделью оперативного управления (части управляющей системы - надстройки) - функциональное выделение той части управляющей системы, которая предназначена для удержания существующих переменных управляемого объекта в заданных планом пороговых значениях.
Все существующие методы решения задач календарного планирования по степени достижения экстремального результата подразделяются на две четко выраженные подгруппы - точных и приближенных решений.
К числу опробованных точных методов решения задачи моделирования относятся методы линейного и динамического программирования, комбинаторные методы дискретного программирования и др.
Метод линейного программирования удачно использован С.М. Джонсоном для решения задачи нахождения оптимального по календарному времени плана обработки m деталей на двух станках. Алгоритм Джонсона чрезвычайно прост. Выбирается самое короткое операционное время, и если оно относится к первому станку, планируют выполнение задания первым на первом станке, а если ко второму - то последним. Затем процедура повторяется до полного перебора всех заданий на обоих станках. Имеются многочисленные обобщения правила Джонсона для различных случаев трехстадийной обработки деталей. Однако этот алгоритм неприменим для случаев обработки деталей на большем количестве станков.
Метод динамического программирования удачно использован Р. Беллманом для однооперационного производства. Он дал частное решение задачи оптимального календарного планирования обработки совокупности изделий, имеющих одинаковый процесс производства, но различных по длительности операций обработки. Запуск изделий в производство необходимо осуществлять, соблюдая условие: min(t11
,
t
22
) < min(
t12
,
t
21
),
где: t11
- трудоемкость выполнения первой операции над изделием, первым запускаем в производство; t
22
- трудоемкость выполнения второй операции над изделием, вторым запускаем в производство, а t12
и t
2
l
-
соответственно наоборот.
Метод «ветвей и границ», являющийся комбинаторным методом дискретного программирования, предполагает уменьшение множества допустимых решений, вплоть до получения конечного множества, при котором оказывается возможным применение метода перебора. В этом методе происходит последовательный выбор пары номеров деталей для получения оптимальной последовательности. Составление последовательности номеров деталей для запуска в производство происходит в процессе работы итерационного алгоритма. На каждой итерации выбираются две детали и помещаются на позиции: (n+ 1) и (d– n), где n - номер итерации, ad- количество наименований деталей, участвующих в производственном процессе. Эффективность метода «ветвей и границ» зависит от уровня, на котором происходит «отсечение» ветви. В общем случае этот метод не исключает полный перебор всех возможных вариантов.
Типичные модели линейного, линейного целочисленного и квадратичного целочисленного программирования свидетельствуют о том, что в них могут быть отражены многие ограничения задачи календарного планирования. В частности, в этих моделях, в форме ограничений на переменные, могут быть выражены требования, накладываемые на сроки выпуска этих деталей. Допускается обработка деталей партиями, но для этого необходимо некоторое предварительное преобразование исходной информации.
Данные модели имеют ограниченное применение при моделировании производственных процессов. Главным недостатком является быстрый рост размеров моделей с ростом задачи календарного планирования. Точные методы оптимизации применимы лишь для частных и небольших по размеру задач. На машиностроительных предприятиях составление оптимального календарного графика усложняется широтой номенклатуры выпускаемых изделий и является динамической, вероятностной задачей большой размерности. Поэтому наряду с разработкой точных методов интенсивно развиваются приближенные методы.
К числу приближенных методов оптимизации задач календарного планирования относятся: частичный и направленный перебор, метод Монте-Карло, аналитико-приоритетные, эвристические и др. методы.
Метод Монте-Карло аналогичен методу перебора и оценки вариантов с той разницей, что оценивается некоторое ограниченное подмножество вариантов, выбор которых производится некоторым случайным образом. Решение задачи календарного планирования методом Монте-Карло можно рассматривать как некоторую задачу статистического моделирования производственного процесса. Метод Монте-Карло имеет ограниченное применение, так как может потребовать перебора и оценки достаточно большого количества вариантов.
В последнее время к решению задач календарного планирования стала привлекаться теория массового обслуживания. Такая возможность появилась в связи с развитием специальной теории очередей с приоритетом. Однако если в задачах массового обслуживания поток требований на обслуживание является свободным процессом, то в задачах календарного планирования требования поступают в детерминированном порядке. Вместе с тем при прохождении требований (партии деталеопераций) через большое количество обрабатывающих устройств (производственных ячеек) происходят задержки в обслуживании, и поступление требования на следующее обрабатывающее устройство может быть рассмотрено как случайное событие. В таком плане эта связь теории расписаний с задачами теории очередей с приоритетом обслуживания может быть использована как средство приближенного решения теории расписаний.
Многие задачи календарного планирования относятся к классу задач, для которых трудна конкретная аналитическая постановка, неярко выражена величина критерия эффективности и отсутствуют эффективные алгоритмы численного решения. Последнее связано с тем, что минимизируемые функции комбинаторных задач лежат не в непрерывной области переменных, а на различных дискретных перестановках элементов. Следовательно, применение приближенных методов, основанных на сочетании аналитических принципов и моделировании календарных планов с использованием правил предпочтительности, является наиболее перспективным направлением практического решения данного класса задач.
Среди приближенных методов различают большую группу аналитико-приоритетных методов. Аналитико-приоритетные методы не следует смешивать с эвристическими. В аналитико-приоритетных методах имеется математическая модель с соответствующей функцией - критерием, что позволяет приблизить решение к оптимальному, тогда как в эвристических методах такая функция отсутствует, либо имеется в неявно выраженной форме или же задается как локальная функция приоритета. Эвристические методы строятся на использовании установленных свойств и приемов решения задач других смежных групп, а также интуитивных свойств и приемов поиска.
Можно выделить семь наиболее удачных правил предпочтительности для формирования приоритетов календарного планирования последовательности работ1
.
1. FCFS (Fist - Come, Fist - Served) - первым вошел - первым обслужен. Работы выполняются в порядке поступления в подразделение.
2. SOT (Short'sOperatingTime) - по кратчайшему времени выполнения. Сначала выполняется работа с самым коротким временем выполнения, затем процедура повторяется для оставшихся работ.
3. Ddate (DueDate) - по установленным срокам окончания. Первой выполняется работа с самой ранней датой начала выполнения.
4. SD - по ранней дате начала выполнения, определяемой как установленная дата выполнения работы, минус время выполнения работы.
5. STR (SlackTimeRemaining) - по наименьшему оставшемуся запасу времени, который вычисляется как разность между временем, остающимся до установленной даты выполнения, и временем выполнения работы.
6. STR/OP (SlackTimeRemainingperOperation) - по наименьшему оставшемуся запасу времени на одну операцию, которое определяется как разность времени, оставшегося до установленной даты выполнения работ, минус время оставшихся операций, деленная на количество оставшихся операций. Заказы с самым коротким STR/OP выполняются первыми.
7. LCFS (Last - Come, First - Served) - последним вошел - первым обслужен. Первой выполняется работа, поступившая последней в подразделение.
Иногда используют различные комбинации функций предпочтения, но это требует многовариантного перебора. В результате отработки информации, полученной при выполнении на модели серии экспериментов каждый раз с новым правилом очередности, были выявлены законы распределения и другие оценки наиболее вероятных длительностей производственных циклов, ________________________
1
Donald W. Fogarty, Yohn H. Blackstone, Yr. And Thomas R. Hoffman. Production and Inventory management (Cincinnati: South - Western Publishing, 1991). P. 452 - 453.
опозданий в выполнении работ по сравнению с плановыми сроками, объемом незавершенного производства, простоев оборудования и т.д. Однако при проведении оптимизации метод не учитывает взаимного влияния моментов начала и окончания смежных операций на разных станках, что значительно снижает степень оптимальности полученного результата.
В условиях многопредметных автоматизированных производственных систем задача построения календарных графиков существенно усложняется. Решение задачи формирования графика производства деталей (парий деталей), имеющих произвольное число и очередность выполнения операций и запланированных к изготовлению на одном и том же технологическом оборудовании является комбинаторной задачей большой размерности.
В этих условиях наиболее удачным методом является аналитический метод, учитывающий взаимное влияние пооперационных трудоемкостей обработки деталей на совокупный цикл их обработки. Метод предполагает оптимизацию длительности совокупного цикла обработки партий (групп) деталей путем анализа и минимизации величин смещения. При этом суммарное время опережения запуска деталей в обработку на каждой технологически связанной паре рабочих мест дифференцируется на две составляющие, первая из которых учитывает несинхронность операций технологических процессов обработки деталей, а вторая - время обработки передаточных партий деталей.
В этом случае задача моделирования сводится к тому, чтобы время опережения начала и окончания обработки партий деталей каждого наименования на передающем и получающем детали рабочих местах обеспечивало непрерывную обработку партий деталей с максимальной параллельностью.
Длительность производственного цикла обработки партий деталей в рассматриваемой постановке решения задачи может быть определена по формуле
(1)
где - номер рабочего места, начинающего процесс обработки деталей данной группы;
k
- номер рабочего места, на котором заканчивается процесс обработки деталей данной группы;
m
- количество групп деталей;
d
- количество деталей в группе;
- величина смещения на j
-м рабочем месте, на котором начинается процесс обработки i
-й партии деталей;
- величина смещения на j
-м рабочем месте, на котором заканчивается процесс обработки i
-й партии деталей;
- время обработки групп деталей на рабочем месте, завершающем процесс обработки, следующих за r
-й группой;
- время обработки деталей групп, предшествующих r
-й группе деталей на рабочем месте, начинающем процесс обработки;
- время обработки партий деталей, предшествующих i
-й партии деталей на рабочем месте, начинающем процесс обработки;
-
время обработки партий деталей, обработка которых следует заобработкой партии деталей i
-ro наименования на рабочем месте, завершающем процесс обработки.
Поскольку время обработки передаточных партий от очередности их обработки не зависит, критерием оптимизации является:
В первую очередь следует запускать в обработку партию деталей, которая обеспечивает наименьшую составляющую в общем смещении. Метод предполагает проведение пошаговой оптимизации: на каждом шаге ищется для партий деталей, очередность которых еще не определена. Величина зависит от , которое определяется как сумма положительных разностей (). Здесь - соответственно время обработки партии деталей на передающем и получающем рабочих местах связанной пары.
Следует учитывать, что положительная разность () времени обработки детали n
-й очереди запуска компенсируется лишь тогда, когда модуль отрицательной разности времени обработки детали (n
+ 1)-й очереди равен или больше разности ()детали n
-й очереди запуска.
Таким образом, при определении любой n
-й очереди запуска необходимо проводить анализ знака разности времени обработки всех оставшихся деталей на всех парах связанных рабочих мест. Связи, у которых эти разности имеют знак плюс, из дальнейшего анализа следует исключать. Это же относится к связям, у которых все разности имеют только отрицательные значения.
На основании анализа разностей () на технологически связанных парах рабочих мест и учитывая то, что эти разности со знаком минус являются компенсаторами, т.е. способны «гасить» положительные разности () деталей следующей очереди обработки, можно сформулировать правила, позволяющие улучшить полученные результаты оптимизации.
1. Если при очередной итерации окажется несколько минимальных значений , то в первую очередь запускается деталь, у которой сумма отрицательных разностей () по модулю наибольшая, так как она имеет большее значение компенсаторов.
2.Если при очередной итерации у i
-й детали на данной связанной паре рабочих мест разность () со знаком плюс по модулю больше суммы разностей () со знаком минус, то в этом случае в значении найденной суммы следует учитывать только абсолютную величину суммы отрицательных разностей.
3. Если при очередной итерации определения очередности запуска деталей в обработку оказывается, что i
-я деталь имеет у всех связей только положительные разности (), то такую деталь следует запускать в последнюю очередь, так как у этой детали нет компенсаторов.
Исследование большого объема статистических данных автоматизированного решения задачи показывает, что использование приведенных правил, улучшающих алгоритм поиска оптимальной очередности запуска деталей в обработку, приводит к уменьшению длительности производственного цикла на 40-50 %.
Результатом моделирования является формирование календарного расписания рабочих мест производственной системы, в котором учитывается информация о затратах времени на наладку и переналадку оборудования, принятый размер партии запуска и время смещений запуска деталей в обработку относительно первого рабочего места системы.
Для оптимизации размера партий, запускаемых в обработку деталей, может быть предложена следующая формула:
, (2)
где р
- размер партии запуска деталей в обработку, компл.;
Е
- коэффициент эффективности капиталовложений;
S
обj
- стоимость оборудования j-ro наименования, р.;
t
пз
- подготовительно-заключительное время по каждому j-му виду оборудования на весь комплект обрабатываемых на нем деталей, ч.;
k
- количество единиц оборудования производственной системы, шт.;
tштj
- штучное время обработки всего комплекта деталей на данном j-м оборудовании, ч./компл.;
М
- затраты материалов (заготовок) на комплект деталей, р./компл.;
Зк
- заработная плата рабочих за изготовление комплекта деталей, обрабатываемых производственной системой, р./компл.;
КТ
- коэффициент технической готовности незавершенного производства;
Зч
- среднечасовая зарплата рабочих, р./ч.
Литература
1. Михайлова Л.В., Парамонов Ф.И., Чудин А.В. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме. М.: ИТЦ МАТИ, 2002.- 60 с.
|