STROŠKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOŠTEVILSKIM NELINEARNIM PROGRAMIRANJEM • Rok Cajzek, izr. prof. dr. Uroš Klanšek
STROŠKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOŠTEVILSKIM NELINEARNIM PROGRAMIRANJEM
CONSTRUCTION PROJECT OPTIMAL TIME-COST TRADE-OFF SCHEDULING BY MIXED-INTEGER NONLINEAR PROGRAMMING
Sv. Florijan 120, 3250 Rogaška Slatina izr. prof. dr. Uroš Klanšek, univ. dipl. gosp. inž.
Univerza v Mariboru, Fakulteta za gradbeništvo, prometno inženirstvo in arhitekturo Smetanova ulica 17, 2000 Maribor
Povzetek l V članku je predstavljeno stroškovno optimalno terminsko planiranje gradbenih projektov z mešanim celoštevilskim nelinearnim programiranjem (MINLP). Predlagana tehnika omogoča pridobitev optimalnega terminskega plana za gradbeni projekt pri minimalnih skupnih stroških njegove izvedbe, upoštevajoč posplošene časovne odnose med aktivnostmi, omejitve trajanja projekta in logične pogoje. Pristop MINLP omogoča obravnavanje nelinearnosti v optimizacijskem modelu. Izhodni rezultati MINLP-optimizacije so eksaktni in določajo terminski plan projekta v diskretnih časovnih enotah. Prednosti predlaganega pristopa so predstavljene na primeru uporabe. Ključne besede: terminsko planiranje, gradbeni projekti, diskretna optimizacija, minimalni skupni stroški, mešano celoštevilsko nelinearno programiranje
Summary l This paper presents the construction project optimal time-cost trade-off scheduling by mixed-integer nonlinear programming (MINLP). The proposed technique enables the acquisition of an optimal time schedule for a construction project at a minimum total cost of its execution, taking into account the generalized precedence relationships among activities, project duration constraints and logical conditions. The MINLP approach allows consideration of nonlinearities in the optimization model. Output results of the MINLP optimization are exact and determine the project's time schedule in discrete time units. Advantages of the proposed approach are demonstrated on an application example.
Key words: time scheduling, construction projects, discrete optimization, minimum total cost, mixed-integer nonlinear programming
Rok Cajzek, mag. gosp. inž.
GIC GRADNJE, d. o. o.
Znanstveni članek
UDK 519.853:69
185
1*UVOD
Začetki uporabe optimizacijskih metod na področju terminskega planiranja projektov segajo v konec petdesetih let prejšnjega stoletja in približno sovpadajo z obdobjem pionirskih prispevkov na mrežnih tehnikah. Med prvimi na tem področju sta bila raziskovalca Morgan Walker in John Sayer [Walker, 1959], ki sta predstavila metodo kritične poti. Po predstavitvi omenjene metode so problemi stroškovne optimizacije sprožili precejšnje zanimanje med raziskovalci, ki so v preteklosti objavili in še vedno prispevajo številne publikacije. Zgodnje raziskave na področju stroškovne optimizacije so bile predstavljene že leta 1959 [Kelley, 1959], njihov cilj je bil znižati skupne stroške projekta s pospeševanjem in razporejanjem aktivnosti v okviru danega strukturnega mrežnega diagrama. Zatem so se zvrstile še številne raziskave in zelo hitro se je spoznalo, da ko skupni stroški projekta izkazujejo nelinearno časovno odvisnost in ko je potek aktivnosti treba podati v diskretnih časovnih enotah (npr. v delovnih dnevih), stroškovna optimizacija terminskega plana postane nelinearni diskreten problem. V splošnem za stroškovno optimizacijo velja, da so stroški virov običajno v obratnem
odnosu s trajanjem posamezne aktivnosti [Feng, 1997]. Na primer, ob uporabi naprednejše opreme in ob angažiranju večjega števila delavcev za posamezno aktivnost lahko dosežemo zmanjšanje potrebnega časa za njeno dokončanje, vendar po drugi strani povečamo stroške izvedbe. Problemi stroškovne optimizacije terminskih planov veljajo za zahtevne naloge predvsem zaradi kombi-natorične narave območja možnih rešitev [Chassiakos, 2005]. Literatura na tem področju je bogata, kar nakazuje na interes raziskovalcev pri iskanju rešitev in novosti s področja. Razloge za priljubljenost lahko iščemo v številnih segmentih, med drugim tudi v zahtevnosti razvijanja robustnih algoritmov za iskanje rešitev kompleksnih optimizacijskih problemov, ki se običajno pojavljajo v praksi. Po drugi strani je področje prav tako zanimivo za industrijo, saj lahko napredne tehnike opti-miranja prinesejo dodatne prihranke in tako upravičijo strošek razvoja modelov. Za iskanje optimalnih rešitev nelinearnih diskretnih problemov stroškovne optimizacije terminskih planov je bilo predlaganih več metod, npr. genetski algoritmi ([Feng, 1997], [Li, 1999], [Hegazy, 1999], [Leu, 2001],
2* ODNOSI MED TRAJANJEM IN STROŠKI PRI PROBLEMIH TERMINSKEGA PLANIRANJA
Pogosto izbrani cilj optimizacije terminske-ga plana je minimizacija skupnih stroškov izvedbe projekta, tj. direktnih (neposrednih) in indirektnih (posrednih) stroškov skupaj. V literaturi zasledimo odnose med trajanjem in direktnimi stroški aktivnosti, ki so formulirani z raznovrstnimi funkcijami, saj imajo avtorji različne poglede na njihov opis. V zgodnjih študijah se največkrat zasledi lineani opis omenjenih odnosov [Kapur, 1973], kar pa se v realnosti le redko odraža. Pozneje so številni avtorji odnose med trajanjem in direktnimi stroški opisovali s konveksnimi funkcijami, npr. ([Kapur, 1973], [Foldes, 1993], [Deckro, 1995], [Deckro, 2003]), s konkavnimi [Falk, 1972] ali s hibridnimi, tj. konkavno-konvek-snimi funkcijami [Moder, 1995]. V primerih, ko bi se pojavila prevelika razhajanja med dejanskimi podatki in aproksimirano funkcijo, se je izkazalo, da je bolj smotrno opraviti
diskretizacijo omenjenih odnosov [Chassiakos, 2005].
Indirektni stroški gradbenega projekta običajno obsegajo začetne stroške, stroške režije, poslovanja, delovanja opreme ipd. Omenjene stroške lahko sicer opredelimo z različnimi izrazi, vendar pa se v večini primerov uporablja linearni odnos med trajanjem projekta in indirektnimi stroški (npr. konstantni strošek na izbrano časovno enoto). Treba je omeniti tudi, da so v gradbene pogodbe pogosto vključene še kazni za nedoseganje pravočasnosti izvedbe projekta in (redkeje) bonusi za predčasen zaključek, ki pa v večini primerov niso zgolj v linearnem odnosu glede na čas [Cajzek, 2016]. Na primer, skladno z gradbeno prakso v Sloveniji in veljavnimi predpisi [Posebne gradbene uzance, 1977] pogodbene kazni običajno nastopajo v kosoma linearni obliki, kjer znaša dnevna kazen za zamudo pri pro-
[Zheng, 2004], [Eshtehardian, 2009]), simulirano ohlajanje ([Azaron, 2007], [He, 2009]), tabu iskanje ([He, 2009], [Hazir, 2011]), nevronske mreže [Adeli, 1997], kolonija mravelj ([Ng, 2008], [Xiong, 2008], [Afshar, 2009], [Kalhor, 2011]), roji delcev [Yang, 2007], dife-renčna evolucija [Nearchou, 2010], harmo-nijsko iskanje [Geem, 2001], mešano celo-številsko linearno programiranje ([Achuthan, 2001], [Vanhoucke, 2002], [Sakellaropoulos, 2004], [Akkan, 2005], [Sonmez, 2012], [Zou, 2017]), in hibridne metode, kot so genetski algoritmi in dinamično programiranje [Ezeldin, 2009], rezanje ravnine in simulacija Monte Carlo [Mokhtari, 2010].
V članku je predstavljeno stroškovno optimalno terminsko planiranje gradbenih projektov z mešanim celoštevilskim nelinearnim programiranjem (MINLP). Predlagani pristop omogoča pridobitev optimalnega terminske-ga plana za gradbeni projekt pri minimalnih skupnih stroških njegove izvedbe, upoštevajoč posplošene časovne odnose med aktivnostmi, omejitve trajanja projekta in logične pogoje. Pristop MINLP omogoča obravnavanje neline-arnosti v optimizacijskem modelu. Izhodni rezultati MINLP-optimizacije so eksaktni in določajo terminski plan v diskretnih časovnih enotah. Prednosti predlaganega pristopa so predstavljene na primeru uporabe.
jektu 0,1 % zneska pogodbe, vendar skupaj ne več kot 5 % njene skupne vrednosti. Takšne posebnosti z vidika optimizacije terminskih planov povzročijo nekonveksno obnašanje skupnih stroškov projekta glede na njegovo trajanje.
186
STROŠKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOŠTEVILSKIM NELINEARNIM PROGRAMIRANJEM • Rok Cajzek, izr. prof. dr. Uroš Klanšek
3'SPLOSNA FORMULACIJA MINLP-PROBLEMA
MINLP predstavlja eksaktno tehniko matematičnega programiranja za reševanje nelinearnih optimizacijskih problemov, ki hkrati vsebujejo zvezne in diskretne spremenljivke. Pri tem za zvezne odločitve uporabljamo zvezne spremenljivke, medtem ko lahko za diskretne odločitve uporabljamo celoštevilske ali pa binarne 0-1 spremenljivke. Zaradi zmožnosti procesiranja nelinearnih odnosov med spremenljivkami in diskretne narave obravnavane naloge smo se za iskanje optimalne rešitve odločili uporabiti pristop MINLP. Optimizacijski problem MINLP lahko na splošno predstavimo v naslednji obliki:
Min z =f[x) + cTy p.p. h(x) = O
g(x) s O	(MINLP-S)
By+Cx<b xeX={x\xe R",<x<xZG} yeY={O, iy,
kjer z predstavlja spremenljivko namenske funkcije; x označuje vektor zveznih spremen-
ljivk, ki je določen z definicijskim območjem A-prostora realnih števil Rn; y označuje vektor binarnih 0-1 odločitvenih spremenljivk in C predstavlja transponiran vektor konstant namenske funkcije. Zvezne spremenljivke x so lahko definirane linearno ali nelinearno v namenski funkciji z in pri omejitvah h(x) ter g(x), medtem ko se binarne 0-1 spremenljivke y lahko uporabijo samo v linearnih izrazih. Funkcije f(x), h(x) in g(x) predstavljajo nelinearne funkcije zveznih spremenljivk x ki so zajete v namenski funkciji. Vse funkcije f(x), h(x) in g(x) morajo biti zvezne in zvezno odvedljive. Izraz By+ Cx< 6 predstavlja skupino mešanih linearnih (ne)enačb.
4'FORMULACIJA MINLP-MODELA
Predhodno prikazana formulacija (MINLP-S) velja na splošno za probleme MINLP, za obravnavani optimizacijski problem pa je treba določiti bolj specifično formulacijo. Formulacija MINLP-modela za stroškovno optimizacijo terminskih planov tako vsebuje namensko funkcijo skupnih stroškov projekta, ki je podvržena minimizaciji, upoštevajoč posplošene časovne povezave med aktivnostmi, omejitve trajanja projekta in logične pogoje. Lahko jo predstavimo na naslednji način:
Min Ct = ^Ci (Di) + Ci(Dp) + Cp(Pl) -
iel
(1)
IsA	ieZ
Si + Di + Lij i Sj iel, jej(i), (tj) eFS (2)
Si + Lij<Sj
iel, jej(i), (ij>SS (3)
Si + Di + Lij S Sj + Dj tel, jej(i), (tj) eFF (4)
Si + Lij i Sj + D, iel, je](i), (ij) eSF (5)
Siat + Diaj- Sia ^ Dp ia, ia el Dp-PI + Pe = Dt PlPe = 0
Di = ^ ydi.kd.di
keK(i)
Zydi*=
H,k
keK(i)
Sf <St< st
iel
iel SieR*
(6)
(7)
(8) (9)
(10) (11)
Df1 <Di< D?	DteR-	(12)
0 <Pe< PeM	PeeR*	(13)
0 <Pl< PlN	PleR*	(14)
DpM < Dp < DpN	DpeR+	(15)
ydt,ke{ 0,1} tel,	keK(t)	(16)
Kriterij optimizacije je opredeljen z namensko funkcijo, ki je formulirana v enačbi (1), kjer spremenljivka Ct predstavlja skupne stroške projekta, množica I zajema projektne aktivnosti i, iEI, C (D) določa direktne stroške projektnih aktivnosti, C(Dp) vključuje indirekt-ne stroške projekta, Cp(Pl) definira stroške pogodbene kazni za zamudo (penale) in B(Pe) predstavlja pogodbeno nagrado za predčasno dokončanje projekta (bonus). Odnos med direktnim stroškom C aktivnosti in njenim trajanjem D, se v gradbeništvu pogosto izkaže za nelinearnega. V nasprotju s tem je višina indirektnih stroškov C pogosto določena v linearni odvisnosti od trajanja projekta Dp. Vsekakor je na tem mestu treba poudariti, da se nelinearne funkcije Ci(Dp) prav tako lahko vključijo v predstavljeni MINLP-model, če se izkaže, da je to potrebno. Stroški pogodbene kazni Cp so odvisni od trajanja zamude Pl pri dokončanju projekta, medtem ko je vrednost pogodbene nagrade Bodvisna od dolžine časovnega prihranka Pe pri predčasnem zaključku projekta. V literaturi so Cp(Pl) in B(Pe) najpogosteje določeni kot konstantne vrednosti (enkratna kazen/nagrada) ali pa kot neomejene linearne funkcije.
Za formuliranje navzgor omejenih linearnih pogodbenih kazni Cp(Pl), ki so najpogosteje določene v gradbenih pogodbah, se lahko uporabi naslednji izraz [Klanšek, 2016]: (Pl
Cp(Pl) = Cpm
Dg
arctan (C/ Pl) V n	2.
('-S)
Dg)
arctan (C/ (Pl - Dg)) 1 h +2
1(17)
kjer Cpm predstavlja najvišjo možno vrednost pogodbene kazni (penala) in Dg predstavlja obdobje zamude, kjer penali naraščajo linearno pod naklonom Pl/Dg. Po koncu omenjenega obdobja funkcija Cp(Pl) doseže maksimalno vrednost Cpm. Torej, če trajanje zamude preseže obdobje Dg, potem funkcija Cp(Pl) poda za Plkonstantno vrednost Cpm, glej sliko 1.
Slika 1* Navzgor omejeni linearni penali.
Faktor prileganja aproksimacijske funkcije Cf se določi kot konstanta velike vrednosti. Prikazana enačba (17) se lahko na podoben način uporabi tudi v primeru omejenih linearnih bonusov.
Strukturni mrežni diagram je sestavljen iz kritičnih aktivnosti (tistih, ki nimajo časovnih
187
rezerv) in nekritičnih aktivnosti (tiste, ki imajo časovne rezerve). Nekritične projektne aktivnosti se lahko pričnejo nekoliko pozneje (v okviru časovnih rezerv) tako, da to ne vpliva na trajanje in stroške celotnega projekta. V namensko funkcijo so dodatno vključeni izrazi +eSi in -eS, ki so dodeljeni aktivnostim z najzgodnejše planiranimi začetki (to so aktivnosti ¡GA) in aktivnostim, katerih pričetki se planirajo najpozneje, kot je mogoče (to so aktivnosti iGZ). Omenjeni izrazi vključujejo konstanto majhne vrednosti e, ki nima praktične posledice na vrednost namenske funkcije (Sakellaropoulos in Chassiakos, 2004), po drugi strani pa je tako omogočeno, da pričetki projektnih aktivnosti S pri minimizaciji namenske funkcije zavzamejo diskretne vrednosti.
Enačbe (2)-(5) definirajo pogoje posplošenih časovnih povezav, ki nastopajo med obravnavanimi aktivnostmi i iGI in njihovimi neposredno sledečimi aktivnostmi j jGJ(i), to so: konec-začetek (Finish-to-Start: FS), začetek-začetek (Start-to-Start: SS), konec-konec (Finish-to-Finish: FF) in začetek-konec (Start-to-Finish: SF). Omenjene splošne omejitve se uporabljajo pri preračunu po metodi kritične poti, glej Sliko 2.
Časi začetkov aktivnosti S in trajanja aktivnosti D so definirani z zveznimi spremenljivkami, časovni zamiki Lu (zakasnitve ali prehitevanja med obravnavanimi aktivnostmi in njihovimi neposredno sledečimi aktivnostmi) pa so določeni s celoštevilskimi konstantnimi parametri.
Pogojne neenačbe (6) zagotavljajo, da bodo vse aktivnosti zaključene med trajanjem celotnega projekta, torej da bodo zaključene med začetkom prve projektne aktivnosti in koncem zadnje projektne aktivnosti. Odločitveni spremenljivki S« in D« označujeta čase pričetkov in trajanja zaključnih aktivnosti i«, i« G I, medtem ko Sa predstavlja trenutke akti-vacije izvajanja začetnih aktivnosti ia, iaGI. Omenjeni pogoji delujejo pod predpostavko, da se neposredno sledeče aktivnosti ne smejo pričeti pred začetnimi aktivnostmi, medtem ko neposredno predhodnim aktivnostim ni dovoljeno, da se zaključijo po končnih aktivnostih.
Pogojna enačba (7) definira logični odnos med trajanjem projekta Dp, trajanjem zamude pri dokončanju projekta Pl, dolžino časovnega prihranka pri predčasnem zaključku projekta Pe in rokom za dokončanje projekta Dt. Sledi enačba (8), ki določa logično dejstvo, da pro-
Slika 2* Posplošene časovne povezave med aktivnostmi.
jekt ne more istočasno zamujati in prehitevati, lahko pa je dokončan pravočasno. Omenjena enačba pri izračunu optimalne rešitve omogoča, da lahko največ ena od spremenljivk Pl in Pe doseže vrednost, ki je različna od nič.
Logične omejitve, prikazane v enačbah (9) in (10), morajo biti izpolnjene pri izboru optimalnih diskretnih rešitev za zvezne spremenljivke D, ki so definirane znotraj superstrukture alternativ. Množica K(i) opredeljuje možne rešitve k, kGK(i) v predstavljenem MINLP-modelu. Pri tem nabor celoštevilskih konstant <ddik določa superstrukturo alternativ za diskretna trajanja aktivnosti. Vsaka celoštevilska konstanta ddk tako predstavlja možno diskretno rešitev za pripadajočo zvezno spremenljivko D, pri čemer se izbor optimalne diskretne rešitve opravi s pomočjo binarnih 0-1 spremenljivk ydik. Binarne spremenljivke ydik so vključene v MINLP-model z namenom, da se vzpostavijo optimalna diskretna trajanja za projektne aktivnosti. Vsaka celoštevilska konstanta, vključena v superstrukturo diskretnih alternativ, se lahko izbere kot diskretna rešitev pripadajoče zvezne spremenljivke, ampak le v primeru, če dodeljena binarna spremenljivka zavzame vrednost 1. Če pa dodeljena binarna spremenljivka zavzame vrednost 0, to pomeni, da diskretna alternativa ni izbrana. Enačba (10) zagotavlja, da se za vsako spremenljivko Di mora izbrati natanko ena diskretna vrednost ddk izmed možnih rešitev.
Neenačbe (11)—(12) definirajo, da morajo biti optimalne vrednosti zveznih spremenljivk S in Di najdene med njihovimi zgornjimi in spodnjimi mejami (tj. med zgodnjimi in poznimi časi za S/ oz. med minimalnimi in normalnimi trajanji za Di) kakor tudi določene s pozitivnimi realnimi števili. Neenačbe (13)-(15) prav tako postavljajo meje za optimalne vrednosti zveznih spremenljivk Pe, Pl in Dp v okviru prostora pozitivnih realnih števil, medtem ko enačba (16) opredeljuje binarnost spremenljivk ydik.
5'PRIMER
Primer obravnava projekt nadgradnje obstoječe dvopasovne hitre ceste v štiripasovno avtocesto z nadzorovanimi prometnimi priključki iz reference [Sakellaropoulos, 2004]. Stroškovna optimizacija terminskega plana z MINLP za omenjeni projekt je bila opravljena z osebnim računalnikom na 64-bitnem operacijskem sistemu s procesorjem Intel Core i7, 2,93 GHz, z 8 GB delovnega pomnilnika
in trdim diskom velikosti 1 TB, rezultati pa so bili pridobljeni prej kot v sekundi. Treba je poudariti, da je kriterij optimizacije tukaj spremenjen glede na izvirno referenco v smislu obravnavanja pogodbenih kazni, zato direktna primerjava rešitev ni možna, lahko pa se rezultati direktnih primerjav najdejo v referenci [Klanšek, 2012]. Modeliranje optimizacijskega problema je bilo opravljeno brez dodatnih
rutin s pomočjo naprednega algebrajskega jezika General Algebraic Modelling System [GAMS, 2018], za izvedbo MINLP-optimizacije pa je bil uporabljen globalni algoritem BARON [Ryoo, 1996].
5.1 Vhodni podatki
Obravnavani projekt obsega 29 aktivnosti. Preglednica 1 prikazuje aktivnosti projekta, časovne povezave in zamike.
Gradbeni vestnik • letnik 67 • september 2018
STROŠKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOŠTEVILSKIM NELINEARNIM PROGRAMIRANJEM • Rok Cajzek, izr. prof. dr. Uroš Klanšek
Aktivnost/Opis aktivnosti	Naslednja Časovna aktivnost povezava		Časovni zamik (dan)
Servisna cesta A:			
1. Izkop skal	2.	konec-začetek	-3
	3.	konec-začetek	0
	6.	konec-začetek	0
2. Izgradnja nasipov	3.	konec-začetek	0
	7.	konec-začetek	0
3. Nevezana nosilna plast	4.	konec-začetek	0
in povozni plato vozišča			
	8.	konec-začetek	0
4. Asfaltna plast	5.	začetek-začetek	1
	9.	konec-začetek	0
5. Začasne označbe, pro-	10.	konec-začetek	0
metni znaki in signa-			
lizacija			
	11.	konec-začetek	0
Servisna cesta B:			
6. Izkop zemlje in skal v	7.	konec-začetek	-1
razpadanju			
7. Izgradnja nasipov	8.	konec-začetek	0
8. Nevezana nosilna plast	9.	konec-začetek	0
in povozni plato vozišča			
9. Asfaltna plast	10.	konec-konec	1
10. Začasne označbe,	11.	konec-začetek	0
prometni znaki in signa-			
lizacija			
Avtocesta:			
11. Preusmeritev prometa	12.	konec-začetek	0
12. Izkop skal	13.	začetek-začetek	2
	15.	konec-začetek	-4
13. Izkop zemlje in skal v	14.	začetek-začetek	2
razpadanju, odstranitev			
vozišča			
14.	Stabilizacija temeljnih tal, podporni zidovi in prepusti
15.	Izgradnja nasipov
16.	Sistem drenažnih cevi
17.	Drenažne plasti
18.	Zasaditev površin ob cesti
19.	Električne inštalacije ob cesti
20.	Odvodni jarki
21.	Nevezana nosilna plast vozišča
22.	Povozni plato vozišča
23.	Varovalne ograje (New Jersey)
24.	Električne inštalacije v varovalnih ograjah
25.	Asfaltna plast #1
26.	Asfaltna plast #2
27.	Obrabna plast vozišča
28.	Trajne označbe, prometni znaki in signalizacija
29.	Preusmeritev prometa
15.
16.
17.
18. 19.
23.
26.
27.
28.
29.
konec-začetek
konec-začetek
začetek-začetek konec-začetek konec-začetek
20. začetek-začetek
21.	začetek-začetek
22.	začetek-začetek
konec-začetek
24. začetek-začetek
25. konec-začetek
začetek-začetek konec-začetek konec-začetek
konec-začetek
4 4 0
4 0 -3
Opomba: Uporaba negativnih časovnih zamikov izhaja iz primera (v gradbeni praksi sicer ni pogosta, vendar lahko ponekod nastopi).
Preglednica 1* Aktivnosti projekta, časovne povezave in zamiki
Rok za dokončanje projekta je bil 75 dni, indirektni stroški in pogodbena za predčasno zaključen projekt pa so
delovnih s 150 denarnimi enotami na dan. Pogodbena nagrada kazen za vsak dan zamude je opredeljena določeni v višini 200 denarnih enot, vendar lahko
znaša največ 1000 denarnih enot. Možnosti izvedbe posameznih aktivnosti so podane v preglednici 2.
Zap. št.	Možnost izvedbe 1		Možnost izvedbe 2		Možnost izvedbe 3	
aktiv-						
nosti	Trajanje	Stroški	Trajanje	Stroški	Trajanje	Stroški
1.	5	2.030	4	2.300	-	-
2.	8	1.020	7	1.280	6	1.510
3.	8	1.700	7	1.850	6	2.090
4.	4	590	3	730	--
5.	2	90	-	-	--
6.	4	910	3	1.100	--
7.	2	250	-	-	--
8.	7	1.490	6	1.650	5 1.830
9.	4	520	3	750	--
3
6
0
189
Rok Cajzek, izr. prof. dr. Uroš Klanšek*STROSKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOSTEVILSKIM NELINEARNIM PROGRAMIRANJEM
10.	2	90	-	-	-	-		20.	6	1.280	5	1.430	-	-
11.	1	50	-	-	-	-		21.	14	1.090	12	1.320	10	1.560
12.	8	3.260	7	3.580	6	3.710		22.	14	900	11	1.140	9	1.400
13.	5	1.140	4	1.400	3	1.720		23.	14	2.220	12	2.510	11	2.690
14.	4	300	3	450	-	-		24.	3	230	-	-	-	-
15.	8	1.020	6	1.300	5	1.430		25.	6	1.590	5	1.790	4	1.990
16.	9	790	8	900	6	1.180		26.	10	2.630	9	2.930	8	3.240
17.	13	3.340	12	3.750	11	4.060		27.	8	2.060	7	2.450	6	2.660
18.	9	470	8	650	7	830		28.	10	320	9	440	8	610
19.	6	460	5	600	4	810		29.	1	50	-	-	-	-
Preglednica 2* Možnosti izvedbe za posamezne aktivnosti
Predstavljeni vhodni podatki in formulacija MINLP-modela, torej namenska funkcija (1), množica pogojnih neenačb za časovne povezave (2)-(5), omejitve trajanja projekta (6), logične omejitve (7)-(10), meje spremenljivk (11)—(16) in funkcija pogodbene kazni (17), so bili uporabljeni pri iskanju stroškovno optimalne rešitve za terminski plan obravnavanega projekta. Optimizacijski model MINLP je tako vseboval namensko funkcijo (tj. spremenljivka Ct), 61 zveznih spremenljivk (tj. 29 spremenljivk S; 29 spremenljivk D; spremenljivko Dp; spremenljivko Pe in spremenljivko Pl), 69 diskretnih spremenljivk (tj. binarnih 0-1 spremenljivk ydik) in 100 omejitev (tj. 35 pogojnih neenačb za časovne povezave, od tega 25 FS + 9 SS + 1 FF; 5 omejitev trajanja projekta; 1 omejitev za
odnos med trajanjem projekta, trajanjem zamude pri dokončanju projekta, dolžine časovnega prihranka pri predčasnem zaključku projekta in rokom za dokončanje projekta; 1 omejitev za dejstvo, da projekt ne more istočasno zamujati in prehitevati, lahko pa je dokončan pravočasno; ter 58 logičnih omejitev).
Zgoraj predstavljeni model tako obsega 29 aktivnosti, od katerih je 6 aktivnosti z 1 možnostjo izvedbe, 6 aktivnosti z 2 možnostma izvedbe in 17 aktivnosti s 3 možnostmi izvedbe, glej preglednico 2. Opredeljene možnosti izvedbe aktivnosti tvorijo skupno število 16x26x317 = 8,265x109 izvedljivih diskretnih rešitev za terminski plan obravnavnega projekta, med katerimi je treba najti tisto, ki izkazuje minimalne skupne stroške.
5.2 Začetna rešitev za optimizacijo
Začetna rešitev za optimizacijo je določena tako, da se projektne aktivnosti postavijo v normalno trajanje pri minimalnih direktnih stroških ob popolnem izkoristku časovnih rezerv, glej terminski plan na sliki 3. Skupni stroški izvedbe aktivnosti po začetnem terminskem planu znašajo 46.840 denarnih enot pri trajanju projekta 93 dni. Indirektni stroški projekta znašajo 13.950 denarnih enot, dodatno pa je predvidena tudi najvišja možna kazen 1000 denarnih enot zaradi 18-dnevne zamude. Kritične aktivnosti na sliki 3 so prikazane z rdečo, medtem ko so nekritične aktivnosti modre barve, ki pa zaradi postavitve v najpoznejše položaje ne izkazujejo skupnih časovnih rezerv.
Gradbeni vestnik • letnik 67 • september 2018
STROŠKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOŠTEVILSKIM NELINEARNIM PROGRAMIRANJEM • Rok Cajzek, izr. prof. dr. Uroš Klanšek
5.3 Optimizacija terminskega plana
Prvi primer obravnava stroškovno optimizacijo terminskega plana z najpoznejšimi časi pričetkov aktivnosti in normalnim trajanjem projekta. S tem namenom se je v namenski funkciji odštel zmnožek konstante male vrednosti (epsilon) in vsote časov pričetkov nastopajočih aktivnosti v projektu na način, kot je bilo predstavljeno pri enačbi (1). Po opravljeni optimizaciji je bil pridobljen terminski plan, ki izkazuje trajanje projekta 74 dni ob minimalnih skupnih stroških 45.970 denarnih enot, glej sliko 4.
Indirektni stroški pri takšnem terminskem planu znašajo 11.100 denarnih enot, dodatno pa je predviden bonus v višini 150 denarnih
enot za dokončanje projekta 1 dan pred postavljenim rokom. Na sliki 4 je prikazan pridobljen optimalni terminski plan v gantogramski obliki, kjer se lahko opazita drugačna razporeditev poteka aktivnosti ter sprememba kritične poti projekta. Pri optimizaciji so bile pospešene naslednje kritične aktivnosti: aktivnost 1 (-1 dan), aktivnost 2 (-2 dni), aktivnost 3 (-2 dni), aktivnost 8 (-2 dni), aktivnost 9 (-1 dan), aktivnost 14 (-1 dan), aktivnost 22 (-5 dni), aktivnost 23 (-3 dni) in aktivnost 28 (-2 dni). Za preostale aktivnosti je bila planirana optimalna izvedba pri normalnem trajanju. Z modro barvo so označene nekritične aktivnosti, ki pa zaradi postavitve v najpoznejše položaje še vedno ne izkazujejo časovnih rezerv.
V drugem primeru je obravnavana stroškovno optimalna rešitev za terminski plan projekta z upoštevanjem najzgodnejših časov pričetkov aktivnosti. Pri tem je bilo, v skladu z referenco [Sakellaropoulos, 2004], predpostavljeno, da premiki aktivnosti (v obravnavanem primeru: premiki aktivnosti v levo na položaje najzgodnejših pričetkov) v okviru časovnih rezerv ne vplivajo na obseg skupnih stroškov. To je bilo doseženo tako, da se je v namenski funkciji prištel zmnožek konstante male vrednosti (epsilon) z vsoto vseh časov pričetkov aktivnosti. Z optimizacijo sta bili pospešeni aktivnost 26 (-1 dan) in aktivnost 27 (-2 dni), prišlo pa je tudi do premika aktivnosti 27 (-1 dan), aktivnosti 28 (-3 dni) ter aktivnosti 29 (-3 dni), glej sliko 5.
1 3 8 9 12		15 18 21 24 27 30 33					36 39 42 45 48 51 54			57 60 63 66 69 72 75 78 81 84 87 90 93 96						99
	«11															
		most $ ttivnost 7	Aktivn AktrJn	st 4 s t B ^Aktivnost 9 uAktrvnost 10 -Aktivnost 11	Iii	ktivnost vnost 1" vnostH	12						stie			
							A	rtivnost 20	17 ktivnost 22 Aktivnost 23		L4	B Aktivne	st 18 3t19			
									^^^m Aktivnost	25	st 26 . Aktp	nost 27 Q Aktivne	28 3t29			
Slika 4* Gantogram za optimalni terminski plan z najpoznejšimi pričetki izvajanj aktivnosti.
Slika 5* Gantogram za optimalni terminski plan z najzgodnejšimi pričetki izvajanj aktivnosti.
191
Pridobljena optimalna rešitev za terminski plan izkazuje enako minimalno vrednost skupnih stroškov v višini 45.970 denarnih enot, vendar s krajšim trajanjem izvedbe projekta, ki sedaj znaša 71 dni. Skrajšano trajanje projekta ob enakih skupnih stroških se je pojavilo zaradi plitkega območja optimu-ma, kjer vsota direktnih in indirektnih stroškov ter bonusov daje isti rezultat. V primerjavi s predhodnim primerom so se direktni stroški
povečali pri aktivnosti 26 za 300 denarnih enot in pri aktivnosti 27 za 600 denarnih enot. Nadalje pa so se znižali indirektni stroški zaradi tridnevnega skrajšanja projekta v višini 450 denarnih enot, kar je prispevalo še k upoštevanju bonusa v višini 450 denarnih enot. Skupna bilanca stroškov je 900 denarnih enot povišanja in 900 denarnih enot znižanja, kar pa odraža enake skupne stroške projekta.
Pri omenjeni rešitvi indirektni stroški znašajo 10.650 denarnih enot, dodatno pa je predviden bonus v višini 600 denarnih enot za dokončanje projekta 4 dni pred postavljenim rokom. Kar se tiče nekritičnih aktivnosti, skupna časovna rezerva znaša pri: aktivnosti 4 (1 dan), aktivnosti 5 (4 dni), aktivnosti 6 (4 dni), aktivnosti 7 (4 dni), aktivnosti 16 (32 dni), aktivnosti 18 (22 dni), aktivnosti 19 (29 dni) in aktivnosti 24 (23 dni).
6*SKLEP
Stroškovna optimizacija terminskih planov gradbenih projektov v splošnem predstavlja področje, kjer v praksi lahko zasledimo kombinatorične, nelinearne in težko rešljive probleme. Namen prispevka je bil predstaviti MINLP-model, ki omogoča pridobitev optimalnega terminskega plana za gradbeni projekt pri minimalnih skupnih stroških njegove izvedbe, upoštevajoč medsebojne povezave med aktivnostmi na osnovi tehnoloških odvisnosti oz. pogojev, omejitve trajanja projekta in logične pogoje. MINLP-pristop omogoča obravnavanje nelinearnosti v optimizacijskem
modelu kakor tudi zveznih in celoštevilskih spremenljivk. Prav svoboda pri uporabi nelinearnih izrazov daje možnost razvoja formulacije optimizacijskega modela v kompaktni obliki. Na primer, v MINLP-modelu se lahko obravnava veliko število diskretnih podatkov naenkrat zgolj z enim (nelinearnim) izrazom, kot je to recimo bilo prikazano pri formuliranju omejenih linearnih pogodbenih kazni. Tovrstna uporaba nelinearnih izrazov se tako lahko izkaže kot prednost pri reševanju problemov terminskega planiranja z velikim naborom diskretnih alternativ, saj zahteva manj ročnega
dela in povzroča manj možnosti za napake pri modeliranju.
S primerom je bilo pokazano, da so izhodni rezultati MINLP-optimizacije eksaktni in določajo terminski plan v diskretnih časovnih enotah ter natanko zadostijo vsem podanim omejitvam v modelu (kar je znana prednost eksaktnih tehnik v primerjavi s hevrističnimi pristopi). Takšne rezultate optimizacije je možno dalje obravnavati s programsko opremo za planiranje, ki je običajna v gradbeni praksi (na primer s programsko opremo MS Project). Prav tako je mogoče ugotoviti kritično pot projekta kakor tudi obravnavati časovne rezerve pri nekritičnih aktivnostih.
7*ZAHVALA
Raziskovalni program št. P2-0129 je sofinancirala Javna agencija za raziskovalno dejavnost Republike Slovenije iz državnega proračuna.
8*LITERATURA
Achuthan, N. R., Hardjawidjaja, A., Project scheduling under time dependent costs - a branch and bound algorithm, Annals of Operations Research, 108, 55-74, 2001.
Adeli, H., Karim, A., Scheduling/cost optimization and neural dynamics model for construction, Journal of Construction Engineering and Management, 123(4), 450-458, 1997.
Afshar, A., Kasaeian Ziaraty, A., Kaveh, A., Sharifi, F., Nondominated archiving multicolony ant algorithm in time-cost trade-off optimization, Journal of Construction Engineering and Management, 135(7), 668-674, 2009.
Akkan, C., Drexl, A., Kimms, A., Network decomposition-based benchmark results for the discrete time-cost trade-off problem, European Journal of Operational Research, 165(2), 339-358, 2005.
Azaron, A., Sakawa, M., Tavakkoli-Moghaddam, R., Safaei, N., A discrete-time approximation technique for the time-cost trade-off in PERT networks, RAIRO Operations Research, 41(1), 61-81, 2007.
Cajzek, R., Klansek, U., Mixed-integer nonlinear programming based optimal time scheduling of construction projects under nonconvex costs, Tehnicki Vjesnik, 23(1), 9-18, 2016.
Chassiakos, A. P., Sakellaropoulos S. P., Time-Cost Optimization of Construction Projects with Generalized Activity Constraints, Journal of Construction Engineering and Management 131(10), 1115-1124, 2005.
Deckro, R. F., Hebert, J. E., Modeling diminishing returns in project resource planning, Computers and Industrial Engineering, 44(1) 19-33, 2003.
192
STROŠKOVNO OPTIMALNO TERMINSKO PLANIRANJE GRADBENIH PROJEKTOV Z MEŠANIM CELOŠTEVILSKIM NELINEARNIM PROGRAMIRANJEM • Rok Cajzek, izr. prof. dr. Uroš Klanšek
Deckro, R. F., Hebert, J. E., Verdini, W. A., Grimsrud, P. E., Venkateshwar, S., Nonlinear time/cost trade-off models in project management, Computers and Industrial Engineering, 28(2), 219-229, 1995.
Eshtehardian, E., Afshar, A., Abbasnia, R., Fuzzy-based MOGA approach to stochastic time-cost trade-off problem, Automation in Construction, 18(5), 692-701, 2009.
Ezeldin, A. S., Soliman, A., Hybrid time-cost optimization of nonserial repetitive construction projects, Journal of Construction Engineering and Management, 135(1), 42-55, 2009.
Falk, J., Horowitz, J. L., Critical path problems with concave cost-time curves, Management Science, 19(4), 446-455, 1972.
Feng, C. W., Liu, L., Burns, S. A., Using genetic algorithms to solve construction time-cost trade-off problems, Journal of Computing in Civil Engineering,
11(3), 184-189, 1997.
Foldes, S., Soumis, F., PERT and crashing revisited: mathematical generalizations, European Journal of Operational Research, 64(2) 286-294, 1993. GAMS, General Algebraic Modelling System, GAMS Development Corporation, https://www.gams.com/, 2018.
Geem, Z. W., Multiobjective optimization of time-cost trade-off using harmony search, Journal of Construction Engineering and Management, 136(6), 711-716, 2010.
Hazir, 0. Erel, E., Günalay, Y., Robust optimization models for the discrete time/cost trade-off problem, International Journal of Production Economics, 130(1), 87-95, 2011.
He, Z., Wang, N., Jia, T., Xu, Y., Simulated annealing and tabu search for multi-mode project payment scheduling, European Journal of Operational Research, 198(3), 688-696, 2009.
Hegazy, T., Optimization of construction time-cost trade-off analysis using genetic algorithms, Canadian Journal of Civil Engineering, 26(6), 685-697, 1999.
Kalhor, E., Khanzadi, M., Eshtehardian, E., Afshar, A., Stochastic time-cost optimization using non-dominated archiving ant colony approach, Automation in Construction, 20(8), 1193-1203, 2011.
Kapur, K. C., An algorithm for project cost-duration analysis problems with quadratic and convex cost functions, AIIE Transactions, 5(4), 314-322, 1973.
Kelley, J. E., Walker, M. R., Critical-path planning and scheduling, Proceedings of the Eastern Joint Computer Conference Boston, 160-173, 1959. Klansek, U., Mixed-integer nonlinear programming model for nonlinear discrete optimization of project schedules under restricted costs, Journal of Construction Engineering and Management, 142(3), 2016.
Klansek, U., Psunder, M., MINLP optimization model for the nonlinear discrete time-cost trade-off problem, Advances in engineering software, 48, 6-16, 2012.
Leu, S. S., Chen, A. T., Yang, C. H., A GA-based fuzzy optimal model for construction time-cost trade-off, International Journal of Project Management, 19(1), 47-58, 2001.
Li, H., Cao, J. N., Love, P. E. D., Using machine learning and GA to solve time-cost trade-off problems, Journal of Construction Engineering and Management, 125(5), 347-353, 1999.
Moder, J. J., Phillips, C. R., Davis, E. W., Project management with CPM, PERT and precedence diagramming, Middleton, Blitz Publishing Company, 1995.
Mokhtari, H., Aghaie, A., Rahimi, J., Mozdgir, A., Project time-cost trade-off scheduling: a hybrid optimization approach, International Journal of Advanced Manufacturing Technology, 50(5-8), 811-822, 2010.
Nearchou, A. C., Scheduling with controllable processing times and compression costs using population-based heuristics, International Journal of Production Research, 48 (23), 7043-7062, 2010.
Ng, S.T., Zhang, Y., Optimizing construction time and cost using ant colony optimization approach, Journal of Construction Engineering and Management, 134(9), 721-728, 2008. Posebne gradbene uzance, Uradni list SFRJ, St.. 18-247, 1977.
Ryoo, H. S., & Sahinidis, N. V. (1996). Branch-and-reduce approach to global optimization, Journal of Global Optimization, 8(2), 107-138. Sakellaropoulos, S., Chassiakos, A. P., Project time-cost analysis under generalised precedence relations, Advances in Engineering Software, 35(10-11), 715-724, 2004.
Sonmez, R., Bettemir, 0. H., A hybrid genetic algorithm for the discrete time-cost trade-off problem, Expert Systems with Applications, 39(13), 11428-11434, 2012.
Vanhoucke, M., Demeulemeester, E., Herroelen, W., Discrete time/cost trade-offs in project scheduling with time-switch constraints, Journal of the Operational Research Society, 53(7), 741-751, 2002.
Walker, M. R., Sayer, J. S., Project Planning and Scheduling, Report 6959, E. I.du Pont de Nemours & Co., Inc., 1959.
Xiong, Y., Kuang, Y., Applying an ant colony optimization algorithm-based multiobjective approach for time-cost trade-off, Journal of Construction Engineering and Management, 134(2), 153-156, 2008.
Yang, I-T., Using elitist particle swarm optimization to facilitate bicriterion time-cost trade-off analysis, Journal of Construction Engineering and Management, 133(7), 498-505, 2007.
Zheng, D. X. M., Ng, S. T., Kumaraswamy, M. M., Applying a genetic algorithm-based multiobjective approach for time-cost optimization, Journal of Construction Engineering and Management, 130(2), 168-176, 2004.
Zou, X., Fang, S. C., Huang, Y. S., Zhang, L. H., Mixed-Integer Linear Programming Approach for Scheduling Repetitive Projects with Time-Cost Trade-Off Consideration, Journal of Computing in Civil Engineering, 31(3), 2017.
Gradbeni vestnik • letnik 67 • september 20