=Paper=
{{Paper
|id=Vol-1623/paperme11
|storemode=property
|title=Algorithm Realization of a Stochastic Network Resource Mega-Project Management Model
|pdfUrl=https://ceur-ws.org/Vol-1623/paperme11.pdf
|volume=Vol-1623
|authors=Nina Plyaskina
|dblpUrl=https://dblp.org/rec/conf/door/Plyaskina16
}}
==Algorithm Realization of a Stochastic Network Resource Mega-Project Management Model==
https://ceur-ws.org/Vol-1623/paperme11.pdf
Àëãîðèòì ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷åñêîé
ìîäåëè ðåñóðñíîãî ìåãàïðîåêòà
Í.È. Ïëÿñêèíà
1
Èíñòèòóò ýêîíîìèêè è îðãàíèçàöèè ïðîìûøëåííîãî ïðîèçâîäñòâà ÑÎ ÐÀÍ,
2
Íîâîñèáèðñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò, Íîâîñèáèðñê, Ðîññèÿ.
pliaskina@hotmail.com
Àííîòàöèÿ  ñòàòüå ïðåäëîæåí àëãîðèòì ñòàòèñòè÷åñêîãî ðîçûãðûøà ïî-
ñòðîåíèÿ ðàñïèñàíèÿ ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè ðåñóðñíîãî ìåãàïðîåê-
òà. Âûáèðàåòñÿ ðåàëèçàöèÿ ìîäåëè ñ ìàêñèìàëüíîé ïðèáûëüþ íà åäèíèöó
âëîæåííûõ èíâåñòèöèé ïðè çàäàííûõ äèðåêòèâíûõ ñðîêàõ è îãðàíè÷åííî-
ñòè ðåñóðñîâ.
Êëþ÷åâûå ñëîâà: ñåòåâàÿ ñòîõàñòè÷åñêàÿ ìîäåëü, àëãîðèòì ñòàòèñòè÷å-
ñêîãî ðîçûãðûøà, ìåãàïðîåêò, çàäà÷à îïòèìèçàöèè, ïîñòðîåíèå ðàñïèñàíèÿ
Óñòîé÷èâîå îáåñïå÷åíèå ýêîíîìèêè ñòðàíû òîïëèâíî-ýíåðãåòè÷åñêèìè ðåñóð-
ñàìè ïðè âîçðàñòàþùåì ñïðîñå è âûñîêîé èíåðöèîííîñòè ìèíåðàëüíî-ñûðüåâîãî
êîìïëåêñà îáóñëîâëèâàåò ïîâûøåíèå çíà÷èìîñòè ìåãàïðîåêòîâ îñâîåíèÿ ðåñóðñîâ
íîâûõ ðåãèîíîâ. Ìåãàïðîåêò ÿâëÿåòñÿ äîëãîñðî÷íûì êàïèòàëîåìêèì ïðîåêòîì ñ
ìíîæåñòâîì ó÷àñòíèêîâ è âûñîêèìè ðèñêàìè ðåàëèçàöèè èõ èíâåñòèöèîííûõ ïðî-
åêòîâ. Äëÿ óïðàâëåíèÿ èíâåñòèöèîííîé ïðîãðàììîé ìåãàïðîåêòà ïðåäëàãàåòñÿ èñ-
ïîëüçîâàòü ñåòåâûå ñòîõàñòè÷åñêèå ìîäåëè.
1 Ôîðìàëüíîå îïèñàíèå ñòîõàñòè÷åñêîé ñåòåâîé ìîäåëè
ìåãàïðîåêòà
Ìîäåëè äàííîãî òèïà ïîçâîëÿþò ó÷èòûâàòü àëüòåðíàòèâíûå òåõíîëîãèè âûïîëíå-
íèÿ ðàáîò ñ îïðåäåëåííîé âåðîÿòíîñòüþ èõ ðåàëèçàöèè. Ñòîõàñòè÷åñêàÿ ñåòåâàÿ
ìîäåëü ìåãàïðîåêòà ïðåäíàçíà÷åíà äëÿ îöåíêè âëèÿíèÿ íåîïðåäåííîñòè âûïîë-
íåíèÿ ðàáîò íà ñðîêè, ìàñøòàáû è ýôôåêòèâíîñòü åãî ðåàëèçàöèè. Çàäà÷à ðå-
àëèçàöèè èíâåñòèöèîííîé ïðîãðàììû ìåãàïðîåêòà ïðåäñòàâëåíà êàê çàäà÷à îï-
òèìèçàöèè ðåñóðñíî-êàëåíäàðíîãî ïëàíèðîâàíèÿ ïðè àëüòåðíàòèâíûõ âàðèàíòàõ
âûïîëíåíèÿ ðàáîò ñ ðàçëè÷íûìè âåðîÿòíîñòÿìè. Ïðåäëîæåí àëãîðèòì ñòàòèñòè-
÷åñêîãî ðîçûãðûøà ïîñòðîåíèÿ ðàñïèñàíèÿ âûïîëíåíèÿ ìåãàïðîåêòà. Âûáèðàåòñÿ
ðåàëèçàöèÿ ìîäåëè ñ ìàêñèìàëüíîé ïðèáûëüþ íà åäèíèöó âëîæåííûõ èíâåñòèöèé
ïðè çàäàííûõ äèðåêòèâíûõ ñðîêàõ è îãðàíè÷åííîñòè ðåñóðñîâ. Ïðåäïîëàãàåòñÿ,
Copyright ⃝
c by the paper's authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
Àëãîðèòì ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè 639
÷òî òåõíîëîãè÷åñêàÿ ïîñëåäîâàòåëüíîñòü âûïîëíåíèÿ ðàáîò ïðîåêòà çàäàíà â âèäå
îðèåíòèðîâàííîãî ãðàôà G = (X, U ), áåç êîíòóðîâ è ïåòåëü, ãäå X ìíîæåñòâî
âåðøèí, ñîîòâåòñòâóþùèõ ñîáûòèÿì ñåòåâîé ìîäåëè; U ⊂ X × X ìíîæåñòâî
äóã, ñîîòâåòñòâóþùèõ ðàáîòàì. Ïóñòü U+− ìíîæåñòâî ðàáîò, èñõîäÿùèõ èç âåð-
øèíû X , Ux+ - ìíîæåñòâî ðàáîò, âõîäÿùèõ â âåðøèíó x ∈ X . Ïðè ïîñòðîåíèè ñòî-
õàñòè÷åñêîé ñåòåâîé ìîäåëè èñïîëüçóþòñÿ âîñåìü òèïîâ ñîáûòèé, îïèñûâàþùèõ
ïðàêòè÷åñêè âñå ñèòóàöèè, âñòðå÷àþùèåñÿ ïðè ìîäåëèðîâàíèè ñëîæíûõ ïðîåêòîâ
[1]. Ïðåäïîëàãàåòñÿ, ÷òî çàäàíû ñëåäóþùèå âåëè÷èíû: N ÷èñëî ðàáîò ñåòåâîé
ìîäåëè; M ÷èñëî âåðøèí (ñîáûòèé); W ñïèñîê ðàáîò ñåòåâîé ìîäåëè ñ ýëå-
ìåíòàìè (xv , yv , τv ), îïèñûâàþùèìè ñîîòâåòñòâåííî, íà÷àëüíîå, êîíå÷íîå ñîáûòèå
è äëèòåëüíîñòü ðàáîòû v, v = 1, . . . , N ; Tmax ïåññèìèñòè÷åñêàÿ îöåíêà äëèòåëü-
íîñòè ïðîåêòà; pu âåðîÿòíîñòü ðåàëèçàöèè ðàáîòû u ∈ U , 0 ≤ pu ≤ 1; P C
ñïèñîê ðåøàþùèõ ñîáûòèé, êîòîðûé âêëþ÷àåò â ñåáÿ èíôîðìàöèþ î êàæäîì àëü-
òåðíàòèâíîì ñîáûòèè ñåòè â ñëåäóþùåì ïîðÿäêå: øèôð ðåøàþùåãî ñîáûòèÿ x,
òèï ñîáûòèÿ x, øèôðû êîíå÷íûõ ñîáûòèé ðàáîò èç ìíîæåñòâà Ux− è âåðîÿòíîñòè
ðåàëèçàöèè ðàáîò, âûõîäÿùèõ èç x; ôîðìèðóåòñÿ ìàññèâ Tp äëÿ âû÷èñëåíèÿ íàè-
áîëåå ðàííèõ âðåìåí âåðøèí (ñîáûòèé) ñåòåâîé ìîäåëè; ìíîæåñòâî UM+ âêëþ÷àåò
â ñåáÿ ôèêòèâíûå ðàáîòû íóëåâîé äëèòåëüíîñòè, ñîåäèíÿþùèå êîíöåâûå ñîáûòèÿ
èñõîäíîé ñåòåâîé ìîäåëè ñ âåðøèíîé M ; K çàäàííîå ÷èñëî ðåàëèçàöèé ñòîõà-
ñòè÷åñêîé ñåòåâîé ìîäåëè.
2 Àëãîðèòì ñòàòèñòè÷åñêîãî ðîçûãðûøà
Àëãîðèòì ñòàòèñòè÷åñêîãî ðîçûãðûøà îòäåëüíîé ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷å-
ñêîé ñåòåâîé ìîäåëè ñîñòîèò â ïîñëåäîâàòåëüíîì ðàññìîòðåíèè ãðóïïèðîâîê ðàáîò
Ux− è âû÷èñëåíèè âðåìåííûõ õàðàêòåðèñòèê ñîáûòèé.  ðåçóëüòàòå ðîçûãðûøà
÷àñòü ðàáîò îêàçûâàåòñÿ ðåàëèçîâàííîé, îñòàëüíûå ðàáîòû èñêëþ÷àþòñÿ èç ñïèñ-
êà. Ðîçûãðûø êàæäîé ðàáîòû (x, y) ∈ Ux− îïðåäåëÿåòñÿ êîíêðåòíûì îïèñàíèåì
ëîãè÷åñêèõ âîçìîæíîñòåé íà÷àëüíîãî ñîáûòèÿ x è êîíå÷íîãî ñîáûòèÿ y ýòîé ðà-
áîòû. Èñêëþ÷åíèå ðàáîòû (x, y) èç òåêóùåé ðåàëèçàöèè ïðîèçâîäèòñÿ ñîãëàñíî
ïðàâèëó A, à âêëþ÷åíèå åå â êîíêðåòíóþ ðåàëèçàöèþ - ñîãëàñíî ïðàâèëó B [1]. Ñ
öåëüþ óìåíüøåíèÿ âû÷èñëèòåëüíûõ çàòðàò èñïîëüçóåòñÿ âåòâëåíèå àëãîðèòìà â
çàâèñèìîñòè îò ÷èñëà N . Ïðè N < M0 /2 èñïîëüçóåòñÿ ïðèâåäåíèå âåðîÿòíîñòåé
ê îáùåìó çíàìåíàòåëþ; ïðè M0 /2 < N < M0 ìåòîä Óîëêåðà; ïðè N > M0
áèíàðíûé ïîèñê, çàòðàòû êîòîðîãî èìåþò ïîðÿäîê log2 N . Çäåñü M0 ðàçìåð
ìàêñèìàëüíîãî ìàññèâà äëÿ çàäàííîãî êîìïüþòåðà è âûáðàííîãî ÿçûêà ïðîãðàì-
ìèðîâàíèÿ. Äëÿ îäíîé ðåàëèçàöèè àëãîðèòì òðåáóåò âûïîëíåíèÿ îïåðàöèé â êî-
ëè÷åñòâå O(nM ) ïðè N < M0 è O(nM log2 N ) ïðè N ≥ M0 . Íåîáõîäèìàÿ ïàìÿòü
ëèíåéíî çàâèñèò îò ÷èñëà ðàáîò n, ÷èñëà ñîáûòèé è Tmax .
Äëÿ àíàëèçà ðåçóëüòàòîâ òåêóùåé ðåàëèçàöèè èñïîëüçóåòñÿ ñ÷åò÷èê K+ óñïåø-
íûõ ðåàëèçàöèé, ãèñòîãðàììà q ðàñïðåäåëåíèÿ âåëè÷èíû Tkp , ñ÷åò÷èêè ðåàëèçî-
âàííîñòè rv è êðèòè÷íîñòè kv ðàáîòû v. Êàæäîé ðåàëèçàöèè ξ, 1 ≤ ξ ≤ K ñòî-
õàñòè÷åñêîé ñåòåâîé ìîäåëè cîîòâåòñòâóåò çíà÷åíèå ñëó÷àéíîé âåëè÷èíû âðåìå-
íè çàâåðøåíèÿ ïðîåêòà Tkpξ . Ðåàëèçàöèÿ ÿâëÿåòñÿ óäà÷íîé ïðè âûïîëíåíèè óñëî-
âèÿ Tkpξ ≤ Tmax .  ýòîì ñëó÷àå óâåëè÷èâàåì íà åäèíèöó êîëè÷åñòâî óñïåøíûõ
640 Í.È. Ïëÿñêèíà
ðåàëèçàöèé ñ÷åò÷èêà K+ èξ êîððåêòèðóåì ãèñòîãðàììó ðàñïðåäåëåíèÿ âåëè÷èíû
Tkp : qτ = qτ + 1, ãäå T = [Tkp ]. Íà ñëåäóþùåì ýòàïå îñóùåñòâëÿåì ïîñëåäîâàòåëü-
íûé ïðîñìîòð ñïèñêà ðàáîò ñåòåâîé ìîäåëè. Åñëè ðàáîòà ñ íîìåðîì v âîøëà â äàí-
íóþ ðåàëèçàöèþ, òî óâåëè÷èâàåì íà åäèíèöó ñ÷åò÷èê ðåàëèçîâàííîñòè rv . Ïðîâå-
ðÿåì ïðèíàäëåæíîñòü êàæäîé ðåàëèçîâàííîé ðàáîòû êàêîìó-ëèáî êðèòè÷åñêîìó
ïóòè.  ñëó÷àå óñïåøíîñòè èñõîäà óâåëè÷èâàåì íà åäèíèöó ñ÷åò÷èê êðèòè÷íîñòè
kv ðàññìàòðèâàåìîé ðàáîòû è îòìå÷àåì ôàêò ïðèíàäëåæíîñòè êðèòè÷åñêîìó ïó-
òè. Ïîñëå ðîçûãðûøà çàäàííîãî ÷èñëà K ðåàëèçàöèé ïðîèçâîäèòñÿ îêîí÷àòåëüíàÿ
îáðàáîòêà ïîëó÷åííûõ ðåçóëüòàòîâ, âêëþ÷àþùàÿ ñëåäóþùèå îïåðàöèè:
1. Âû÷èñëåíèå ýìïèðè÷åñêîé ôóíêöèè ðàñïðåäåëåíèÿ âðåìåíè âûïîëíåíèÿ ïðî-
åêòà [2].
− +
pT − = qT − ; pT = pT −1 + qT , T = Tkp + 1, . . . , Tkp .
kp kp
 ðåçóëüòàòå âåëè÷èíà pT äàåò−îöåíêó âåðîÿòíîñòè îñóùåñòâëåíèÿ ïðîåêòà â
