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

发布时间：2018-06-07 06:42

  本文选题：激活费用 + 恒速机　； 参考：《曲阜师范大学》2016年硕士论文

【摘要】：本文主要研究在资源有限前提下带激活费用的恒速机上工件的博弈排序问题.机器初始状态未被激活,激活每一台机器都会产生一定的激活费用.没有中心权力者来控制排序,每一个工件相当于一个局中人,它们会极小化个体成本来选择机器进行加工,其中每一个工件的个体成本是它选择的机器的完工时间与其所要承担的那部分激活费用之和.用无序代价(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的上界(?).
[Abstract]:In this paper, we mainly study the game ordering problem of the workpiece with activation cost under the condition of limited resources. The initial state of the machine is not activated, each machine will be activated at a certain cost. There are no central weights to control the sort, each job is the equivalent of a player, and they minimise individual costs to select machines for processing. The individual cost of each of the workpieces is the sum of the completion time of the machine it chooses and the portion of the activation cost it has to bear. The difference between the social cost and the optimal value of the worst Nash equilibrium is measured by using the disordered cost (POA). In this paper, the different objective functions of the game ordering problem of two constant speed machines with activation cost and m constant speed machines are studied. The first chapter mainly introduces the sequencing problem, the game theory and the research background of the game scheduling problem, related theoretical knowledge and research status, and briefly explains the main research results and innovation points of this paper. In chapter 2, the model of game ordering problem for two machines with activation cost is studied. In the model, the speed of the two machines is 1 and 伪, respectively, and the activation cost B of the machine is the same as its speed. Social costs) The goal is to minimize the social cost for the sum of individual costs of all artifacts. By analyzing the model POA, we obtain the upper bound 伪 1 of POA and give an example of POA lower bound 伪 -1. In chapter 3, we mainly study two models of the game ordering problem of the workpiece of m machine with the same activation cost. In the model, there are m machines with different speeds. The speed of machine Mi is 伪 1. Assume that 伪 1 伪 2 鈥，

本文编号：1990243