Genetic algorithms using multi-objectives

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

RoboticsandAutonomousSystems33(2000)

179–190

Geneticalgorithmsusingmulti-objectives

inamulti-agentsystem

AlainCardona,ThierryGalinhob,Jean-PhilippeVacherc,

b

LIP6ParisVI,UPMC,Case69,4,PlaceJussieu,75252ParisVI,France

LIH,InstitutSupérieurd’EtudesLogistiques,QuaiFrissard,BP1137,76063LeHavreCedex,FrancecLIH,InstitutUniversitairedeTechnologie,PlaceRobertSchuman,BP4006,76610LeHavre,France

Received1January1999;receivedinrevisedform1May1999;accepted1December1999

a

Abstract

Weareinterestedinajob-shopschedulingproblemcorrespondingtoanindustrialproblem.Ganttdiagram’soptimizationcanbeconsideredasanNP-dif cultproblem.Determininganoptimalsolutionisalmostimpossible,buttryingtoimprovethecurrentsolutionisawayofleadingtoabetterallocation.Thegoalistoreducethedelayinanexistingsolutionandtoobtainbetterschedulingattheendoftheplanning.

Weproposeanoriginalsolutionbasedongeneticalgorithmswhichallowstodetermineasetofgoodheuristicsforagivenbenchmark.Fromtheseresults,weproposeadynamicmodelbasedonthecontract-netprotocol.Thismodeldescribesawaytoobtainnewschedulingswithagentnegotiations.Weimplementtheagentparadigmonparallelmachines.

Afteradescriptionoftheproblemandthegeneticmethodweused,wepresentthebenchmarkcalculationsthathavebeenperformedonanSGIOrigin2000.Theinterpretationoftheseisawaytore neheuristicsgivenbyourevolutionprocessandawaytoconstrainouragentsbasedonthecontract-netprotocol.ThisdynamicmodelusingagentsisawaytosimulatethebehaviorofentitiesthataregoingtocollaboratetoimprovetheGanttdiagram.©2000ElsevierScienceB.V.Allrightsreserved.

Keywords:Job-shopschedulingproblem;Multi-objectivegeneticalgorithm;Multi-agentsystem;Contract-netprotocol

1.Introduction

Inthejob-shopschedulingproblem(JSSP),Ganttdiagram’soptimizationcanbeconsideredasanNP-dif cultproblem[10].Determininganoptimalsolutionisalmostimpossible,buttryingtoimprovethecurrentsolutionisawayofleadingtoabetterallocation.Multi-agentsystems[15]areoftenused

ExpandedversionofatalkpresentedattheSecondInterna-tionalSymposiumonIntelligentManufacturingSystems,IMS’98,SakaryaUniversity,Turkey,6–7August1998. Correspondingauthor.

E-mailaddresses:alain.cardon@lip6.fr(A.Cardon),thierry.galinho@univ-lehavre.fr(T.Galinho),jean-philippe.vacher@poleia.lip6.fr(J.-P.Vacher).

forsuchproblems,whereasolutionexistsbutisnoteasilycalculable[52–55].Weexpectsomesolutiontoemergefromsuchsituations,thatisthereasonwhyweusethem.Weusethemtosimulatethebehaviorofentitiesthataregoingtocollaboratetoaccom-plishactionsontheGanttdiagramsoastosolveagiveneconomicfunction.Theidealsolutiontosuchaproblemisapointwhereeachobjectivefunctioncorrespondstothebest(minimum)possiblevalue.WepresentourJSSP,whichisasimpli edversionofFISIAS[41].Wepresentsomeresultsbasedonge-neticalgorithms[50],thenwepresentanagentmodelbasedonthecontract-netprotocoltoimproveasolu-tioncorrespondingtoaGanttdiagram.

0921-8890/00/$–seefrontmatter©2000ElsevierScienceB.V.Allrightsreserved.PII:S0921-8890(00)00088-9

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

180A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

1.1.Job-shopschedulingproblem

Schedulingisanessentialfunctioninproductionmanagement.Itisadif cultproblemdependingonthenumberofcalculationsrequiredtoobtainaschedul-ingthatoptimizesthechosencriterion[37].Inaddi-tion,therearemanyschedulingproblemsandvariousapproachmethodshavebeenproposedtosolvesomepartsofthem.Wearegoingtode neourschedulingproblemanddescribesomeexistingproblemsaswellastheconstraintsthatweconsidered.

Amongvariousde nitionsoftheschedulingprob-lem,wecanhighlightacommondenominator:itisthetaskallocationwithaminimumcostandinareason-abletime.Weareinthe eldofdiscontinuousproduc-tionwiththeprocessingofsmallandaverageseries.Aschedulingproblemexists:

whenasetoftasks(jobs)istobeprocessed;

whenthisproblemcanbebrokenupintotasks(operations);

whentheproblemconsistsinthede nitionofthetemporaltasklocationand/orthemannertoallocatethemtothenecessaryresources.

Lamy[34]de nestheschedulingproblemofdiscon-tinuousproduction:“Theschedulingproblemoftheproductionconsistsinmanufacturingatthesametime,withthesameresources,asetofdifferentproducts.”Schedulingdetermineswhatisgoingtobemade,when,whereandwithwhatresources;givenaset

of

taskstoaccomplish,theschedulingproblemconsistsindeterminingwhatoperationshavetobeexecutedandingivingdatesandresourcesfortheseoperations.1.2.Ourjob-shopschedulingproblem

Schedulingandplanningaredif cultproblems[34,37]withalongandvariedhistoryintheareasofoperationalresearchandarti cialintelligence,andtheycontinuetobeactiveresearchareas.Theschedulingproblem,whichissubjecttoprecedenceandresourceconstraints,isanNP-dif cultproblem[13].Itisthusimpossibletoobtainanoptimalsolu-tionsatisfyingtherealtimeconstraint.

