Dr.BoZhao,Prof.Dr.YushunFan
DepartmentofAutomation,TsinghuaUniversity
TsinghuaYuan,Beijing100084P.R.ChinaABSTRACT:UptodatemoreandmoreresearchofschedulinguseMulti-agentSystem(MAS)technique.InthispaperMASisusedtorealizeintegrationofschedulingalgorithms.Firstly,Multi-agentSchedulingSystem(MASS)isdividedintotwotypes:Entity-typeMASSandProcess-typeMASS.Someoftheresearchesareintroduced.Secondly,theconceptofintegrationofschedulingalgorithmsisputforward.Thirdly,themodelsofagents,computingagentandmanager,areproposed.ThenaProcess-typeMASSofmulti-agentbasedintegrationofschedulingalgorithms,whichcomposeabovetwosortsofagents,isbuilt.Finally,weconcludebydescribingthesignificanceofourresearchandhighlightingfutureextensions.
KEYWORDS:Scheduling,Multi-agentSystem,IntegrationofSchedulingAlgorithms,Multi-agentSchedulingSystem
1.Introduction
Algorithmisthekeyfortheschedulingtheory.Theprincipleofschedulingistofindanoptimalscenarioofjoballocationorresourcedistributionwithschedulingalgorithms.
Inthepastdecadesmanyalgorithmsoriginatedfromotherfieldshavebeenusedinschedulingresearchandthereforeformedtheso-calledschedulingalgorithms.Theseworkshaveenrichedschedulingtheory.However,anysinglealgorithmthatpeoplehaveusedsofarareonlyapplicabletoafewspecialenvironmentsandcannotadapttodynamicproductionenvironment.Thismakesschedulingalgorithmshavenotexertedalloftheirpowerinpracticalproduction.Itisoftenthecasethattheplanformulatedbyschedulingalgorithmsisdisabledbecauseofsomedisturbancesuchasmachinefailure,unexpectedjobscomingintoworkshop,materialshortage.Theinconsistencyofschedulingtheorywiththeschedulingpracticehasremainedabigissueinmanufacturing.
Tosolvetheproblemsonemaythinkoftwosolutions:
1)Findinganall-purposeschedulingalgorithmthatisapplicabletoalmostallsortsofschedulingcases.
2)Findingamechanismbywhichappropriatealgorithmsofschedulingalgorithmslibrarycanbecalleddynamicallyandintegratedrapidlytorespondtothechangeofproductionenvironment.
Unfortunatelythereisnoone-fits-allalgorithmthatmeetstherequirementofsolution1.Thepromisingandrecommendableapproachwouldbethelatter.ThepurposeofthispaperistofindsuchamechanismnamedIntegrationofSchedulingAlgorithms(ISA)anduseMAStechniquetorealizeit.
MAS(Multi-agentSystem)technique,whichisabranchofdistributeartificialintelligence,hasbeenregardedasoneofthemostpromisingapproachestosolveschedulingproblemsunderdynamicenvironmentsandhasattractedalotofattentionrecently.Inthispaper,theMAStechniqueisusedtorealizedynamicintegrationofschedulingalgorithm.Andthesolutionwillensureeithertheoreticalefficiencyoroperationrobustness.
Wemaycallaschedulingsystemthatusesmulti-agenttechniqueasMulti-agentSchedulingSystem(MASS).Byreviewingsomeimportantliteratures,wefindthatMASScanbedividedintotwotypes:
1)Entity-typeMASS
AgentsinsuchMASSmapphysicalentitiesinreal-lifesystemsasjobsandresources(machine,conveyance,storage,etc.).ThemajorfeatureofsuchMASSisthereciprocitybetweenresourceagentsandjobagents.Everyagenthasintentionofitself,goalandbenefit.Theyarecapableofself-advancementandself-control.Theycanalsobedistinguishedfromenvironmentalinformationandthentakeaction.Resourceagentsandjobagents,assupplierandcustomerinmarket,achievetheirmaximalbenefitsandsystemgoalsthroughnegotiationortransaction.
ResearchofEntity-typeMASSisveryplentiful.Linetal.[1]usedagentstoresponsefunctionsandentities(machine,job,database,etc.)ofmanufacturingsystemintheirframework.Andtheyusedmark-likemodeltorealizenegotiationamongagents.Ramos[2]alsoputforwardascenariothatcomposeofresourceagentsandjobagents.Gomesetal.[3]viewaMASSasanthreelevelorganization.Agentsaresigneddifferentrolesandfunctionsdependingontheirpositionwithinthestructureofthesystem.Agentsofthelowlevelareclassifiedresourceagentsandjobagents.Ouelhadjetal.[4]definedan“actor”architecturewhereagentsisassociatedwithparticularfunctionswhicharedistributedoverresourceagentsandusecontactnetprotocolfordynamicscheduling.Rabeloetal.[5]studiedmulti-agentbasedschedulinginvirtualenterpriseenvironmentsonthebaseofHOLOSschedulingsystem,whichisaframeworkdevotedtoderive“instance”ofagileschedulingsystem.
2)Process-typeMASS
PredominantagentsinsuchMASSarecalledprocessagents.Theymapprocessesthatrealizeafunction[6],acomputation[7],anactivity[8],etc.Eachprocessagentcanonlysolvepartofaproblem.Differentagentsworktogetherbycollaborationtoachievesystem’sgoal,aspeoplecomingfromdifferentfieldstoateamwilldo.
UnlikeEntity-typeMASSthatmainlycomposesofresourceagentsandjobagents,Process-typeMASShasnotypicalarchitecture.Thereismuchdifferenceamongresearchesofsuchsystembynow.Lau[6]definedaMASSforFMSscheduling,whichiscapableofindividuallearningandgrouplearning.Agentsinthesystemareschedulingmodelsthathaveabilityofpredictiveschedulingandmakingreactiontowardenvironmentorotheragents.Morikawaetal.[7]useagentmapsgeneticalgorithminhisresearchofschedulinginprocessofCIM.Thewholeprocessofsolvingproblemisdividedintoseveralstages.Eachagentresponsesonestage.Theyworkonebyone.Oneagentgetsinputfromupriveragentsandoutputresulttodownriveragents.GaryKnotts[8]presentamulti-agentschedulingmethodtosolvemultimode,resource-constrainedprojectschedulingproblem.Agentsmapactivitiesofproject.
Baker[9]reviewedmostschedulingalgorithmsandprovedthattheycanbeusedintomulti-agentheterarchy.Soweconsidertointegratingmoreschedulingalgorithmsintooneframeworktoadaptrequirementofcomplicatedproductionenvironmentbydefiningaprocess-typeMASS.Theagentsinourarchitecturemapschedulingalgorithms.
Therestofthepaperisorganizedasfollow.Insection2,weintroduceconceptofintegrationofschedulingalgorithms.Insection3,wedetailthesolutionofmulti-agentbasedintegrationofschedulingalgorithms.Inthelastsection,weconcludebydescribingthesignificanceofourresearchandhighlightingfutureextensions.
2.INTEGRATIONOFSCHEDULINGALGORITHMS
Differentschedulingalgorithmshavetheirownfeatureandusingconditionorarea.Asunits,theircapabilitiesarelimited.Buttheycanbeusedtosolvecomplexschedulingproblemifonlytheyarecombinedtogether.IntegrationofSchedulingAlgorithms(ISA)issuchaprocessormechanismofintegratingvariousschedulingalgorithmstogenerateasinglearchitecture,whichprocessmoreapplicability.
Tosomeextent,somemixedalgorithms,whicharecomposeofotheralgorithms,areparticularinstancesofISA.Butthesecombinationaresimpleandimmovable,andtheresult,whicharealsosinglealgorithm,isstilllimitedtosomespecialproductionenvironmentsandwearenotinterestedinithere.
ISAthatbedefinedhereisaflexibleandintelligentscenarioofcollaborationamongschedulingalgorithms.Itcandynamicallycallorjointdifferentalgorithmstogetherfordifferentenvironmentundervariousconditionsandconstraints.Eachalgorithm(wecallitatomicalgorithm)joiningthescenarioisindependent.
TherearetwocasesofISA.Oneisthatatomicalgorithmsstoreinasystemaredynamicallycalledtoresponsethechangeofenvironments.Theotheristhatschedulingproblemisdividedintoseveralsubproblems.Eachsubproblemisslovedbyoneatomicalgorithm.Thewholeproblemissolvedbydynamiccollaborationofseveralatomicalgorithms.
Wemaydesignanintelligentsystemthatconsistsofarulebase,analgorithmbase,areasonmachineandothercomponents.Therulebasestoresknowledgeofusingalgorithm.Thealgorithmbasestoresallsortsofschedulingalgorithms.Thesystemcanmakeestimationinreasonmachineandselectagoodalgorithmfromalgorithmbaseaccordingtorulesfromrulebase.Theoreticallyitcansolveanycomplexschedulingproblem.Butitsefficiencyishardtoensurebecausewehavetoomanyalgorithmsandrulesofhowtousethesealgorithms.Toretrieverulesandalgorithmsneedverylongtime.
Then,ofcourse,wethinkofdistributedstructure.MASissurelyagoodarchitecturetohelprealizingISA.
3.MULTI-AGENTBASEDISA
Aschedulingalgorithmisaprocessofsolvingschedulingproblems.Theprocessneedstokeepcontactwiththeenvironment.Assembledwitharulebase,ananalysismodule,aninterface(tocontactwithoutside),andareasonmachine,etc.,aschedulingalgorithmcanbecharacterizedasanintelligentagent.Theagentcanmakedecisionsbasedontheresponsefromtheenvironmentandtakeaction(computation).Wenamethisagentcomputingagent.Thedynamicintegrationofschedulingalgorithmsistheintegrationofdifferentcomputingagentsundertheschedulingofamanager.
3.1DEFINITIONOFAGENTS
Awholecomputationconsistsofseveralsteps:environmentanalysis,goalsetting,evaluationofcomputationcapability,decisionmaking,computing,outputconclusion,etc.WeintegratedthesestepsintoageneralmodelofcomputingagentasFig.1
Elementsofacomputingagentaredetailedasfollow:
1)AlgorithmBase
Storesalgorithmsthatbelongtothesametype,e.g.schedulingrules.Eachalgorithmcanbeusedinsidetheagentaccordingtoconditionoftheirbeingused.Also,newalgorithmsbelongtothetypecanbeaddedin.
Infact,thecontentsinthebasemaybeinformationas:IDofanalgorithm,Input,etc.Itpointstoaprogramofanalgorithm.
2)RuleBase
Storesknowledgeofusingalgorithms:applicableconditions,capability,efficiency,etc.Newrulecanbeaddedinatanytime.
Therulesusetheformatof4-vector:(ID,Condition,Capability,Efficiency),thereinto:
lID:IDofthealgorithm;
lCondition:relationbetweenthealgorithmwithsomeschedulingmodels,i.e.ifthealgorithmcanuseinoneofalgorithms.
lCapability:degreeofoptimization.Itisarelativevalueofanalgorithmweselectasastandard.
lEfficiency:thetimeoffinishingcomputation.
3)Analyzer
Analyzesinformationfromthesensorandmakesdecisionofwhetherornotrespondingtotheinformation.
InformationfromsensorismainlyIDofschedulingmodel.ItthenbeusetoretrieveIDofalgorithmsinRuleBase.FindingasuitedIDofanalgorithmmeansagentscanresponsetheschedulingmodel.
4)ReasonMachine
IfthereareseveralalgorithmsintheAlgorithmsBasethataresuitedwiththeschedulingmodel,selectsthebestoneaccordingtocapabilityandefficiencyunderthesupportoftherulebase.
5)ComputingCell
Finishingcomputationwithselectedalgorithm.
6)Sensor
Receivesinformationsuchasjobs,resourcesandschedulingmodelsfromtheManagerandrespondswithbiddingornot.
7)Driver
Outputsresult.
Inordertoharmonizecomputingagents,weneedamanager.It’saspecialagentasshowninFig.2andisresponsibleforfollowingfunctions:
1)RegisterseachcomputingagentwithRegisterModelandstorestheirpropertiesinDatabase.
2)SearchesinformationfromenvironmentthroughtheSensorandtranslatesitintoappropriateschedulingmodelintheModelerunderthesupportoftheKnowledgeBase.
3)CommunicateswithcomputingagentsviaCommunicator.
4)RecordsandanalyzesmiddleresultinBlackboardandthenoutputsfinalresultviaDriver.
We’llpresentthereciprocitybetweenthemanagerandthecomputingagentsin3.2.
3.2SYSTEMARCHITECTURE
Thousandsofschedulingalgorithmshasbeenproposedsofar.Theseschedulingalgorithmscanbeclassifiedintoseveralcategories.ThehierarchyisshowninFig.3:
Ofcoursewecannotandneednotdesignagentsforeachalgorithm.Butwecandothatforeachclass.OursolutionistojointdifferentclassesofcomputingagentsintoaMASStorealizedynamicintegrationofschedulingalgorithms.Exceptforamanager,everynodeofthesystemisacomputingagent,whichprovidescongeneralgorithmsthatstoreinitsalgorithmbase.AstarlikearchitectureofthesystemisshowninFig.4.
Fig.4isonlyoneexampleofmulti-agentbasedintegrationofschedulingalgorithmssystem.WemaychooseeithertwoormorecomputingagentstobuildaMASSaccordingtotherequirementsofareal-lifeproductionsystem.Andcomputingagentscanbedistributed.Theyworkindependentlyandconcurrently.
Thesystemworksasfollow:
1)Themanagersearchesinformationfromtheenvironmentandtranslatesitintoaschedulingmodel.Thenitbroadcastsabidrequesttoallcomputingagentsandsendanexpressionoftheschedulingmodel;
2)Whenreceivingbid,computingagentsretrievetheirownRuleBase.Whetherornottherearerecordsconcerningwiththemodelmeanswhetherornottheagentshavecapabilitytosolvetheproblem.Accordingtotheircapabilities,thecomputingagentsdecidetobidornotandthensendmessagestothemanager.
3)Themanagermakesachoicefromcomputingagentswhomakethebidsandsendinformationtotheselectedagents.
4)Theselectedcomputingagentaccomplishesthetaskandoutputsitsresulttothemanager.
5)Ifthecurrentresultdoesnotfulfillsystem’sgoal,themanagerwillinviteanewpublicbid.
Sometimes,oneproblemcanbedividedintoseveralsubproblems.Thenmanagerwillsendbidstoseveralcomputingagentsconcurrently.Andsubproblemsaresolvedindependentlybycomputingagents.
Thecomputingagentintheabovescenariois“fat“.Facingrequirementofsomecases,WecanalsodesignaMASSof“thin”computingagent,i.e.computingagentsisrelativelysimple,e.g.itprovideonlyonealgorithm,notaalgorithmsbase.Anyway,theideaofbuildingMASSinthispaperisflexible.
4.Conclusion
Classicalschedulingtheoryisproblem-based.Itisdifficulttobeapplieddirectlytopracticesinceitsimplifiesthereal-lifeschedulingsystem,whichisusuallycomplexandcontainsseveralproblems.Whereas,inthispaper,weproposedamechanismnamedintegrationofschedulingalgorithmsandbuiltarchitectureofprocess-typeMASStosupportit.Themechanismissystem-based.Itcantakeintoaccountofthecomplexityofreal-lifesystemsandintegratealmostallofschedulingalgorithmsintoonesystemarchitectureandthenusethemdynamicallytoadapttothechangeofproductionenvironments.
Ifwelookuponthealgorithmresearchofclassicalschedulingtheoryasamicrocosmicworkforsimpleproblems,
thentheideadescribedhereisthesolutiontomacroscopicallyapplicationsforcomplexsystems.Furtherresearchwillbecarriedoutinthisaspectasfollow:
1)ResearchofMASSneedfullyutilizeresultsofclassicalschedulingtheoryandotherproductioncontroltechniques.
2)Thefunctionsofbothcomputingagentandmanagerinthispaperarebasicandrelativelysimple.Wewillexpendtheirfunctionsinnextwork.
3)Ingeneral,structureofagentisoftencomplexandneedlotsofworktodesign.Sowemaydevelopstandardmodelofsometypesofagent(suchascomputingagent,resourceagent,jobagentandetc.)onthebaseofcurrentresearch.Itwillmakereusingagenteasy.
4)Asweknow,itisunpracticaltodesigndirectlyauniversalsystemforscheduling.Butwecandynamicallyassembleschedulingsystemforreq
uirementsofpracticalproductionenvironmentwithstandardagentswhichresponsebasicelementsofenterprise.
References
[1]GraceYuh-jiunLin,JamesJ.Solberg.IntegratedshopfloorcontrolusingautonomousAgents.IIETransactions,Volume24,Number3,July1992:57-71
[2]CarlosRamos.AnArchitectureandanegotiationprotocolforthedynamicschedulingofmanufacturingsystems．Proceedings-IEEEInternationalConferenceonRoboticsandAutomationpt4May8-131994,SponsoredbyIEEE:3161-3166
[3]CarlaP.Gomes,AustinTate,LynThomas.Distributedschedulingframework．ProceedingsoftheInternationalConferenceonToolswithArtificialIntelligenceNov6-91994:49~55
[4]D.Ouelhadj,C.Hanachi,B.Bouzouia.Multi-agentsystemfordynamicschedulingandcontrolinmanufacturingcells.IEEEInternationalConferenceonRoboticsandAutomationv3May16-201998,SponsoredbyIEEE:2128-2133
[5]R.J.Rabelo,L.M.Camarinha-Matos.Multi-Agent-Basedagilescheduling.RoboticsandAutonomousSystems(1999)27,15-28
[6]RachelLau,JoelFavrel.Intelligentschedulingagentfordistributeddecision-making.Proceedingsofthe35thConferenceonDecisionandControl,Kobe,Japan,December,1996,SponsoredbyIEEE:3849-3850
[7]KojiMorikawa,TakeshiFuruhashi,YoshikiUchikawa.EvolutionofCIMsystemwithgeneticalgorithm.IEEEConferenceonEvolutionaryComputation-Proceedingsv/2Jun27-Jun29,1994,SponsoredbyIEEE:746-749
[8]GaryKnotts,MosheDror,BruceC.Hartman.Agent-basedprojectscheduling.IIETransactions(2000)32,387-401
[9]AlbertD.Baker.Surveyoffactorycontrolalgorithmsthatcanbeimplementedinamulti-agentheterarchy:Dispatching,scheduling,andpull.JournalofManufacturingSystemsv17n41998SME:297-320
