计算机工程

• 先进计算 • 上一篇    下一篇

结合对策论与多目标MILP的Web服务组合调度问题求解

李靖  1,乔蕊  1,刘志中  2   

  1. )(1.周口师范学院计算机科学与技术学院,河南 周口 466001; 2.哈尔滨工业大学计算机科学与技术学院,哈尔滨 150001)
  • 收稿日期:2015-07-27 出版日期:2016-01-15 发布日期:2016-01-15
  • 作者简介:李靖(1982-),女,讲师、硕士,主研方向为服务计算、Web服务调度;乔蕊,讲师、硕士;刘志中,讲师、博士后。
  • 基金项目:
    国家自然科学青年基金资助项目(61300124);河南省科技厅软科学研究计划基金资助项目(132400411365);河南省高等学校重点科研基金资助项目(15B520046)。

Solution of Web Service Composition Scheduling Problem Combining with Game Theory and Multi-objective MILP

LI Jing  1,QIAO Rui  1,LIU Zhizhong  2   

  1. (1.School of Computer Science and Technology,Zhoukou Normal University,Zhoukou,Henan 466001,China; 2.School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China)
  • Received:2015-07-27 Online:2016-01-15 Published:2016-01-15

摘要: 针对单目标优化问题,结合对策论与多目标混合整数线性规划(MILP),提出一种Web服务组合(WSC)调度方法。根据5个基本的服务质量(QoS)属性定义WSC的QoS属性,将WSC调度问题转换为求解MILP问题,服务商之间的交互模拟为一个非合作、不完备的贝叶斯对策,利用参与者的贝叶斯纳什均衡保证服务商对于组合任务的公平竞争,从而达到最小化执行时间和成本,同时最大化声誉、可靠性和可用性的目标。数值分析结果表明,该方法具有较高的求解效率,能避免效应函数中的多属性聚合现象,适用于求解中小规模的WSC调度问题。

关键词: 对策论, 混合整数线性规划, Web服务组合, 服务质量, 多目标优化

Abstract: Aiming at single objective optimization problem,a Web Service Combination(WSC) scheduling method based on game theory and multi-objective Mixed Integer Linear Programming(MILP) is proposed.The Quality of Service(QoS) attributes of WSC are defined according to five basic QoS attributes.WSC scheduling problem is converted to the multi-objective optimization problem considering QoS.The interaction between service providers is simulated as a non-cooperative and incomplete Bayesian countermeasure.The competition strategy is guaranteed by the Bayesian Nash equilibrium of participants when service provider executes tasks.Thus,the execution time and execution cost is minimized,the reputation,reliability and availability are maximized at the same time.The numerical analysis result shows that the proposed method has a high solving efficiency,can avoid the aggregation problem of multiple attributes in utility function,and it is suitable for solving the small and medium size WSC scheduling problems.

Key words: game theory, Mixed Integer Linear Programming(MILP), Web Service Composition(WSC), Quality of Service(QoS), multi-objective optimization

中图分类号: