机器具有学习效应的博弈排序问题

发布时间：2017-08-20 07:30

  本文关键词：机器具有学习效应的博弈排序问题

  更多相关文章： 学习效应 博弈排序 纳什均衡 POA 协调机制

【摘要】：本文研究的是机器具有学习效应的博弈排序问题,具体来说,我们研究了在机器环境为m台同速机和m台恒速机的情况下,目标函数分别为极小化工件的最大完工时间和极小化总完工时间的问题,并分别对每个问题求出了POA的界.博弈排序问题在近年来受到了国内外学者、专家、及企业家的高度关注,新的研究成果也是不断出现,机器具有学习效应这一类型的排序问题也已被好多学者研究过,而博弈排序这一问题从未与学习效应问题结合在一起被研究,本文的创新点和着力点就在于把机器具有学习效应与博弈排序这两个问题结合起来,针对每个目标函数求出其相应的POA的界.机器具有学习效应是指随着工件在机器上的加工,机器获得了学习效应,从而使后面加工的工件实际加工时间逐渐缩短.本文研究的是与位置有关的学习效应,也就是说,所有工件都在零时刻到达,每个工件都有一个本身的基本加工时间,工件在机器上加工都会有一个相对应的位置.如果工件排在机器上第一个被加工,由于此时机器还未获得学习效应,所以它的加工时间不变,而排在后面的工件被加工时,由于机器获得了学习效应,它们的加工时间都会逐渐缩短.博弈排序是排序中的重要部分,是一类新型排序问题,有着很重要的应用价值,在理论上也有重要的意义.一个纳什均衡是一个工件的排序状态,纳什均衡同样是博弈论的一个重要概念.作为一个纳什均衡,如果其它所有工件的策略都不变,任何一个工件如果单方面的去改变自己的策略,那么它自己的成本不会变的比原来的更好.但在博弈排序中,工件只追求自身利益的最大化,而不在乎社会资源的浪费,这往往导致所得解与最优解偏差过大.为衡量纳什均衡解的好坏,学者们提出了无秩序代价(POA)的概念,即最坏情况下最坏的纳什均衡解对应的目标函数值与最优解的目标函数值的比值.本篇论文分为四章,主要结构安排如下：第一章主要介绍了本文所需的基础知识；第二章主要研究了目标函数为极小化最大完工时间Cmax的博弈排序问题,并求出了在机器环境分别为m台同速机和m台恒速机下对应的POA的界m·T2/T(?)(其中T1和T2分别表示所有工件按SPT序和LPT序排在一台机器上加工时机器的负载)和(其中s1和sm分别表示恒速机中加工工件最慢和最快的机器的加工速度)；第三章研究了目标函数为极小化总完工时间的博弈排序问题,同样求出了在机器环境分别为m台同速机和m台恒速机下对应的POA的界(其中n为工件的个数,P为所有工件本身加工时间之和)和第四章对本文进行了总结及前景展望.
【关键词】：学习效应 博弈排序 纳什均衡 POA 协调机制
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要3-5
• Abstract5-8
• 第1章 绪论8-13
• 1.1 排序问题8-9
• 1.2 博弈排序和纳什均衡9-10
• 1.3 无秩序代价(POA)10-11
• 1.4 学习效应11
• 1.5 协调机制11-13
• 第2章 极小化最大完工时间的博弈排序问题13-18
• 2.1 引言13
• 2.2 问题描述13-14
• 2.3 主要结果14-18
• 2.3.1 P_m|p_(jr)=p_j·r~a,a≤0|C_(max)14-16
• 2.3.2 Q_m|p_(jr)=p_j·r~a,a≤0|C_(max)16-18
• 第3章 极小化总完工时间的博弈排序问题18-25
• 3.1 引言18
• 3.2 问题描述18-19
• 3.3 主要结果19-25
• 3.3.1 P_m|p_(jr)=p_j·r~a,a≤0|(?)C_j19-21
• 3.3.2 Q_m|p_(jr)=p_j·r~a,a≤0|(?)C_j21-25
• 第4章 总结25-26
• 参考文献26-28
• 在读期间发表的学术论文及研究成果28-29
• 致谢29

