БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра менеджмента

РЕФЕРАТ

на тему:

«ОПТИМИЗАЦИЯ МОДЕЛЕЙ ПРОЦЕССОВ ПРОИЗВОДСТВА»

МИНСК, 2008

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

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

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

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

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

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

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

Метод линейного программирования удачно ис­пользован С.М. Джонсоном для решения задачи на­хождения оптимального по календарному времени плана обработки m деталей на двух станках. Алго­ритм Джонсона чрезвычайно прост. Выбирается са­мое короткое операционное время, и если оно отно­сится к первому станку, планируют выполнение зада­ния первым на первом станке, а если ко второму - то последним. Затем процедура повторяется до полного перебора всех заданий на обоих станках. Имеются многочисленные обобщения правила Джонсона для различных случаев трехстадийной обработки деталей. Однако этот алгоритм неприменим для случаев обра­ботки деталей на большем количестве станков.

Метод динамического программирования удачно использован Р. Беллманом для однооперационного производства. Он дал частное решение задачи опти­мального календарного планирования обработки со­вокупности изделий, имеющих одинаковый процесс производства, но различных по длительности опера­ций обработки. Запуск изделий в производство необ­ходимо осуществлять, соблюдая условие: min (t11, t22) < min (t12, t21), где: t11 - трудоемкость выполнения первой операции над изделием, первым запускаем в производство; t22 - трудоемкость выполнения вто­рой операции над изделием, вторым запускаем в про­изводство, а t12 и t2l - соответственно наоборот.

Метод «ветвей и границ», являющийся комбина­торным методом дискретного программирования, предполагает уменьшение множества допустимых решений, вплоть до получения конечного множества, при котором оказывается возможным применение метода перебора. В этом методе происходит последо­вательный выбор пары номеров деталей для получе­ния оптимальной последовательности. Составление последовательности номеров деталей для запуска в производство происходит в процессе работы итерационного алгоритма. На каждой итерации выбираются две детали и помещаются на позиции: (n + 1) и (d – n), где n - номер итерации, a d- количество наименова­ний деталей, участвующих в производственном про­цессе. Эффективность метода «ветвей и границ» зави­сит от уровня, на котором происходит «отсечение» ветви. В общем случае этот метод не исключает пол­ный перебор всех возможных вариантов.

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

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

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

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

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

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

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

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

1. FCFS (Fist - Come, Fist - Served) - первым вошел - первым обслужен. Работы выполняются в порядке поступления в подразделение.

2. SOT (Short's Operating Time) - по кратчайше­му времени выполнения. Сначала выполняется работа с самым коротким временем выполнения, затем про­цедура повторяется для оставшихся работ.

3. D date (Due Date) - по установленным срокам окончания. Первой выполняется работа с самой ран­ней датой начала выполнения.

4. SD - по ранней дате начала выполнения, оп­ределяемой как установленная дата выполнения рабо­ты, минус время выполнения работы.

5. STR (Slack Time Remaining) - по наименьше­му оставшемуся запасу времени, который вычисляет­ся как разность между временем, остающимся до ус­тановленной даты выполнения, и временем выполне­ния работы.

6. STR/OP (Slack Time Remaining per Operation) - по наименьшему оставшемуся запасу времени на одну операцию, которое определяется как разность времени, оставшегося до установленной даты выпол­нения работ, минус время оставшихся операций, де­ленная на количество оставшихся операций. Заказы с самым коротким STR/OP выполняются первыми.

7. LCFS (Last - Come, First - Served) - последним вошел - первым обслужен. Первой выполняется рабо­та, поступившая последней в подразделение.

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

1 Donald W. Fogarty, Yohn H. Blackstone, Yr. And Tho­mas 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 с.