Методы оптимизации технологического процесса на производстве

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

Целями данной работы являются:

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

· выполнение расчёта на технологические операции и исследование методов её решения на основе линейных стохастических сетей

· решение задачи маршрутной оптимизации в технологической цепи изготовления конструктивных узлов электронно-вычислительных систем и исследование методов её решения

· исследование задачи оптимизации структуры технологической линии по экономическим критериям и исследование возможных методов её решения.

1. Определение оптимального варианта конструкции эвм с учетом последовательности операций

1.1 Постановка задачи

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

Здесь каждое частное решение S_i (i = 1,2, …, r) в конструировании или технологии производства электронных устройств может быть формально представлено функционально-структурной схемой устройства или структурно-логической схемой технологического процесса (схемами сборочного состава, сборки, обработки поверхностей и т. д.).

Тогда топологическая модель множества допустимых проектных решений может быть построена множественным объединением частных решений, представленных топологически ориентированными схемами:

Задача определения оптимального варианта конструкции изделия с учётом последовательности выполнения операций заключается в определении по выбранному критерию оптимальности кратчайшего пути в MM_D из начальной вершины в конечную.

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

· Коэффициент сложности конструкции;

· Коэффициент интеграции и технологичности;

· Коэффициенты виброи удароизоляции;

· Вероятность безотказной работы;

· Потребляемая мощность и массогабаритные параметры и др.

В теории технологического проектирования критериями являются:

· Стоимость материальных элементов, входящих в состав изделия;

· Стоимость выполнения операций технологического процесса;

· Стоимость оборудования, отнесённая на единицу изделия, для выполнения данной операции;

· Коэффициент выхода годных изделий с линии, точность технологического процесса, его надёжность;

· Уровень механизации и автоматизации операций технологического процесса, удельный уровень межоперационных заделов и др.

1.2 Анализ и краткое описание возможных методов решения

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

Считаем, что множество проектных решений задано графом:

с пронумерованными вершинами от 1 до n. Где E={e₁, e₂,.e_n} - множество графа, которому поставлено в соответствие множество узловых реализаций, т. е. частных, промежуточных технических решений;

V={v₁, v₂,…, v_m} - множество возможных переходов (связей) между узловыми реализациями.

При этом каждой дуге графа (е_i, e_j) приписано значение интегрированного критерия качества, т. е. длина дуги а (e_i, e_j)

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

Модифицированный метод последовательных приближений предполагает :

1.разбиение сетевой модели ТП на уровни (слои);

2.решение системы линейных уравнений обычным методом последовательных приближений с учётом модели:

Г^-1 e_i — множество вершин графа G, предшествующих вершине e_i.

При решении задачи графическим способом на заданном графе определяются вершины, которые не имеют предков и которые образуют первый слой. Затем удаляются вершины первого слоя с инцидентными дугами и рёбрами и определяются вершины, которые не имеют предков и которые образуют второй слой. Операция п. 2 повторяется многократно до полного расслоения графа.

Нахождение кратчайшего пути на графе модифицированным методом заключается в решении следующей системы уравнений (по минимальному критерию) Модифицированный метод решения задачи сводится к решению системы:

Где kномер приближения; rчисло слоёв сети; nномер конечной вершины сети.

N_g— множество вершин, расположенных в g-том слое. Очевидно, что для нахождения оптимального решения достаточно (r-2) итерации.

1.3 Решение задачи по варианту

Необходимо определить оптимальный вариант конструкции конденсатора МБМ. Задачу требуется решить по критерию минимальной технологической себестоимости:

где l — множество дуг маршрута из вершины е1 в вершину е45; L — множество вариантов маршрутов из вершины e₁ в e₄₅,

В таблице 1 представлены веса дуг графа.

Таблица 1. Значения весов дуг графа сетевой модели

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

1. Нулевое приближение (k = 0)

V₄₃⁽⁰⁾=12