【共引文献】

中国期刊全文数据库 前10条

1 袁芬;谷云东;尘非;;关于模糊工期平行机调度问题的若干结果[J];北京师范大学学报(自然科学版);2006年03期

2 张忠文;李四海;;一类离散型多资源排序算法[J];长春大学学报;2009年12期

3 陈小林;任子亭;;误工工件个数最少的多目标排序问题(英文)[J];重庆工学院学报(自然科学版);2009年01期

4 李蒙;唐万梅;唐国春;;机器不同时开工平行机排序问题的原始阈值算法[J];重庆师范大学学报(自然科学版);2008年03期

5 唐国春;;误工排序问题的研究[J];重庆师范大学学报(自然科学版);2009年02期

6 彭洪洁;苏永英;唐国春;;部分工件必须不误工的误工排序问题[J];重庆师范大学学报(自然科学版);2009年02期

7 彭洪洁;唐国春;;两个多重目标排序问题的多项式时间算法[J];重庆师范大学学报(自然科学版);2010年02期

8 杨明明;张淑娟;韩翔凌;;具有学习效应的间歇批生产的单机排序问题[J];重庆师范大学学报(自然科学版);2011年03期

9 王松丽;赵玉芳;崔苗苗;;带有释放时间的半连续型批处理机调度问题[J];重庆师范大学学报(自然科学版);2012年02期

10 陈荣军;两机器自由作业稠密时间表的优势集研究[J];常州工学院学报;2005年01期

中国重要会议论文全文数据库 前1条

1 陈荣军;唐国春;;自由作业环境下的供应链排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

中国博士学位论文全文数据库 前10条

1 马英;考虑维护时间的机器调度问题研究[D];合肥工业大学;2010年

2 钟雪灵;带强制工期非正则目标函数的排序问题研究[D];暨南大学;2010年

3 柳春锋;工程项目中技能型员工调度问题研究[D];合肥工业大学;2011年

4 王磊;面向订单生产的供应链排序问题研究[D];暨南大学;2011年

5 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

6 白芳;民航发动机机群调度优化与视情维修决策方法研究[D];南京航空航天大学;2009年

7 郑斐峰;占线订单排序问题及其竞争策略研究[D];西安交通大学;2006年

8 付旭云;机队航空发动机维修规划及其关键技术研究[D];哈尔滨工业大学;2011年

9 杨名;若干流水作业排序问题的算法研究[D];华东理工大学;2011年

10 方阳;关于一些在线分批排序问题的研究[D];华东理工大学;2011年

中国硕士学位论文全文数据库 前10条

1 吴丽华;服装零售供应配送中的若干问题研究[D];浙江理工大学;2010年

2 任立莉;可拒绝平行批平行机与在线平行批两台一致机排序[D];郑州大学;2010年

3 孟令玉;基于网络流的开放式车间调度问题研究[D];哈尔滨工程大学;2010年

4 于庆莲;基于静态并行时间确定可增加瓶颈设备的研究[D];哈尔滨理工大学;2010年

5 苏胜龙;带一个服务器的两台平行机半在线排序问题[D];华东理工大学;2011年

6 陈杰;总延误问题的一种贪婪启发式算法分析[D];华东理工大学;2011年

7 史媛媛;两类双目标排序问题研究[D];武汉科技大学;2010年

8 何少龙;具有安装时间和变量加工时间的单机排序问题[D];沈阳师范大学;2011年

9 林骋;多目标网络计划图的机动时间特性研究[D];华北电力大学（北京）;2011年

10 杨明明;具有学习效应的间歇批生产的单机排序问题[D];曲阜师范大学;2011年

，

本文编号：705359