带激活费用的恒速机的有限资源博弈排序问题

作     者：桑琳 

作者单位：曲阜师范大学 

学位级别：硕士

导师姓名：张玉忠

授予年度：2016年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：激活费用 恒速机 博弈排序 纳什均衡(NE) 无序代价(POA) 

摘      要：本文主要研究在资源有限前提下带激活费用的恒速机上工件的博弈排序问题.机器初始状态未被激活,激活每一台机器都会产生一定的激活费用.没有中心权力者来控制排序,每一个工件相当于一个局中人,它们会极小化个体成本来选择机器进行加工,其中每一个工件的个体成本是它选择的机器的完工时间与其所要承担的那部分激活费用之和.用无序代价(POA)来衡量最差的纳什均衡(NE)排序的社会成本与最优值之间的差异.本文将有限台恒速机、激活费用综合考虑,分别对带激活费用的两台和m台恒速机的博弈排序问题的不同目标函数进行了研究.第一章主要介绍了排序问题、博弈理论和博弈排序问题的研究背景、相关理论知识和研究现状,并简要说明了本文的主要研究成果及创新点.第二章主要研究带激活费用的两台恒速机上工件的博弈排序问题的模型(?).模型中,两台机器的速度分别为1和α,机器的激活费用B与其速度相同.社会成本(?)为所有工件的个体成本Cj之和,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界α+1,证明并给出了POA下界α-1的一个实例.第三章主要研究带相同激活费用的m台恒速机上工件的博弈排序问题的两个模型,即(?).模型中,有m台速度不同的机器,机器Mi的速度为α1,假设α1α2…αm且α1=1.P为所有工件的加工时间之和,每台机器的激活费用B均为1.模型一的社会成本(?)为所有工件的个体成本Cj之和,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界(?);模型二的社会成本Cmax为工件的最大个体成本,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界(?).第四章主要研究带不同激活费用的m台恒速机上工件的博弈排序问题的模型Qm(·),B=αi|ut=-Cj|Cmax.模型中,有m台速度不同的机器,机器Mi的速度为αi,激活费用B也为αi,假设α1α2…αm且α1=1.社会成本Cmax为工件的最大个体成本,目标为极小化社会成本.通过对模型POA的分析,我们得到了POA的上界(?).