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

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

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

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

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

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

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

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

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

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

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

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

Q^PA =(PA, PC, PG),

Q^PB =(PB, PC, PD, PF, PE),

Q^PC =( PA, PB, PC, PE, PF, PG),

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



PA

PB

PC

PD

PG






PE

PF

Фиг. 1.1.12 “Граф на конфликтите”

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

Подграфът G^xi може да бъде записан посредством множеството от върховете Q^xi и съответствията им Γ , показващи по какъв начин те са свързани помежду си:

(1.1.23)
Независимата двойка x_i x_m се разширява до независима тройка като се изключат от Q^xi върховете свързани с x_m :
, (1.1.24)
а съответствията за се редуцират както следва:
(1.1.25)
Респективно, всяко едно следващо разширяване на независимите тройки до четворки и т.н. изисква повтаряне на операции (1.1.22) и (1.1.23), по отношение на някой от останалите във фрагмента на подграфа свързани върхове. Критерият, че на n –тата стъпка, след елиминиране на върховете свързани с :

, (1.1.26)
е получено максимално независимо множество от върхове, е наличието във фрагмента G^xi(n) само на висящите върхове Q^xi(n) т.е.
(1.1.27)
Важно е процесът на конструиране на МНМ да бъде управляван. Това се осъществява като на първите стъпки на разширяването се присъединяват най-силно свързаните върхове от подграфа, тъй като те участват в най-малък брой МНМ и след тяхната елиминация голяма част от останалите върхове се превръщат във висящи. Следователно, подреждането за декомпозиция на върховете в Q^xi се осъществява според броя на върховете в прилежащите им съответствия. Приоритет имат тези, чиито съответствия са с най-голям брой елементи.
Процедурата на насочено претърсване ще бъде илюстрирана върху подграфа G^PB (фиг. 1.1.13) от горния пример.

PB

PC

PD





PE

PF

Фиг. 1.1.13 Подграф G^PB

Подграфът G^PB е дефиниран чрез множеството от върховете му Q^PB и съответствията им Γ :

PF

Фиг. 1.1.14 Първи фрагмент на подграф G^PB

Съответствията за този фрагмент са:

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

Полученият на този етап фрагмент от подграфа е показан на фиг. 1.1.15.

PB

PD

PF

Фиг. 1.1.15 Втори фрагмент на подграф G^PB

След това второ разширяване се вижда, че полученото множество от върхове PB,PD,PF е максимално. Изпълнен е критерият за конструиране на МНМ, (1.1.25). Следователно е необходимо да се пристъпи към конструиране на друго максимално независимо множество от върхове. За целта е необходимо да се осъществи реконструкция на точно определен, още неизследван фрагмент на подграфа G^xi .

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

Ако Q^xi(n) е МНМ получено на n –тата итерация след елиминацията на върховете Γ(x_l)^(n-1) , реконструкцията на неизследван фрагмент от G^xi е свързана с връщане назад към множеството Q^xi(n-1) и изключване от него на върха x_l :

(1.1.28)
както и с определяне на новите съответствия Γ. Реконструираният фрагмент на подграфа насочено се претърсва с цел определяне на МНМ.
Така, за разглеждания по-горе пример, реконструкцията включва връщане към фрагмента на подграфа получен на първата итерация и изключване от него на върха PD, заедно с прилежащите му дъги:

След намирането на всички МНМ, в които участва първоначално избраната независима двойка x_i x_m върхът x_m се отстранява от множеството Q^xi и се избира нова независима двойка за разширяване. Многократното изпълнение на описаните процедури по отношение на върховете от подграфа G^xi позволява да се построят максимално независимите множества от върхове на графа с базов връх x_i .
Полученото, с помощта на описаната методология, семейство от максималните по размер производствени кампании позволява по-лесната формализация и редуциране на степента на сложност на задачите за разписания при многоцелеви ХТС.

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

Изтегляне 113 Kb.

Сподели с приятели: