论文摘要
随着互联网技术的发展，网络服务(Web Service)整体响应时间(Response Time)中网络延时(Network Latency)所占比重越来越大。在网络服务应用范围不断扩大，人们对其响应时间要求却越来越高的情况下，如何对网络服务进行合理选址，从而降低总体响应时间,提高网络服务的服务水平显得尤为重要。本文重点从响应时间的角度对网络服务选址问题进行了研究，因为网络服务体系中响应时间是决定服务水平的关键因素。研究中应用选址问题的相关理论并结合网络服务自身特点，提出了基于时间满意度的多服务带容量限制的网络服务选址模型。本文模型在国外相关研究的基础上，分析了网络服务体系的自身特点，结合这些特点进行了模型改进：网络服务需求点(Web Service Requester，WSR)只能选择一个网络服务提供商(Web Service Provider，WSP)；增加了网络服务的容量约束；提出了“有效覆盖”的想法，强调了网络服务需求方可以根据自己的服务水平偏好自主选择网络服务。同时还将时间满意度引入目标函数，采用离散的时间满意度函数，与网络服务体系中的分级定价相关联，使得本文的模型不仅更好地贴合了实际应用，也具有了比较好的拓展性。本文问题时NP困难问题，因而采用贪婪算法思想求解，将问题划分为多个子问题后，根据子问题规模较小，使用了贪婪算法和动态规划法相结合的混合算法进行了求解，取得了比较好的求解效果。