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

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

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

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

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

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

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

Метод линейного программирования удачно ис-пользован С.М. Джонсоном для решения задачи на-хождения оптимального по календарному времени плана обработки 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 с.