V₄₄⁽⁰⁾=7

V₄₅⁽⁰⁾=0.

2. Первое приближение (k = 1)

i = 37, V₃₇⁽¹⁾ =V₄₃⁽⁰⁾ + _37,43=12+6=18

i = 38, V₃₈⁽¹⁾ = V₄₃⁽⁰⁾ + a_38,43=12+7=19

i = 39, V₃₉⁽¹⁾ = V₄₄⁽⁰⁾ + a_39,44=7+4=11

i = 40, V₄₀⁽¹⁾ =V₄₄⁽⁰⁾ + a_40,44, =7+4=11

i = 41, V₄₁⁽¹⁾ = V₄₃⁽⁰⁾ + a_41,43= 12+6=18

i = 42, V₄₂⁽¹⁾ =V₄₄⁽⁰⁾ + a_42,44 = 12+7=19

3. Второе приближение (k = 2)

i = 22, V₂₂⁽²⁾ = V₃₈⁽¹⁾ + a_22,38= 19+9 = 28

i = 23, V₂₃⁽²⁾ = V₃₈⁽¹⁾ + a_23,38= 19+5= 24

i = 24, V₂₄⁽²⁾ = V₃₇⁽¹⁾ + a_24,37= 18+8 = 26

i = 25, V₂₅⁽²⁾ = V₃₇⁽¹⁾ + a_25,37= 18+3 = 21

i = 26, V₂₆⁽²⁾ = V₃₈⁽¹⁾ + a_26,38= 19+17= 36

i = 27, V₂₇⁽²⁾ = V₃₈⁽¹⁾ + a_27,38= 19+13= 32

i = 28, V₂₈⁽²⁾ = V₃₈⁽¹⁾ + a_28,38= 19+14= 33

i = 29, V₂₉⁽²⁾ = V₃₈⁽¹⁾ + a_29,38= 19+3= 22 i = 30, V₃₀⁽²⁾ = min{V₃₇⁽¹⁾ + a_30,37; V₃₈ ⁽¹⁾ + a_30,38} = = min{(18+20), (19+2)} = min{38; 21}=21

i = 31, V₃₁⁽²⁾ =V₃₈⁽¹⁾ + a_31,38= 19+8= 27

i = 32, V₃₂⁽²⁾ = V₃₈⁽¹⁾ + a_32,38= 19+8= 27

i = 33, V₃₃⁽²⁾ = V₃₈⁽¹⁾ + a_33,38=19+12= 31

i = 34, V₃₄⁽²⁾ = min{V₃₉⁽¹⁾ + a_34,39, V₄₀⁽¹⁾ + a_34,40} = = min{(11+7), (18+ 6)} = min{18; 24}=18

i = 35, V₃₅⁽²⁾ =V₄₂⁽¹⁾ + a_35,42 = 19+7 = 26

i = 36, V₃₆⁽²⁾ = min{V₄₁⁽¹⁾ + a_36,41, V₄₂⁽¹⁾ + a_36,42} = = min{(18+20), (19 +2)} = min{38, 21}=21

4. Третье приближение (k = 3)

i = 8, V₈⁽³⁾ = min{V₂₂⁽²⁾ + a_8,22, V₂₃⁽²⁾ + a_8,23} = = min{(28+12), (24+7)} = min{40; 31}=31

i = 9, V₉⁽³⁾ = V₂₆⁽²⁾ + a_9,26=36+5 = 41

i = 10, V₁₀⁽³⁾ = V₂₆⁽²⁾ + a_10,26= 36+10= 46

i = 11, V₁₁⁽³⁾ = min{V₂₄⁽²⁾ + a_11,24, V₂₅⁽²⁾ + a_11,25, V₂₇⁽²⁾ + a_11,27, V₂₈⁽²⁾ + a_11,28} = = min{(26+9), (21+15), (32+10), (33+3)} = = min{35;36;42;46 }=35

