Resource-constrained project scheduling_ Notation, classification, models, and methods

项目进度管理

EuropeanJournalofOperationalResearch112(1999)

3±41

InvitedReview

Resource-constrainedprojectscheduling:Notation,classi®cation,

models,andmethods

PeterBrucker

a

a,1

hring,AndreasDrexlb,*,RolfMo

ErwinPesche,4

c,2

,KlausNeumann

d,3

,

tOsnabru ck,FachbereichMathematik/Informatik,Albrechtstr.28,49069Osnabru ck,GermanyUniversit b

tKiel,Institutfu rBetriebswirtschaftslehre,Olshausenstr.40,24118Kiel,GermanyUniversit

c

TechnischeUniversit tBerlin,FachbereichMathematik,Straûedes17.Juni,10623Berlin,Germany

d

tKarlsruhe,Institutfu rWirtschaftstheorieundOperationsResearch,Kaiserstr.12,76128Karlsruhe,GermanyUniversit

e

tBonn,Institutfu rGesellschafts-undWirtschaftswissenschaften,Adenauerallee24-42,53113Bonn,GermanyUniversit

Received1June1998

Abstract

Projectschedulingisconcernedwithsingle-itemorsmallbatchproductionwherescarceresourceshavetobeallocated

todependentactivitiesovertime.Applicationscanbefoundindiverseindustriessuchasconstructionengineering,softwaredevelopment,etc.Also,projectschedulingisincreasinglyimportantformake-to-ordercompanieswherethecapacitieshavebeencutdowninordertomeetleanmanagementconcepts.Likewise,projectschedulingisveryattractiveforresearchers,becausethemodelsinthisareaarerichand,hence,di culttosolve.Forinstance,theresource-con-strainedprojectschedulingproblemcontainsthejobshopschedulingproblemasaspecialcase.Sofar,noclassi®cationschemeexistswhichiscompatiblewithwhatiscommonlyacceptedinmachinescheduling.Also,avarietyofsymbolsareusedbyprojectschedulingresearchersinordertodenoteoneandthesamesubject.Hence,thereisagapbetweenmachineschedulingontheonehandandprojectschedulingontheotherwithrespecttoboth,viz.acommonnotationandaclassi®cationscheme.Asamatteroffact,inprojectscheduling,anevergrowingnumberofpapersisgoingtobepublishedanditbecomesmoreandmoredi cultforthescienti®ccommunitytokeeptrackofwhatisreallynewandrelevant.Onepurposeofourpaperistoclosethisgap.Thatis,weprovideaclassi®cationscheme,i.e.adescriptionoftheresourceenvironment,theactivitycharacteristics,andtheobjectivefunction,respectively,whichiscompatiblewithmachineschedulingandwhichallowstoclassifythemostimportantmodelsdealtwithsofar.Also,weproposeaunifyingnotation.Thesecondpurposeofthispaperistoreviewsomeoftherecentdevelopments.Morespeci®cally,wereviewexactandheuristicalgorithmsforthesingle-modeandthemulti-modecase,forthetime±costtradeo problem,forproblemswithminimumandmaximumtimelags,forproblemswithotherobjectivesthanmakespanminimizationand,lastbutnotleast,forproblemswithstochasticactivitydurations.Ó1999ElsevierScienceB.V.Allrightsreserved.

*1

Correspondingauthor.Fax:+49-431-880-1531;e-mail:drexl@bwl.uni.kiel.deE-mail:peter@mathematik.uni-osnabrueck.de2

E-mail:moehring@math.tu-berlin.de3

E-mail:neumann@wior.uni-karlsruhe.de4

E-mail:E.Pesch@uni-bonn.de

0377-2217/99/$±seefrontmatterÓ1999ElsevierScienceB.V.Allrightsreserved.PIIS0377-2217(98)00204-5

项目进度管理

4P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

Keywords:Projectscheduling/resourceconstraints;Notation;Classi®cationscheme;Single-modecase;Time±costtradeo s;Multi-modecase;Minimumandmaximumtimelags;Nonregularobjectives;Stochasticactivitydurations;Constraintpropagation

1.Scopeandpurpose

ingProjectpractice.attentionschedulinginrecenthasyearsattractedbothanevergrow-batchItisconcernedwithsingle-itemfromscienceandbeproductionwherescarceresourcesorhavesmalltotime.metorderProjectwhencutcompaniesschedulingschedulingdependentactivitiesoverwhereistheimportantcapacitiesforhavemake-to-concepts.downinordertocopewithleanmanagementbeenresearchersProjectarealso,becauseschedulingisveryattractiveformizationrichingeneralproblemsthesensethemodelsinthisareaarethatspecialmanycaseswell-knownopti-theprojectschedulingmodels.Foroftheinstance,morelemresource-constrainedspecialcontainsthejobshopprojectschedulingschedulingprob-problemscase.Withoutsurprise,projectproblemschedulingasacomputationalingeneralpointarereallychallengingfromahaveBothpracticeandofscienceview.

ofprojectschedulingacronymsevolvedclasses.todistinguishfastrecently,betweenproducingdi erentnumerousprojectAlso,avarietyofsymbolsareproblemusedonedi cultandschedulingresearchersinordertodenotebyallstandardized.about,tothebecausekeepsameaclearsubject.themodelsviewHence,ofinwhatsometimesthistheareasubjectitisarenotis®rstprojectattempttoRecentlyHerroelenetal.[94]madeanotscheduling.provideUnfortunately,aclassi®cationtheirschemeschemeformachinecompatiblewithwhatiscommonlyacceptedinisbetweenprojectboth,schedulingmachinescheduling.schedulingHence,thereisstillagapontheontheonehandandscheme.viz.gap.Oneacommonpurposenotationotherofourpaperandwitharespecttoisclassi®cationtoscriptionWeprovideaclassi®cationscheme,closei.e.thischaracteristics,oftheresourceenvironment,theactivityade-tively,ingandwhichwhichisandcompatibletheobjectiveallowstowithfunction,respec-classifymachinetheschedul-most

importantproposemodelsdealtwithsofar.Also,weofAnotheraunifyingpurposenotation.

ofthishavethebeenrecentpaperistoreviewsomegivendevelopments.5by,AdditionalsurveystheThetroduced.notationpaperandisorganizede.g.,[67,92,113,151].

