有资源限制的平行机博弈排序问题

发布时间：2020-09-18 15:13

　　排序(scheduling)问题是组合优化问题的一个重要分支,在传统的排序问题中,都是由一个中央集权代理人安排工件排序,而现在排序问题大多研究一个代理人管理一个工件的情况,由代理人安排工件到机器上加工.设计算法,如何安排工件加工,以减少社会资源的浪费具有重大的研究意义.本文主要研究有限资源的博弈排序问题,用POA(Price of Anarchy)来衡量一个纳什均衡(Nash Equlibrium)排序的目标函数值与一个最优排序的目标函数值的差异.本文结构如下:第一章绪论主要介绍了问题的背景,相关概念及相关的研究现状,并简要介绍了本文研究的主要成果和创新点.第二章研究了 m台同类机情况下的的资源分配问题,不妨假设机器的速度分别为s1 =s,s2 = s3= =s…=sm=1,目标函数为全部工件的完工时间和.证得当有一台速度比1大,其余速度均为1时,POA的上界为4m-3+1/2,下界为3/4+1/4 m+1/m-1;当有一台机器速度小于1,其余速度均为1时,PCA的上界为4m-3+1/2,下界为3m-3+(m2-3m+2)2m-1/(m2+4m+2)2m-1+2m2-m,这里的m都是指机器台数.第三章研究了m台同型分批处理机下的资源分配问题,假设每台机器的批容量为b,一批工件中的加工时间是该批中最长工件的加工时间.目标函数为全部工件的完工时间和.设计了一个LPT-贪婪算法,证得POA的上界为bn/m告.
【学位单位】：曲阜师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O223

【参考文献】