i = 12, V₁₂⁽³⁾ = V₂₆⁽²⁾ + a_12,26 = 36+15=51

i = 13, V₁₃⁽³⁾ = min{V₂₉⁽²⁾ + a_13,29, V₃₀⁽²⁾ + a_13,30} = = min{(22+4),(21+5)} = min{26, 26}=26

i = 14, V₁₄⁽³⁾ = min{V₂₄⁽²⁾ + a_14,24, V₂₅⁽²⁾ + a_14,25, V₂₇⁽²⁾ + a_14,27, V₂₈⁽²⁾ + a_14,28} = = min{(26+8), (21+15), (32+15), (33+13)} = = min{34;36;47; 46}=34

i = 15, V₁₅⁽³⁾ = min{V₂₇⁽²⁾ + a_15,27, V₂₈⁽²⁾ + a_15,28} = = min{(32+7), (33+17)} = min{39, 50}=39

i = 16, V₁₆⁽³⁾ = min{V₂₉⁽²⁾ + a_16,29, V₃₀⁽²⁾ + a_16,30 } = = min{(22+10), (21+4)} = min{32, 25}=25

i = 17, V₁₇⁽³⁾ = V₃₁⁽²⁾ + a_17,31 = 27+18= 45

i = 18, V₁₈⁽³⁾ = V₃₁⁽²⁾ + a_18,31= 27+25 = 52

i = 19, V₁₉⁽³⁾ = min{V₃₂⁽²⁾ + a_19,32, V₃₃⁽²⁾ + a_19,33, V₃₄⁽²⁾ + a_19,34, V₃₅⁽²⁾ + a_19,35} = = min{(27+8), (31+24), (18+2), (26+2)} = = min{35, 55, 20, 28}=20

i = 20, V₂₀⁽³⁾ = min{V₃₂⁽²⁾ + a_20,32, V₃₃⁽²⁾ + a_20,33, V₃₄⁽²⁾ + a_20,34, V₃₅⁽²⁾ + a_20,35} = = min{(27+12), (31+6), (18+9), (26+26)} = = min{39, 37, 27, 52}=27

i = 21, V₂₁⁽³⁾ =V₃₆⁽²⁾ + a_21,36 = 21+7 = 28

5. Четвёртое приближение (k = 4)

i = 2, V₂⁽⁴⁾ = V₈⁽³⁾ + a_2,8= 31+8 = 39

i = 3, V₃⁽⁴⁾ = V₉⁽³⁾ + a_3,9= 41+7 = 48

i = 4, V₄⁽⁴⁾ = min{V₁₀⁽³⁾ + a_4,10, V₁₁⁽³⁾ + a_4,11} = = min{(46 +5), (35+12)} = min{51;47 }=47

i = 5, V₅⁽⁴⁾ = min{V₁₂⁽³⁾ + a_5,12, V₁₃⁽³⁾ + a_5,13} = = min{(51+9), (26+18)} = min{60; 44}=44

i = 6, V₆⁽⁴⁾ = min{V₁₄⁽³⁾ + a_6,14, V₁₅⁽³⁾ + a_6,15, V₁₆⁽³⁾ + a_6,16, V₁₇⁽³⁾ + a_6,17, V₁₈⁽³⁾ + a_6,18, V₁₉⁽³⁾ + a_6,19} = min{(34 +6), (39+7), (25+16), (45+18), (52+7), (20+3)} = min{40, 46, 41, 63, 59, 23}=23

i = 7, V₇⁽⁴⁾ = min{V₂₀⁽³⁾ + a_7,20, V₂₁⁽³⁾ + a_7,21} = = min{(27+16), (28+4)} = min{43, 32}=32

6. Пятое приближение (k = 5)

