ATMS在基于约束的产品配置问题中的研究和应用

上海交通大学硕士学位论文ATMS在基于约束的产品配置问题中的研究和应用姓名：吴宇申请学位级别：硕士专业：计算机科学与技术指导教师：李小勇;蒋兴浩20070101-I-ATMSConstraintSatisfactionProblemCSPCSPCSPATMSdeKleerATMSATMSATMSCSPCSPATMSATMSATMSATMSB/SATMS-II-ATMSATMS-III-RESEARCHESANDAPPLICATIONSOFATMSINCONSTRAINTBASEDPRODUCTCONFIGURATIONPROBLEMABSTRACTConfrontedwiththetideofglobalizationandtheimpactofthepersonalbuyers'market,moreandmoreenterprisesrealizedthattoquicklyconfiguratetheproductssoastomeetthedifferentcustomerdemandsinthefastchangingmarketandwinmorecustomerswillbecomethefocusofthefuturecompetitionsbetweenenterprises.Thecoreoftheproductconfigurationproblemisthemethod;theconstraint-basedproductconfigurationmethodfocusesonthereaserchofCSP(ConstraintSatisfactionProblem).SinceCSPframeworkhastheadvantageofunspecializeddomainandsimpletouse,moreover,withitsmatureresolvingtechnology,itcomestobethewidelystudiedapproach.While,currentlythestudyofCSPisgenerallylimitedtoBinaryCSP,However,productconfigurationknowledgecontainsalotofnon-binaryconstraintinpracticeofproductconfiguration,andBinaryCSPcan’tdescribetheproductconstraintdirectlyandflexibly.Indeed,wecantransferthenon-binaryconstraintCSPtotheequivalentbinary-constriantone,buttherepresentedknowledgecannotbedescribeddirectlyandtheefficiencyofproblemsolvingwillbereducedduetotheprocessoftransmission,thustorestricttheapplicationsbasedonCSPproductconfigurationmethod.-IV-ATMS(Assumption-basedTruthMaintenanceSystem),theresearchfindingsofArtificialIntelligence,isinventedbydeKleerJ.theoretically,allthediscreteCSPcanbetransferedtotheproblemsolvedbyATMS,sothisthesisattempstosolvetheconstraint-basedproductconfigurationprobleminATMS,TheadvantageofATMSisthatit'smoreflexiblethanCSPwhendescribingproductconstraints,andmoreconsistentwiththeknowledgerepresentationofproductconfiguration.ThisthesisresearchesandanalizesthefeasibilityoftransferringCSPtosolvingproblemswithATMS,acorrespondingproblemsolverbasedonATMSisalsosetup,meanwile,thefeasiblityisverifiedbyusingtheself-developedATMSenginefromthepracticablepointofview.Combinedwithresearch,thethesisputsforwardakindofB/SstructuredproductionconfirgurationmodelwiththecoreofATMSengine,andmakesdetailedanalysisanddescriptiontothismodelfromthreeaspects:user'slayout,problemsolvingtransmission,andATMSknowledgemanagement.Thiskindofproductconfigurationmodelhasbeenappliedinthecomputerproductsconfiguration.Regardingsomekeyproblemsoccuredintheapplicationofproductconfirguration,thisthesisalsocreativelyproposesasplit-stitchandoptimizationtechnology.TheATMSbasedproductionconfigurationstudiedinthethesiscannotonlybeappliedinpersonalproductssalesine-businessbutalsocanbeappliedinmanufaturemanagementsystemoflarge-scalemodernenterprises.KEYWORDS:ConstraintSatisfactionProblem,ProductKnowledgerepresentation,Assumption-basedTruthMaintenanceSystem,ProductConfigurationModel200711820071182007118-1-1.1Configurableproduct1.1.1-2-1-11Figure1-1ConfigitCarOnline1-3-1-22Figure1-2ConfigitCarOnline2-4-1.1.2:1.:]3][2][1[]5][4[2.]6[3.:]9][8][7[-5-ifthen,]4[AB,,,,,ConstraintSatisfactionProblemCSP]11][10[1.1.3Gusgen199219941998FaltingsB.WeightlR]11[GelleE]10[1-3-6-1-3Figure1-3ProductConfigurationmodelbasedonConstraint-7-CSPP={X,D,C,U}X={1x,2x,…nx}DXDxi={di1,di2,…dim}C={c11S,c22S…cjSj}UCSPCSP1.1CSPTable1.1MappingbetweenProductConfigurationandCSPmodel1.-8-2.3.1.1.480R1/XCON]2][1[R1/XCONDEC-VAXR1/XCON6200]3[30.5DEC14000R1/XCON1.8080R1/XCONR1/XCONSiemens1985SICOMPSICONFEX]4[-9-R1/XCON2.8090R1/XCON600090ERPSAP]12[UCAIInternationalJointConferenceonArtificialIntelligenceWorkshoponConfigurationECAIEuropeanConferenceonArtificialIntelligenceWorkshoponConfiguration3.-10-1.2CSP]14][13][6[-11-ATMSdeKleer]56[ATMS]61[CSPATMSCSPATMSATMSATMSATMSATMSCSP,ATMSCSPATMSATMS1.CSPATMS2.ATMS3.ATMS4.ATMS5.ATMSB/S-12-1.3ATMSATMSCSP()ATMS()CSPATMSATMSATMS-ATMSATMSATMS-13-2.1ConstraintSatisfactoryProblem2.1.11805]15[-14-00180-15-]16[]17[CSPConstraintSatisfactionProblem]18][16[2.1.2]21][20][19][16[R={X,D,C}:1.XX={x1x2…xn}2.DXxi1≤i≤nxiDxixiDxi={di1,di2,…dim}dik1≤k≤mxixi-16-3.CC={c11S,c22S…cjSj}lSlc1≤l≤jlSlclSX⊆lSClSlclSXXIXICRXIRRCX2.1.3N]16[N460701975Waltz]22[23]24][23[]16[1975BitnerReingold-17-Backtrackingarcconsistency]26][25[pathconsistency]27][25[i-i-consistency]29][28[8090backmarking]30[backjumping]33][32][31[forwardchecking]36][35][34[NP-completeNP]37][17][16[]15[]39][38[-18-2.1.4]40[]41[]42[]43[]44[]45[]46[]47[2.1.5]16[2-1Figure2-1ConstraintDiagram-19-2.1.5.11.1-consistency]16[2.2-consistency]16[R={X,D,C}Cijcixjxixid∈ixDjxjd∈jxDidjdijcixjxijcixjxjxix-20-2-2ijcix:2-2Figure2-2ConsistentReviseProgrammingFrameworkkO2k]25[Mackworth1977AC1AC7AC1Arc-consistency-1AC1]25[2-3-21-2-3AC-1Figure2-3AC-1ProgrammingFrameworknke]25[O2ekOnkAC-1O3enk3.3-consistency]16[R={X,D,C}ixjxkxixjx(idjd)∈ijcid∈ixDjd∈jxDkxkd∈kxDidkdkdjdjdkdjkckdjdkjcixjxkdixjxkxixjxkx-22-2-42-4Figure2-4PathConsistentProgrammingFrameworkPC-1]25[path-consistency-1kn]25[O3kPC-1O2n2kO3nO3kPC-1O5n5kPC-1:-23-2-5PC-1Figure2-5PC-1ProgrammingFramework4.K–]16[,1−KK1−KKK–(1−K)–2−K-…NN–x11dN–x2x22d{1d,2d}{1d,2d,3d}{1d,2d,…nd}