So,heuristicalgorithmsareusuallyimplementedtoobtaina“good”solutioninsteadofanoptimalone[34,50].Duetothenumberofvarietiesofproductionprocessesandtheincreasingrateofchangeinoper-ationalparameterscharacterizingthedatatobepro-cessed(capacitiesoftheresources,demands,etc.),itisbecomingmoreandmoredif cultformanagementboardstomakedecisions.

ThereasonthatwehavechosentheJSSPwithMmachinesandNjobsisbecauseitisthemostcom-plexandthemostoftenconsidered[10].Todeterminethequalityofthesolution,agraphicalinterfacehasbeendeveloped(Fig.1).Forourproblem,thegoalistheminimizationofdelaysandadvancesforalljobsaccordingtothe“duedates”givenbythemanager

Fig.1.GraphicalinterfaceusedforourJSSP.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190181

accordingtotheirobjectives.Thisobjectivehasbeenchosentoobtainsolutionsveryrapidlybecausecal-culationsareverynumerouswithgeneticalgorithms.Alsobecauseitissuf cienttocomparethesealgo-rithmswithothermethodssuchasthegradient,thesimulatedannealing,etc.Geneticalgorithmsenableustoobtainagoodqualitysolutionquicklyandeasilycomparedtootherresearchtechniques[20,26].2.Theselectionfunction

Wecannotusetheclassicselectionfunctionlikeamethodoftheroulettewheel,foritisproportional.Indeed,wewouldtakeanagentasaspeci centitybutwithouttakingintoaccountsomeexteriorpres-suresontheagent:itsenvironmentandthesystem’semergencephenomena.Therefore,theselectionfunc-tionshouldnotonlyconsidertheactionsoftheagent,whethertheseactionsaregoodorbad,butalsothecommunicationsbetweenagents.Wetalkaboutsenses(semanticorlink).Bysenses,wemean:

thesenseofcommunicationwiththeotheragents(networklinks);

thesemanticsofthecommunicationbetweentwoindividuals.

Therefore,ourcrossoverprocesshastotakeintoaccountthesemanticsofcommunication.Butanagent,seenasastructureisacompoundentitymadeofthefollowingelements:functionsofcommunica-tion,functionsofaction,functionsofbehavioralongwithalocalgeneticpatrimony.JustasevolutionaryalgorithmssimulateaDarwinianprocess,MAScansimulatetheevolutionofanucleusoragroupandbyextensionofanorganization.Asocialorganizationmaynotdiversifyandevolvebycloning:inallsocialorganizations(humanoranimal),wehaveacrossoverprocessthattendstopreservethenaturalinheritancebutalsotomakeitmorepowerful.Therefore,ourmulti-agentsystem,byintegratingthisnewconceptofreproductionwithcrossing,willhavetotakeintoaccounttheseparameters.Toachievethis,wecanuseageneticalgorithmswitchboard,asde nedbyHolland[26]oranevolutionarystrategyasde nedbyBäck[2].Bydoingthat,eachagent(individual)willbecharacterizedbyachainofbitswhoselengthwillcorrespondtoamultipleofthenumberofparam-eters.Thischainwillcorrespondtoachromosome

[54]thatwillrepresentthestructureoftheagent.Eachcharacter(action,behaviorandcommunication)composingtheagentwillcorrespondtonumericaldatareferringtorulesdatabase.Atoanaddressdatabase.Sincei,BknowledgejandCkwillreferisan“in nitedimension”,duetothefactthatanagentonlyhaslimitedknowledgeofitsenvironment,theformeronlyhas,apriori, niteknowledge.By niteknowledge,wesupposethatithasa nishednumberofactionsorknowledgeavailable.Especially,atthelevelofrulesofaction,ifonetakesthesetofplace-mentrulesdescribedbyPécuchetetal.[41],wehaveatmostnrules,thereforebyusingassignmenttech-niquescommonlyusedinelectronicandespeciallyintheassignmentmemory,wecanreserveacertainnumberofaddressescorrespondingtorules.There-fore,forabinaryrulecoding,wecanuseacodingon10bits;inthisway,itisalwayspossibletoincreasetheknowledgetothelevelofourdatabase.Neverthe-less,thesizeofourchromosomeisimportantinordertoreducethememoryspace.WeusethecodingofGray.Thus,wecanusegeneticalgorithmsonMAS.3.Themutationfunction

Themutationwillcorrespondtothechangeofabit,thus,wecanuseswitchboardoperators[17,22].Ourconstraintatthemutationlevel,consistsinhav-ingacorrespondencebetweenthebitsstringandthedatabase.Thus,bychangingthevalueofonebit,wecanintroduceanewcharacter.Thiswillhavearepercussionontheenvironment,butespeciallyonitsmembershiptoagroup.Thecommunicationsithasbeenabletohavewithotherelementsofthegroupwill,incontestably,bechanged.Forexample,considerthatthemutationintroducesacertainag-gressivenessattheagentlevel,thencommunicationswiththegrouparegoingtochangeandthegroupconsequently,willprobablylosesomeofitssocialcohesion.Thereforeinordertoavoidthetooabruptupsetofthesocialbalancethatcanexistbetweenin-dividualscomposingagroupandtheorganizationit-self,themutationinterventionsbygeneticalgorithmswillneedtobeweak.Nevertheless,wecanconsiderthatatthebeginningofthesimulationoftheorgani-zation,asatthebeginningofacivilization,progresswasrapidenough.Therefore,atthebeginning,wecanintroduceanimportantnumberofmutations.We

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

182A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

willuseasdistributionforthenumberofmutationbygeneration,acurveofparameters(α,β)

f:x→β

withβ∈R+andα∈R+ .