i = 1, V₁⁽⁵⁾ = min{V₂⁽⁴⁾ + a_1,2, V₃⁽⁴⁾ + a_1,3, V₄⁽⁴⁾ + a_1,4, V₅⁽⁴⁾ + a_1,5, V₆⁽⁴⁾ + a_1,6, V₇⁽⁴⁾ + a_1,7}= min{(39 +7), (48+3), (47+3), (44+5), (23+7), (32+3)} = min{46, 51, 50, 49, 30, 35} = 30

По данным таблицы 3 при k = 5, V₁⁽⁵⁾ = 30 находим оптимальный маршрут в MM_D, который проходит через состояния (вершины) (e₁, e₆, e₁₉, e₃₄, e₃₉, e₄₄, e₄₅) и отметим его на графе (рисунок 1).

Таблица 2. Значение оптимального пути от е_i до е₄₅

Таблица 3. Номера промежуточных вершин L45 до оптимального пути от е1 до е45

Рисунок 1 — Сетевая модель множества допустимых вариантов

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

1) базовая деталь — секция;

2) к секции припаяны токовые выводы;

3) на секцию в сборе с токовыми выводами подмотана бумажная лента;

4) на выводы секции в сборе установлен набор прокладок;

5) пакет конденсатора в сборе с уплотнительными элементами установлен в корпус с донышком;

6) корпус собранного конденсатора завальцован;

7) получено готовое изделие.

2. Расчет запусков на технологические операции на основе использования линейных стохастических сетей

2.1 Понятие линейной стохастической сети

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

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

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

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

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

Если сеть построена путём соединения конечного числа М систем массового обслуживания и внешнего источника множеством дуг, веса которых Pij определяют постоянную вероятность поступления требований в систему j (j=1,2,…M) из системы i (i=1,2,…, M);

Вероятности того, что требования поступают в систему j (j=1,2,…M) из внешнего источника равны P_0j ;

Вероятности того, что требования покинут сеть, равны P_i0 (i=1,2,…, M);

Для всех i=1,2,…, M имеет место равенство причём Р₀₀=0;

Линейность сети определена тем, что вероятность поступления требования в систему j в течение интервала (t, dt) является линейной комбинацией с постоянными коэффициентами P_ij вероятностей выхода требований из разных систем сети.

2.2 Метод определения запусков на операции на основе линейной сетевой стохастической модели

Рассмотрим обобщённый метод определения запусков на технологические операции с использованием линейных сетевых стохастических моделей производственных систем.

Допустим, N_j — суммарная интенсивность потока требований (количество заготовок) в системе j (запуск на j-ю операцию); N₀— интенсивность предыдущего производственного участка или склада заготовок; N_m— интенсивность последующего производственного участка или склада готовой продукции (выпуск линии). Если процесс стационарен (т. е. установившийся режим), то

или, используя матричную запись,

где P^T — транспонированная матрица Р

Тогда для получения значений запусков на каждую операцию N_j необходимо решить следующую систему линейных однородных уравнений с (m+1) неизвестными (включая N₀):

(1)

где D^T — матрица, транспонированная по отношению:

D = P — I. (2)

где I — единичная матрица.

Если N_m известно (задано):

N_m=П, (3)

где П — план выхода годных изделий с линии, то в соответствии с теоремой Кронекера-Капелли система (1) может иметь нулевое единственное решение, если при N?0 и условии (3) det D^T =0, а ранг матрицы D^T был равен в точности m.

2.3 Решение задачи по варианту

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

Таблица 4 Вариант задания

План выхода годных изделий/смену П=5000 шт/смену.

Из равенства найдем недостающие коэффициенты выхода после технологической операции.

Рисунок 2 — Структура химической металлизации в производстве печатных плат Рисунок 3 — Граф передач технологического процесса химической металлизации в производстве печатных плат Составим для сети матрицу передач Р:

Затем получим матрицу D=P-I:

Составим транспонированную матрицу D^T:

Запишем систему линейных однородных уравнений:

Решая систему уравнений, можно найти величины запусков на все технологические операции изготовления печатных плат:

· =5000 шт/смену;

· на операции промывки =5000 шт/смену;

· на операции химической металлизации =7143 шт/смену;

· на операции активизации =2679 шт/смену;

· на операции сенсибилизации =804 шт/смену;

· на операции химического матирования =4018 шт/смену;

· на операции предварительной обработки =2679 шт/смену;

· на операции промывки и декапирования =6696 шт/смену;

· на операции травления =8163 шт/смену;

· на операции промывки и декапирования =8163 шт/смену;

· на операции подтравливания диэлектрика =2432 шт/смену;

· на операции химической и металлической очистки =6079 шт/смену;

· на операции заготовки =5836 шт/смену.

Как видно из полученных результатов, запуск на операции химической и механической очистки больше, чем интенсивность источника (N₁>N₀). Это объясняется тем, что на эту операцию поступаю заготовки с последующих операций.

3. Решение задачи оптимизации структуры технологической линии методом расшивки узких мест

3.1 Постановка задачи

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

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

1. Задана последовательность выполнения технологической операции;

2. Известны технико-экономические показатели оборудования на каждой технологической операции;

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

n_i =f_i(x_i, k _i, k_i+1, …k_m, П); (1)

_i=_i(n_i)=max;

z_i=v (n_i);

a П b,

где

m — количество оборудования;

k _i (i=1,m) — коэффициент выхода годных изделий на i-ой операции;

П — годовой план выхода годных изделий с линии;

n_i — количество единиц оборудования на i-ой операции;

x_i — вектор технико-экономических показателей оборудования на i-ой операции;

z_i — ёмкость накопителя перед i-ой операцией; _i — коэффициент загрузки оборудования на i-ой операции по запуску;

Тогда целевой критерий производительности технологической линии можно представить:

q=f (n_i, x_i, k_i, z_i, П); (2)

В этом случае задачу по выбору оптимальной структуры линии можно сформулировать следующим образом: необходимо путём варьирования плана в интервале [a, b] найти такие n_i, которые обеспечат оптимизацию (2) при выполнении условия (1).

3.2 Анализ и описание метода решения

Для решения задачи необходимо технологический процесс представить в виде связной ориентированной сети, состоящей из множества узлов и множества связывающих технологические операции дуг. То есть транспортную сеть представим в виде конечного графа без петель G=(E, U), где Е=(Х₀, Х₁,…, Х_n) — множество вершин (множество технологических операций); U=(u₁, u₂,…, u_m) — множество связывающих технологические операции технологических переходов. Для графа должны выполняться следующие условия:

1. Существует такая вершина Х₀ E, которая обладает свойством:

(! Х₀ E) Г^-1 Х₀= Ш;

2. (! Х_n E) ГХ_n =Ш,

где, ГХ_n — множество вершин графа G, следующих за вершиной Х_n;

3. Каждой дуге приписываются значения С (u) =0, u U, где

Х₀, Х_n — соответственно вход и выход сети (начальная и завершающая операции технологического процесса);

С (u) — пропускная способность дуги «u» (максимальная производительность технологического участка).

Алгоритм Форда-Фалкерсона для отыскания максимального потока в заданной транспортной сети основывается на следующих теоремах:

Теорема 1

Пусть =(Х₀, Х_i1,… Х_in, Х_N) — путь, соединяющий вход Х₀ с выходом Х_N транспортной сети. Если все дуги этого пути ненасыщенные, то можно увеличить поток на величину *=min ((U)=C (U)-ц (U)), не нарушая свойств транспортной сети.

Теорема 2

Если *0, то увеличивая на * поток в каждой попутной дуге из Х₀ в Х_N и уменьшая на * поток в каждой встречной дуге, мы увеличиваем поток в цепи.

Теорема 3

Если не существует цепи от Х₀ до Х_N с *0, то поток ц в сети нельзя больше увеличить, т. е. он максимальный.

Х_N =c (U⁺_A)= c (u), u U⁺_A, где

