Sampling Based Approximation Method for the Stochastic PERT Problem

(1)

瑠−『輪3

2003年日本オペレーションズ。リサーチ学会

春季研究発表会

Samp且五mg迅asedÅpp『0Ⅹ五ma七五omM如払od

鮎釘も払e Sも①C払a雨量c PE訊町野『の払皿em

OlO12560 王くoma2；aWaUniversityIJDA7もtsuo0

01206492 TbhokuUniversity SUZUKIKenichi

theもhenetworkofprojectswhoseprocesstimevary

randomly．Itisformulateda5fbllows・ A：SetOfarcs（eacharcrepresentssubproject） ∫＝（1，2，…，Ⅳ）：且 Im屯『OdⅦCも五om

Traditionally PERT／CPM has been used to man−

ageIargeprojects・Theideaofthecriticalpathstill

Plays animportant partin thescheduling．How− ever，mOSt Ofexist・ing researches and applications Of PERT tackled the deterministic problem．On theother hand，unCertaintyisthemostsignificant aspectsofthepracticalproblem，Sinceitcancause

delayoftheschedule，increa5eOfthecost，andde−

teriorationofthequalityofoutputs．

HereweformulateastochasticPERTproblcma5

a two s†・age StOChasticlinear programmlng mOdel withrecourse（SLP），Sinceitcanhandleoptimiza− tion problemsunder uncertainty．Itiswe11known

thatSLPcanbesoIvedbythedecompositionba5ed

algorithm［1］・Themaindi爪cultyonthecomu−

tation ariscsfromthenumberofstates：比mayJn− CreaSeeXPOnentially，COnSumlngalargeamountof memories，eVenifproblem containsafbwrandom Variables．柑ence，COmbinationofdecompositional− gorithm and Monte Carlosampling technique are

proposcdbyseveralauthors（e・g．【3】）・

In our previous work（JORSJgeneralmeeting， Fhl12002），We Showed the efhciency ofsampling baseda）gorithm forthestochasticPERTproblem． AIso，WeSuggeSted theformulaofnewdensityon theimportancesamplingmethod，bywhichweex− pecttoreducevarianceoftheestimator．Unfbrtu− natelythecomputationalexperimentwerestillpre− 1iminaryone．Inoursubsequentresearch，WeCOn− ducted n】OrethorougllCOmPutationalexperimcnts・ We compare two variance reduction method：im−

portancesamplingandcontroIvariate．

thesetofnodes，WllereNisnumberofnodes

aij：arCfromnodeitonodej T；j：theactivitytimeofarcaij 73：tllearrivaltimeofnodej B＝amOuntOfbudget

o The nodeland the node N correspond the

start no（le alld the銭nish node，reSpeCtively． WeindexaijSatisb，ingi＜j・

o VVe assume theearliest start．．

0Wecanreducetheactivitytimetocertainex− tentbyconsumingresources（budget）・

Xij：reducedtimeonarcaij・Itislessもhanupper

bou∫−d叫・ Cij：COStPerunittimetoreduce W：SCenarioorsample O：Set Ofscenario pU：PrObabilityofreali2；ationofthescenarioLL，【ma5terprOblem］： min g（∬） S・t・∑叫∈Aqj∬iJ≦β 0≦∬iメ≦叫，∀叫∈A （1） whereQ（3：）＝E［Q（77v；LJ）】・【childproblem］： Q（7≠；U）＝ _筍オ一二町勇 2 飢⊃『mⅦ且a屯瓦￠m

We focus on the stochastic PEnT problem with

crashing，Wheretheprojectmanagerdecidetheal−

locationムfhis／herlimitedresource（budget），given

(2)

3 L−Shapedmethod usingMonte

Carlo sampling

Tb’solvetheprob7em（l），Weneedtoevaluate the Objective function Q（x）・Sinceitisdefinedascx− pecte（1valueoftlleObjectivein（2），WeCan eVal− uateit byMonteCarZosamp7ing．However，Crude SamPlingisknowntobeiTlefBcienttoensuretheac−

C−1raCy・Numprousvariancereduction methodsare

Cla5S摘ed toseveralcategories．Even thoughthe−

OreticalcharacteristicofeachInethodsarealready Clarified，Weneedtocustomizeandmodifythemto applytoindjvidualproblems． 3.1 importance sampling 3C：1st＄tagedecisionvariable LetA＝（al，a2，・‥，af（），WhereKisnumberof arCS． 7L‘‥PrOCeSStimefbrarc FbranarCi，）et usdefinethefb1lowingfunction：怖‘（7芸，〇）＝maX（7芸＋J叫（T，訂），エーα‘（T，可），・Wherelat（T，X）＝lニ‘（T，3，）−7L‘andl；‘（T，X）indi− CateS thelength ofいIelongest path containingai under the base sample T and thefirst stage varト ablex・AIsoL−ai（T，． tain arcai．Weselectthebasesampleasthemini− mumprojecttime． Let吼‘（x）＝E（吼‘（7Li，X）］，thenwegenfrate thesamplesfromthedistribl・ltionofp。iMa‘／〃町

The aboveidea can be exploited to the ad−

vanced proced11rP，in which we consjder multip】e arcsal，a2，．‥，akratherthanslnglearcai．〃妬．‥，αk（花，・‥，7㌫，‡）＝maX（花＋J几l（T，諾），…，7芸＋J。鳥（T，諾），

エ叫1，…，＿αた（T，∬））′

3．2 controIvariates TheetrktivenessofthccontroIvariatesdependson thechoiceofvariates．Theyshouldbeeasytocalctl− 1ateexpectedval11eSalldbehighlycorrelatedwith targetedvariable，Whichiscompletetimeofproject lnOurCaSe． normpbasedcontrol：Higlesuggestedin【2】two methodtoconstructthecontroIvariateforgen−

eralstochasticlinearprograms・HereweappJy

thenorm−basedcontrol．Underoutnotations， cont．roIZis Z＝∑（句一β恥】）・叫∈A

upper bound control‥Weproposeanother con−

trol based on the upper bound of completion

time．Fbr acertain realization LL），WeCanCal−

Culateacriticalpath．Ofcourseitmaynotbe

thecriticalpathinotherrealizationofu，butit PrOvidesupperboundofcompletiontime．We

CaneXPeCtthattheupperboundpositivelycor−

related with truecompletion time．Moreover，

WeCanimmediatelycalculateexpectationvalue

Ofupper bound becauseitis thesumofpro−

CeSSlngtimeonfixedpath．

Z＝∑鶴一利れJ】），

叫∈鞄

where PE indicates the critical path derived

from the project network with expected pro−

CeSSlngtime・ ■tll▼l、●−−t

Figurel：tlleprOjectnetworkusedforthecompu−

tationalexperitnents：26nodesand38arcs

Refbrences

tl］JohnR・BirgeandFtanGOisLoVeauX・Int7V−

duction to Stochastic PTT）gmmmm9．Springer， 1997．

［2】Julia L・Higle・Variance reduction and ob− jective function evaluation in stochastic linear

programs．INFORMSJoumαlqFComputin9， 10（2）：236「247，1998・【3）GerdInfanger・Montecarlo（importance）sam− plingwithinabendersdecompositionalgorithm brstochasticlinearprograms．ATmaLsq／Oper・− α如那月eβeα化九，39：69−95，1992． −】01− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.