(1)Thus,byusingthistypeofdistribution,weintroducealotofmutationsatthebeginningofthesimulationandfewattheendinordertoavoiddisruptingtheprocessofevolutionbydeeplymodifyingcharacteristicsofchromosomes,andthereforeofindividuals.Toomanymutationsinthesystemswouldinexorablysowtheseedsofchaos.Wehavepreviouslyseenapossibledistribution.Nevertheless,byusingaGaussiandistri-butiontodeterminetheprobabilityofmutation,wekeeptheswitchboardofthegeneticalgorithm[39].4.Thecrossoveroperator

Fromanhistoricalpointofview,geneticalgorithms[27]correspondtoarandomphenomenon,butthemaindifferencecomparedtoaclassicrandommethodisthathere,weconverge,stepbysteptoanoptimum(localorglobal)inthespaceofsolutions[3].Thus,wearenotsubjecttochanceasweareintheformer,totallyrandommethod.A rstcrossingapproachwouldbetoconsideranagentasa“piechart”whereeachslicecorrespondstoacharacter.Byrandomlychoosingtwocutpointsinouragentcomparedtoareferential,wewouldexchangetwopartstoformnewindividuals.However,aproblemarises,astohowdowesetourreferential?Wecannotsetapermanentreferential,be-causeinthiscase,itsupposestoconsideranadjustableindividual.So,anagentisanentitythathasnofacets.Anagentiscomparabletoanindividualpartofanor-ganization.Nevertheless,itisnotpossibletodescribeitasaphysicalindividual(aman).Thereforethis rstapproachisinterestingbutdoesnotgivesatisfaction.Knowingthatnotallagentshavethesamegeneticpatrimony,thatistosaythattheyhavenoequalchro-mosomelengths,andknowingthatanagenthasnofacets,wecanrepresentitasatoroïdalchainofbits: Thisrepresentationdoesnotsupposetheinterven-tionofthenotionoffacetsofanagent.

Wecancrossindividualsofdifferentlengths[20].Itisalwaysnecessarytode neastartingpointforourchromosomeinordertocorrectlyexchangephe-notypes.Whichonedowechoose?Inoursystem,anagentiscomposedoffunctionsofaction,knowledge

andbehavior,thatmakeacertainnumberofpossi-blereferentials.Therefore,thechoiceofareferentialwouldbeaproblem,exceptbyrandomlychoosingit.Amongpossiblefunctions,whatdistributionwemustuse?Intheory,nodistributionisideal,nevertheless,tocontinuewiththiscirclescheme,wewilluseacir-cledistributionorGaussianmethodaccordingtotheprobability.Thus,itispossibletosetareferentialforthecrossing.However,theuseofasimplecrossingdoesnotalwaysgivegoodresults.Consequently,theuseofmultiplecrossingsallowsustomakeabiggermix.Wewillusetheuniformcrossovertoalwayshaveviableindividualsforourrepresentation.However,itisalwayspossibletousethecrossoversde nedbyGoldberg[20]suchastheCX,OXandthePMX[38],thatalwaysgiveviableindividuals.5.The tnessfunction

Inourcase,itisnecessaryforustooptimizeaGanttdiagram[43].Therefore,thelastoperationtoundertakewillhavetocorrespondtotheduedatemi-nuscompletiontime.Itisnecessary,thereforetomin-imizethedelayandtheadvanceofthesetofjobs.Theobjectivewithanadvanceandanulldelayisnearlyimpossible.Inageneralmanner,weallowacertaindelayoradvance.Whenwecalculatethe tnessofanagent,wedetermineitsimpactontheGantt[46].Ofcourseforthesetofjobs,wecanhaveadelayoraweakadvance.Consequently,wenolongerhaveasin-gle tnessfunctionbutmany.Wehaveasmanyobjec-tivesaswehavejobs.Consequently,wehaveacaseof“multi-objectivegeneticalgorithms”[44,45].Forthistypeofproblem,wewillusethebasicconceptsofthemulti-objectiveoptimizationproblem(MOP)[42].5.1.Basicconceptsandde nitions

Thefundamentaldifferencebetweenanoptimiza-tionhavingsimpleormultipleobjectivesisintheideaofthede nitionofanoptimalsolution.Theideaofoptimalityinthemulti-objectivecaseisanaturalex-tensionofwhatwehaveduringanoptimizationforauniqueobjective.

AnMOPcanbede nedasfollows:MOP:minx∈X

f(x),

wheref(x)=(f1(x),...,fn(x))(2)

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190183

isavectorofnrealvaluescomingfromobjectivefunctions,xisavectorofnvariablesofdecisionandX={x|x∈Rm,gk(x) 0,

k=1,...,m,andx∈S}

(3)

isasetofpossiblesolutions.gkisarealfunctionvaluerepresentingmthekthconstraintandSisasubsetofRrepresentingalltheotherformsofconstraints.Theidealsolutiontosuchaproblemisapointwhereeachobjectivefunctioncorrespondstothebest(minimum)possiblevalue.Theidealsolutioninmostcases,doesnotexistinviewofcontradictoryobjectivefunctionsandhencecompromiseshavetobemade.Adiffer-entconceptofoptimalityhastobeintroduced.Solv-inganMOPgenerallyrequirestheidenti cationofParetooptimalsolutions[33],aconceptintroducedbyV.Pareto,aprominentItalianeconomistattheendofthelastcentury.AsolutionissaidtobeParetoopti-mal,ornondominated,ifstartingfromthatpointinthedesignspace,thevalueofanyoftheobjectivefunctionscannotbeimprovedwithoutdeterioratingatleastoneoftheothers.AllpotentialsolutionstotheMOPcanthusbeclassi edintodominatedandnon-dominated(Paretooptimal)solutions,andthesetofnondominatedsolutionstoanMOPiscalledParetofront.The rstandmostimportantstepinsolvinganMOPisto ndthissetorarepresentativesubset.Af-terwardsthedecisionmaker’spreferencemaybeap-pliedtochoosethebestcompromisesolutionfromthegeneratedset.Thenaturalorderingofvectorval-uedquantitiesisbasicforParetooptimality.Tode nethenotionofdomination,letf=(fg=(g)betworeal-valuedvectors1,...,offnn)and1,...,gmele-ments:fispartiallysmallerthangif: i∈1,...,nand k∈1,...,m,fg,wei≤saygkand i|fthatfdominatesi≤gk,wenotef<pg.Iff<pg.Con-sequently,afeasiblesolutionx issaidtobeaParetooptimaloftheproblemifandonlyifanotherx∈Xdoesnotexistsuchthatf(x)<pf(x ).6.DevelopmentofParetooptimalsolutionsTwodifferentstrategiesareeffectiveingeneratingParetooptimalsolutions[12,16].Inthe rststrategy,anappropriatescalaroptimizationproblem(SOP)[42]isset-upinparametricform,sothatthesolutiontothe

