
　　摘要：网格环境的特点是开放性和动态性，网格资源、用户和管理策略都可能随着时间动态地发生变化，因此，需要重点解决网格工作流调度系统中的多目标优化问题。将多目标粒子群优化算法应用于求解网格工作流调度中的多目标优化问题，并尝试对MOPSO算法进行改进，以更好地适应网格工作流调度系统。实验表明，该算法是可行的且具有良好的可扩展性。
　　关键词： 网格工作流；任务调度；多目标粒子群优化算法；多目标优化
　　中图分类号：P283文献标识码：A
　　文章编号：1672-1098（2012）03-0029-04
　　网格关注的核心是资源的共享和协同工作，对网格工作流的研究正是为了更好地执行协同工作机制。目前网格工作流的相关研究主要有两个方向：一是网格工作流的规范化、标准化；二是网格工作流的实际应用及研究，即采用网格工作流来管理复杂网格应用，并研究和处理相关的问题[1]。本文所做的网格工作流调度研究属于第二个方向。
　　网格工作流的调度可简单描述为一种映射，它根据任务信息和当前的资源信息，凭一定的策略找到一个调用执行服务时间最短的调度实例[2]。具体过程可分为三步：第一步是寻找和匹配最合适任务运行的资源；第二步对资源的信息进行实时收集，然后对任务进行资源的分配，即决定该资源上任务的执行顺序；第三步任务的执行，包括任务初始化、任务执行和任务结束。
　　网格工作流调度的目标是缩短整个程序的运行时间，这是一个NP完全问题，目前这一问题的解决多采用一些启发式算法，如遗传算法（Genetic Algorith， GA）、模拟退火算法、粒子群优化算法（Particle Swarm Optimization， PSO）、差分演化（Differential Evolution， DE）算法及将多个算法进行融合构成新的算法等。遗传算法是一种全局随机搜索优化算法，它借鉴了生物界的自然选择和生物进化而发展起来。其优点是具有种群多样性和全局解空间搜索能力，缺点主要是早熟收敛问题和局部搜索能力较差的问题。文献[3]定义了三种收敛判据，并采用最优保存策略实现跨代保留，从而避免了算法的早熟收敛问题。文献[4]把服务质量引入网格工作流，为其调度提供依据，从而更多地从用户需求的方面进行考虑。文献[5]采用多算法融合，使免疫算子和遗传算子相结合来避免单一遗传算法的早熟和退化问题。模拟退火算法是一种启发式的随机搜索算法，基于蒙特卡罗求解法，通过模拟热力学中经典粒子系统的降温过程来找出全局最优解。文献[6]将遗传算法和模拟退火算法相融合，提出了一种遗传退火算法，目的是弥补使用单一算法的不足。
　　本文重点解决的是网格工作流调度中的多目标优化问题，即将多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization， MOPSO） 应用于网格工作流的调度，并尝试对MOPSO算法进行改进，以更好地适应网格工作流调度系统。
　　1标准粒子群优化算法