模糊环境中工作流任务分配的多级模型

ISSN100021239PCN1121777PTPJournalofComputerResearchandDevelopment44(2):302309,2007:2005-11-26;:2006-05-16(310027)(xiaozj1976@1631com)AMultilevelModelofTaskAssignmentinFuzzySituationsofWorkflowXiaoZhengjin,HeQinming,andChenQi(CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027)AbstractTheautomaticassignmentofusertaskisakeytechnologyforincreasingtherunningefficiencyofworkflowmanagementsystem1Workflowenginesarealwaysobligedtoassessacomplexandconfusingsitu2ation,identifythecomplexrelationshipofcandidatesandtasks,decidetoassignaspecialtasktothemostappropriatecandidates,andensureworkflowsystemexecutesefficiently1Theeffectivenessdependslargelyontheevaluationoftheinfluencingfactors1Aftersystematicallyanalyzingtheinfluencingfactorsandtheirlinguisticfuzzinessofusertaskassignment,asectionalmultilevelmodeloftaskassignmentandataskas2signmentmethodcorrespondingtothemultilevelmodelareputforward1Furthermore,thedesignmethodofalladaptiveweightingfactorsinthetaskassignmentmodelisalsodiscussedbriefly1Finally,theperfor2manceofthemultilevelmodelfortaskassignmentisgivenbycomparingthesimulationresultofthemulti2levelmodelandothertwotaskassignmentmethods1Keywordsworkflow;taskassignment;fuzzytheory1,,1,,1;;TP3111,,[1]1,[2]1,,1,:1[324],1Aalst[5],;[6],;,Petri[7]11,1[2],1,,,,018,11LiangWang,,[8]1YaakobLiang[9],,,1Shen(multi2criterataskassignment,MCTA)[10],,,1Shen,,(multilevelmodeloftaskassignment,MM2TA),11,1,:,,,,1,,,11,1,,,1:,,1,,,11,,,1,1,,,,11:Fig11Thefactorsaffectthetaskassignmentandtheirre2lations11,,Zadeh[11],11,112211Dubois(linguisticvariable)[12]1ŽA=(l,m,r),ŽAŽA(x):R(0,1)xŽA1ŽA(x):303:ŽA(x)=(x-1)P(m-1),1xm,(r-x)P(r-m),mxr,0,1(1)ŽA1=(l1,m1,r1),ŽA2=(l2,m2,r2),k1::ŽA1©ŽA2=(l1+l2,m1+m2,r1+r2)1:ŽA1ŽA2=(l1-l2,m1-m2,r1-r2)1:ŽA1ªŽA2=(l1l2,m1m2,r1r2),kªŽA1=(kl1,km1,kr1)1:ŽA1§ŽA2=(l1Pr2,m1Pm2,r1Pl2),,l20,m20,r201,,,,1(bestnon2fuzzyperformancevalue,BNP)1(cen2terofarea,COA)BNP,1ŽA=(l,m,r)BNP:BNP=l+(m-l+r-l)P31(2)BNP,,1212:,;,11,,,,15,,(0,0,011),(0,013,015),(013,015,017),(015,017,019),(017,019,1)1215,,15,,1Fig12Themembershipfunctionoflinguisticvaluescapability125,,(0,0,0),(0,012,014),(012,014,016),(014,016,018),(016,018,1)1,3121,,,,:Ba,B‰B=(a,a,a)133111111Jnew,Jnewk(Ct,t=1,,k),Ctw(Jnew,Ct),wimp,wkind,m(1),m1,wcoo11JnewU={U1,,Un},1,313(3):‰S(Ui,Jnew)=˜WŽD5n1(3)4032007,44(2)Fig13Multilevelmodeloftaskassignment13(3),˜W=(wcap,wexp,wrel,wload,wflex)351ŽD5n51,ŽD5n1,(3)Ui‰S(Ui,Jnew)(2)BNP,BNP,JnewBNP1,1m1,,[10],,mJnew‰S(team,Jnew)=wcoopªq,pr(Uq,Up)m(m-1)P2+mi=1‰S(Ui,Jnew)1(4)nCmn,(4)Cmn‰S(team,Jnew)BNP,JnewBNP1wcoop=wcoo13,,5,131231,1UiCth(Ui,Ct)1Ui,Jnew‰Scap(Ui,Jnew)(5)‰Scap(Ui,Jnew):‰Scap(Ui,Jnew)=1kkt=1[h(Ui,Ct)ªw(Jnew,Ct)]1(5)UiJnew,Ui,Ui,Ui1JjUij(Ui),JjCtw(Jj,Ct)1JjCtJnewCt,Ct,UiJjJnew,11JjCtJnewCt,Ct,UiJjJneww(Jj,Ct)w(Jnew,Ct),01,w(Jnew,Ct)=(l1,m1,r1),w(Jj,Ct)=(l2,m2,r2),Ct,UiJjJnews(Jj,Jnew,Ct)s(Jj,Jnew,Ct)=1,rll2,min(w(Jj,Ct),w(Jnew,Ct))max(w(Jj,Ct),w(Jnew,Ct)),otherwise0,r2l11,(6)UiJjJnews(Jj,Jnew)s(Jj,Jnew)=1kkt=1s(Jj,Jnew,Ct)1(7)Uiz,UiJnew‰Sexp(Ui)503:‰Sexp(Ui)=1zªzj=1s(Jj,Jnew)1(8)n,Ui‰Sexp(Ui,Jnew)‰Sexp(Ui,Jnew)=‰Sexp(Ui)Pni=1‰Sexp(Ui)1(9),Uitci,sci,s-=1nni=1si,tc=1nni=1tci1‰Srel(Ui)(10):‰Srel(Ui)=si,tcitc,(min(s-,si),si,max(si,s-)),tcitc1(10),,1Jj,1Uil,UiŽLoad(Ui)=1j=1ŽTaver(Ui,Jj),(11)ŽTaver(Ui,Jj)UiJj,1ŽLoad(Ui),Ui‰Sload(Ui),‰Sload(Ui)Ui:‰Sload(Ui)=nj=1ŽL(Uj)-ŽLoad(Ui)nj=1ŽLoad(Uj)1(12)Uir(Ui),Ui,‰Sload(Ui),Ui‰Sflex(Ui)(13),‰Sflex(Ui)Ui:‰Sflex(Ui)=nj=1r(Uj)-r(Ui)nj=1r(Uj)1(13)313(5)(13),,1,,,,1wcapability=wimp,wreliability=wimp,wexperience=wkind1,,,,,,,1,,,,,;,,,1,,,1U={U1,,Un},UiŽLoad(Ui)(11)1,wload(14):wload=wimpnni=1ŽLoad(Ui)-1nni=1ŽLoad(Ui)1(14),wload,(12),1,,(12)‰Sload(Ui),,,,(14)wload,1,,,,,,wflex,1,:wflex=min(1Pwload,1)1(15)6032007,44(2)4,MMTA,MCTARound2Robin,31:4,C1T2013,T301711P,T2T3,(FIFO),1Fig14Theworkflowmodeloftest14T2,T3A,B,C1T2T3311T2,T31,13T2,T321Table1CapabilityRequirementsofTasksandSkillLevelofCandidates1CapabilityRequirementsTaskT2TaskT3LevelofSkillCandidateACandidateBCandidateCwriteextremelynowritenormalgoodexpertcomputebarelyextremelycomputeexpertgoodlowprojectmoderatelyextremelyprojectexpertnormalnormaldesignverybarelydesigngoodnormalnormalTable2TheIncidenceofSuccessandTime2ConsumingofCandidatesforTasks2CandidatesTime2ConsumingIncidenceofSuccessTaskT2TaskT3TaskT2TaskT3CandidateA5301930199CandidateB6701920190CandidateC7801990160,MMTA,MCTARound2Robin5113:Table3ThePerformanceIndexofThreeAlgorithms3AlgorithmsOverallIncidenceofSuccessIncidenceofSuccessforImportanceTaskAverageCompleteTimeofTasksMMTA0197701980315100MCTA0197701989390104Round2Robin0187901851501187Round2Robin1T2,T3,C,A,B1,,,1MCTA,,1T3C,T3100%C,T370%,CAB,T31MMTA,,1A1AT3,13,3,Round2Robin,,T31MCTAMMTA,MMTA1MCTARound2Robin1MCTA,,MCTA1MMTA,1703:Fig15Thecandidatesloadofthethreetaskassignmentalgorithms1(a)ThecandidatesloadofthetaskassignmentalgorithmRound2Robin;(b)ThecandidatesloadofthetaskassignmentalgorithmMCTA;and(c)Thecandidatesloadofthetaskassign2mentalgorithmMMTA151(a)Round2Robin;(b)MCTA;(c)MMTA,3,Round2RobinMCTA1,MMTA151,,,1,,1,,,