U⁺_A — множество дуг, входящих в разрез;

c (U⁺_A) — пропускная способность разреза.

Теорема 4(теорема Форда-Фалкерсона)

Для заданной транспортной сети максимальное значение потока равно минимальной пропускной способности разреза.

max Х_N =min c (U⁺_A).

Алгоритм Форда-Фалкерсона подразумевает следующие этапы:

1. Отыскание какого-нибудь потока;

2. Отыскание полного потока;

3. Отыскание максимального потока.

3.3 Решение задачи по варианту

На рисунке 4 приведен граф, в виде которого представлен ТП с соответствующими ТО:

Рисунок 4 — Граф ТП Путь (1, 4, 6, 7, 9) не содержит насыщенных дуг.

Находим разность в каждой дуге между максимальной её пропускной способностью и действительной:

д (1,4)=6 — 2=4;

д (4,6)=6 — 4=2;

д (6,7)=5 — 3=2;

д (7,9)=6 — 1=5.

е^*= 2.

Увеличение потока, проходящего через этот путь на 2, приводит к насыщению дуг (4,6) и (6,7) (рисунок 5).

Рисунок 5 — Граф ТП с насыщенными дугами (4,6) и (6,7)

Рассмотрим следующий путь, не содержащий насыщенных дуг:

(1, 4, 5, 7, 9).

д (1,4)=6 — 4=2;

д (4,5)=7 — 2=5;

д (5,7)=5 — 3=2;

д (7,9)=6 — 3=3;

е^*= 2.

Увеличение потока, проходящего через этот путь на 2, приводит к насыщению дуг (1,4) и (5,7) (рисунок 6).

Рисунок 6 — Граф ТП с насыщенными дугами (1,4) и (5,7)

Рассмотрим следующий путь, не содержащий насыщенных дуг: (1, 3, 2, 8, 9).

д (1,3)=8 — 4=4;

д (3,2)=6 — 4=2;

д (2,8)=9 — 5=3;

д (8,9)=7 — 6=1;

е^*= 1.

Увеличение потока, проходящего через этот путь на 1, приводит к насыщению дуги (8,9) (рисунок 7).

Рисунок 7 — Граф ТП с насыщенной дугой (8,9)

Рассмотрим путь (1, 3, 2, 8, 7, 9) и по теореме 2 увеличим поток до максимального:

д (1,3)=8 — 5=3;

д (3,2)=6 — 5=1;

д (2,8)=9 — 6=3;

ц (4,9)=2>0;

д (7,9)=6 — 5=1;

е^*= 1.

Увеличение потока сонаправленных дуг и уменьшение потока встречных дуг приводит к насыщению дуг (3,2) и (7,9) (рисунок 8).

Рисунок 8 — Граф ТП с максимальным потоком Так как невозможно пометить последнюю вершину, можно сделать вывод, что поток, изображенный на рисунке 8 является максимальным, потому что нельзя найти еще один путь, который доходил бы до конечной вершины и не содержал бы насыщенных дуг.

Подмножеству непомеченных вершин А={9} отвечает разрез {(7,9),(8,9)} c пропускной способностью равной 6+7=13.

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

4. Исследование задачи маршрутной оптимизации на примере технологии изготовления печатных плат

4.1 Технологическое обеспечение оптимальности управляющих программ

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

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

Например:

· обход отверстий на плате при работе сверлильного станка;

· траектория перемещения резца при токарной обработке;

Рассмотрим постановку задачи минимизации холостого пробега исполнительного механизма и её решение методом ветвей и границ.

4.2 Формальная постановка задачи на примере работы сверлильного станка при производстве печатной платы

Пусть на печатной плате необходимо просверлить n-1 отверстие. Поставим в соответствие каждому i-ому отверстию (i=1, n-1) вершину x_i полного неориентированного взвешенного графа G (X, U), а также нуль станка= x₀ .Веса рёбер графа равны расстояниям между центрами отверстий.

