Internet技术的飞速发展带动了商业方式改变的创新大潮流。为了获取更多的自动化,有效的业务过程,全球业务视图等,许多公司正在将主要的经营转移到网络。为了在新的在线经济竞争中生存,公司需要应该选择或实现正确的软件科技解决方案。Web服务就是一种企业整合的新型软件系统,能够提高不同计算平台,应用,商业参与者之间的协作,而Web服务组合技术是组合不同的服务以解决更为复杂的应用需求。自动Web服务组合能够通过使用AI Planning技术实现,其中HTN规划方法已经研究用于处理基于OWL-S语义Web服务描述模型的服务组合问题。然而现有的基于HTN的Web服务组合方法不考虑多分解方法选择的问题,而每种不同分解方法的选择可能导致产生不同的组合方案,同时用户也希望有多种可选的方案和建议的最佳选择。因此,如何给用户提供较优的组合方案是Web服务组合问题中一个研究的重点问题。本论文提出了一种基于Markov-HTN的自动Web服务组合方法。该方法分两部分,首先改进原HTN的分解方式,使其在规划过程中能同时搜索更多的解空间,以提供给用户更多的可行组合方案。然后,对HTN的分解过程进行MDP建模,求解HTN规划输出的多种方案中的最优方案。同时也给出了一种基于Markov-HTN多组合方案在执行过程中消解冲突的方法。我们实现了Markov-HTN组合方法,以进行有效性验证。实验的结果表明,该方法能够得到多种Web服务组合方案并评价出最优方案。