1. Многоасортиментни периодични химико-технологични системи. Моделиране. Оптимални производствени разписания (оперативно оптимално управление). Оптимален синтез


Фиг. 1.1.10. Суперструктура на многоцелева система за целите на проектирането



страница6/7
Дата25.10.2018
Размер402.5 Kb.
#97615
1   2   3   4   5   6   7

Фиг. 1.1.10. Суперструктура на многоцелева система за целите на проектирането

За да се определи суперструктурата при задачите за разписания е необходимо:



  • за всяка технология да се намерят технологичните й маршрути в производствената система; и

  • да се определи множеството от максималните по размер кампании от производствени маршрути.



1.1.5.2. Определяне на технологичните маршрути

Еквивалентни апарати
За да се определят производствените пътища на дадена технология най-напред трябва да се идентифицират всички апаратурни единици от производствената система подходящи за реализиране на съответните технологични стадии. Условно те са наречени еквивалентни апарати. Дадена апаратурна единица е еквивалентна, ако е от съответния тип и притежава необходимите характеристики.





















Фиг.1.1.11-а Граф представящ структурата на технология
Производствена суперструктура за дадена технология
Системата от еквивалентни апарати и съществуващите или възможни твърди и гъвкави връзки между тях образуват производствената суперструктура на съответната технология. Производствената суперструктура на технологията от фиг.1.1.11-а е показана на фиг. 1.1.11-б.
Stage 3


m31





m11

ml1

mL1





m3i


m1i










m21








mli

mLi

m2i



Stage1 Stage2 Stage l Stage L

Фиг. 1.1.11-б Производствената суперструктура на технологията

Производствената суперструктура също може да се представи във вид на граф, в който върховете представляват еквивалентните апарати, а дъгите връзките между тях.




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

- стойността на ненулевите елементи на повдигнатата на степен (p) матрица на съседството е равна на броя на пътищата с дължина (p) между върховете, на чиито номера съответстват тези елементи.
Ясно е, че за технологии с линейна структура определянето на производствените пътища с помощта на горното свойство е лесно разрешима задача следвайки следния алгоритъм:

  1. Матрицата, представяща производствената суперструктура на технологията, се повдигната на нужната степен (p), равна на броя на върховете на графа представящ съответната технология, за да се определи броя на технологичните маршрути и върховете, между които те съществуват.

  2. За така определените върхове, между които съществуват пътища с търсената дължина се прилага алгоритъм за достижимост (базов алгоритъм от теория на графите), за да се идентифицират търсените производствени маршрути.

Значително по-сложна е задачата за определяне на производствените пътища при технологии с разклонена структура. За тях е невъзможно директно прилагане на горния подход, поради което алгоритъмът се променя по следния начин:



Стъпка 1. Графът представящ структурата на технологията се декомпозира на линейни последователности от технологични стадии по следните правила:

  1. множеството от линейните последователности трябва да покрива всички върхове на графа;

  2. всяка линейна последователност трябва да включва върхове с еднакво насочени дъги;

  3. всяка линейна последователност трябва да минава през особени върхове на графа (особен връх е този, в който влизат или излизат повече от една дъги).

Естествено, технологиите може да бъдат декомпозирани по много и различни начини. Необходимо е, когато това е възможно, да се избягва включване в някоя линейна последователност на върхове, обхванати вече от други. Например, графът, представен на фиг. 1.1.11-а, може да бъде декомпозиран на следните линейни последователности 1,2,…,l,L и 1,3,…,l.L минаващи през особените върхове 1 и l.

Стъпка 2. Производствената суперструктура също се декомпозира на подструктури в съответствие с декомпозицията на съответния граф.

Стъпка 3. За всяка подструктура се прилага алгоритъмът, описан по-горе, за да се определят технологичните маршрути за съответните линейни последователности.

Стъпка 4. Получените множества от производствени пътища се редуцират до подмножества, съдържащи едни и същи еквивалентни апарати съответстващи на особените върхове в графа. За реалните системи броят на тези подмножества като правило не е голям. Това позволява прилагането на комбинаторни методи за получаване на производствените маршрути на технологиите.

Стъпка 5. Подмножествата между които се прилагат комбинаторните методи се отнасят до линейни структури, съдържащи едни и същи номера на особени върхове. Комбаниториката се прилага по реда на нарстване на номерата на еквивалентните апарати, съответстващи на някой особен връх. Условието за конструиране на технологичен маршрут е матрицата на съседството на получената производствена структура да съвпада с тази описваща структурата на технологията.

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

А) множеството от технологичните й маршрути в производствената система; и

Б) множеството от производствените апарати, които тези маршрути включват.

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

1.1.5.3. Определяне на множеството от максималните по размер производствени кампании

Максимално-независимо множество от върхове в граф. Граф на конфликтите.
От теорията на графите е известно, че за всеки неориентиран граф може да бъде построено семейство от максимално-независими множества от върхове, т.е. такива върхове които не са свързани помежду си. Това свойство на графите може да бъде използвано за построяване на множеството от максималните по размер производствени кампании. Двата етапа, които последователно трябва да бъдат решени, за да се конструира множеството от максималните по размер производствени кампании, са следните:


  1. Да се построи граф отразяващ невъзможността за съвместната реализация на технологичните маршрути в производствената система; и

  2. Да се построи семейството от максимално-независими множества от върхове за горния граф.

Както бе показано, по-горе, технологичните маршрути на един или няколко продукта може да бъдат реализирани съвместно в една производствена кампания, само когато не използват общи апарати от производствената система. Този факт се използва за да се представят производствените пътища по подходящ начин посредством граф.

Графът G=(P,Г), който се дефинира, отразява конфликтите между отделните производствени маршрути на база общност на използваните апаратурни единици. По тази причина той условно е наречен “граф на конфликтите”.