SOPwithgivenvaluesoftheparameters,undercer-tainconditions,belongstotheParetofront;changingtheparametersoftheSOPleadsthesolutiontomoveonthefront.Inthesecondone,theMOPissolvedwithadirectapproachusingthedominancecriteria,sothatasetofParetooptimalsolutionsisdevelopedsimultaneously.Themainadvantageofthe rststrat-egyisthatSOPsaregenerally,verywell-studiedprob-lemsandmanyef cientmethodsareavailabletosolvethem.

6.1.EquivalentSOP1:TheweightingapproachFollowingtheweightingapproach[16],theMOP[42]ismadetocorrespondtothefollowingparametrizedSOP:P(w):minwT

f nx∈X

(x)=

wjfj(x),(4)

j=1

where

w∈W=

w|w∈Rn,wj(x) 0,

n j=1,...,nand

w

j=1j=1

,

(5)

thecorrespondencebetweentheMOPandtheSOPissubjecttosomerules.Ifx0isanoptimalsolutionofP(w0),thenitisalsoParetooptimalifoneofthetwofollowing0conditionsisveri ed:

xistheuniqueoptimalsolutiontoP(w0w0);isstrictlypositive.

ThisimpliesthatatleastsomeParetooptimalso-lutionscanbegeneratedbysolvingP(w)forsomeproperlychosenw,withoutanyhypothesisonthecon-vexityofXandf(X).Instead,someconvexityhy-pothesesareanecessitycondition.Therefore,ifbothXandf(X)areconvex,thenforanygivenParetoop-timalsolution,x ,itispossibleto ndaweightvectorw,notnecessarilyunique,suchthatx isasolutiontoP(w).Therefore,whentheseconvexityassumptionsareveri ed,allParetooptimalsolutionscan,inthe-ory,befoundbyvaryingwandsolvingP(w),whileiftheyarenotveri ed,someParetooptimalsolutionsmayneverbediscoveredbythisprocedure.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

184A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

6.2.EquivalentSOP2:TheconstraintapproachTheconstraintapproach[16,19]isbasedonthefol-lowingparametrizedminimumproblem:Pk( ):minx∈X

fk(x),

(6)

subjecttofj(x)≤ j,j=1,...,nandj=k,where =( 1,..., n)T∈Rnisthevectorofparameters.Themainadvantageofthisapproachisthatconvex-ityassumptionsarenotrequired.ThereforeallParetooptimalsolutionscanalwaysbediscoveredbysolv-ingtheconstraintproblemPtheMOPk( )foranyk.Thecorre-spondencebetweenandtheSOPissubjecttothe0followingrules.

IfxisanoptimalsolutionofPfeasible,thenk( 0x)0with 0avec-torforwhichPk( 0)isisanondomi-natedsolutionoftheMOP,ifoneofthetwofollowingconditionsoccurs:

x0isauniquesolutionofPk( 0)forsomegivenkbetween01andn.

xisnotunique,butsolvesP,n.

k( 0)foreachandeveryk=1,...Onthecontrary,ifx isanondominatedsolutionoftheMOP,an canalwaysbefoundsuchthatx istheoptimalsolutionofPkk( )for =1,...,nfor.Inallfact,i=this1,...condition,nwithiseachi=veri edandeveryk.wheni=fi(x )6.3.Resultsfromthegeneticalgorithm

Fromourobjectmodelization,ageneticalgorithmusingtheplacingmethodhasbeendeveloped[24,47].ThisprogramusestheC++languageinordertouseitonanSGIOrigin2000.Herearesomebenchmarks(seeTable1).

Asthecomputationaltimedependsonthecom-puterloading,thisrealtimedoesnotcorrespondto

Table1

BenchmarkresultsNumberofNumberofNumberofCalculationjobsoperationsmachinestime

1010450s

50549min,53s5010414min,27s100101040min,58s500

100

50

2h,24min,7

s

Fig.2.Dataextraction

software.

Fig.3.Tardinessasafunctionofthenumberofgenerations.

theCPUtime(Fig.2).Wecanthendetermineheuris-tics[8,9,24],tousewithourdynamicmodelbasedonthecontract-netprotocol[40,48].Anotherresultcomingfromthesimulationprocessisasetofgraphsgivingthetardinessandtheadvanceasafunctionofthenumberofgenerations.Wecanseethatthedelaydecreasesrapidly.Butitisnotnecessarytoincreasethenumberofgenerationstoobtainabetterresult(Fig.3).

6.4.Problemsencountered

Inourproblem,the rstlevelofmodelizationwasastaticmodel.Itdoesnottakeintoaccountthefactthatwehaveinteractionsbetweenmachinesandjobs.Ajobcanbedoneonlyiftheresourceisfree.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190185

Ontheotherhand,thestaticmodeldoesnotin-cludethepossibleinteractionbetweentheworkshopandtheenvironmentsuchasastrike,amachinefailure,etc.