X={x₁ , x₂, …, x_n} — множество вершин графа

U={u₁, u₂ ,…, u_m} — множество дуг графа (переходов между отверстиями).

Задача состоит в том, чтобы найти в графе гамильтонов цикл с минимальным суммарным весом рёбер.

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

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

Исходными данными для алгоритма является матрица расстояний S.

Алгоритм:

1)Приведение матрицы расстояний S по строкам и столбцам и определение нижней оценки множества вариантов гамильтоновых контуров.

где c_i и q_i — элементы приведения по строкам и столбцам соответственно, — длина самого короткого гамильтонова контура в исследуемом множестве вариантов.

2)Определение оценок на включение в искомый гамильтонов контур для всех «нулевых» дуг.

3)Включение дуг с максимальной оценкой в решение.

При этом необходимо соблюдать следующие правила:

· в решение включаются дуги с максимальными равными оценками;

· дуги не должны образовывать частных контуров;

· дуги должны соответствовать выбранному направлению обхода.

4) Коррекция матрицы S, заключающаяся в вычёркивании строк с номерами i и столбцов j в соответствии с дугами, включёнными в решение.

5) Гамильтонов контур найден? Если нет — переход к пункту 6, если да — переход к пункту 8.

6) Определение подмножества гамильтоновых контуров с минимальной оценкой .

7) Переход к пункту 1.

8) Гамильтонов контур оптимален? Если нет — переход к пункту 6. Если да — конец алгоритма.

4.3 Решение задачи по варианту

Заданы координаты отверстий на печатной плате (рисунок 10). Необходимо найти такую траекторию обхода всех этих отверстий при работе сверлильного станка, чтобы её длина была минимальной. За направление обхода контура примем направление по часовой стрелке. На основании технологической карты определим расстояния между центрами отверстий в миллиметрах и составим матрицу расстояний S.

Рисунок 9 — Технологическая карта Матрица расстояний S будет иметь вид:

1-й шаг: приведём полученную матрицу по строкам. Для этого из каждой строки вычитаем её минимальный элемент.

Найдём сумму минимальных для каждой строки элементов с_i.

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

Найдём сумму минимальных для каждого столбца элементов q_i.

Теперь получим уточненную оценку снизу для гамильтоновых контуров:

Найдем увеличения оценок для дуг, у которых, для этого сложим наименьшие значения в i-ой строке и j-ом столбце:

Максимальное увеличение оценки, равное 22, имеет дуга (4,2). Включаем в решение дугу (4,2), так как она удовлетворяет выбранному обходу. Вычёркиваем четвертую строку и второй столбец.

Получаем матрицу расстояний, в которой наложен запрет на дугу (2,4).

2-й шаг: Полученную матрицу аналогично приводим по строкам:

Также приведём матрицу по столбцам:

r=192+16=208

Максимальное увеличение оценки, равное 16, имеет дуга (7,5), но она не соответствует выбранному направлению обхода по часовой стрелке. Включаем в решение дугу (5,7).

Вычёркиваем из матрицы 5 строку и 7 столбец. Получаем матрицу, в которой наложен запрет на дугу (7,5):

3-й шаг: Полученную матрицу вновь приводим по строкам:

Приводим матрицу по столбцам:

r=208+16=224

Найдем увеличения оценок :

Максимальное увеличение оценки, равное 48, имеет дуга (7,4). Включаем в решение дугу (7,4). Вычёркиваем из матрицы седьмую строку и пятый столбец. Накладываем запрет на дугу (2,5), так как она создает частный контур.

Получаем матрицу:

4-й шаг: Полученную матрицу вновь приводим по строкам: матрица уже приведена по строкам.

Приводим матрицу по столбцам:

r=224+4=228

Найдем увеличения оценок :

