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



Дата25.10.2018
Размер90.89 Kb.
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


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

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

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

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

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

PB

PC

PD





PE

PF


Фиг. 1.1.13 Подграф GPB

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



Нека PB, PF, бъде първата независима двойка от върхове обсъждана за разширение до независима тройка. Разширението се осъществява чрез изключване на върховете свързани с PF и прилежащите им дъги:

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

PB

PC

PD




PF


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

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



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

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

PB

PD


PF


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




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

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

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


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

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


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

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