Resource-constrained project scheduling_ Notation, classific

项目进度管理

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