Inthestaticmodel,theplacingobtainedgivesasolutioncorrespondingtothescheduleofalljobs.But,bynegotiations,theschedulecanbebuiltstepbystep.Forexample,ifajobarrivestoosoon,thedelaycorrespondingtothetardinessincreases.Therefore,ifwecanchangethescheduleduringthecalculationprocess,wecanimprovethetardiness.Itisoneofoureconomicfunctions.

7.ActionsontheGanttdiagram

TheJSSPdoesnotadmitacomputablesolution,sotheuseofmulti-agentsystemsforthesolvingofsuchaproblemseemsreasonable[23].Multi-agentsystemresearchisconcernedwiththebehaviorofasetofagentsthatcooperateinordertosolveaproblem[31].Inamulti-agentsystem(MAS)[11],theagentsareseenaslittleproblemsolversthatcooperativelyworkinordertosolveaproblem[58]farbeyondtheirin-dividualabilities[13].Here,weconsideranagentasanentitywithgoals,actionstoaccomplishandareasofknowledge,whichissituatedinitsenvironment[56].Therefore,becauseoftheknowledgeofagents,rulesofactions,etc.,theMASwillhave,forprinci-palobjective,togroupagentshavingsimilarbehavior[49]toelaboratestrategiestothejobslevel,jobsofjobs,machines,machinesofmachines,etc.Indeed,theproblemofcon ictsbetweenagentsisamajorconcerninMASresearch[4,30–32].TheobjectiveoftheMASistoimprovetheGanttdiagram[35,36],thereforeitleadsustoestablishthenotionofgroupcorrespondingtoelementaryentitieshavingcom-mongrindsandphysicalsameness(samecapacityofmachine,etc.)orinterdependence.

WewillusethenotionofzonefortheroundupofentitiesontheGanttdiagram,whilewewillspeakaboutthenotionofgroupfortheroundupofentitiesofsimilarorclosenature.Sinceagentshavetoin-terveneongroupsandelementaryentities,theMASwillthenbecomposedofmicro-andmeta-agents.Itisthereforeimportantforthisevolution,tointroduceagentshavinganevolvingcharacter:themeta-agentsofevolution.Thesemeta-agents’functionwillbetomakethisorganizationevolvebymeansofa

geneticalgorithmestablishingasexualreproductionofagents.Itisinterestingtonotethat,traditionally,agentsonlyclonethemselves.Buthere,weuseage-neticalgorithmforthephysicalevolutionoftheagents[28,29].Inthecourseoftheevolution,differentagentgranularitiesappear.Wehavethereforemicroandmeta-agentsthataregoingtointervene,accordingtotheirgranularity,onanentityoragroup,bypassingthroughintermediatelevels.Thus,agentshavingameta-knowledgearegoingtobeabletointerveneonthemacro-entities(groups)aswellasonsomezonesoftheGanttdiagram.Thus,thereisadistributedagentsystembeingabletomutateandhostingagentsabletoachieveacrossoverbasedreproductionbetweenthem.

8.Acontractnetbasedapproach

Thecontractnetisaprotocolfortheresolutionofdistributedproblem,de nedbySmith[48].Themainobjectiveofthisprotocolbeingthenegotiation,itpro-ceedsbyallocationoftaskstoasetofproblemsolversandusestheconceptofnegotiationtograntcontracts.Thebasicarchitecturecontainsnodeshavingachiefandcarryingroles[7].8.1.Thecontract-netprocotol

Contract-netbasedsystemsrepresentaconceptthatcanbeusedtoestablishmechanismsofcooper-ationbetweenagents[6].Acontractnetconsistsofanumberofnodesthatarerepresentedbyindivid-ualagents.Byanalogytoasalesession,suspendedsub-tasksareopenlyproposedtoauctionstowhicheachnodecanreplyaccordingtotheinterestthatithasforthissub-task.Thestageoftaskattributionrep-resentsaprocessinwhichallthenodes(agents)areassociated.Theideaistousetheavailableresourcesandtheexistingknowledgeofagentsasef cientlyaspossible[51];thatistosaybyallocationofonesub-tasktotheagentwhichisthemostapttooperateatagivenmoment.Thecontract-netprotocolformstheskeletonofoursystem.Itisde nedbyalan-guagebetweenthenodesthatcanbeunderstoodbythesetofagents.Thecommunicationbetweenagentsisalwaysbasedonthenotionofan“acceptancemessage”.Thisspeci cityde nestheexactroleofanagent.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

186A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

8.2.Thedifferenttypesofagents

Thelocaldatabasecontainsthebasicknowledgeoftheassociatednodesandalsoinformationonthepro-gressionstateofthecooperativenegotiationaswellasthestateoftheresolutionprocess[57].Thetaskofthecommunicationmanageristoestablishcommu-nicationswithotheragents.Itistheuniquecompo-nentofanodethatisindirectrelationshipwiththesystem.Especially,itensuresthereceptionandsendsmessages.

Thecontractmanager’sjobistoexaminethe“auctioned”task,thecompliancewiththecontractanditsending.Inotherwords,thecontractmanagerensuresthecoordinationofallagents[14].Thetaskadministratorisresponsiblefortheprogressmadeinaprocessandtheresultsofataskassignedtoagivenagent.Itreceivestheproblemthatneedstobesolvedfromthecontractmanager.Itusesthelocaldatabaseinorderto ndasolutionandgivesitbacktothecontractmanager.

Thejobofacontract-netbasedsystemoftenbeginswithaproblemdivisionstage[15].Afterthat,theprob-lemtobesolvedisdividedintoasetofsub-problems[25].Aspecialagent,themanager,assignstaskstoasub-problem.Themanagerissuesapublicoffer,calledacontractforeachsub-problemtobesolvedaccord-ingtotheschemede nedbySmith[48].