Максимальное увеличение оценки, равное 6, имеет дуга (2,6). Включаем в решение дугу (2,6). Вычёркиваем из матрицы вторую строку и шестой столбец. Накладываем запрет на дугу (5,2), так как она создает частный контур.

Получаем матрицу:

5-й шаг: Полученную матрицу вновь приводим по строкам:

Таблица уже приведена по столбцам.

r=228+3=231

технологический стохастический печатный плата Найдем увеличения оценок :

Максимальное увеличение оценки, равное 7, имеет дуга (8,1). Включаем в решение дугу (8,1). Вычёркиваем из матрицы восьмую строку и первый столбец.

Получаем матрицу:

6-й шаг: Полученную матрицу вновь приводим по строкам:

Таблица уже приведена по столбцам.

r=231+1=232

Найдем увеличения оценок :

Максимальное увеличение оценки, равное 13, имеет дуга (1,5), включаем в решение дугу (1,5). Вычёркиваем из матрицы первую строку и пятый столбец. Получаем матрицу:

7-й шаг: Полученную матрицу вновь приводим по строкам:

Таблица уже приведена по строкам и столбцам.

r=232

Найдем увеличения оценок :

Наибольшие значения получились равными у дуг (3,8) и (6,3). Таким образом, эти обе дуги можно отнести к намечаемому гамильтонову контуру, получая оптимальный гамильтонов контур (1,5,6,4,2,6,3,8,1) длиной 232. Построим дерево разбиений (рисунок 10):

Рисунок 10 — Дерево решений В ходе построения дерева некоторые неконечные вершины (в частности вершина, соответствующая не включению дуги (5,7) получали оценки лучшие, чем вершины в других ветвях дерева). Для них также было произведено оценивание длины гамильтонова контура, расчет приводится ниже.

После второго шага получили следующую матрицу (дуга (5,7) не включается в контур, а наоборот, запрещается):

Приведем полученную матрицу по строкам:

Приведем полученную матрицу по столбцам:

r = 218+10=228

Максимальное увеличение оценки, равное 40, имеет дуга (2,7), но она не соответствует выбранному направлению обхода по часовой стрелке. Следующее максимальное значение оценки, равное 16, имеет дуга (7,5), но она также не соответствует выбранному направлению обхода. Включаем в решение дугу (6,3). Вычёркиваем из матрицы 6 строку и 3 столбец.

Получаем матрицу, в которой наложен запрет на дугу (3,6):

r = 228+61=289

Так как оценка r получается больше, чем значение r=232, дальнейшее продолжение этой ветки дерева не требуется.

Наложим запрет на дугу (6,3), получим следующую матрицу:

r = 218+13+3=234

К оценке r дополнительно прибавляется

Так как оценка r получается больше, чем значение r=232, дальнейшее продолжение этой ветки дерева не требуется.

Рабочий чертёж оптимального маршрута перемещения исполнительного механизма на печатной плате изображён на рисунке 11:

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

Заключение

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

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

При выполнении второго задания был произведён расчёт величин запусков на технологические операции ТП химической металлизации печатных плат, модель ТП рассматривалась в виде линейной стохастической сети.

При выполнении третьего задания была рассмотрена возможность оптимизации заданного ТП. Был выделен максимальный поток производственной линии, отмечены участки, ограничивающие производительность.

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

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

Библиографический список

1. Таганов А. И. Использование линейных стохастических сетей для расчёта запусков на технологические операции: Методическое указание к лабораторным работам. Рязань: РРТИ, 1994.

2. Таганов А. И. Оптимизация структуры технологической линии методом расшивки узких мест: Методическое указание к лабораторным работам. — Рязань: РРТИ, 1997.

3. Таганов А. И. Определение оптимального варианта конструкции изделия с учётом последовательности операций: Методическое указание к лабораторным работам. — Рязань: РРТИ, 1994.

4. Таганов А. И. Технология ЭВС и автоматизация производства: Методическое указание к лабораторным работам. — Рязань: РРТИ, 1992.