Элементы сетевого графа в применении к технологии машиностроения

УЧЕБНОЕ ПОСОБИЕ

для выполнения

курсовых и расчетных работ

по курсу:

«CALS-технологии»

ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ

Задача согласования

В конкурентных рыночных условиях перед промышленными предприятиями встают новые задачи:

· четкое выполнение клиентских заказов,

· управление себестоимостью продукции,

· снижение издержек и пр.

Каждое современное промышленное предприятие тем или иным образом автоматизирует планирование материальных ресурсов и производства – номенклатуру в тысячи позиций вручную просчитывать невозможно. Однако полностью исключить нештатные ситуации довольно сложно, и периодически приходится оперативно решать множество проблем: как выполнить заказ, если вовремя не привезли материал или субподрядчики срывают срок поставки, или вышел из строя станок, или близится плановый ремонт оборудования? При широкой номенклатуре изделий «держать в голове» всю информацию по имеющимся на складе материалам, производственным мощностям просто невозможно. В этих условиях многие промышленные предприятия обращаются к ERP-системам, в первую очередь к функциональности планирования материальных ресурсов и производственных мощностей. (ERP – Enterprise Resources Planning).

Главная задача цикла планирования — получение адекватных планов по закупкам материалов и услуг, по производству, по субподрядным работам. Для этого необходимо строго учитывать, по какому технологическому маршруту производится изделие, какие материалы и услуги, производственные мощности нужны для каждой операции и т. д. Все эти данные в ERP-системе консолидируются в блоке нормативно-справочной информации (НСИ), который является своего рода «костяком» системы. От правильного задания этой информации зависят и планирование, и управление производством, и решение таких задач, как управление запасами, расчет себестоимости, планирование бюджета и пр.

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

Элементы сетевого графа в применении к технологии машиностроения

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

· полный путь, или просто путь – путь от исходного события до завершающего события;

· путь, предшествующий данному событию – путь от исходного события до данного события;

· путь, последующий за данным событием – путь от данного события до завершающего события;

· путь между двумя какими-либо промежуточными событиямиi и j;

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

Работой называются любые процессы и действия, приводящие к достижению определенных результатов (событий):

ü действия – проектирование маршрутной технологии, проектирование черте-жей штампов, изготовление штампов;

ü процессы – механическая обработка деталей, старение отливок.

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

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

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

Далее будем рассматривать графовое изображение событий.

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

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

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

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

Матричное представление сетевого графика

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

Представление сетевого графика в виде линейчатых диаграмм

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

Рис. 1. Представление сетевого графика в виде линейчатых диаграмм

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

Алгоритм расчета сетевого графика с детерминированным временем выполнения операций

Обозначим:

t_ij – время операции; i – номер предшествующего события; j – номер последующего события.

T_рi, T_рj– ранний срок наступления события, т.е. минимальный срок, необходимый для выполнения всех работ, предшествующих данному событию, t_р.оij – ранний срок окончания операции i–j.

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

R_i, R_j – резервы времени событий i, j, т.е. такой промежуток времени, на который может быть отсрочено наступление этих событий, без нарушения сроков завершения разработки в целом.

R_пij – полный резерв времени операций i‑j, т.е. максимальное количество времени, на которое можно увеличить продолжительность данной операции, не изменяя при этом продолжительность критического пути.

R_сij – свободный резерв времени операции i‑j, т.е. максимальное количество времени, на которое можно увеличить продолжительность операции или отсрочить ее начало, не изменяя при этом ранних сроков начала последующих работ, при условии, что начальное событие этой работы наступило в свой ранний срок.

Задача решается в три этапа:

1. Рассчитываются ранние сроки наступления события T_pj ;

2. Рассчитываются поздние сроки наступления события T_пj ;

3. Рассчитываются резервы времени:

­ события R_j ;

­ полные резервы времени операции R_{пi j};

­ свободные резервы времени операции R_сij .

Правила оформления и обозначения рассчитанных значений на графе и в таблицах при комбинированном методе расчета

Рассчитанные данные удобно заносить в таблицу и на граф (рис. 2) в последовательности расчета.

Рис. 2. Обозначение параметров на графе

Цифра в левом секторе каждой вершины означает ранние сроки наступления события T_{pj ,} а в правом секторе – поздние сроки наступления события T_пj. Цифра в правом секторе отличается от цифры в левом на величину резерва времени события R_j. Цифра у конца дуги указывает на ранний срок окончания операции – t_роij, а у начала – на поздний срок начала операции - t_пнij.

Первый этап расчета.

Принято, что ранний срок наступления первого события равен нулю, Т_{р1 }= 0.

Ранний срок окончания операции t_роiопределяется как сумма раннего срока наступления события и времени операции t_роij = Т_рi + t_ij.

Ранний срок наступления события Т_рi равен максимальному значению раннего срока окончания операций, подходящих к событию j, Т_рj = max{t_роij}.

Расчеты t_роij и Т_рjведутся от начальной вершины сетевого графика к конечной.

Второй этап расчета.

Поздний срок начала операции t_пнij определяется как разность позднего срока наступления события и времени операции t_пнij = Т_пj – t_ij, причем для конечного события Т_рк = Т_пк. Если от события отходит более одной операции, то Т_пiравен минимальному значению позднего срока начала операций, отходящих от данного события, Т_пi = min{t_пнij}. Расчеты t_пнij и Т_пiведутся от конечной вершины сетевого графика к начальной.

Третий этап расчета.

Резерв времени события R_i определяется как разность между наиболее поздним и наиболее ранним сроками свершения этого события, R_i = Т_пi - Т_рi.

Полный резерв времени операции R_пij – это максимальное время, на которое можно отсрочить или увеличить продолжительность операции i–j, не изменяя директивного или раннего срока наступления завершающего события, R_пij = Т_пj - t_роij = Т_пj - Т_рi - t_ij.

Свободный резерв времени операции R_сij – это максимальное время, на которое можно увеличить продолжительность операции i–j при условии, что все события сети наступают в свои ранние сроки, R_сij = Т_рj - t_роij = Т_рj- Т_рi - t_ij.

Значения t_ij для представления исходных данных для всех вариантов заданий содержатся в приведенной ниже матрице.