（计算机应用技术专业论文）迁移工作流系统中的动态适应性研究.pdf

山东大学博士学位论文 摘要 迁移工作流是将移动计算技术应用于工作流管理的一项新技术。与传统的 工作流模型不同，迁移工作流是一个或多个迁移实例在不同的工作位置之间不 断迁移，并按照自身携带的工作流说明，就地利用工作流服务协同完成任务的 过程。在迁移工作流系统中，工作位置是迁移实例的运行场所，它代表工作流 参与者为迁移实例提供安全运行环境和本地工作流服务，工作流服务既可以是 参与者的数据资源，也可以是参与者的业务活动或业务子过程。迁移实例是一 个以移动a g e n t 为范型的智能计算体，它既可以执行良好定义的结构化业务流 程，也可以处理不完善的工作流说明，后者不需要在工作流定义时为迁移实例 规划所有的活动及其转移关系，也不需要在工作流定义中为迁移实例描述所有 可达的工作位置、位置服务、服务规则和服务步骤。工作流说明可以首先基于 业务过程的起始信息进行部分定义，然后通过迁移实例执行期间的服务发现、 迁移决策及多迁移实例之间的协作进行过程扩展。因此，迁移工作流模型可以 大大提高工作流系统对业务过程及其执行环境的动态适应性，特别适合那些因 过程规则或执行环境多变而不能完整定义的跨地域、跨机构业务过程管理。 因此，关于迁移工作流中的动态适应性研究，就是提出动态适应性方法并 建立相应的工作机制，使迁移工作流系统能够在业务过程规则和工作流服务变 化时，预测、修正、扩展或重构自己的工作流程，以保证具有不完善工作流说 明特征的业务过程，在动态多变的工作流环境中仍然能够被正确执行。 迁移工作流中的动态适应性包括多个方面，本文结合国家自然基金课题“面 向目标的迁移工作流方法研究”，主要研究了迁移工作流中的过程动态适应性、 服务动态适应性和运行环境动态适应性问题。迁移工作流过程动态适应性研究 了迁移工作流系统面向目标的迁移决策能力，旨在通过服务发现和优化迁移路 径，处理不完善的工作流说明。迁移工作流服务动态性适应性研究了面向目标 和基于语义的工作流服务替换机制，旨在避免业务流程因服务不可用或发生变 化而中断。迁移工作流运行环境动态适应性研究了迁移实例的协同感知和协同 学习能力，旨在弥补迁移实例个体对运行环境变化认知的不足。本文完成的具 体工作如下： 山东大学博士学位论文 1 迁移工作流过程动态适应性研究。在迁移工作流中，由于工作流说明的 不完善，设计者在初始时没有为迁移实例规划好所有的工作位置，所 以要求迁移工作流系统能够根据过程的变化对旅行图作出相应的调整 与改变。迁移工作流过程包括业务活动依赖关系和迁移位置有序关系 两个方面。迁移工作流系统支持运行中对活动规划( 工作流说明) 和工作 位置规划( 旅行图) ，则系统具有过程动态适应性。文中第三章提出了关 于工作位置规划的迁移路径优化算法，该算法对基本遗传算法进行了 改进，提出了具有改进的e a x 算子和强化变异算子的改进的混合遗传 算法，通过实验对比论证了该算法在路径规划方面的性能优于一般启 发式方法。工作流引擎根据迁移决策方法动态调整工作位置，并以最 优的方案利用资源完成任务，该方法可以通过实例得到验证。通过对 迁移域中工作位置状态的判断，再结合优化算法可以实现对工作位置 的合理访问，保证迁移实例能够有效地适应不完善的工作流说明，提 高了处理业务流程自适应能力。 2 迁移工作流服务动态适应性研究。工作位置为迁移实例提供运行时服务 ( 例如迁入、迁出、安全保护等) 和工作流服务( 例如数据服务、工作项 服务、自动调用服务等) 。工作位置的逻辑故障异常主要指工作位置提 供的工作流服务发生了变化、服务不能按照计划进行或不能产生预期 的结果等。如果迁移工作流系统支持对工作位置的逻辑故障异常作出 反应和处理，则具有服务动态适应性。关于解决工作位置的逻辑故障 异常的方法，文中第四章提出一种服务本体替换机制，在系统运行期 间可以动态替换、调整那些出现异常的服务。服务本体替换机制用本 体描述工作流服务，若发生工作位置的逻辑故障异常则动态地发现可 以替代的服务来执行：如果工作流在运行时，某服务出现服务删除、 服务失效和服务操作超时异常等情况时，迁移实例可以使用新服务替 换异常服务，保证流程的继续运行。在该机制基础上本文给出了实现 方法。使用该机制，不仅可以实现服务发现的自动化还可以提高服务 发现的效率。该机制使得工作流程具有变化性，为了调整现有的某个 流程，不需要重新设计一个新流程，不仅对现有资源充分利用，更极 i i 山东大学博士学位论文 大地提高了工作流效率。 3 迁移工作流运行环境动态适应性研究。工作位置提供迁移实例的运行时 环境。通过运行环境，迁移实例能够获取当前工作位置能够提供的服 务列表，以及当前驻留在本工作位置的其他迁移实例的信息。工作位 置物理故障异常是指位置主机崩溃、网络断连等。如果迁移工作流系 统支持对工作位置物理故障异常作出反应和处理，则系统具有运行环 境动态适应性。由于异常现象造成迁移实例在运行环境中感知到的信 息是一些局部的不完全信息( 不确定的工作位置和服务) ，因此文中第五 章研究了在不确定环境下迁移实例的高效、动态和灵活的局部迁移路 径规划算法。迁移实例利用从环境中得到的不完全信息进行初步规划， 规划出自己针对当前环境的一个可行策略集，然后根据与其它迁移实 例的协作以及自己初步规划的策略集进步进行局部规划。迁移实例 在动态运行环境下的规划使得迁移实例的可以适应运行环境下的多种 变化，提高系统自适应能力。 本文工作的创新点主要体现在： 1 提出一种基于迁移路径优化算法的过程动态适应性方法。本文提出一种 路径优化算法r m g a ，该算法以t s p 为数学模型，是一种具有改进的 e a x 算子和强化变异算子的混合遗传算法，其中一个城市代表一个工 作位置。对t s p 实例的试验结果可以证明，r m g a 算法有更高的运行 效率和实际应用价值。这种适应性方法可以对工作流过程进行改进和调 整，使得系统具有灵活、动态地处理过程变更的能力。 2 提出一种基于工作流服务本体替换机制的服务动态适应性方法。本文结 合本体的概念提出迁移工作流服务本体替换机制，使工作流系统在无法 得到预定义的服务或资源时，可以寻找可替代的服务或资源继续执行。 该机制可以实现服务的自动发现和基于领域本体的服务的动态组合，在 领域本体的支持下，以概念相似度为基础，计算服务之间的关联度，然 后形成服务组合。 3 提出一种基于局部迁移路径规划算法的运行环境动态适应性方法。本文 以部分可观察的马尔可夫决策过程( p o m d p ) 作为迁移路线的规划模型， i i i 山东大学博士学位论文 提出一种局部迁移路径规划算法。通过求解不确定性的p o m d p 得到的 近似最优策略，使得工作流系统可以对工作位置物理故障异常进行反应 和处理，而不中断工作流的执行。同时给出多迁移实例的协作模型，在 求解过程中可以通过多个迁移实例协作完成迁移路径的规划。 本文的动态适应性方法在仿真实验中得到了充分的证明，但是迁移工作流 动态适应性是一个复杂的问题，因此很多方面还需要改进。本文进一步的主要 工作包括： 1 迁移工作流过程适应性中过程变更时的正确性的验证，只是依靠过程定 义中的验证工具对修改后模型进行验证，其粒度是不够的，在以后的工 作中，要进行多层次划分，尽可能的用多层验证来确保变更后模型的正 确性。 2 为迁移工作流服务适应性方法解决理论上存在的问题，探讨迁移工作流 服务变化的语义的和形式化表示方法等。下一步从应用实践中进行总结 和归纳，制定出一个丰富全面的服务变化分类体系。 3 从迁移工作流运行环境适应性实现的角度上，针对局部最小、反复路径 等问题，还需要进一步的研究。下一步的工作将在路径规划算法上进一 步改进。 在上述研究工作的基础上，我们期望能够对本文中讨论的一些实现方法进 行进一步的分析、比较和改进。 关键词：工作流管理：迁移工作流：动态适应性：规划算法；本体 山东大学博士学位论文 a b s t r a c t t h em i g r a t i n gw o r k f l o wi s8 1 e m e r g i n gt e c h n o l o g yf l a a ta p p l i e st h em o b i l e c o m p u t i n gp a r a d i g mt o w o r k f l o wm a n a g e m e n t d i f f e r e n tf r o mt h et r a d i t i o n a l w o r k f l o wm o d e l ，t h em i g r a t i n gw o r k f l o wi sap r o c e s si nw h i c ho n eo rm o r em i g r a t i n g i n s t a n c e sm i g r a t ec o n t i n u o u s l ya n dm i l i z el o c a lw o r k f l o ws e r v i c et oe x e c u t et h e i r t a s k s i nt h em i g r a t i n gw o r k f l o ws y s t e m , w o r k p l a c ei st h er t m n i n gl o c a t i o no f m i g r a t i n gi n s t a n c e s i tp r o v i d e ss a f er u n n i n ge n v i r o n m e n ta n dw o r k f l o ws e r v i c e sf o r m i g r a t i n gi n s t a n c e so nb e h a l fo ft h ew o r k f l o wp a r t i c i p a n t s w o r k f l o ws e r v i c e sa r en o t o n l yt h ed a t ar e s o u r c e so ft h ep a r t i c i p a n t sb u ta l s ot h e i rb u s i n e s sa c t i v i t yo rb u s i n e s s s u b - p r o c e s s am i g r a t i n gi n s t a n c ei st h eb u s i n e s sp r o c e s se x e c u t o r , w h i c hi sm o d e l e d f r o mad e f i n e dm o b i l ea g e n tp r o t o t y p e i tn o to n l ye x e c u t e sw e l l d e f i n e ds t r u c t u r e d b u s i n e s sp r o c e s s ，b u ta l s od e a l sw i t hi n c o m p l e t ew o r k f l o we x p l a n a t i o n t h ew o r k f l o w e x p l a n a t i o nn e e dn o tp l a na l lt h ea c t i v i t i e s ，t r a n s f e rr e l a t i o n sa n dd e s c r i b ea l lt h e a c c e s s i b l ew o r k p l a c e ，p l a c es e r v i c e s ，s e r v i c er u l e sa n ds e r v i c es t e p sf o rm i g r a t i n g i n s t a n c e s i n c o m p l e t ew o r k f l o we x p l a n a t i o nm a yb ep a r t l yd e f i n e db a s e do nt h e o r i g i n a li n f o r m a t i o no fb u s i n e s sp r o c e s s ，a n db ee x t e n d e db yt h es e r v i c ef i n d i n g ， m i g r a t i n gd e c i s i o n - m a k i n g a n d c o o p e r a t i o nb e t w e e nm i g r a t i n g i n s t a n c e s c o n s e q u e n t l yt h em i g r a t i n gw o r k f l o wm o d e lc a ng r e a t l ye n h a n c et h ed y n a m i c a d a p t a b i l i t yo fb u s i n e s sp r o c e s sa n de x e c u t a b l ee n v i r o n m e n t e s p e c i a l l y ，t h em o d e l a d a p t st ot h o s ei n c o m p l e t e l yd e f i n e db u s i n e s sp r o c e s sm a n a g e m e n to fm u l t i - t e r r a i n ， m h i o r g a n i z a t i o nc a u s e db yt h ed i v e r s ep r o c e s sr u l e so re x e c u t i n ge n v i r o n m e n t a c c o r d i n g l y , d y n a m i ca d a p t a b i l i t yo fm i g r a t i n gw o r k f l o wp r o v i d e st h ed y n a m i c a d a p t a b l em e t h o d sa n de s t a b l i s h e sc o r r e s p o n d i n gw o r km e c h a n i s mf o rm i g r a t i n g i n s t a n c e sa n dw o r k p l a c e s i tm a k e st h em i g r a t i n gw o r k f l o ws y s t e mt o f o r e c a s t , m o d i f ya n dr e - c o n s t r u c ti t sf l o ww h e nb u s i n e s sp r o c e s sr u l e sa n dw o r k f l o ws e r v i c e s a r ec h a n g e d t h u si te n s u r e st h a tt h eb u s i n e s sp r o c e s sw i t hi n c o m p l e t ee x p l a n a t i o n c a nb ee x e c u t e dc o r r e c t l yi nd y n a m i cw o r k f l o we n v i r o n m e n t t h e r ea r em a n ya s p e c t sa b o u td y n a m i ca d a p t a b i l i t yo fm i g r a t i n gw o r k f l o w t h i s v 山东大学博士学位论文 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! = ! ! = ! = ! 竺竺= = ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺竺 s t u d yi sm a i n l ys u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a u n d e r “r e s e a r c ho nt h em e t h o d so fm i g r a t i n gw o r k f l o wo b j e c to r i e n t e d t h e p r o c e s sd y n a m i ca d a p t a b i l i t y , s e r v i c ed y n a m i ca d a p t a b i l i t ya n dr u n n i n ge n v i r o n m e n t d y n a m i ca d a p t a b i l i t yo ft h em i g r a t i n gw o r k f l o wa r em a i n l yd i s c u s s e d f i r s t l y , t h e p r o c e s sd y n a m i ca d a p t a b i l i t ys t u d i e st h ed e c i s i o n - m a k i n ga b i l i t yo ft h em i g r a t i n g w o r k f l o ws y s t e mi no r d e rt od i s c o v e ra n do p t i m i z em i g r a t i n gr o u t ea n dd e a lw i t h i n c o m p l e t ew o r k f l o we x p l a n a t i o n s e c o n d l y , t h e s e r v i c ed y n a m i ca d a p t a b i l i t y f o c u s e so nt h es e r v i c es u b s t i t u t i o nm e c h a n i s mt h a ti so b je c ta n ds e m a n t i co r i e n t e di n o r d e rt oa v o i dh a l to ft h eb u s i n e s sp r o c e s sb e c a u s eo ft h eu n u s a b l eo rc h a n g e d s e r v i c e s l a s t l y , t h en m n i n g e n v i r o n m e n td y n a m i c a d a p t a b i l i t yp r o v i d e s t h e c o o p e r a t i v ea p p e r c e i v i n ga n dl e a r n i n gm e t h o do fm i g r a t i n gi n s t a n c e si n o r d e rt o m a k eu pt h ec o g n i t i v ed e f i c i e n c yo fe n v i r o n m e n t t h em a i nc o n t r i b u t i o n so ft h i s t h e s i sa r ed e s c r i b e da sf o l l o w s ： 1 r e s e a r c ho np r o c e s sd y n a m i ca d a p t a b i l i t yo fm i g r a t i n gw o r k f l o w i nt h e m i g r a t i n gw o r k f l o w , b e c a u s eo ft h ei n c o m p l e t ew o r k f l o we x p l a n a t i o n ，a l l t h ew o r k p l a c e st h a tm i g r a t i n gi n s t a n c en e e d sa r en o tp l a n e da tt h eb e g i n n i n g s ot h es y s t e mm u s ta d ju s ti t i n e r a r yg r a p ha c c o r d i n gt ot h et h ec h a n g eo ft h e p r o c e s s i ft h em i g r a t i n gw o r k f l o ws y s t e mi sp r o v i d ew i t ht h ea b i l i t yt h a t m a yp l a na c t i v i t i e sa n dw o r k p l a c e sd u r i n gf l o wr u n n i n g ，i th a sp r o c e s s d y n a m i ca d a p t a b i l i t y c h a p t e r 3 p r e s e n t s a no b je c t - o r i e n t e dm i g r a t i n g d e c i s i o n m a k i n gm e t h o d i m p r o v i n go nt h eb a s i cg e n e t i ca l g o r i t h m , t h i s m e t h o dp r o v i d e sa ni m p r o v e dh y b r i dg e n e t i ca l g o r i t h mw i t he n h a n c e de a x o p e r a t o ra n dr e i n f o r c e m e n tm u t a t i o no p e r a t o r l a r g ee x p e r i m e n t so nt s p i n s t a n c e ss h o wt h a tt h i sm e t h o do u t p e r f o r m so t h e rh e u r i s t i cm e t h o d si n r o u t ep l a n b a s e do nt h i sm e t h o d ，t h em i g r a t i n gi n s t a n c ec a nd y n a m i c a l l y a d j u s ti t sw o r k p l a c e sa n dc o m p l e t et h et a s kw i t ht h ee x c e l l e n tu s eo f r e s o u r c e s t h i sm e t h o di sv a l i d a t e di nt h ee n v i r o n m e n to fm i g r a t i n g w o r k f l o wa n ds h o w st h a tt h ew o r k p l a c em a yb er e a s o n a b l ea d j u s t e dt o e n h a n c et h es e l f - a d a p t a t i o na b i l i t yo fb u s i n e s sp r o c e s s 2 r e s e a r c ho ns e r v i c ed y n a m i ca d a p t a b i l i t yo fm i g r a t i n gw o r k f l o w t h e 山东大学博- & - 学位论文 w o r k p l a c ep r o v i d e sn m n i n gs e r v i c e ( s u c ha sm i g r a i n gi n ，瑚i 伊撕n go u t , s a f e t yp r o t e c t i o na n ds oo n ) a n dw o r k f l o ws e r v i c e ( s u c h 勰d a t as e r v i c e , a u t o m a t i c a l l yt r a n s f e rs e r v i c ea n ds oo n ) t h ew o r k p l a c el o g i ca b n o r m i t y m a i n l yd e n o t e st h a tt h ew o r k f l o ws e r v i c et h a tt h ew o r k p l a c ep r o v i d e si s c h a n g e d ，i sn o tc a r r i e dt h r o u g ha c c o r d i n gt oap l a no ri sn o tp r o d u c e d e x p e c t e dr e s u l t s t h ew o r k f l o ws e r v i c ed y n a m i ci st h a tw h e nas e r v i c ei s n o ta c c e s s e d c a s u a l l ya n o t h e re q u i v a l e n t s e r v i c em a yb ef o u n da n d s u b s t i t u t e dt oc o m p l e t et h es a m et a s k c h a p t e rgp r e s e n t sas e r v i c eo n t o l o g y s u b s t i t u t i o nm e c h a n i s mb a s e do nt h ed e s c r i p t i o no fo n t o l o g ya n dp r o v i d e sa f l e x i b l e m i g r a t i n gw o r k f l o ws y s t e mf r a m e w o r k w h e nt h em i g r a t i n g i n s t a n c ef i n d st h a tt h es e r v i c ei sc h a n g e d , i tm a yf i n ds u b s t i t u t e ds e r v i c et o e x e c u t e w h e ns e r v i c ed e l e t i o n ，s e r v i c ei n v a l i d a t i o n ，a n ds e r v i c eo v e r t i m e o rs e r v i c ea b n o r m i t ya p p e a r , t h em i g r a t i n gi n s t a n c em a ys u b s t i t u t ean e w s e r v i c ef o re x c e p t i o n a ls e r v i c et oe n s u r et h ec o n t i n u o u se x e c u t i o no f w o r k f l o w t h i sm e c h a n i s mm a k e st h ew o r k f l o wc h a n g e a b l e ，n a m e l yt h a tm o r d e rt oa d ju s tt h ee x i s t i n gf l o wi tn e e dn o tr e d e s i g nan e ww o r kf o l w t h u s t h er e s o u r c e sc a nb em a d et h eb e s tu s ea n dt h ew o r k f l o we f f i c i e n c yc a nb e e n h a n c e dg r e a t l y 3 r e s e a r c ho nr u n n i n ge n v i r o n m e n td y n a m i ca d a p t a b i l i t yo fm i g r a t i n g w o r k f l o w t h ew o r k p l a c ep r o v i d e sar u n n i n ge n v i r o n m e n tt ot h em i g r a t i n g i n s t a n c e ，i nw h i c ht h em i g r a t i n gi n s t a n c ec a no b t a i nas e r v i c el i s tt h a tt h e c u r r e n tw o r k p l a c em a yp r o v i d ea n dt h ei n f o r m a t i o na b o u to t h e ri n s t a n c e s t h a tr e s to nt h es a m ew o r k p l a c e i ft h em i g r a t i n gw o r k f l o ws y s t e mm a y r e s p o n s ea n dd e a l 、而mt h o s ea b n o r m i t yb r o u g h tb yw o r k p l a c ep h y s i c a lf a u l t ， i t p o s e st h er u u n i n ge n v i r o n m e n td y n a m i ca d a p t a b i l i t y b e c a u s ea b o v e a b n o r m i t y ，i nt h er u n n i n ge n v i r o n m e n tt h em i g r a t i n gi n s t a n c ea p p e r c e i v e s s o m ep a r t l yi n c o m p l e t ei n f o r m a t i o n c h a p t e r5i n v e s t i g a t e sap l a n n i n g m o d e la n da l l e f f i c i e n t ，d y n a m i ca n df l e x i b l em e t h o dw h i c hm a k e st h e m i g r a t i n gi n s t a n c et op o s s e s sp a r t l yp e r c e p t i v e ，c o m p e t i t i v e l yc o o p e r a t i v e i 山东大学博士学位论文 a n ds e l f - l e a r n i n ga b i l i t i e s t h em i g r a t i n gi n s t a n c em a k e su s eo ft h i s i n c o m p l e t ei n f o r m a t i o nt om a k ea ni n i t i a lp l a na n do b t a i n saf e a s i b l e s t r a t e g ys e t a f t e r w a r d s ，t h em i g r a t i n g i n s t a n c eo b t a i n st h er e c e n t i n f o r m a t i o no fi t sf e l l o w a c c o r d i n gt ot h i si n f o r m a t i o na n di t si n i t i a l p l a n n e ds t r a t e g ys e t ，t h em i g r a t i n gi n s t a n c em a k e si n c o m p l e t eg l o b a lp l a n t h ep l a n n i n gm e t h o do ft h em i g r a t i n gi n s t a n c em a k e st h em i g r a t i n g i n s t a n c et oa d a p tt om u l t i f o r mc h a n g e sa n de n h a n c e st h es e l f - a d a p t i v e a b i l i t yo f t h es y s t e m t h em a i ni n n o v a t i v ec o n t r i b u t i o n so ft h i st h e s i sa r e ： 1 t h i st h e s i s p r o p o s e sap r o c e s sd y n a m i ca d a p t a b i l i t y m e t h o db a s e do n o p t i m i z e dp l a n n i n ga l g o r i t h mo fm i g r a t i n gr o u t t h i sm e t h o di sb a s e do n t h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) m o d e li nw h i c hac i t yd e n o t e sa w o r k p l a c e ，a n dt h e nah y b r i dg e n e t i ca l g o r i t h mr m g a w i t hi m p r o v e de a x o p e r a t o ra n dr e i n f o r c e m e n tm u t a t i o no p e r a t o ri sp r o p o s e d t h ec o r eo f r m g al i e si nt h eu s i n gh e t e r o g e n e o u sp a r i n gs e l e c t i o ni n s t e a do fr a n d o m p a r i n gs e l e c t i o ni ne a x a n dt h ec o n s t r u c t i o no fr e i n f o r c e m e n tm u t a t i o n o p e r a t o r , n a m e dr e - m , b ym o d i f y i n g t h eq l e a r n i n ga l g o r i t h ma n d a p p l y i n gi t t ot h o s ei n d i v i d u a l sg e n e r a t e df r o mm o d i f i e de a x t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tr m g ao u t p e r f o r m e dt h ek n o w ng e n e t i c a l g o r i t h mi nt h eq u a l i t yo fs o l u t i o n sa n dt h er u n n i n gt i m e b a s e do nt h e h e u r i s t i ct r a n s c e n d e n tk n o w l e d g e ，t h es y s t e md y n a m i c a l l yp l a n st h em i g r a t e r o u t eu s i n gt h i sm e t h o d 2 t h i st h e s i sp r o p o s e sas e r v i c ed y n a m i ca d a p t a b i l i t ym e t h o db a s e do n w o r k f l o ws e r v i c es u b s t i t u t i o nm e c h a n i s m t h i sm e t h o di n c o r p o r a t e s k n o w l e d g eo n t o l o g yt op r o v i d eas e r v i c eo n t o l o g ys u b s t i t u t i o nm e c h a n i s m t h i sm e c h a n i s mm a k e st h em i g r a t i n gi n s t a n c et of i n ds u b s t i t u t e ds e r v i c eo r r e s o u r c et o c o n t i n u a l l ye x e c u t e w h e np r e c o n c e r t e ds e r v i c eo rr e s o u r c e c a n n o tb eo b t a i n e d t h i st h e s i sa l s op r o v i d e sam e t h o dt h a tc a nr e a l i z et h i s m e c h a n i s mi nt h em i g r a t i n gw o r k f l o wm o d e l t h eo n t o l o g ys u b s t i t u t i n g m e c h a n i s mm a yr e a l i z ea u t o m a t i cs e r v i c e - f i n d i n ga n dt h es e r v i c ed y n a m i c 山东大学博士学位论文 c o m b i n a t i o nb a s e do nd o m a i no n t o l o g y u n d e rt h es u p p o r to ft h ed o m a i n o n t o l o g ya n dt h eb a s eo fs i m i l a r i t ym e a s u r e m e n ti no n t o l o g y , t h er e l e v a n c y m e a s u r e m e n tb e t w e e ns e r v i c e si sc o m p u t e da n ds e r v i c ec o m b i n a t i o ni s f o r m e d 3 t h i st h e s i sp r o p o s e sar u n n i n ge n v i r o n m e n td y n a m i ca d a p t a b i l i t ym e t h o d b a s e do nl o c a l p l a n n i n ga l g o r i t h mo fm i g r a t i n gr o u t e i nt h er u n n i n g e n v i r o n m e n t , t h em i g r a t i n gi n s t a n c ea p p e r c e i v e si n c o m p l e t ei n f o r m a t i o n s ot h ee n v i r o n m e n tm a yb em o d e l e db y p a r t i a l l yo b s e r v a b l em a r k o v d e c i s i o np r o c e s s e s ( p o m d p ) o nt h i sc o n d i t i o nal o c a lr o u t ep l a n n i n g a l g o r i t h m a l g o r i t h m i s p r o v i d e d t os o l u t es u c hu n c e r t a i np o m d p a p p r o x i m a t e l yo p t i m a ls t r a t e g y t h ec e r t a i nl i m i t e dh i s t o r i c a li n f o r m