Всеки връх в “граф на конфликтите” представя точно определен производствен маршрут на периодичните технологии. Наличието на дъга между два върха означава, че съответстващите им технологични пътища използват поне една обща апаратурна единица от производствената система.

За да може два или повече маршрута да бъдат включени в обща производствена кампания е необходимо между представящите ги върхове в “графа на конфликтите” да не съществуват дъги, т.е:
, (1.1.18)
където Pij и Pft са множествата от апарати включени в j-тия и t-тия маршрути съответно на i-тия и f-тия продукти.
Построяването на “графа на конфликтите” се базира на получената вече информация за технологичните маршрути и апаратите включени в тях.

Структурата на графа G=(P,Γ) се представя от неговата матрица на съседството:


, (1.1.19)
където;
(1.1.20)
Поради неориентираността на графа и липсата на примки в него матрицата на съседство е симетрична относно главния диагонал. Предполага се, че всеки технологичен маршрут е съвместим сам със себе си, поради което диагоналните елементи в матрицата на съседството се приемат равни на 0. Всеки останал нулев елемент от нея обозначава двойка от производствени маршрути, които може да бъдат реализирани съвместно (едновременно) в обща производствена кампания.

Анализът на матрицата на съседството позволява да се елиминират от по-нататъшно разглеждане технологични маршрути, които не са съвместими с нито един от останалите, както и тези, които са съвместими със всички останали и по същество представляват самостоятелни технологични линии. За първата група маршрути всички елементи от матрицата на съседството (с изключение на диагоналните елементи) са равни на 1, докато за втората всичките елементи са равни на 0.



Алгоритъм за построяване на МНМ от върхове в гарафа на конфликтите.
Всяко независимо множество от върхове (т.е. множество, в което, която и да е произволна двойка от върхове се вземе, те не са съседни) на “графа на конфликтите”, представлява група от технологични маршрути, които може да бъдат реализирани в обща производствена кампания. Ако това множество е максимално, т.е. няма друго, в което да се съдържа и не може да бъде разширено повече чрез добавяне на нови върхове, означава че съответстващата му кампания е максимална по размер. За даден произволен граф съществуват повече от едно максимално-независимо множество от върхове (МНМ), които образуват семейство. Отнесено за “графа на конфликтите” това означава че съществува семейство от максимални по размер производствени кампании.

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



декомпозиция на изходния граф G на подграфи Gxi около зададени базови върхове xi , последвана от редуване на фази на:

- насочено претърсване в дълбочина на подграфа Gxi с конструиране на МНМ; и

- реконструкция на неизследван фрагмент от подграфа Gxi .
Целта на декомпозицията е да подпомогне процеса на търсене на МНМ посредством подходящо разделяне на изходния граф на по-малки и удобни за изследване подграфи. Декомпозицията на изходния граф G се осъществява около предварително избран базов връх . Тя се състои в отнемането от графа G на всички върхове свързани с базовия заедно с прилежащите им дъги. Матрицата на съседството, съответстваща на подграфа Gxi , се получава от матрицата на съседството на изходния граф, като се изключат от нея редовете и стълбовете, за които, . В резултат се получава подграф, в който базовият връх xi е висящ т.е. не е свързан с никой от останалите върхове в подграфа. Тогава всеки елемент от множеството Qxi , съдържащо върховете на подграфа Gxi :
(1.1.21)
образува независима двойка с базовия връх.
Фактът, че изходния граф е неориентиран и без примки, позволява всеки връх разглеждан веднъж като базов, да се изключва от графа заедно с прилежащите му дъги. Това предпазва от повторно изследване, в процеса на търсене на МНМ при друг базов връх, на изследвани вече фрагменти от графа.

По принцип всеки връх xi може да бъде избран за базов. В много случаи, обаче, съответствуващият му подграф Gxi се явява фрагмент на вече изследван подграф Gxj , което води до определяне на множества, които са максимално независими за Gxi , но независими за Gxj и за целия граф G . Подходящият избор на базовите връхове позволява да се заобиколи това неудобство. Върхът xi може да бъде избран за базов ако множеството Qxi не се съдържа в никое друго множество Qxj :


. (1.1.22)
На фиг. 1.1.12 е изобразен граф, който с помощта на описаната процедура се декомпозира на 4 подграфа GPA , GPB , GPC и GPD , включващи съответно множествата;

QPA =(PA, PC, PG),

QPB =(PB, PC, PD, PF, PE),

QPC =( PA, PB, PC, PE, PF, PG),

QPD =( PD, PE, PF, PB, PG).
Най-добрият случай е когато няма дъги между върховете на селекционирания подграф. Тогава всички върхове образуват едно МНМ, както е в случая с GPA. В общия случай, подграфът съдържа повече от едно МНМ и тогава е необходимо да се приложи алгоритъмът за насоченото му претърсване в дълбочина с последваща реконструкция.



PA

PB

PC

PD

PG






PE

PF



Каталог: www systems engineerig laboratory -> Distance learning systmeng -> Distance Course 1 -> Lekcii Course 1 -> BTU
BTU -> На работа в науката и администрацията
BTU -> Оптимални разписания при многопродуктови периодични химични системи
BTU -> Отново в института и в ЦК на бкп
BTU -> На отговорна работа в Министерство на вътрешната търговия
BTU -> Студентството в страната на съветите – СССР
BTU -> Това се случи в моите детски години
BTU -> Бригадирското движение и участието ми
BTU -> Определяне на множеството от максималните по размер производствени кампании


Сподели с приятели:
1   2   3   4   5   6   7




©obuch.info 2024
отнасят до администрацията

    Начална страница