Becauseofthedistributednatureoftheproblem,wechoseanagentbasedmodelization,asimpli edversionofFISIAS[41].Thedifferentelementsoftheenvironment(theuniverse)canbethemachines(andgroupsofmachines),thejobs(andgroupsofjobs),theGanttdiagram(anattribute)anddistributoragentofjobs(DAJ)(Fig.4).Universeelementsarethe“objects”thatcanreceiveorsenddatatoagents.Machinescanbeseenasagentswhosetaskistoperformthejoboperationatagiventime.However,themachinecanalsobeseenasapurelyreactiveagent,which,accordingtothejob,canreply:“Icandoitornot”(Fig.5).

Then,wecanusethecontractnet(Fig.6)de nedbySmith[48],whosemanager,theDAJ,willproposetheallocationofajobtoamachinethroughtheuseofanegotiationagentdelegatedforthisjob(NA).Ac-cordingtotheinformationgivenbyamachine,theNAwillestablishacontractbetweenamachineMiandtheDAJ[5].ButtheDAJcanalwaysproposeajob

to

Fig.4.Representationoftheuniverse.

severalmachinestocreatesomecompetitionbetweenmachineagents.However,theDAJcanbreakthiscon-tractatanytimeiftheagentisunabletocomplywiththe

contract.

Fig.5.Firstrepresentationofthecontractnet.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

187

Fig.6.Representationofthecontract-netprotocolinanagent.

Amachinecanacceptmanycontractscorrespond-ingtothesamejob,butnegotiatedbydifferentNAswhichhavedifferentstrategies.Then,thecontractideologyis“thestrongestwins”sinceacontractcanbebrokenbybothpartners[21].However,wecanproposetwotypesofagents:aforwardplacingandabackwardplacingagent.Moreover,therearesomeworkshopconstraintssince,wehavegenericma-chines,groupsofmachinesandspecializedmachines.Wecanconsiderthatwehave“groupofmachines”agentswhichwillproposethedifferentjobsto

themachinestheyrepresent.Atthislevel,wecanoperateaparallelcomputationonthemachinesandso,ontheGanttdiagram(Fig.7).Nevertheless,forthemoment,weconsiderthattheDAJcanonlyprocessonejob.Anintermediateagentinchargeofchoosingthenum-berofjobscanbeproposed.Resultscorrespondingtothisapproacharegiveninthefollowingdiagram(Fig.8)whichgivesthevalueoftheeconomicfunc-tion(minimizationofthetardinessandtheadvance)accordingtothenumberofagentsandthenumberofgeneticoperationsusedbyagents.

9.GoingdeeplyintotherelationshipsofGAandMAS

TheuseofGAinMASisthebeginningofwhatcanbeaninterestingresearcharea.Thereareclearlytwokindsofapproaches,the rstiscentralized,inotherwords,someofthegeneticisoutsidetheagent.Thefunctionofselectionisagoodexampleofsuchfeatureout-of-the-agent[18,55].

However,webelievethatifonewantstocompletelymergetheGAandMAS(Fig.9),wemustmaketheagentacompletelyautonomousgeneticentity.Bythis,wemeanthatnotonlythegeneticpatrimonymustbe“onboard”butalsothefunctionsofselectionandcrossing.Anagentmustchoosewhichotheragentitwantstoreproducewith[55].Thelocationofthefunctionofmutationisnotclearlyknownsinceitis

Fig.7.Contract-netstructurebetweenthedifferentlevelrepresen-tations.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

188A.Cardonetal./RoboticsandAutonomousSystems33(2000)

179–190

Fig.8.Evolutionoftheeconomicfunctionaccordingtothenumberofagentsandthenumberofgenetic

operations.

causedbythepossibleexposuretoexternaleventsoriginatingintheenvironmentandduringthegeneticcodereplicationphase.

Ifwealsointroducethenotionofmotivatedbe-haviorforagents[5],wegodeeplyintoarti ciallifeproblematics.Thegeneticautonomyandthenotionofmotivationforanagentmayleadtoadrasticallynewkindofemergencephenomenon[1](differentso-cialbehavior,auto-referringevaluationprocess,etc.)inself-organizingMASs.Itiscertainlyadif culttaskbutitmaysowtheseedsofaproli capproachcon-cerningarti ciallife.10.Conclusion

Determininganoptimalsolutionisalmostimpos-sible,buttryingtoimproveanexistingsolutionisthewaytoimprovetaskallocation.Duringthesimulationprocess,agentsgranularityappearswiththemutationbehaviorintroducedbyGA[38].Attheendofthesimulation,communicationsbetweenglobalandlocal

Fig.9.MASandGAintheenvironment.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190189

agents,duetotheiractions,leadtotheappearanceofagentsofintermediategranularityandgeneralopti-mizationinproductionscheduling.Thiscommunica-tionre ectsthegeneticintegrationinanMAS.Thedistributedvisionofaschedulingproblemofjob-shopenablesustoreachamorerealisticvisionbecauseeachagenthasavisionofitsenvironment.Thatistosaythateachiscapableofreactingtoaparticularproblemjustlikeaforemaninhisworkshop.Heisgoingtoreactimmediatelyfollowingthebreakdownofamachine.Similarly,heisgoingtotakedecisions,asagents,thataregoingtohavearepercussionontheenvironment.Consequently,therepresentationbyanMASusingacontractnetisaclosevisionofre-alitythatcanbeeasilytransferredtoanindustrialorganization.

Researchcorrespondingtoouroriginaldynamicap-proachisinprogress.References

[1]W.R.Ashby,DesignforaBrain:TheOriginofAdaptive

Behavior,Chapman&Hall,London,1960.

[2]T.Bäck,Self-adaptationingeneticalgorithms,in:Proceedings

oftheFirstEuropeanConferenceonArti cialLife,MITPress,Cambridge,MA,1992,pp.263–271.

[3]R.K.Belew,L.B.Booker,in:ProceedingsoftheFourth

InternationalConferenceonGeneticAlgorithms,MorganKaufmann,SanMateo,CA,1991.

[4]A.H.Bond,L.Gasser,ReadingsinDistributedArti cial

Intelligence,MorganKaufman,SanMateo,CA,1988.

[5]A.Cardon,F.Lesage,Towardadaptiveinformationsystems:

consideringconcernandintentionality,in:ProceedingsoftheKAW’98,1998.

[6]A.Cardon,F.Lesage,Aninterpretationprocessof

communicationbetweenactorsinadistributedsystemforcrisismanagement,in:ProceedingsoftheSymposiumonInformaticsEconomics,1997.

[7]A.Cardon,S.Durand,Amodelofcrisismanagement

systemincludingmentalrepresentations,in:AAAISpringSymposium,StanfordUniversity,CA,1997.

[8]A.Cardon,J.-P.Vacher,RapportTechniquepourOuverture

deCompteauCrihansurMachineParallèleIlliac8,Crihan,1998,http://www.crihan.fr.

[9]A.Cardon,J.-P.Vacher,AlgorithmesGénétiquesdansun

SystèmeMulti-Agentspourl’Ordonnancement,Crihan,1998.[10]J.Carlier,P.Chretienne,Problèmesd’Ordonnancement

Modélisation/Complexité/Algorithmes,Masson,Paris,1988.[11]W.Chainbi,M.Jmaiel,B.Abdelmajid,Conception,

behaviouralsemanticsandformalspeci cationonmulti-agentsystems,in:ChengqiZhang,D.Lukose(Eds.),Multi-AgentSystems:Theories,LanguagesandApplications,Lecture

NotesinArti cialIntelligence,Vol.1544,ProceedingsoftheFourthAustralianWorkshoponDistributedArti cialIntelligence,Springer,Berlin,1998,pp.16–28.

[12]

V.Chankong,Y.Y.Haines,Multiobjectivedecisionmaking:theoryandmethodology,North-HollandSeriesinSystemScienceandEngineering,Vol.8,North-Holland,Amsterdam,1983.

[13]

E.H.Durfee,V.R.Lesser,Negotiatingtaskdecompositionandallocationusingpartialglobalplanning,in:L.Gasser,M.N.Huhns(Eds.),DistributedArti cialIntelligence,ResearchNotesinArti cialIntelligence,Pitman,London,1989,pp.229–243.

[14]D.McFarland,T.Bosser,IntelligentBehaviorinAnimalsandRobots,MITPress,Cambridge,MA,1993.

[15]J.Ferber,LesSystèmesMulti-agents,versuneIntelligenceCollective,InterEditions,Paris,1995.

[16]

C.M.Fonseca,P.J.Fleming,Geneticalgorithmsformultiobjectiveoptimization:Formulation,discussionandgeneralization,in:ProceedingsoftheFifthInternationalConferenceonGeneticAlgorithms,MorganKaufmann,SanMateo,CA,1993,pp.416–423.

[17]

S.Forrest,ProceedingsoftheFifthInternationalConferenceonGeneticAlgorithms,MorganKaufmann,SanMateo,CA,1993.

[18]

T.Galinho,A.Cardon,J.-P.Vacher,Geneticintegrationinamultiagentsystemforjob-shopscheduling,in:H.Coelho(Ed.),ProgressinArti cialIntelligence—IBERAMIA’98,LectureNotesinArti cialIntelligence,Vol.484,Springer,Berlin,1998,pp.76–87.

[19]

S.Gass,T.Saaty,Thecomputationalalgorithmfortheparametricobjectivefunction,NavalResearchLogisticsQuarterly2(1955)39–65.

[20]D.E.Goldberg,GeneticAlgorithmsinSearch,Optimization,andMachineLearning,Addison-Wesley,Reading,MA,1989.[21]

J.J.Grefenstette,LamarckianLearninginMulti-agentEnvironments,in:ProceedingsoftheFourthInternationalConferenceonGeneticAlgorithms,MorganKaufmann,SanMateo,CA,1991,pp.303–310.

[22]

J.J.Grefenstette,InternationalConferenceonGeneticAlgorithmsandTheirApplications,LawrenceErlbaumAssociates,Hillsdale,NJ,1985.

[23]

B.Hayes-Roth,A.Collinot,Asatisfyingcycleforreal-timereasoninginintelligentagents,in:ExpertSystemswithApplications,Hermes,Paris,1993,pp.31–42.

[24]

T.Haynes,Onlineadaptationofsearchviaknowledgereuse,in:J.R.Koza,K.Deb,M.Dorigo,D.B.Fogel,M.Garzon,H.Iba,R.L.Riolo(Eds.),GeneticProgramming,ProceedingsoftheSecondAnnualConference,MorganKaufmann,LosAltos,CA,1997,pp.156–161.

[25]T.D.Haynes,CollectiveAdaptation:TheSharingofBuildingBlocks,UniversityofTulsa,Tulsa,1998.

[26]J.H.Holland,AdaptationinNaturalandArti cialSystems,UniversityofMichiganPress,AnnArbor,MI,1975.

[27]

J.H.Holland,Adaptationinnaturalandarti cialsystems:Anintroductoryanalysiswithapplicationsinbiology,controlandarti cialintelligence,ComplexAdaptiveSystems,MITPress,Cambridge,MA,1992.

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

190A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

[28]IBMCorporation,IBMAgentBuildingEnvironment

Developer’sToolkit:User’sGuide,IBMIntelligentAgentCenterofCompetence,1997,/iag/iaghome.html.

[29]IBMCorporation,IBMAgentBuildingEnvironment

Developer’sToolkit:ComponentsandAdapterReference,IBMIntelligentAgentCenterofCompetence,1997.

