工件带权重的平行机博弈排序问题

发布时间：2017-12-31 01:41

本文关键词：工件带权重的平行机博弈排序问题　出处：《曲阜师范大学》2015年硕士论文　论文类型：学位论文

【摘要】：在资源配置问题中,不同的工作任务被安排到各个加工资源上来完成,例如:平行机排序问题.在近几年的研究中,博弈论的概念和工具被应用到资源配置问题中,形成了博弈排序.本文研究的是平行机博弈排序的三种模型:负载均衡模型、包含启动费用的新模型、恒速机上的负载均衡模型.前两个模型中,机器是同速机,第三个模型中,机器是恒速机.与前人成果不同之处在于:我们考虑的是工件带权重的情况,相应的将目标函数(社会成本)定义为所有工件的加权总成本.这里工件的成本或者是拥塞时间(定义为工件所在机器的负载),或者是复合成本(包含拥塞时间和分摊的启动费用).这一类平行机上的博弈排序问题,不同于传统排序问题:一个权威专家做出排序决定.现在每一个局中人,以最小化自己的成本为目的,决定由哪台机器加工他的工件.在运行过程中,会导致纳什均衡.然而就一个给定的目标函数而言,这样的均衡不一定达到最优,事实上,常常与最优值相差甚远.因此,分析纳什均衡序相较于最优序的性质至关重要.我们用无序性代价(PoA)和稳定性代价(PoS)两个指标来衡量纳什均衡序的效果.针对每个模型,分析其纳什均衡序的性质,并且得到了PoA和PoS的界.工件带权重的同速机负载均衡模型,￡￡-+--PoSnmnm1)1()1(2min1wPoA￡;工件带权重的启动费用分摊模型,( )2121 wPoSPoA+￡￡￡r;工件带权重的恒速机负载均衡模型,÷???è?+￡ 11mnswsPoAm.其中,min1pr=,minp是工件加工时间的最小值,min maxwww =,maxw和minw分别表示所有工件权重中的最大值和最小值,1s和ms分别是机器速度的最小值和最大值.
[Abstract]:In the problem of resource allocation in different tasks assigned to each processing resources to complete, for example: the parallel machine scheduling problem. In recent years, the concepts and tools of game theory are applied to the problem of resource allocation, formed game sort. This paper is a study of three parallel machine scheduling game model the load balancing model, the new model includes start-up costs, constant speed machine load balancing model. The first two models, the machine is the same speed machine, the third model, the machine is in constant speed machine. Unlike the previous results: we consider is the workpiece with the weight of the corresponding. The objective function (Social cost) is defined as the weighted total cost of all the jobs here. The cost of the part or congestion time (load is defined as the machine, the workpiece) or composite cost (including congestion time and sharing start-up costs) this. The game scheduling problem on parallel machines, different from the traditional scheduling problem: an authoritative expert to make sequencing decisions. Now every person in the game, to minimize their cost so as to decide which machine processing of his work. In the process of operation, will lead to a Nash equilibrium. However, an objective function given, this equilibrium is not necessarily optimal, in fact, often with the optimal value far. Therefore, it is important to determine the Nash equilibrium order compared with optimal properties. We use random price (PoA) and price stability (PoS) two indicators to measure the Nash equilibrium for each order. Analysis of the properties of Nash equilibrium model, order, and get PoA and PoS. A load balance model with the same speed machine workpiece with weight, F & -+--PoSnmnm1) 1 (1) 2min1wPoA (f; workpiece with the weight of the start-up cost allocation model, (2121) WPoSPoA+ & & F R; workpiece with the weight of the constant speed machine load balancing model, /??? S? F + 11mnswsPoAm. min1pr=, where MINP is the minimum processing time, min = maxwww, maxw and minw respectively, the maximum and minimum weight of all jobs, 1s and MS respectively. Minimum and maximum speed of the machine.

【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O225

【相似文献】