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

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

作　　者：李靖[1] 乔蕊[1] 刘志中[2] 

机构地区：[1]周口师范学院计算机科学与技术学院,河南周口466001 [2]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机工程》2016年第1期11-17,共7页Computer Engineering

基　　金：国家自然科学青年基金资助项目(61300124);河南省科技厅软科学研究计划基金资助项目(132400411365);河南省高等学校重点科研基金资助项目(15B520046)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]