[30]R.Jackendoff,SemanticsandCognition,MITPress,

Cambridge,MA,1983.

[31]N.R.Jennings,K.Sycara,M.Wooldridge,ARoadmap

ofAgentResearchandDevelopment,KluwerAcademicPublishers,Dordrecht,1998.

[32]P.Jorion,PrincipesdesSystèmesIntelligents,Masson,Paris,

1989.

[33]J.Koza,GeneticProgramming,MITPress,Cambridge,MA,

1992,pp.329–355.

[34]my,OrdonnancementetGestiondeProduction,Hermes,

Paris,1987.

[35]ngton,Arti cialLife,Proceedingsofan

InterdisciplinaryWorkshopontheSynthesisandSimulationofLivingSystems,LosAlamos,NM,September,1987,Addison-Wesley,RedwoodCity,CA,1989.

[36]J.LeMoigne,LaModélisationdesSystèmesComplexes,

Dunod,Paris,1990.

[37]K.Mesghouni,S.Hammadi,P.Borne,Productionjob-shop

schedulingusinggeneticalgorithms,in:ProceedingsoftheIEEE/SMC,Information,IntelligenceandSystems,Vol.2,1996,pp.1519–1524.

[38]Z.Michalewicz,GeneticAlgorithms+DataStructures=

EvolutionPrograms,Springer,Berlin,1992.

[39]H.Mühlenbein,Evolutionintimeandspace—theparallel

geneticalgorithm,in:G.Rawlins(Ed.),FoundationsofGeneticAlgorithms,MorganKaufmann,SanMateo,CA,1990,pp.316–338.

[40]N.Muscettola,S.Smith,Aprobabilisticframeworkfor

resource-constrainedmulti-agentplanning,in:ProceedingsoftheIJCAI-87,Milan,Italy,1987,pp.1063–1066.

[41]J.-P.Pécuchet,etal.,FISIAS,fastinteractivesystemfor

intelligentautomatedscheduling,RevueAutomatiqueetProductiqueAppliquées2(4)(1989)23–38.

[42]C.Poloni,HybridGAformultiobjectiveaerodynamicshape

optimisation,in:G.Winter,J.Périaux,M.Gálan,P.Cuesta(Eds.),GeneticAlgorithmsinEngineeringandComputerScience,Wiley,Chichester,UK,1995,pp.397–416.

[43]M.C.Portmann,Méthodesdedécompositionspatialeet

temporelleenordonnancementdeproduction,Doctoratd’Etat,Vol.1,UniversitédeNancy,1987.

[44]G.Rawlins,FoundationsofGeneticAlgorithms,Morgan

Kaufmann,SanMateo,CA,1991.

[45]J.D.Schaffer,Multipleobjectiveoptimizationwithvector

evaluatedgeneticalgorithm,in:ProceedingsoftheInternationalConferenceonGeneticAlgorithmsandtheirApplications,LawrenceErlbaumAssociates,Hillsdale,NJ,1985,pp.93–100.

[46]J.R.Searle,SpeechActs,CambridgeUniversityPress,

Cambridge,1969.

[47]G.Seront,Externalconceptsreuseingeneticprogramming,

in:E.V.Siegel,J.R.Koza(Eds.),WorkingNotesfortheAAAISymposiumonGeneticProgramming,AAAIPress,MenloPark,CA,1995,pp.94–98.

[48]R.G.Smith,Thecontractnetprotocol:High-level

communicationandcontrolinadistributedproblemsolver,IEEETransactionsonComputersC-2912(1980)1104–1113.[49]S.P.Stafford,Caringaboutknowledge:Theimportanceof

thelinkbetweenknowledgeandvalues,in:ProceedingsoftheAAAISpringSymposium,1997.

[50]J.Stender,E.Hillebrand,J.Kingdon,Geneticalgorithms

inoptimisation,simulationandmodelling,in:FrontiersinArti cialIntelligenceandApplications,Vol.23,IOSPress,Amsterdam,1994.

[51]E.Tzafestas,Versunesystémiquedesagentsautonomes:

Descellules,desmotivationsetdesperturbations,Thèsede

Doctorat,UniversiteParis´VI,1995.

[52]J.-P.Vacher,T.Galinho,Z.Mammeri,Uneapplicationdes

algorithmesgénétiquesàl’ordonnancementd’atelier,in:M.Itmi,J.-P.Pécuchet,H.Pierreval(Eds.),MOSIM’97,ActesdelaPremièreConférenceFrancophone,ModélisationetSimulationdesSystèmesdeProductionetdeLogistique,Hermes,Paris,1997,pp.43–50.

[53]J.-P.Vacher,A.Cardon,T.Galinho,Geneticalgorithmsin

amulti-agentsystem,in:ProceedingsoftheEUROGEN’97Conference,Trieste,Italy,1997,http://eurogen.cira.it.

[54]J.-P.Vacher,A.Cardon,T.Galinho,Heuristicsgranularityin

amulti-agentssystem(MAS):Applicationtotheproductionmanagement,in:ProceedingsoftheYOR10Conference,1998.

[55]J.-P.Vacher,A.Cardon,F.Lesage,T.Galinho,Genetic

algorithminamulti-agentsystem,in:ProceedingsoftheIEEEInternationalJointSymposiumonIntelligenceandSystems,IEEEPress,NewYork,1998.

[56]F.J.Varela,P.Bourgine,TowardsaPracticeofAutonomous

Systems,ProceedingsoftheFirstEuropeanConferenceonArti cialLife,MITPress,Cambridge,MA,1992.

[57]F.J.Varela,Organism,ameshworkofsel essselves,in:

ProceedingsoftheEast–WestSymposiumontheOriginsofLanguage,1996.

[58]R.Weyrauch,Buildingconsciousartifact,in:Consciousness,

DistinctionandRe exion,Bibliopolis,Napels,1995.

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