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.