ïðåäåëàõ ïëàíîâîãî ïåðèîäà [Tkp , T ].
2. Âû÷èñëåíèå êîýôôèöèåíòîâ ðåàëèçîâàííîñòè è êðèòè÷íîñòè ðàáîò
rv = rv /K+, v = 1, . . . , N ; kv = kv /K+, v = 1, . . . , N.
3. Îöåíêà âåðîÿòíîñòè íåóäà÷íîãî èñõîäà ñåòåâîãî ïðîåêòà âåëè÷èíîé Pn = 1 −
K + /K (äëÿ ñîáûòèé c Tkp > Tmax ).
4. Îöåíêà âåðîÿòíîñòè âîçìîæíûõ èñõîäîâ ñòîõàñòè÷åñêîé ñåòåâîé ìîäåëè ïî
çíà÷åíèÿì rv äëÿ ôèêòèâíûõ ðàáîò èç ìíîæåñòâà UM+ , âõîäÿùèõ â ñîáûòèå
ñ íîìåðîì M .
 ðåçóëüòàòå ïðèìåíåíèÿ àëãîðèòìà ïîëó÷àåì ñåìåéñòâî äåòåðìèíèðîâàííûõ ñå-
òåâûõ ìîäåëåé. Â êàæäîé êîíêðåòíîé ðåàëèçàöèè äåòåðìèíèðîâàííîé ñåòåâîé ìî-
äåëè ðåøàåòñÿ çàäà÷à îòûñêàíèÿ äîïóñòèìîãî ðàñïèñàíèÿ η∗ ìèíèìàëüíîé äëè-
òåëüíîñòè, ïðè êîòîðîì öåëåâàÿ ôóíêöèÿ
T (η) = max ∈ V (tu + τu ) → min
u η
Ïðè ýòîì âûïîëíÿþòñÿ óñëîâèÿ:
1. ñîáëþäàåòñÿ òåõíîëîãèÿ âûïîëíåíèÿ ðàáîò tu + τu ≤ tv äëÿ ëþáîé ïàðû ðàáîò
u, v ∈ U òàêîé, ÷òî yu = xv ;
2. âûïîëíÿþòñÿ äèðåêòèâíûå ñðîêè tu + τu ≤ Tdir (x) äëÿ âñåõ ðàáîò u ∈ U ñ
yu = x, ãäå x ∈ X dir ;
3. ñóììàðíàÿ èíòåíñèâíîñòü â ëþáîé ìîìåíò âðåìåíè t = t, . . . , T è äëÿ ëþáîãî
òèïà ðåñóðñîâ (k = 1, . . . , m) ïîòðåáëÿåìûõ ðåñóðñîâ íå ïðåâûøàåò êîëè÷åñòâà
Σu∈U k(t) ruk ≤ R¯tk ðåñóðñîâ, èìåþùèõñÿ â ìîìåíò t, ãäå Rtk -çàïàñ ðåñóðñîâ k -ãî
òèïà â t-ì ïðîìåæóòêå ïëàíèðóåìîãî âðåìåíè.
Ïðåäëîæåííûé àëãîðèòì ðåàëèçîâàí íà ÏÊ ñ ïîìîùüþ ÿçûêà ïðîãðàììèðîâàíèÿ
Ñ++ íà ðåàëüíîé ýêîíîìè÷åñêîé èíôîðìàöèè ìåãàïðîåêòà ÂÑÍÃÊ. Ïðîèçâåäåíî
20 ðåàëèçàöèé ñòîõàñòè÷åñêîé ñåòåâîé ìîäåëè. Âû÷èñëåíà ôóíêöèÿ ðàñïðåäåëåíèÿ
Àëãîðèòì ðåàëèçàöèè ñåòåâîé ñòîõàñòè÷åñêîé ìîäåëè 641
âðåìåíè âûïîëíåíèÿ ïðîåêòà, ïîñòðîåíà ãèñòîãðàììà ðàñïðåäåëåíèÿ Tkp è èíòå-
ãðàëüíàÿ ôóíêöèÿ ðàñïðåäåëåíèÿ. Ïåññèìèñòè÷åñêàÿ îöåíêà äëèòåëüíîñòè ïðîåê-
òà Tmax ðàâíà 44 ãîäàì, Tkp äëÿ ýôôåêòèâíîé ðåàëèçàöèè ñîñòàâëÿåò 42, 5 ãîäà.
Äëÿ ðåàëèçàöèè ïðîãðàììû ìåãàïðîåêòà íåîáõîäèìî èíâåñòèðîâàòü 144, 1 ìëðä.
äîëë. êàïèòàëüíûõ âëîæåíèé. Óäåëüíàÿ ïðèáûëü ñîñòàâëÿåò 768,8 äîëë./ò íåôòè.
Ñïèñîê ëèòåðàòóðû
1. Ãèìàäè Ý.Õ., Ãîí÷àðîâ Å.Í., Çàëþáîâñêèé Â.Â., Ïëÿñêèíà Í.È., Õàðèòîíîâà Â.Í.:
Î ïðîãðàììíî-ìàòåìàòè÷åñêîì îáåñïå÷åíèè äëÿ çàäà÷è ðåñóðñíî-êàëåíäàðíîãî ïëà-
íèðîâàíèÿ Âîñòî÷íî-Ñèáèðñêîãî íåôòåãàçîâîãî êîìïëåêñà. Âåñòíèê Íîâîñèáèðñêîãî
ãîñóäàðñòâåííîãî óíèâåðñèòåòà. Ñåðèÿ: Ìàòåìàòèêà, ìåõàíèêà, èíôîðìàòèêà. Ò. 10,
âûï. 4. - Ñ. 5267 (2010)
2. Ãèìàäè Ý.Õ., Ãëåáîâ Í.È.: Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ïðèíÿòèÿ ðåøåíèé.
Ó÷åáíîå ïîñîáèå. Íîâîñèáèðñê: ÍÃÓ, (2008)
Algorithm Realization of a Stochastic Network
Resource Mega-Project Management Model
Nina I. Plyaskina
1
Institute of Economics and Industrial Engineering of SB RAS
2
Novosibirsk State Univer-sity, Novosibirsk, Russia,
pliaskina@hotmail.com
Abstract. An algorithm random drawing of construction schedule network
stochastic model resource megaproject. Selects the implementation of the model
with the maxi-mum profit per unit of investments at specified deadlines and lim-
ited resources.
Keywords: stochastic network model, a statistical algorithm lottery, mega-
project, the optimization problem, the construction schedule.
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org