theclassi®cationasfollows.InSection2gorithmsSection3coversexactandschemeheuristicarein-al-projectforthesingle-moderesource-constrainedsolutionschedulingproblem.InSection4wereviewproblem.proceduresprojectThemulti-modeforthetime±costtradeo tionconstrained5.InschedulingSection6problemweconcentrateisresource-constrainedthesubjectofSec-minimumdedicatedandprojectmaximumschedulingtimeinlags.theonSectionpresenceresource-7offunctions.toproblemswithnonregularobjectiveischasticinSectionactivitySectiondurations.8discussesmodelswithsto-di erentOurwork9withWeconcludethepaperwillanexpositionoffurthermodels.methodsmodelsillustrate(computational)inordereachthattherearenumeroustoofwhichrequirestailoredstraintcomplexity.copewithNevertheless,theirinherentcon-evolved,propagationconstrainttheaimofwhichtechniquesistosolvehaveavarietyrecentlyofimpactject)onsatisfactionthe®eldproblems.Althoughtheiranpropagation-basedAppendixschedulingAthestillisofnotresource-constrainedclearwedecidedto(pro-addsequencesubjectofconsistencywhichareconstrainttests.2.Notationandclassi®cationscheme

projectIntheschedulinglastfewyearshavemanybeendi erentconsideredproblemsandtime

in5

availableMostoftheworkingpaperscoveredinthisreviewrcpsp/.

ontheinternetviahttp://www.wior.uni-karlsruhe.de/are

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±415

isclassi®cationreadytohaveimportantschemeauni®edfornotationandageneralwhat(cf.isgenerallythatthisschemeprojectiscompatiblescheduling.Itwithisscheduling[77])models(cf.andacceptedinmachinescheduling[18]),resource-constrainedbecausemachinemachinemodels.

arespecialcasesofprojectschedulingschedulingnotation.Inthesequelwewillofplicity,activitiesBasically,(jobs)1weYFFassume®rstproposeFYn.Foraprojectathesaketounifyingofconsistsim-tivityn0inandgeneralauniqueauniquedummydummybeginningac-project 1are(AON)isadded.Frequently,terminationthestructureactivityoftherepresentnetworkdepictedwherebyaso-calledthenodesactivity-on-nodeandthearcstions,precedencerespectively.theactivitiesq and Yi thedenotesprecedencethegraphrela-ofwhilealternativelysingleconstraintssetbyprecedencei3jorconstraints(transitivelyreduced), iYj .aredenoteddirectofdirectofactivitysuccessorspredecessorsofactivitywhilej.The u redprocessing jj isde®nesthesetthetimeofThereisjisagivensetRqbypj.

nonrenewablestrainedand,possibly,ofrenewable,asetofasetRmofspeci®edresources.forrenewableeverynumberperiodofofRenewableunitsmeansdoublythatacon-pre-theplanningofaresourcehorizonisavailable .sourceAsresources,usual,isavailablesaysthatanumberofunitsofNon-are-weskipthefornotiontheentireofdoublyplanningconstrainedhorizon.newablerioddenotedusageandbecauseoftheactivitynonrenewabletheycanbecoveredones.Thebyperthepe-re-q

jofrenewableresourcekis

numberperiod.ofInofbytheunitsrjkwhile qkde®nesthe(constant)

multi-modeofresourcecase,kavailableMineveryjde®nesitymodes,givenj.Thethatis,processingalternativesoftheactiv-setconsumption)bypprocessingThetimeofactivityjinmodemisjm.newable)de®nesresourceofactivityperperiodkisgivenjofusagebyrenewable(totalresourceq(rm

(nonre-jkm)while msourceInjthesingle-modektheavailablenumberforofunitsofrjkmnonrenewablere-k

case,thethatentireisforplanningjMhorizon.superscriptandRm qY,forwejj 1foralltheskipsaketheofmodesimplicity.

indexmandtheof scheduleactivityj(gj)denotescompletionandj.Consequently,thestarttimeg g (completion FY time)1YFFn isa1YFFFYgn isthevectorsibleschedulesschedules,times.Sthesetoftime-fea-ofTde®nesschedules.andSS RSthesetofresource-feasibleR dtisanindexforStimeTthesetoffeasibletimeij

minanddijmax

denoteminimumperiods.andmaximumFinally,itiesbeinteger-valued.

ilags,andjrespectively,.Ingeneral,betweenparametersthearestartassumedofactiv-toalongTable1summarizesthemachineNowwithwesomeextendminornotationintroducedtheadditions.

ajbjc-schemeusedinthetweena:Resourceschedulingenvironment:literature.

Todistinguishbe-projectspeci®cmachineschedulingproblemsand®eldprojectPSscheduling(projectscheduling)problemsweorintroduceinthea-m[18]YrYqaccordingscheduling).tothePSnotationcanbeMPSaugmented(multi-modeofBlaz

ewicztoetPS

al.Innonrenewabletheforcaseresource-constrainedofmulti-modeprojectmachineschedulingscheduling.casew mtheYrYqnotationresourcesYlYsYx.isanalogouslymaybeconsidered.augmentedInalsothisby w project mYrYq

multi-modescheduling

mprojectresourceresources,runitsschedulingofityrequiresavailable,atmosteacheachqunitsactiv-ofw mYrYqYlYsYxthemulti-moderesources

withunitsmrenewableprojectresources,scheduling

able,ofeachresourceavail-rmosteachlqactivityrequiresatunitsnonrenewableunitsoftheresources,able,ofeachresourceresources,smosteachxunitsactivityoftherequiresavail-resourcesatvaluesIfanForofentrytheparametersofmYrYqYlareYsYxspeci®edisreplacedbyÁ,therespectively, mYÁYÁandspeci®edinthefor mYrYÁwewrite minandthe minput.Yr,input,short.weIfallwritevaluesÁinsteadinmYrofYqÁYareÁYÁ.

项目进度管理

6

Table1

BasicnotationSymbol ni

q Yi i3j, iYj red j u j pjRq qkqrjkMjpjmRm mkqrjkm

mrjkm

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

De®nition

setofactivities

numberofrealactivities

setofprecedenceortemporalconstraints

directedgraphofprecedenceortemporalconstraintsprecedenceconstraint

setofdirectpredecessorsofactivityjsetofdirectsuccessorsofactivityjprocessingtimeofactivityjsetofrenewableresources

constantamountofavailableunitsofrenewableresourcekperperiodusageofactivityjofrenewableresourceksetofmodes(processingalternatives)ofactivityjprocessingtimeofactivityjinmodemsetofnonrenewableresources

totalamountofavailableunitsofnonrenewableresourcekperperiodusageofactivityjofrenewableresourcekwhenprocessedinmodem

consumptionofactivityjofnonrenewableresourcekwhenprocessedinmodemstarttimeofactivityjschedule

completiontimeofactivityjvectorofcompletiontimessetoftime-feasibleschedulessetofresource-feasibleschedulessetoffeasibleschedules

resourceconsumptionofresourcekofschedule attimetdeadlineforprojectdurationtimehorizon,indexforperiodsperiods

timeintervalcorrespondingtoperiodt

minimum/maximumtimelagbetweenstartofactivitiesiandj

j

1YFFFY n gj

g g1YFFFYgn STSR

S S S rk Yt "d Yt

t 1Y2YFFFY tÀ1Yt minmax

adijdij

Likewise,for Áandw ÁYÁwewrite andw ,respectively.Examples: mY1Y1 mYI

mresources,1unitofeachresourceavailable,eachactivityrequiresatmost1unitoftheresources

mresources,unlimitednumberofresourceunitsavailable(i.e.,therearenoexplicitresourceconstraints,e.g.inresourceleveling)oneresource

processingtimes,pre generalprecedencecon-straints,etc.pj 1pj sto"dpre

h ins,intree,outtree,treeFFFtemp

allprocessingtimes(activitydurations)areequaltoonestochasticprocessingtimesdeadlineforprojectdurationprecedenceconstraintsbe-tweenactivities

precedencerelationsbetweenactivitiesarespeci®edby

chains,intree,outtree,treeFFFgeneraltemporalconstraintsgivenbyminimumandmaxi-mumstart±starttimelagsbe-tweenactivities

1

b:Activitycharacteristics:Weuseestablishednotationsfrommachinescheduling(cf.[77])likepj

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±417

chinec:Objectivefunction:Asinmostcasesforma-byobjectivetheschedulingcorrespondingwedescribeformulas.objectiveBesidesfunctions classicalfurthercriteriafunctionsmaybelikeconsidered,gmaxYvmaxforYexample:wjgjetc., Fjb

gjnet

bpresentvalue( Fcashkf rk Yt

resourcediscount¯ow,unitlevelingfactor)

( kcostperageofresourcek,rk Yt

givenofkmaxrk Yt

resourcescheduleresourceinvestment

k)attimetus-Di erentconsideredtypescussedinliteratureoffunctionsandpracticefwhichwillhavebebeendis-nowSomeinofSection7.1.

· beproblemjpre classi®edthemodelsjgasfollows:

coveredinthispapercanmax:Thismodelformsstrainedwhileprojectamongschedulingtheclassthecoreproblems.ofresource-con-havestraints.tominimizingobserveprecedencetheproject'sandmakespan,Basically,wetributedRecently,acoupleofpapersresourcehavecon-con-problemnewputationalisstillsolutionratherprocedures.challengingHowever,fromathe·thisw modelpointresource±resourcejpre jareofview.Methodsforsolvingcom-greviewedModelsinofSectionthisclass3.

max:captureHence,servedodsintheyandtime±resourcetradeo s.realitycomeofmoreclosetowhatcanbeob-·Sectionforsolvingthisprojectmodelmanagement.arereviewedMeth-in minimumjtemp5.

jgmax:Inmanyapplications,lagsalreadybetweentimeactivitieslags,maximumbesidemuststart±starttimeinthestrongthefeasibilityproblembeobserved.isNP-completeHere,·model thejtemparejreviewedsense.Methodsforsolvingthis

inSection6.kf rk and,availabilityscheduleinaddition,ofrenewable Yt :Insomeapplicationswehavetoresourcescomeupislimitedtime.edonesMethodswhicharereviewedforlevelssolvingtheresourceusagewithoverainSectionthismodel7.

andrelat-3.Single-modecase

methodsInthisprojectsummarized.schedulingforsolvingsectionenumerativeandheuristic

problemthebasic resource-constrainedjpre jgmaxsettivity f0Y1YAssumeFFFYnYnthattheprojectconsistswillofbea(termination)j 0(j 1gofactivitieswhereac-beactivity. n 1)Theisa®ctitiousbeginningnetworkacyclicanddepictedbynetworkanactivity-on-nodeisassumedtocedencewithThererelations.nodesPreemptionasactivitiesandisnotarcsaspre-assumedare®ndconstraintsamakespan-minimaltoscarcebeinteger-valued.renewableresources.Allallowed.dataarescheduleThethatobjectivemeetsisthetoandimposedbytheprecedencerelationsprojectGivenbylimitedresourceavailabilities.

tionsdurationanupperwecanbounduse theontheminimum latestigYvgtoderivetimewindows,precedencei.e.intervalsrela-jj ,withearliestcompletiontimeigjanddencecompletionbyfeasiblecompletiontimevgjtimes,containingofactivitytheprece-jP ,theforwardandbackwardrecursion.Analogously,aboveinterval i jYv j boundedfrombelowandtimebytheearlieststarttimei jandlateststartthe programjprecedencev j,respectively,pre jgfeasiblecanstartbecalculatedtimes.Intogeneral,re¯ectmaxisformulatedasactivitywhichmakesuseofvariablesa0-1xintegerjt Alternatively,jiscompleted1,ifsenteditinperiodt(0,otherwise). notjtempinjgSectionisstated6.1forsimilarthetomorewhatgeneralispre-max.ForthesakeapproachesSectionpresentofshortness,wedo3.1aformalmodelhere.

surveysfordescribes jpre recentjgbranch-and-boundmaxwhileforSectionbothheuristics.are3.2.typesInofLowerboundsareSectionimportant3.3Sectionmethods.3.4TheycomputationalarethesubjectresultsofimprovedWithinbrie¯ydiscussed.

optimizationthethesolvabilitylastyearsbranch-and-cutmethodstionthroughofvalidproblemsinequalitiessubstantially.ofseveralcombinatorialandThegenera-earlyanLPsolvermightbetheirconsideredpropagationasanbasede ectiveonconsistencystartoftests.propagationInschedulingofconstraintssuccessful

项目进度管理

8P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

applicationsschedulingareproblemshavebeen(e.g.achievedjobshopfordisjunctive celeratejpre currentlyjggoingtobescheduling)extendedandtomax.Theaimofsuche ortsisthroughheuristicsfeasibleanearlydetectionorbranch-and-boundofnonattractivemethodstoac-orin-constraintnodes.AcomprehensiveintroductionintoTsangsistency[195].propagationtestsareConstrainthasdescribedpropagation-basedbeenprovidedbyinAppendixA.con-e.g.3.1.Branch-and-boundmethods

varietyStartingdevelopedofbranch-and-boundwithanearlyworkofJohnson[101]apartialverticesschedulesfor jwhichpre jgalgorithmshavebeenaremax.associatedMostofthemwithuseprocessinanddi erentconsistsoftheenumerationtheways.oftree.ThebranchingDominanceextendingrules,thepartiallowerschedulebounds,numberimmediateschedule.ofalternativesselectionforallowtodecreasetheschemes®rst-searchandThemethodsuseextendingdi erentthebranchingpartialquirementsispruningusedinmethods.ordertoIngeneral,depth-proposedThePrecedencelow.

keepmemoryre-Tree:Pattersonetal.precedenceaningeachthedummytree.algorithmTheguidedbytheso-called[155]beginningprocedureactivitybeginsattimewithstart- tlevelgofthebranch-and-boundtree,the0.Atsetitgofthecurrentlyscheduledactivitiesandthesetthegdetermined.predecessorsoftheeligibleactivities,thatis,thoseactivitiesNowThenofanwhicheligibleareactivityalreadyscheduled,isstartassignedtimetheearliest precedenceandresourcejgisselected.feasiblejgthatisnotlessthanthecomputed.ondummyThenthepreviouswebranchleveltoofthethenextsearchstartlevel.treetimeIftheisscheduleterminationinguntestedtothehaspreviousbeenfound.activityiseligible,acompletelevelInoccurs.thiscase,Here,backtrack-activitieseligibleactivityischosen.Ifalltheeligiblenextback.precedenceEachhavebranchbeenfromtested,wetrackanotherstepthesetofactivitiestreecorrespondstherootwhichisprecedencetoatopermutationaleafofthefeasibleofintheathissmallersensethatsearchalgorithmindexeachpredecessorofanactivityjghashasinthebeensequenceenhancedthanwithjg.Recently,conceptDelaytreeAlternatives:reductiontechniquesThisalgorithmbySprecherpowerfulbaseson[185].etmeulemeesteral.[40]ofdelaywhichalternativeshasbeenusedbyChristo®desthethetheprecedenceandtreeHerroelenalgorithm,[48].enhancedIncontrastbyDe-to®xedbranch-and-boundhereeachlevelgoftivitiestimetreeisassociatedwithade®nitionmayinstantbestarted.tg(decisionConsequently,point)atawhichac-rithm:eligibleAcurrentlyofeligibleunscheduledactivitiesisactivityusedinthisdi erentalgo-scheduledattimetjiscalledgifallofitspredecessorsithermore,withacompletiontimegareiTtg.Fur-beTheinprocessanatactivitytimetjwithstarttime jissaidtogifwehave jTtg` branch-and-boundproceedingatthecurrentlevelgofj thepj.cisionpletionpointttreeisasfollows:Thenewde-gisdeterminedNotetimeoftheactivitiesasintheprocessearliestatcom-tgthescheduledrenewablethat,duetoÀ1.resources,theconstantavailabilitylevelsofstartingactivitiesunscheduledactivitiespoint,thatare®nishedones.needtoonlybe®nishconsideredtimesforofatUsingorbeforethesetptgoftheputed.thesetitoftheeligibleactivitiesthedecisiongiscom-addingHavingprocess,themtostartedthesetallts eligibleactivitiesbygofThus,computedthemaysetofhavecausedaresourcetheactivitiescon¯ict.indelayforalternativeaccordingtheminimaltothefollowingdelayalternativesde®nition:Ais

eachrenewableDAgisaresourcesubsetofkts PgRsuchitthatiscalledjPts gnDAgrjkdelayselectedalternative.minimalTif kno.AdelayalternativeDAgisAminimalpropersubsetdelayofalternativeDAgisisamovednofromandthethecurrentactivitiespartialtobedelayedarere-alternativeresourcetimesiscon¯icttheoccurs,theonlyschedule.minimalNote,delayifinformationofanactivityemptyjtobeset.delayedWestorethestarting.nextThenithasisbranchedtoberestoredduringbecausebacktrack-thiscompletedecisionpointiscomputed.tothenextIfthelevelscheduleandthenextminimalnow,delaybacktrackingalternativeisperformedistested.Clearly,

andtheis

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±419

thisalgorithmproceduregle)branch-and-boundactivitiesinthatisdi erentaresetsfromtheprecedencetreestartedofactivitiesateachinsteadlevelofof(sin-instantterminedatwhichactivitiestree.Moreover,mayherethetimethelected.algorithm,Finally,beforetheactivitiesthemselvesbestartedareisde-se-schedulingthisinapproachcontrasttoallowstheprecedencetowithdrawtreebeenmadedecisionsataloweratthecurrentlevelthathaveproposedExtensionpartialtouseAlternatives:level.

extensionalternativesStinsonettoal.[188]eachsociatedlevelschedules.goftheAsinthepreviousalgorithm,constructactivitieswithtivities,inprocess,adecisionbranch-and-boundasetpointpttasetts treeisas-g,gofthegcurrentandasetitofthe®nishedac-gofeligibleactivities.subsetwithoutofpartialthescheduleisextendedbystartingThentheaprecisely,violatingeligibletheactivitiesresourceatconstraints.thedecisionMorepointofholdstheeligibleanextensionsetforalternativewhich EAgisasubsetjPts g EAgrjkTEAforeachresourcekPRand,moreover, ktheg Yifts g Y.Note,inorderemptyalgorithmprocess.extensionterminates,wemayonlytosecurehavenon-thatinHowever,alternativesifthereareifnocurrentlyactivitiesareinalternativeprocess,theguaranteewhichemptymustsetisalwaysanextensionactivitiesbranch-and-boundoptimality.AtthebecurrenttestedlevelinordergtoDeterminesetthenewtreedecisiontheprocedureisasfollows:ofthealternatives.oftheeligibleactivitiesandpointtheandsetcomputeoftheEAbranchingandstartFinally,thecorrespondingselectanextensionalternativeextensiongmechanismtorithm.theNoteequalsthenextactivitiesbeforethatthisthelevel.Thebacktrackingprocedureoneoftheispreviousdi erentalgo-fromcludespreviousbeenthepossibilityalgorithm:todelayWhereasactivitiestheformerin-latterstartedonalowerthanthecurrentthatlevel,havethedecisiondoesmayofnotalowerallowlevel.towithdrawaschedulingalternativesnotrestrictthesearchtoAs``maximal''aconsequence,extensionweconsideringStinsononlywhileminimalwedonotdelaylosealternatives.optimalityNote,whenbymeansetofal.an[188]example.

introducedtheproceduresolelyaingslightlyBlockExtensions:di erentapproachMingozzibasedetal.on[126]theconsidertimes

ideas.Thereexistsanoptimalschedulede®ningfollow-t0 0`t1`t2`ÁÁÁ`tl

andthat

correspondingsetsofactivitiese1YFFFYelsuch(i)tivity,

eachti ib0 isthe®nishingtimeofsomeac-(ii)duringallactivities(iii)itifan tineicanbeprocessedjointlyiÀactivity1Yti i jP1YeFFFYl ,

iisnot(iv)willalsobeprocessedin t®nishedin tiÀ1Yti iYti 1 ,and

ataAtimeallpredecessorsblocktofanyactivitywhichstarticonsistsarescheduledofsuchbeforeanintervaltime tti.

iÀFurthermoresete1Yti withiofactivitieswhichcanquenceThenofblocksapartialschedulebeisprocessedde®nedbyjointly.ase-vidingitisbranchedsatisfyingbyaddingconditionsnew(iii)blocksandpro-(iv).gorithmScheduleagainizesdevelopedschemes:partialschedules.

byTheBruckerbranch-and-boundetal.[32]al-schedulingbranch-and-boundschedulingproblemandmethodsthemultiprocessorforthejobgeneral-shoptaskconcepts[12].whichproblemcanbe(cf.found[30,118]).inBartuschItalsoetusesfeasibleInsteadscheduleschedulesofusingarerepresentedpartialschedules,al.bysetsofvatedschemes.Scheduleschemescantheso-calledeitherForasbemoti-twofollows.

arbitraryconjunctionsaparallelityifi3jorrelationactivitiesj3i.iik3jascheduleorjoneof theinducestwoitimeandi®nishesjarebeforeprocessedthestartinparalleltimeofholdsjfor.ikjifandonlyatmeansleastthatonetheseunit.disjunctionrelations.WegetiiÀji.3setsiÀjorofj3schedulesiarerelaxedbyrelaxingbytheparallelity3jorj3relationsrelationsi.FurthermorejmeansthatwehaveeitherikjcanbedisjunctionsrelaxedtoiÀjandwhichi$j.i$jmeansthatitisundecided¯exibilityCofthetworelationsiÀjorikjholds.yetdisjunctions,YDYNandrelations,respectively.parallelityUdenotethe Crelations,setsofYDYNYU andconjunctions,isa¯exibilityschedule

项目进度管理

10P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

schemeonejschedule3ofiPtheifforanytwodi erentactivitiesiYjexactlyCfollowingrelationsholds:i3jPCorfeasibleschemeoriÀjP CDYDorYNikjPNori$jPU.Aallschedules(whichmayYU bede®nesempty),anamelysetofinCfeasibleYDYNscheduleswhichsatisfyalltherelationsDIfC.

0isthesetofallgivenprecedencerelations,be0straints,processedisthesetofinallparallelpairsofactivitieswhichcannotthenschedules. CandUduetotheresourcepairsicon-0thesetofallremaining$j,0YD0YYofthe CYYUD0 representsthesetofallfeasible00YYYU0 correspondstotherootitForenumerationascheduleschemetree.

oftheform CYDsatisfyingcanbeshownthateithernofeasiblescheduleYNYY feasiblecanscheduleallthecanrelationsbecalculatedexistsor(cf.a[117]).dominatingofbedoneinO n3 time.Thus,scheduleschemesBoththetheform CYDYNYY canbetreatedasplacingenumerationa¯exibilitytreeandonecanbranchleavesbyre-ofschemesTheinclusionrelationi$jbyiÀjorikj.nodeallowstoformofconjunctionsatemporalanalysisinscheduleineachconjunctions,oftheenumerationaredisjunctionstree.orByparallelitythisanalysisrelationsnewwindowsdeduced.boundcanFurthermore,becalculatedforwhichtheimproveactivitieslowertimemacherMinimalcalculations.

scheme[99,100]forbiddenhavesets:introducedIgelmundaandbranchingRader-detailedbasedinSectionsdiscussiononminimaloftheseforbiddenconceptscansets.beAmoreSectionBesidelower6.2andbounds8.2offoundwhichthissurvey.

arewithinDemeulemeestere.g.3.2,thedominancepartialenumerationrulesaresuccessfullydescribedusedinSprechersearch[185]inorderandtoHerroelenalgorithmsprunelarge[48,49]paresDuringaboutthealreadyevaluatedpartialstoredobtainabledata.theIfcurrentpartialsearchscheduleprocesswiththerulethenotfromitthecancurrentbeprovenpartialthatscheduleanysolutioncan-previouslybebetterevaluatedthanasolutionpartialscheduleobtainablethefrominfor-

amationtrackingofrulestheisskippedmaywhichbehasbeenstored,thenback-hereperformed.fortheAsakedescriptionofsuchrulesreaderareoutlined.

isreferredtoSectionof5.2shortnesswheresomeand3.2.Lowerbounds

valueUsuallylowerboundsfortheoptimallaxingof jpre jgsolutionmaxcanbecalculatedlaxedsomeoftheconstraintsandsolvingthebyre-re-resourceproblemlengthconstraintstooptimality.leadstoRelaxationthecriticaloftheStinsonwhichanetal.[188]providesasimplelowerbound.pathpathactivitytimeg .Theyiwhichimprovecalculatedoesanotthismaximalbelongboundbyaddingnumbertoacriticalewithpathg units.Byactivityaddingimaxcanfbe0YpprocessedinparalleliofiÀesteadlengthanewlowerboundiisgtothecriticalandpathHerroelenofaddingaugmentasingleactivity,Demeulemeesterprovided.In-bound node-disjointprocedure.forg usingwithaag criticaldynamicandcalculatepathg byaprogrammingalowercoincideg ation (cf.withIngeneral[172]).theHowever,optimalthislowersolutionbounddoesnotthetwo-pathvaluerelax-formethodcantwooptimaljobs.developedbesolvedThisapproachfortotheoptimalityjobbyagraphicalalsoshopallowsproblemtowithwindowssolutionforg whichrespects®ndtimeanfollowingAboundforoftheactivitiesing (cf.[28]).thelinearMingozziprogrametwhichal.[126]isbasedontheTheyprecedencebeconsidermaximalconstraintssetsandallowsrelaxespreemption.partiallycharacteristicprocessedinparallel.Letof activities whichcan1Y2YFFFY qbethelinearprogrammingvectorsrelaxationofallthesehassets.theformThenthemin qxj

1 j 1 qsXtX

ijxjPpiYi 1YFFFYnY

2 j 1

xjP0Yj 1YFFFYqY

3

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4111

wheretivitiesxintegerrepresentedjdenotesthebynumber oftimeunitsallac-jareprocessedjointly.packingversionofthedualofEqs.(1)±(3)isThelowerproblem.Mingozzietal.[126]provideasetschedulingboundsproblemproblemforthebyresource-constrainedsolvingthesetpackingprojectdirectlyBaaretheuristically.

al.[5]solvetheniques.byapplyingcolumnlineargenerationprogram(1)±(3)tech-growingAlthoughtiesexponentiallythewithnumbertheofcolumnsis[31]thetimeenhancedmethodtheisapproachquitefast.byBruckernumberofactivi-takingintoandaccountKnustdowswindowsusingarefortheactivities.Thesetimewin-Nowa®ctitiousderivedupperfromboundtheprecedenceconstraintswhichthewindow.cancolumnsbeprocessedcorrespond jointlytoforinsetsthemakespan.aofgivenactivitiesscheduleTheobjectiveisto®ndapreemptivetimeschedulesearchdoesrespectingnotalltimeswindows.Ifsucha``destructiveprovidesexist, isalowerbound.Binarybeenimprovement''largest withtechniquethisproperty.hasThesevarioususedbyKleinandScholl[105]whotestedalsoupperboundmethods forprovinginfeasibilityofanbeenOtherand-boundintroducedlinear.

programmingalgorithminconnectionbasedboundshaveofChristo®deswithettheal.branch-[40].

3.3.Heuristicmethods

basedThe®rstheuristicmethodswerepriority-rulemultitudeschedulingmethods(cf.[103]).Uptonow,atestedority-basedexperimentallyofpriority(cf.rules[4,22,42,153,194]).wereproposedandintuitive,computationaleasyheuristicstohavetheadvantageofbeingPri-withoptimalrespecttoe ort.implement,theaverageHowever,andfastintermsofdeviationtheydonotexcelresearchobjectiveristicsintegerlikeinterestsfunctionvalue.Hence,fromrecentthetruncatedshiftedbranch-and-boundtomoreelaborate(cf.heu-disjunctiveprogrammingstraint-basedarcanalysisconceptsbasedheuristics(cf.[148]),[4]),(cf.(cf.[196]),[4,14]),samplinglocaltech-

con-niques[5,24,85,108,119,169]).(cf.[110]),andlocalsearchtechniques(putationalresults

branch-and-boundDemeulemeester(cf.algorithmandHerroelenon[48]testedtheirup[154])whichconsistsof110testtheproblemsPatterson-setanto51activities.TheysolvedtheseproblemswithwithModelaveragerithmof70computationtimeof0.21s(IBMPS/2StinsonA21,25etal.MHz)outperformingthealgo-drivenKolischetal.[116][188]developedbyafactortheofparameter-nearly12.hasprojectgeneratorProGenwhichthereafteralgorithmsbeenwidelyusedasatoolfortheevaluationofproject90,scheduling.proposedMeanwhileforresource-constrainedtestsetswith30,consistingand120activitieshavebeengeneratedeach60,activitybytestofset480instancesofvarioustypes.The30sonalDemeulemeesterwasalso15computer(IBMandusedtotesttheapproachPS/2HerroelenModel[48]55SX,onaper-solvedMHz).480timeproblemswithinWhereaslimitof1000instances1.06sonthePatterson-sethas386SX,beensperhaveaverage,beenonlysolved415withinoftheaprogrammingMingozzietbetterformulational.[126]problem.

reportthattheirlinearbythanthecriticalsequencebasedboundboundsintroducedperformcompetitiveStinsonetal.[188],andthattheiralgorithmismeulemeestertoknownandtheHerroelenprocedure[48],presentedbyDe-[49]uptothen.DemeulemeesterandtheHerroelenbestoneboundenhancedfourunsignedresourcesofMingozzitheirof8etapproachbyadaptingalowerbital.[126]sizeandbyrepresentingtheyinteger.Allowingasthroughmuchasone32bitsetcouldsolvetheentire30activitybenchmark-24Mbyte34forSprechersonthea®rsttime.TheCPU-timeaveragesaboutalgorithm[185]personalcomparedcomputerhis(80486,25MHz).rithmwiththeenhancedversionbranch-and-boundofthealgo-outmemorytheoftradeo DemeulemeesterbetweenandcomputationHerroelentimespointingrithmsolves479ofrequirements.ofDemeulemeesterWhilethe480benchmarkandtheenhancedalgo-andproblemsHerroelenwith[49]30

项目进度管理

12P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

activitiesMbytewithinaveragetimeof12.33susing24theusingsamememory,problemsthewithalgorithmaverageoftimeSprecherof12.85solvessal.The400but[32]branch-and-boundKbytememory.

solveslessproblemsalgorithmthanotherofalgorithms,Bruckeretquirement.itsmainusesproblemsatmostForadvantageissmallermemoryre-10problemswithupto90activitiesit®rst20/801timewithinwith60Mbyte.a1activities326ofhtimelimitwerethe480veri®edbenchmarkfortheconcludedComparingworkstation.

onaSUN/SparctheheuristicmethodsitKolischbasedandthattheadaptivesearchalgorithmcanbeofgeneticonlatedalgorithmscheduleDrexlofschemes[110],theHartmannoftabuBaarsearchmethod[85]andetal.[5],thecocqannealingalgorithmofBouleimentheandsimu-Le-Kolisch[24]parisonandprovideHartmannthe[112]bestperformedresults.Recently,rithmsofmostoftheavailableheuristicacom-algo-results,thetheforgeneticlargeralgorithminstances.ofAccordingtotheseandsimulatedLecocq[24]annealingarethemostalgorithmHartmannpromisingofcandidates.Bouleimen[85]and4.Time±costtradeo problems

worksSofar,generalizationwithwe®xedhaveonlyconsideredprojectnet-ministicof(andthisknown)settingprocessingthatistimes.Aobtained(andaccordingbyassumescompleteinformation)stilldeter-ispaytopermittinghowmuchprocessingtheplannertimestovaryonlocationtheforprocessingit.Inviewoftimesthecannextiswillingtobesection,interpretedthiscontrolasties,ofanonrenewableresourcetotheactivi-al-higherwherecostalargerallocationtoanactivity(i.e.,aprojectTheplannerinput)thenreducesaimsatitseitherprocessingtime.onmakespansubjecttoa®xedminimizingupperboundthelemtoproblema),thegivenornonrenewableatminimizingresource(thebudgetprob-boundonthethemakespantotalallocationsubjectmoney,).Astheallocationisusually(themeasureddeadlineinastime±costthesetradeo problemsproblems.

arecommonlyreferredto4.1.Model

lemsAactivities,consistsformalmodelofasetfor time±cost f0Y1YFFtradeo FYnYn prob-denceadirectedgraphq Yi of1gofeachtimesactivityconstraintsj,aamongsetMtheactivities,and,prece-forfunctionpPMjofpossibleprocessingjj,togetherwithanonincreasingtradeo andbetween jXMj3R thatmodelstheindividualcatedthecost(oramountprocessingoftimeresource)pjof activityjj pj allo-w toit.Section5coversthemodeldealtjasimilarwithpre wayinjgthismax,ageneralizationofthemodeltosection.denotetheThere,setMjwillbeusedincostDi erentcostfunctionsassumptions leadtodi erentontheofsubcasessetsmodes.

Mjofandtime±thejMFortradeo instance,problems.

ifeveryMjonproblemM isaclosedintervalj jY j andjisa nelinearanddecreasingj,wehavethelinear(i.e.,If,the®nite)onintroducedthesetotherbyand hand,Kelleyeveryandtime±costMWalkertradeo [104].jisadiscretejisdecreasingonMbyMuthHarveydiscreteandtime±costj,wehavePattersontradeo problemintroducedsignmentArealization[96].

[87]andHindelangand 2

oftheprojectisanas-jgivenP .TheoftotalprocessingpPRn

costtimespjPMjtoactivities p ofgearliestp byofthe p therealizationpisjP j pj .Themakespanmax hasstartschedulerealizationofthepisprojectthemakespanwhenactivityofthepathprocessingjPinq timeYi pwithi.e.,pthelengthofalongestjj,jas``length''ofvertexoptimizationFixing .

eithermizeproblemscostortime,withweobtaintworelatedgetBudgettheothertheobjectivetomini-minimizes P0,problem:parameter.

®ndarealizationForagivenpwithnonnegative p T bud-makespan,Deadlinethethat®ndproblem:makespanarealizationForgthatamaxgiven p .

pdeadlinewithgonthemax p allUsually,minimizesonethewantstotalcost p .

Tfunction

possiblebudgetsortodeadlines.solvetheseThisproblemsleadstoforthe

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4113

opt X minfgmax p jpjPMjY p T ggivingbudgetthe ,andminimumthefunction

makespanasafunctionofthefopt X minf p jpjPMjYgmax p TgYgivingdeadlinethe(theminimumcostasafunctionofthew Thebudgetprojectproblemcostiscurvea).

specialcaseofWhile1jpre jgmaxwhichiscoveredinSection5.sourcesinsource,andthisonlysectionwehavenorenewablere-version.Section5considersonesinglethegeneralnonrenewablemulti-modere-characteristicsSimilarly,andofthethemulti-modedeadlineproblemcase(Sectioncombines5)Inofw ourthe1jpre notation,resourcelevellingj

ritcouldproblembedenoted(Section7).bykk Yt .

4.2.Exactalgorithms

getKelleycontextproblemandandWalkerthedeadline[104]discussproblemboththebud-In[15]),thisthethesettingofthelineartime±costtradeo withinproblem.theproject(andcostalsoinamoregeneralone,seesiderinverseonlyffunctionofcurve foptcanbeobtainedasopt,soitsu cestocon-opt.

pressedForevery®xeddeadlinefopt canresemblesasUsingaaspecialmin-costlinear¯owprogramproblemwhosebe(see[74]).dualex-optimizationstandardresultsfromparametriclinearpiecewiserameterlinearithenceandconvexfollowsfunctionthatfoptof the ispa-adevelopedFulkerson[74]andprojectactivity-on-arccostthecurvesamealgorithmKelley[102]toindependentlycomputetheiterativelyrepresentationfopt.Thisofalgorithmtheusesan``cheap''activitiescutscalculatesinasequenceofnetworklessandandlessbreakpointbywhichthethecurrentmakespannetworkisreduced.ofcriticaltoone.

achangeofofthethecurrentprojectcutcosttocurveamorecorrespondsEveryexpensive¯owEverycomputationsuchcutincanwhichbedeterminedthecapacitiesbyaaremax-de-

rivedoffromtheslopesofthelinearcostfunctions jquentlythecritical[159,160].

beenimprovedactivities.byThesePhillipsideasandhaveDessoukysubse- [79]),O jThis j2logalgorithmj j byispolynomialpercutbepleslarge.butSkutellathenumberstandard[178]ofprovidescutsto¯owbemethods(cf.acomputedclassofmaynentiallyforwhichtheprojectcostcurvehasexam-expo-exponentialmanybreakpoints,thusrequiringanareThenumberofcutcalculations.

cently,discretecase Deetiswhereal.quitethe[46]commonpossibleprocessingtimesshowedthat,inpractice.Onlyre-there,itisgisstronglyarealizationNP-completepsuchtogiventhatdecidethebudget p Twhether andatmaxjMmost p Ttwo2.Thisprocessingholdsalreadytimeforalternatives,activitieswithi.e.,manyDuejjT2.

been(exponentialtothepracticaltime)importanceexactalgorithmsoftheproblem,havegrammingproposed.[96]approachesEarlyexamplesbyHindelangaredynamicpro-gorithmandRobinson[164],andanenumerationandMuthal-onThecurrentlybyHarveybestandknownPattersonalgorithms[87].

stilladditiondynamicunderlyingthedecompositionprogramming,putationThedecompositionisknownasmodularthatofthefa-hascombinatorialmanyapplicationsorsubstitutiondecompositionandcomprehensiveoptimizationinnetworkandothermacherarticlebyM oproblems,hringandseeRader-the

lemIts[129].

Rothfarbwasusefulness®rstparalleletal.observedforthe[165]forbytime±costtradeo prob-theFrankspecialetcaseal.of[71]series±andtiondue[130]).

totheoremdecompositions.Thegeneraldecomposi-BillsteinthatandinvolvesRadermacherarbitrary[15]modules(seealsoisprojectBecausecertaincostofthemodulardecomposition,theinindecomposablecurveneedssubnetworksonlytobeevaluated(theforThisacompositioncomposableisdoneseries)oftheoriginalnetwork.factorsnetworkby``transforming''toaseries±parallelsuchannetwork

inde-

项目进度管理

14P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

andtheseries±parallelseries±parallelthenperformingcase.theThe``easy''calculationsfortaintionnodesfornetworksuccessivelytransformationidenti®esintocer-aparalleltransforms``duplication''.thenetwork``closer''Anysuchtoaduplica-amultiplicativeone,butincreasesthecomputationtimeseries±byandThisideaseemsfactor.

tobeduetoRobinson[164]DealsoethasbeenfurtherdevelopedbyBeinetal.[13],in¯uencedcameal.[45]upandElmaghraby[66].Thesameideaseachinreliabilityother,seetheoryandseemtohaveimplementationDemeulemeestermentduplication.twostrategiesofetthisal.[6].

[50]providethe®rstforapproach.®ndingtheTheynodesimple-foretofal.toduplications[13],whichThe®rstfollowsthetheoryofBeinrequired,resultsinwhiletheminimumthenumbertominimizethenumberofrealizationssecondthathavetriesmeulemeesterbeconsideredexperienceetal.[50]duringreportthealgorithm.De-withoutfornetworkswithupontocomputational45activitiestwoidentifyingaclearwinnerbetweentimeThestrategies.

worknetwork.[13]referintoaseries±Ittoprovidesitasthefrombeingforthe``distance''ofthegivennetworkadesignSuchnetworkofadistanceseries±parallel.

measureisimportantforthechasticproblemspolynomial-time(seealsoalgorithmsSection8.1foronmanyproachesscheduling),extendedforseries±parallelsincegraphscomputationalsto-canap-areseries±parallel,exponentialtoalgorithmsforarbitrarygraphsoftenthatberatheronlyinthanthein``distance''itsfrombeingtoringAnother[13],allwhichcomplexitymeasureforthisdistancesize.

isthefac-isbasedalsoonintroducedbyBeinetal.work.pathscomplexityBeinfrometal.the[13]sourceaspecialshowedtothewaysinkofofdescribingthenet-ductionprovidesanupperthatboundtheforfactoringthere-bothmeasurescomplexity.areinNaumannfactequal.

[137]showedthat4.3.Approximationalgorithms

time±costTheapproximationalyzedtradeo problembehaviorhasrecentlyofthebeendiscretean-caseHe®rstbySkutellapresents[177].

apolynomialreductiontothecessingwhereMtimes,everyj"andactivityoneofhasthematmostistwozero.pro-So

jgorMj fp"jgforSkutellaFor f0suchYp

activityjP .replacesde®nesadiscreteanaturaltime±costlineartradeo problem,~relaxation,which

costandfunctionMjby theintervallinearinterpolationM

j 0Yp"j andtakesasjthebetween j 0

j "j .Allotherparametersremainthesame.®xedNowp

relaxationdeadlineconsider.Onethedeadlinethenproblem foraan

~forthesamedeadline®rstsolveswhichthelinear

yieldsSinceoptimaltheallparametersrealizationarep

~of ~inpolynomialtime.specialobtainedfcasealsooptimalbeintegral,realizationassumedtobeintegral,solution0Yp

"jg.This~isthenbutp

~pwillinthis

``rounded''jneednotbeinprocessingofthesolutionoriginalptoa0~problem byroundingthe

jofthoseactivitiesjwiththe`thelowerp

~j`p"timep

jvaluetotheislowernecessaryvalueinpj order0.RoundingtotoroundingIfdeadlinepreservethe.

i.e.,Inp"mustbudget,thusbeproblemisconsidered,thepreservingdoneintothethebudgetothercondition.direction,

jdiscretebothj cases,p

proximation,time±costtheproducedtradeo problemrealizationisanpof -ap-thecessingwhere isthelargestoccurringpro-and ptime T ofÁfanyactivity.Sogmax p T Á opt opt guaranteeFortheroundingofdeadline,respectively.

cannotproblem,betheperformancebehowever,improvedalgorithmatanditisopenimprovedwhetherbyitthiscanalgorithms.Skutellaall.Forthebudgetproblem,problem,Unlikedevelopsthesituationbetterforapproximationroundinghevaluesomecannowprocessingrepairathedeadlinetimesbudgetviolationbythen"``saving''partofthebudgettothethathigher

j,thuscantothebep

lower``reinvested''value0.

toshorten``critical''activitiesapproximation,Forprojectswithi.e.,pfor"jPaf0givenY1Y2gbudgetthisleads ,thetoaal-

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4115

gorithmgproducesarealizationpwith p T andgorithmmax p TisdO jopt j3 elog.Thej runningtimeoftheal-makespanTheNP-completenessj .

showsof2canberealizedofdecidingwithwhetheraimprovedthattheperformanceratioofagivenbudgetcannotbetionalForprojects(unlesswithP NPp).

jT ,Skutellausesstronglypartitioningtechniquesandobtainsaddi-awithdi erentaperformancepolynomialvariantyieldsguaranteeapproximationalgorithmof2 log2 1 .AconsistsAnotherlog2 3.

getinrelaxingideaforapproximationalgorithmsbicriteriaordeadline),alsothetightconstraint(bud-similarapproximationthusarrivingattheso-calledvalue polynomialY (i.e.,0to`thosel` 1above, ingtime±costthat,ideasforpairaopt and fopt l ptimeconstructarealization ),ponesuchcanthatintwice ` 1a 1Àl andgmax p T 1al .For,realizationasthisexpensiveyieldsaandrealizationtwiceaslongwhichasanisatoptimalmostChoosing lforthegivendeadlineorbudget.tios1aeYexpectedof1 eoneamakespan. eÀobtainsuniformlyatrandomintheinterval1 %1Ximproved58fortheapproximationexpectedcostandra-5.Multi-modecase

rithmsThis®nedforsectionsolvingcoversw exactjpre andjgheuristicalgo-maxwhichisprojectaspologicallynetworkfollows.isLikeassumedinthede-toprevioussectionstheexecutedeachinsorted.EachactivitybeacyclicjP mayandto-beonceactivityonetivityselectedmayoutmaynotofasetofMjmodes.Also,notbebepreemptedchanged,thatandis,aanmodeac-completedjoncecessingisactivityinstartedmodeinmodemPMjhastobejinmodemwithoutmtakesinterruption.pPro-jmperiodsofsupportedbyasetRqofrenewableandasetandRm span,,nonrenewablethatis,anupperresources.boundonConsideringtheahorizonrenewablewehaveresourceanavailablekinperiodamountproject'st 1ofYFF qmake-FkY unitslikeofin

Sectionableprocessedresource3.ThekoverallPRmiscapacitygivenbyofthenonrenew-q

mk.Ifactivityjisnewableisunitsinprocess.resourceinmodemthenrjkmunitsofthere-Similarly,kareusedactivityeachperiodactivitym

j

theofthenonrenewableresourcejconsumesk.Ingeneral,rjkmWeparametersnondecreasingassumethemodesareassumedtobetobeinteger-valued.pprocessinglabeledtimes,withrespectthattois,mjmTpjYm 1forallactivitiesjP andmodesmakespan-minimalPf1YFFFYjMjjÀ1gconstraintsschedule.TheobjectiveSisto®ndaand formulatedjpre bylimitedimposedjgresourcebytheavailabilities.precedencethatmeetsSimilarrelationsthetomaxingeneralalsow optimizationmathematicallyintermsjpre ofajgbinarymaxisvariablesmodexmodelwhichmakesuseofbinaryjmt 1,ifshortness,minperiodt(0,activityotherwise).jisForcompletedinfeasibleIfjRmwedonotpresentaformalmodelthesakehere.ofever,solutionjP2andisjNP-completeMjjP2YjP (cf.Ythen[109]).®ndingariodupperavailabilitypresumingfeasibilityoftherenewableandaconstantper-pe-How-bytimes.theboundontheminimummakespanresources, isgivenanprecedenceGivensumofantheuppermaximumboundactivity weprocessingprocessingrelationstervalstimesandthemodesofcantheshortestusetheplained inigtoderivetimewindows,i.e.in-SectionjYvgj similar3.towhathasbeenex-5.1.Exactalgorithms

w Optimalinjpre jgproceduresforsolvingmaxgeneralizeproceduresdescribed jSectionpre jg3.1forsolvingthespecialcaseimprovedThePrecedencemax.WeTree:summarizeSprecherthreeandalgorithms.Drexl[186]ducedboundingbyPattersontheprecedenceetal.[155]treebyalgorithmintro-and-boundcriteria.quently,EachamodetreeanHere,onlevelgofincludingthebranch-newmeligibleactivityjgand,subse-jgrelatedcombinationofofanthiseligibleactivityactivityareselected.andacurrentmodenodeincorrespondsthebranch-and-boundtoadescendanttree.

ofthe

项目进度管理

16P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

branch-and-boundModeanddelayalternatives:WesummarizethehermodeetapproachproposedbySprec-atactivitiestimemal.[187].Aneligibleactivityjscheduledinjtwithstarthavetime jissaidtobeinprocessgifwejTtg` j pjmj.Eligiblepointpreviousthatarehave(temporarily)alreadybeenstartedassignedattheadecisiongiblelevelofthesearchtree.Iftheremodeareateli-amode,activitiessetternativeofmodethatis,alternativesifthatithavenitnotyetbeenassignedaggisÀ1isnotempty,thenthejalternative,Pitisamappingwhichcomputed:assignseachAmodeactivityal-gnitgÀ1amodemjPMj(temporarily)theHavingstartedremaining.Selectingamodeateligibleactivitiescanbethemhavetothestartedalleligiblethedecisionactivitiespointbyasaddingwell.minimalcausedsetaresourcets gofthecon¯ict.activitiesinprocess,maytoDAthefollowingdelayalternativesThus,thesetofthede®nition:iscomputedAaccordingnewablegisa qresourcesubsetofkPts Rq

gitsuchis

thatdelayforalternative

eachre-jPts qgnDAgrjkmjTternativek.Observethateachcombinationofamodeal-correspondsandarelatedminimaldelayalternativethetoadescendantofthecurrentnodetheModebranch-and-boundinandextensiontree.

ternativesconcept[86]areofintroducedmodealternativesalternatives:UsingagainbyHartmannextensional-cisely,totheholdseligibleanconstructextensionpartialsetforalternativeschedules.MoreandDrexlpre-which EAgisasubsetofjPqq

moreover,foreachts g EAgrjkmjT kbranch-and-boundEArenewableresourcekPRqand,g Yifts decisiontreeweg determineY.Atlevelthegoftheties.tivesThenpointwecomputeandthesetoftheeligibleactivi-newthatfor®xingthemodestheofsettheofeligiblemodeactivitiesalterna-activitieshave®xed.thenotmodesbeeneligibleofwhichbefore,havethatis,thosetheextensionsetAfterofextensionselectingamodealternative,notyetcomputebeenspondinglevel.activitiesalternativealternatives.beforeEAFinally,selectangandstartthecorre-andaaEachrelatedcombinationofbranchingamodetoalternativethenextand-bounddescendantextensiontree.

ofthecurrentalternativenodecorrespondsinthebranch-tow Recently,straintsjtempjgthemoregeneralproblemmaxstartgivenbyminimumwithgeneralandmaximumtemporalstart±con-subjecttimeexactofresearchlagsbetweeninactivitieshasbeentheo Acombinationbranch-and-boundHeilmann[88],whereanofprocedureispresented.modeproblemstudiedcasecoveredbyAhndealtandwithintheSectiondiscreteErengin uthis4c[1].sectionandtime±costofthetrade-hasmulti-been

5.2.Dominancerules

severalInHartmannthemwillboundingandberevisitedrulesDrexl[86]adescriptionof

incanwhatbefound.SomeofcannotNon-delayabilitycurrentbefeasiblyscheduledrule:Ifanfollows.

ineligibleactivityestpartialschedulewithoutanyexceedingmodeitsinlat-thetobe®nishexaminedtime,thennoothereligibleactivityneedsstartedLocalleftshiftonrule:thisIflevel.

anactivitythatboundchangingtreeatthecurrentlevelofthebranch-and-hasbeenscheduleitscanmode,belocallythentheleftshiftedcurrentwithoutunscheduledMulti-modeneedsnotrule:beAssumecompleted.

partialthatnocurrently®nishrentleftpartialtimeofactivityscheduleascheduledwillbestartedbeforetheiscompleted.activityjIfwhenthecur-resultingshiftonmodeoramodemH,1TreductionmHofactivityamulti-modejwithjjrmthecurrentpartialscheduleTjwjj,and,canbemoreover,performedifkjkmHmjcompleted.

,thenTrjkmthejholdscurrentforpartialeachnonrenewablescheduleneedresourcenotbetheOrderswaprule:start®nishthetimetimethatofmaywhichConsiderbeisassignedlessthanascheduledactivitywhenorequaltoanythiscurrentpartialschedule.Ifanordercompletingswaponthatactivitythecurrent®nishattogetherpartialitsstartwithanyofthoseactivitiesscheduletimecanneedbenotperformed,thenscheduleCutsetinPSrule:De®ningacutsetbeofcompleted.apartialfollowingPS,Sprecherastherule.LetandsetoftheactivitiesscheduledDrexldenote[186]apreviouslyproposedeval-

the

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4117

uatedimalpartialschedulewithcutsetg ,max- m®nishtimefmax andleftovercapacitiesbek ofthenonrenewableresourcesk.LetPSextendedthecurrenttimebyschedulingpartialschedulesomeactivityconsideredjtobe Ifwehaveg PS withg startj.kjPPRfmaxm

,

m,then PSand mk PS T k forallityImmediateformablejnomodeselection:needsConsidernotbecompleted.

aneligibleactiv-inwithanyofcurrentlywhichisunscheduledsimultaneouslyactivityper-eachanytheactivities,maximalothermode.eligibleIftheearliestfeasiblestarttimeof®nishactivitytimeofinanymodeisequaltoneedsthenjistheonlytheeligiblecurrentlyactivityscheduledthatcurrenttolevelbeselectedofthebranch-and-boundforbeingscheduledtree.onthe5.3.Heuristicalgorithms

gHeuristicalgorithmsforsolvingw jpre j[60],maxhaveforinstanceandDrexlandGr unewaldbeen[61],providedOzdamar byDrexl

addressKolischmulti-criteriathesameandDrexlsetof[111].constraints,Slowi n

skietal.[149][179]0Boctor,jpre jgversionoftheproblem.butw mattackYrtheYqYmaxisthesubjectofBoctorpriorityDrexl,andDrexlandGr u

newald[23].analyzeWhile

etOzdamar al.providerulebasedsimulatedmulti-passheuristics,Slowi n

skilischsearchandfavorizesDrexlpresentageneticannealingproblemalgorithmalgorithms,speci®candlocalKo-e ectiveRecently,algorithms.

Hartmann[84]developedthemostingthistheneticsection.generalande cientItversionheuristicisageneralizedoftheproblemalgorithmforsolv-versiondealtofwithinandrithmbasicallyalgorithmgeneration,generatesworksalreadymentionedinSectionthege-3.3aninitialasfollows.population,Thegenetici.e.thealgo-®rstdeterminesbetheircontaining®tness y values.individuals y isandthendomlyaneveneachpartitionedinteger.intoThenpairstheofpopulationassumedindividuals.isran-toTooperatorpairof(parent)individuals,thecrossoverquently,theproducesmutationtwooperatornewo springs.isappliedSubse-tothe

genotypescomputingofaddedthethe®tnessnewlyofproducedtheo springs,children.theyAfterpopulationtotheeratorsizecurrentof2Ápopulation,leadingtoareaformerisappliedtoreduce y .Thenthepopulationtheselectiontoop-toThiswhichsizeagain y theandcrossovertoobtainthenextgenerationitsofgenerationsprocessiswhichrepeatedforaprespeci®edoperatorisapplied.numbertorsNowdetailscrossover,ashortdescriptionisdenotedoftheasqixgenetic.

opera-awmotherConsiderthereadermutation,isreferredselectiontoHartmannisgiven[84]).(forandtwoafather.individualsThenselectedtworandomforcrossoverintegers,new1andw2with1Tw1Yw2Tducedindividuals,adaughternareanddrawn.ason,Nowarepro-twofollows:fromdaughter,Inthefromthetheparents.positionssequenceThedaughteri of1YFactivitiesisde®nedasFFYwofthe1tionstheHowever,i wmother.Theactivitysequenceareoftakenposi-1 1YFFFYnistakenfromthefather.kenThisfromthethemotheractivitiesmaythatnothavebealreadybeenta-inObservethede®nitionparents'ensuresactivitythatsequencestheconsideredrelativeagain.arepositionsprecedencethatthe®nedpositionsfeasible.theresultingi 1YFTheFFYwmodesactivityofthesequencepreserved.activitiesonis2modesbyinthedaughterarede-imode wofthetheremainingmother'sactivitiesmodeassignment.onthepositionsThe2 1YFFHowever,assignment.FYnaretivitythepositionsThederivedson1YFFisFYcomputedfromthefather'swsimilarly.1oftheson'sremainingsequenceAnalogously,positionsaretakenaredeterminedfromthefatherandac-themodethe®rstpartuptopositionbythewmother.2ofthethermother.whileassignmentthesecondofthepartsonistakenfromthefa-assignmentGivenscheduleforanisderivedfromtheallactivitysequenceandamodechildThemutationisconstructed.

activitiesanearlieststartisappliedtoeachnewlyindividualindividualrandomsofandtheiscurrentde®nedasfollows:generatedGivenan1tivityTqintegersqandqpopulation,thentwo12with1Tq1`nand2Tnaredrawn.q1isjs

ifsequencetheresultbyisexchangingusedtoanactivityactivitiesmodifysequencejthesac-q1which

andq1 1

项目进度管理

18P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

ful®llsofthatthechangedtheprecedenceactivitiesconstraints.keepsitsNotethateachassignment.is,thismodi®cationassignedmode,positionThendoesnotchangethemodetermineofmqanewmodefortheactivityon2s jissrandomlychosen,thatis,werede-q2 activityf1YFFFYMbydrawingarandomintegeroutjsqg.Whilethe®rststepmaycreate

ducedmaycurrentintroducebysequences2

thecrossoverthatcouldnothavebeenpro-amodethatoperator,hasnottheoccurredsecondinstepformingpopulation.necessarilyamutationItonshouldbenotedthatper-thetothechangetherelatedanindividualschedule.ThisdoesisduenotbeenTworedundancyvariantsofinthethegeneticselectionrepresentation.operatorhavevival-of-the-®ttestconsidered.Thetionmethod:®rstvariantTheoriginalisasimplesur-individualssizeistheandrestoredremovingbykeepingthe y popula-bestsecondpopulationtheremainingonesfromsurvival-of-the-®ttestvariant(tiesisaarerandomizedbrokenarbitrarily).versionofThethewhichAnumberofs vtechnique.

islandstakeswithplace.thearti®cialareconsideredonOneachevolutionisland,theasdescribedevolutionabovestartstion.begenerationdenotedLetanindependentlythegeneratedinitialpopula-asislandiwithcurrently1Tiunderconsiderationprespeci®edbeandmigrationdenotedprobabilityas`gs vwith,and1letthecurrentwTgTqix.AmigrationistrolarandomnumberqP 0Y1 isusedqtionTwthemigrationbetweenthedrawnislands:tocon-Ifwheregmigrationg.

itleaves,thenisaddedislandthetoi®ttestindividualofgenera-theandpopulationmigratestoofislandgenerationi 1speci®edThestoppingcriterioniseithertoreachaalternatively,numbertimetomeetofislandsaasdescribedabovepre-or,thewithoutboundingthegivennumberlimitofonislands.theCPUIncompletedlatterweandcase,theiftimeqixlimitgenerationshavebeention.skips vClearly,totheifnextthenumberislandandhasofstartnotyetbeenmet,islandsanewisgivenevolu-byare,calculated.

atmosts vÁ y Áqixdi erentindividualsproblemThegeneticspeci®calgorithmlocalsearchismethodaugmentedtoimprove

byatheproachscheduleleftal.shiftiswhichbasedrelatedtoanindividual.Theap-hasonbeenthede®nitionofamulti-modebound[187]inordertoaccelerateintroducedtheirbySprecheretleftscheduleshiftalgorithmofanoutlinedabove.Abranch-and-multi-modewithoutotherchangingwhichactivityreducesjisanoperationonagiventhemodesthe®nishortimeofactivityjstraints.activitiesandwithoutviolating®nishtimestheofcon-thechanged.

Thereby,putationalresults

jectAsetoftestproblemsconstructedbythepro-byavailableKolischgeneratoretProGenal.[116]whichhasbeendevelopedPSPLIB.intheprojectschedulinghasbeenproblemused.Theyarereferredalso).toForKolischdetailedandinformationSprecher[115]thereaderlibrary(cf.[114]isinstancesThemulti-modeproblemsetscontainingtivitiesmayhavewithbeen10,12,14,and16nondummyac-durationbeperformedused.ods.ofamodeinvariesoneEachoutoftherealactivitiesbetweenofthree1modes.TheableTherearetworenewableandtwoandnonrenew-10peri-instancesresources.fourwasForeachproblemsize,asetoftheparameters,generatedthatis,bythesystematicallyresourcefactorvaryingcomparisonInresourceHartmannstrengthandofeachresourcecategory.andcombinationofthethreeDrexlbranching[86]acomputationalschemesinTheisprecedencewithtreeboundingalgorithmrulescanbefound.timesthedelayfasterfastestthanprocedurethealgorithmonthewithbasedaverage.thecutsetruleonmodeItistwoandandties,sevenalternativesincreasingthatis,timesthecomparisonfasterwhenfor10activitiesprojectsareconsideredfactorwith16activi-basedtimesextensionfasteronmodenumberofactivities.increasesThealgorithmwithanthanandthedelayalternativesisatmost1.4performedalternatives,algorithmhence,thebasedlatterononemodeandtobytheothertwoalgorithmswithrespectisout-toaverage``maximal''thefactcomputationthattimes.Thisseemstobedueextensionbranchingalternatives.maynotTheberestrictedprecedence

to

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4119

treeduresalgorithmisfasterthantheothertwoproce-treeNoteworthyevenifthetocutsetruleisnotincluded.

branchingalgorithmtime-varyingschemesismorementioninthegeneralthatsensethatthantheprecedencethethecaseothersourcescanbeavailabilitypro®leofrenewablere-ofbeenTheDrexlcomparedgeneticcovered.

algorithmofHartmann[84]haswithrithm10[111]nondummyandwithOzdamar thealgorithmofKolischand

activities.[149]onHartmann'stheProGenset

fromKolischtheproducesanaveragedeviationof0.22%algo-ofandoptimalDrexlproducesmakespan.anTheprocedureofAlso,morethan0.8%fromtheoptimalaveragemakespan.

deviationdeviationthedeviationofalgorithmofOzdamar hasanaverage

Hartmannproducedmorethanthoseofthe[84]twoisheuristicsnearlyby0.8%.theHence,theaveragefourgeneticfromtimesalgorithmtheliterature.lowerthanof6.Minimumandmaximumtimelags

Thissectionisconcernedwiththetweenjtempditionthejstartgproblemmax,ofthatdi erentis,maximumactivitiestimelagsbe-oftentominimumones.Maximumtimeoccurlagsinad-neousneededinpractice,forexample,ifsimulta-arerequired,ornondelayactivitiesdeadlinesexecutionsourcesareprescribed,forsubprojectsofseveralactivitiesistimewindowsorindividualforre-orderproductionaregiven,orinschedulingofmake-to- Sectionboundjtemp6.1deals(cf.[138,139]).

withmodelingproblemproceduresmethodsjgmax.Sectionfor 6.2jtempdescribesjgbranch-and-max.Heuristiclatterresults.twosectionsarebrie¯yalsodiscussedsummarizeinSectioncomputational6.3.The6.1.Model

setAsinSection3, theof f0Y1YFFFYnYn 1gistheprojectnodeactivitiesnetwork.setofofthetheproject,whichcoincideswithThecorresponding®ctitiousactivity-on-nodeactivities0and

nthe 1mumproject,representdi erenttimelagrespectively.thebeginningdIfthereandisterminationaofij

min

PZthegivenstartofmini-P0betweentwowewithintroduceactivitiesanarciandj,thatis, jÀ iPmin

,min

timeweight. iYj intheprojectnetwork

dij

ilagdijmax

dijP Zdij

IfthereisagivenmaximumP0betweenmax

andj,thatis, jÀ iTdijmax

,thewestartintroduceofactivities

anarcworkjYi withweightdji Àdij.Theresultingnet-whichwith mumiYj Pisatisfynodegenerallytheset containsconstraints,arcseti,andcycles arcweightsdijjÀdue iPtodijmaxi-forminimumtimelags.Anappropriatespeci®cationoftheuniqueingGivenprojectassignmentandmaximumtimelagsensuresthea(seeofthenetworktotheunderly-schedule[139]).

0Y 1YFFFY n 1 ,A Yt fjP j jTt` j pjg

is(orthespectively)insettimeofactivitiesand

interval tinYtprogress 1 orperiodattimett P1,ZPre-0r

k Yt

rjkjPA Yt

isProblemtheusagefollows:

ofjtemprenewablejgresourcekPRattimet.

maxcanthenbestatedasmin n 1

4 sXtX jÀ iPdij iYj Pi

jP0YjP X

5

rk Yt T kYkPRYt 0Y1YFFFY À1Y 6

wherebound

iP max piYmax iYj PischedulesItisondij isanupperwelltheknownminimumthatprojectduration.

actlypositiveifthe(whichsatisfytheEq.set(5))STisofnonemptytime-feasibleex-scheduleslengthnetwork(see[12]).doesnotThecontainsetSofacyclefeasibleoferallyconvexdisconnected(whichsatisfyandEqs.represents(5)andthe(6))unionisgen-oftiallywhetherinpolyhedrawhosenumbergrowsexponen-[12,144]).

ornnot.Moreover,S YisstronglythedecisionNP-completeproblem(cf.Z SometimesjP areaddedtheconstraintstoEq.(5). We0 deleted0andthese

jP

项目进度管理

20P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

constraintsoptimal scheduleforthe itfollowingholdsthatreasons: Foreach0 0.Moreover,any0 0forallSinceheuristicfeasiblethereallparametersmethodschedulesddiscussed constructedinSectionusing6.3.ij iYj PiprovidedalwaysSections6.2thatexistsanintegeroptimal areintegers,scheduleandS Y.AllmethodsdiscussedindecompositionForapproximately6.3constructsolvinginteger jtempschedules.jgexpedient.isAcycleapproachoftenturnsoutmaxto,beanodes.astrongcomponentstructurewhichofcontainstheprojectatnetworkrateForeachcyclestructuretreatedasleastasepa-twoandsubprojectcorrespondingstartedattimewithzero,originalaschedulingresourcecapacitieswhosesubschedules(feasible)toproblemssolutions(4)±(6)arecanbeproblemstatedproventhefollowing.Neumanntheorem.

andZhancalled[140](feasible)workThereisafeasiblesched-foreachifcycleandonlystructure.ifthereisaly)Severalstrictsolvingheuristicprojectschedulingproceduresproblemsfor(approximate-requirelengthordertheofa0longestinnodepathsetfrom (cf.node[70]).iLettodaijbethepathprojectifrominetwork,toj.ForwhereiYdtherenodeisjnoinij ÀIifand0jdifandonlyifeitherjP(a) Ydi j,0weorthen(b)dde®neijbij 0ji`0.

6.2.Branch-and-boundmethods

forThemalsolvingbasic ideajofbranch-and-boundalgorithms example,jtempsolutiontempjgtothejgmaxresourceisasfollows.relaxationAnopti-ofmax(i.e.problemsi theearliestschedulei (4) and i (5)),forj jP withStartingj d0j,atwithcanschedulebefound i inpolynomialtime.

pointsintimet,thatis,,resourcecon¯ictsrjkb kforsomekPRandp A Yt

jPp

7

cantionalbeseveraltemporalresolvedsuccessivelyconstraintsbywhichintroducingdelayoneaddi-biddenclusion,setactivities.SetpinEq.(7)iscalledafor-orReyckBartuschit.isIftermedpisminimalwithrespecttosetin-etal.[12],aminimalDeReyckforbidden[51],setand.

precedenceandHerroelenwhichpcorrespondconstraints[54]toaddingofhaveDethearcstypeused ``ordinary''jP i pi,disjunctivetothenetwork.precedenceSchwindt iYj withweighticonstraints[174]hasintroduced jPiPminpnfjg

i pi Y

8

wheredelayingpbeonlyisaoneminimalactivityforbiddenjset.Insteadofminimaldelayedatthesametimewhich,severalformactivitiesacan(Eq.(8))isdelayingreplacedalternativeby(cf.[51]).so-calledThenminjPw2

jPminiPw1

i pi

withwminimaldelayingalternativew2andcontaining1X A Yt nw2.w2forbiddensetatleastoneiselementaninclusion-minimalofeachminimalsetconsideredTosolveproblemtwo p jA Yt .

partialtempjgproblems.max,SchwindtThesequencing[174]haswhichsuchschedulingthatsatisfyconsistsY disjunctiveof®ndingSprecedenceaset ofconstraintsschedules S.Thesubjectordinarytogionprecedence problemPSconsistsofminimizingcorresponding n 1 .IncontrasttothecaseofconvexSconstraints,thefeasiblere- ofthelatterproblemused,dra.butifrepresentsdisjunctivetheprecedenceisnolongerunionconstraintsareforvisedsolvingApseudopolynomialofconvexpolyhe-bySchwindtthescheduling[174].

problem®xed-pointhasalgorithmbeende-of appropriatelyThebranch-and-boundalgorithmthenconsistsYFFFY rwith enumeratingrsequencingsuchsolutions1m 1 S m Sthatmin PS

n 1 m min

1YFFFYr PminS m

n 1X

Preprocessingboundsand-boundandproceduresaswellasgoodlowermethodfathoming(see[174]).rulesspeedAnoverviewuptheofbranch-recent

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4121

preprocessingdestructivefoundinHeilmannlowertechniquesboundsasandSchwindtforwell jastempconstructiveand[89].

jgmaxcanbestraintsTheationmarkedlyconceptofreducesdisjunctivethenumberprecedenceofenumer-con-comparisonnodesofbywiththethesearchtreetobeinvestigatedinanalysisDeReyckproblembySchwindt[51].Anbranch-and-boundexperimentalmethod[174]performancesourcesProGen/maxeachinstances(generatedwith100bytheactivitiesbasedproblemandupongenerator®ve1080re-Schwindt'sbySchwindt[174])hasshownthatmalitys(usingwithinmethod10sthansolvesDemoreReyck'sinstancestoopti- AnotheranIBM-compatiblemethodin100etjtempjgbranch-and-boundPCPentiumprocedure200).maxhasbeeninvestigatedby hringfor

resolvingal.[135].Themaindi erenceliesintheMwayo

ofcedures[51],proposedresourcebycon¯icts.BartuschContraryetal.tothepro-[174],DeconstraintswhereReyckandHerroelen[54][12],andDeSchwindtReyckideaThatisareadditionalintroduced(disjunctive)toresolveacon¯ict,precedencetheresolvedis,toaintroducetivitiesbyresourceordinaryincreasingcon¯ictthereleaseatreleaseacertaindatesinstead.datesdtimetis0j0andjjPPwwofac-2(i.e.thetimelagsbetweenactivities2)accordingto

d0newjX miniPw1

i pi

foralljPw2Y

whereww2isatreeX datesisAthen Yt nminimalwdelayingalternativeand12.Everynodeoftheenumerationtheunchangedvalues(orstartrepresenteddtimes,respectively),onlybyavectorand,exceptofreleasefor0inj,thethecoursepathlengthsofdij iYjP remaintheOnobservedenumerationtheonehand,thismaytheinalgorithm.

principleenlargerelationbySchwindttreeconsiderably[174].Sinceasnohasprecedencealsobeendisjunctive,iscon¯ictitintroduced,mayhappenneitherthatthe``ordinary''samenorexistencehashand,markablethisoftoberesolvedseveraltimes,dueresourcetothewaymaximalofbranchingtimelags.givesButontheotherfeasibleformed.schedulesspeedupinthecomputationriseoftoatime-re-Moreprecisely,onceathebranchingcomputationhasbeenofopti-

per-mallowertime-feasiblelinearboundsdateinthenumberforschedules,newlyandthecorresponding

ofgeneratednodesisthenvantagethatcedenceoverhasbeentheproceduresincreased.activitiesThisforeveryreleasethatisintroduceamajorad-computationconstraints,wherethecomplexityforpre-thedraticprecedenceinthenumberoftime-feasibleofschedulesisqua-andconstraint(seeactivitiese.g.Bartuschforeveryetaddedprecedencepseudopolynomialinthecaseofdisjunctiveal.[12]),schedulingconstraints(seetheabove-mentionedsameTheproblemand[174]).

growthresourcedisadvantagecon¯icts,ofmultipleandoccurrenceofthesmalloftheenumerationtreetheistriedcorrespondingtowellbyperformingimmediateselectionrulesbekeptasComputationalasa(surprisinglyimplementationresultsindicatesimple)that,dominancerule.bounds,proposedtheprocedureofmoresophisticatedevenwithoutlowerHerroelenbySchwindtis[174]competitiveandwiththeonespropagationRecently,[54].

DeReyckandDorndorfetal.[57]showedonthattechniquesanintegrationfor ofjfurthertempusedjgconstraintmax.Theywithinthestarttimesintheaforementionedconstraintssenseprovidesaverynewpromisingtime-orientedresults.branchingscheme6.3.Heuristicprocedures

proximately,Tosolvelargeinstancesof jtempjgmaxap-niquespriority-rulebasedtruncatedbranch-and-boundtech-truncatedmethodsuponhaveSchwindt'sbeendeveloped.algorithmAsandbeamrithm,searchbranch-and-boundtechnique,procedures,a®lteredtoproposedandadecompositionane-approximatemethodalgo-methodSectionexploitsbySchwindt[174].Thedecompositionhavebeennetwork,6.1.theanFirst,theoptimalforDecompositionscheduleeachcycleTheoremfrom CstructureCofthecyclebranch-and-boundiscomputedbyofusinglengthstructurealgorithm.Second,eachzeroCisreplacedbyanequivalentcycleapplied Cto.Third,whosearcweightsaredeterminedtheresultingthee-approximatenetwork.

algorithmis

项目进度管理

22P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±41

beenPriority-rulemethodsfor jtempjgmaxhaveandandZhandevised[140],andBrinkmanntestedbyZhan[201],NeumanncontainsFranckandNeumann[70]and(theNeumannlastreference[26],approachesthesequentialhavemostturnedrecentoutresults).toTwodi erentoneordirectmethodschedulesbeexpedient.theactivitiesThestructuresafteranothertractionofthenetworkwithoutconsideringseparately.ThethecycleTheorem.methodminedFirst,againafeasibleexploitstheDecompositioncon-structureforeachcyclestructure.subscheduleSecond,eachisdeter-cyclerespectively,isreplaceddependent)withappropriatebyasinglenodeoractivity,schedulewithoutforresourcetheusage.durationThird,aandfeasible(time-schedulecyclesisresultingcomputed.``contracted''Fourth,anetworkfeasibleusingthetheforschedulestheoriginalforthecontractednetworkisdeterminedwork,Toindividualathe®ndcontractedafeasiblecyclestructures.

networkandnetwork,scheduleor(foracyclethewholestructure),net-haveserialprioritybeenandbest.rules,developed.aparallelschedulegenerationschemetheLSTAmongrulehasaturnedlargenumberofalwaysThatis,theactivitytobescheduledouttobewithscheduled)respectan``eligible''activity(allofitspredecessorsnextisTogenerationtakemaximumwithtostrictsmallestordertimelatest0havealreadybeenlagsstartintoaccount,time(cf.[70]).bothprocessfeasiblewhichschemesexceedsstarttimeisasoffollows:containabackwardschedulingtheactivityIfthejearliesttoresource-someactivitymaximumthelatestpossibletimelagstartdmax

time,theofbestartjinducedscheduledtimeby

ofscheduled)i(andhasofsomeadditionalij

activitiesalreadyuponAnresources120experimentaltobeenlargedappropriately.

instancesperformanceanalysisbasedprovidedeach(generatedwith500byactivitiesProGen/max)and®vehasThetruncatedpriority-rulethefollowingmethodsmainareresultsmuch(cf.[142,174]):the2thes,directbranch-and-boundfasterthantherespectively,andcontractionprocedures.Whereasofcomputingmethodstimeperrequireinstance1andcompositionaverage(usingaPCPentium200),thede-onalmost1m.methodThedecompositionasslowestheuristicandcontraction

requiresmethods,rem,(6%)providewhichfeasibleexploit(optimal)theDecompositionschedulesforTheo-instances,and98%thewhere(4%),therespectively,ofallsolvable100%boundprojectdurationcomputedaveragerelativefromthedeviationbestlowerofsolvemethodmuchisaroundlessinstances5%.Thetoremainingheuristicsmality(theonly®ltered53%),beambutsearchmorefeasibilityinstances(thetechniquetodirect62%).opti-7.Nonregularobjectivefunctions

gTheobjectivecreasingdiscussedtheintheinfunctioncompletionSection6ofisproblem jtempjmaxtimesregular,ofactivitiesi.e.nonde-tion,casetiveminimumfunctionswedealofawithminimizationproblem).Inthissec-(inwheretwowekindsagainofnonregularobjec-given.representsIftheandmaximumstart±startassumetimethatlagsgeneralaresourcesomeobjectivemeasurefunctionofthetovariationbeminimizedproblemutilization,jectivetheprojectfunction.Inthewespeakofaresourcelevelingofre-whichrepresentsnetpresentvalueproblem,theob-istobemaximized.thenetpresentvalueof7.1.Model

In jtempadditiontothetemporalconstraints(5)ofproject jPjg max ,,weexplicitlyrequirethat 0 0YjPZproblemInthedurationandPthereZisaprescribedmaximumP0withPd0Yn 1.cost objectivejtempfunctionj

oftheresourcelevelingkf rk Yt bestatedperunitofresourcek.Thisproblem, kb0canisthenthemin

asfollows:

kf rk Yt 9 kPR

sXtX jÀ iPdij iYj PiY

0 0Y

n 1Td

"Y 10

jPZP0jP Yrk Yt T kYkPRY

t 0Y1YFFFYd

"À1X 11

项目进度管理

P.Bruckeretal./EuropeanJournalofOperationalResearch112(1999)3±4123

IntypesNeumannofobjectiveandfunctionsZimmermann(9)are[141,142],considered.threeIff rk Yt

t 0Y1YFFFYÀ1

rk Yt Y 12

wenotedspeakusedbyof thejtempresourcej investmentproblemde-kmaxrk Yt bewherepurchased.inpracticeAwhen,whichissecondexpensivetypeofobjectiveresourcesfunctionhavetof rk Yt

1 rk Yt À k

13

t 0

measuressource kfromthedeviationoftheutilizationkP0. kmayaconsumptionofre-

betargetequalvaluetotheforaverageresourceresourceusagereplacedjP rjkpja FFF infunctionbywherejFFFjor FFF 2.AthirdtypeEq.(13)ofobjectivecanbef rk Yt

rk Yt Àrk YtÀ1

14

t 0

withtionforofrk YÀ1 rk Y 0considersthevaria-kindsexample,resourcereplacedofmanpower.ifutilizationthebyjFFFjorAgainresourcesover FFF 2 FFF representtimeandinEq.(14)di erentisused,

canbeentThefoundvaluesbasicofconceptsthecashof.

cash¯owsandnetpres-theinRussell[166]and¯owsHerroelenofaprojectetal.canbeproblemobjectivefunction Fofgthenetpresent[95].valueInj

per jtempj jb,bisthediscountrateactivityperiodpletionj,whichand Fisjthecash¯owassociatedwithpositivetimecurred).(paymentgassumedtooccuratthecom-j received)j pjofactivityornegativejand(costcanin-beformulatedThenetpresentvalueproblemcanthenbemax

asfollows:

FgP

jb

j

jsXtX 10 Y 11 7.2.Exactalgorithms

whetherAswiththereproblemisafeasible solutionjtempjgtomax ,jtesting

tempj

NP-complete. kf rk Yt or jtempj Fjbgj

isstrongly Forthe sourceYIjposedconstraintstempjnet Fjbgpresentvalueproblem

j

(11)),(thatDeis,Reyckthere[51]arehasnopro-re-O n4arecursivesearchprocedureproblem time.only ThisYIjalgorithmpre j generalizeswhichF

methodsrunsforin

jbgjmin

(thatGrinoldminimumtimelagsdij

pis,thereare

i)devisedbyHerroelen[78],dureetElmaghrabyandHerroelen[68],andtostartswithal.[93].theearliestDeReyck'sschedulerecursivei andproce-setsdelay®rstlyactivitiesjwith Ftriesj`0andsecondlypresentofconnectedactivitieswithnegativenetthevalueasfaraspossiblewithoutviolatingthetemporalmentalnetpresentconstraintsvalueof(10)theinproject.ordertoAnincreaseaverage,performancesolvedaninstanceanalysiswithhas100shownactivitiesthat,experi-onthe Forinthelessthan1susingaPCPentiumcan60.bebranch-and-boundjtempj general Fjbg,DenetReyckpresent[51]valuehasdevisedproblemjDemethod,whichisbasedupona schedulingjtempReyck'sjgbranch-and-boundalgorithmformax,wheretheresource-unconstrainedobjectivecursivefunctionproblemsarewithsolvednetbypresentDevalueas Reyck'sexperimentalprocedurefor YIjtempj Fjgre-jwithshownupto50performanceactivitiesandanalysis®vewithinstancesb.Anmethodthat,fectivenessforprocedureand injprinciple,temp theFgbranch-and-boundresourceshasj

e ciencyj jasbthehasthesameef- similar Ffor jtempjgcorrespondingmax.For jpre jjbgj

,Icmeli c[98]haveproposedatroducesbranch-and-boundandErengu

solveadditionalprecedencealgorithm,constraintswhichtoin-re-and-boundresourcecon¯ictsinanalogytotheHerroelenFor[48]procedurebyDemeulemeesterbranch-andexact f rtheresourcefor levelingjpre jproblemgmax.

YIjpre jkk Ytprogramming,algorithms withspecialobjectivefunctions,beenorbaseddynamicuponenumeration,programmingintegeret al.proposed[7],andbyAhuja[2],Easa[62],Bandellonihave YounisbasedYIjtempbranch-and-boundj andSaad[200].Forkf rk Yt procedure,atime-windowhasbeen

本文来源：https://www.bwwdw.com/article/mw7j.html