Web服务支持网络平台之间异构系统相互协作，在最近的十年中，它得到了迅速的发展。Web服务理念的最激动人心之处在于，它允许简单地组合的方式得到复杂的服务，满足所有的预先指定的功能或者非功能的约束比如响应时间、成本等等。但是，服务组合问题的困难的之处在于即使简单情形，它仍然可以建模为多维多选择背包问题，而后者则是众所周知的NP难的问题。为了解决服务组合的难题，本文提出了两种启发式算法WS_PA和WS_Tabu。WS_PA和WS_Tabu都是典型的局部搜索算法，它们从一个初始解出发，反复搜索解空间，期望能够找到更优越的解。一些经典的禁忌搜索的技术如禁忌表(Tabu list)、路径重连(Path relinking)和重启(Restart)等等被引入到我们的算法中以提高算法的性能。在进行实验时，我们的算法不仅和服务组合领域的算法进行比较，还和多维多选择背包问题领域的算法进行比较，实验表明，无论是考虑算法时间还是求解的质量，WS_PA和WS_Tabu都是是非常有竞争力的算法