导读:本文包含了同类机论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:同类,在线,算法,竞争,近似,等级,启发式。
同类机论文文献综述
杨阳[1]（2019）在《同类机成本限制下的延迟时间优化调度》一文中研究指出本文研究的内容是考虑机器使用成本的最大延迟时间同类机调度问题。机器调度问题在生产制造领域一直是研究的重点课题,而同类机作为日常生活中很常见的一类机器更加需要我们的关注。最大延迟时间是指客户的等待时间与既定时间的差值,是顾客满意度的重要体现。因此,本文所研究问题具有重要的理论和现实意义。在本文中,先研究了机器具有固定使用成本的情况,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。对于作业不可中断的问题,构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法A_1,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。作业可中断情况下,同样也设计了相关算法A_2进行调度,并给出算例进行验证。在前一部分的基础上,进一步拓展了机器使用成本的条件。假设机器的使用成本是与机器加工时间相关的,研究了最小化最大延迟时间的问题。针对不可中断问题,建立了混合整数规划模型,通过相关规则,设计了调度作业的算法A_3,并通过算例和大量的随机数据实验,说明了算法解具有较好的优越性。对于可中断问题,设计了启发式算法A_4,并通过算例说明了算法的执行过程。(本文来源于《合肥工业大学》期刊2019-05-01）
魏麒,吴用,蒋义伟[2]（2019）在《MapReduce同类机排序问题的改进算法》一文中研究指出研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3~(1/2)/3的近似算法.上述结果是对已有文献的改进.(本文来源于《高校应用数学学报A辑》期刊2019年01期）
彭南南,张玉忠,柏庆国,王成飞[3]（2019）在《工件满足一致性的同类机在线分批排序问题》一文中研究指出研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,叁元素法分别表示为Q_2|r_i<r_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_i<r_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.(本文来源于《运筹学学报》期刊2019年01期）
周鹏程,刘朝晖[4]（2018）在《有服务等级约束的同类机在线排序问题的可分算法》一文中研究指出研究了一类有四个服务等级的可分排序问题,在一定条件下改进了下界,并且提出了一种最优算法。在该问题中,工件和机器都带有各自的服务等级约束,当且仅当工件的服务等级比机器的服务等级高或者相同时,该机器才被允许对该工件进行加工,并且每个工件都被允许在所有机器之间按照任意的比例分割后进行加工,同一个工件的各个部分被允许同时放在各台机器上进行加工,优化目标是找到最小时间表长。(本文来源于《华东理工大学学报(自然科学版)》期刊2018年06期）
韩曙光,郑聪[5]（2019）在《叁台同类机MapReduce排序问题的最优算法》一文中研究指出研究MapReduce环境下的可中断同类平行机排序问题。在MapReduce环境中,每个工件含有两种类型的任务集,即Map任务集和Reduce任务集。在加工完工件的Map任务集后才能开始加工Reduce任务集中的任务。考虑Map任务为可分的情况,即Map任务可以任意分割为不同的小任务并能在不同机器上同时进行并行加工,而对于Reduce任务则考虑允许中断的情形,目标设为极小化最大完工时间。针对叁台同类机的离线排序问题,通过分解所有实例的类型,给出了最优解算法。(本文来源于《浙江理工大学学报(自然科学版)》期刊2019年04期）
姜昆,杨峥,王吉波[6]（2018）在《具有学习效应的非同类机资源约束排序问题研究》一文中研究指出研究具有学习效应和资源约束的非同类平行机排序,即工件的加工时间与所排机器,所排位置和所用资源都有关系.目地是确定每台机器所分配的工件及其排序和所用的资源量,使所有工件的总完工时间和总资源消耗费用的加权和最小.在非同类机的数量给定的情况下,证明了这个问题能够在多项式时间内解决,并给出了一个例子来说明问题是如何求解的.(本文来源于《数学的实践与认识》期刊2018年20期）
秦阳阳,张玉忠,任建峰[7]（2018）在《m台同类机上的分配博弈》一文中研究指出研究n个工件在m台同类机上的资源分配问题.每个代理人管理一个工件并"自私"的选择一台机器加工,目标是极小化他的完工时间.该问题的性能与代理人的目标不同,是通过目标函数来衡量的,该问题的目标函数为全部工件的完工时间和.该文用POA(Price of Anarchy)来衡量一个纳什均衡(Nash Equilibrium)排序的目标函数值与一个最优排序的目标函数值的差异.证得当有一台速度比1大,其余速度均为1时,POA的上界为((4m-3)~(1/2)+1)/2,下界为3/4+(1/4)((m+1)/(m-1))~(1/2);当有一台机器速度小于1,其余速度均为1时,POA的上界为((4m-3)~(1/2)+1)/2,下界为1+(m(2m+1)~(1/2)-2m+1)/(m~2-4 m+2)((2m-1)~(1/2)+2m~2-m)).(本文来源于《曲阜师范大学学报(自然科学版)》期刊2018年02期）
周鹏程[8]（2018）在《有服务等级约束的同类机在线排序问题的可分算法》一文中研究指出研究了一类有四个服务等级的可分排序问题,在五种情形下改进了下界,并且提出了一种最优算法。在该问题中,工件和机器都带有各自的服务等级约束,当且仅当工件的服务等级比机器的服务等级高或者相同时,该机器才被允许对该工件进行加工,并且每个工件都被允许在所有机器之间按照任意的比例分割后进行加工,同一个工件的各个部分被允许同时放在各台机器上进行加工,优化目标是找到最小时间表长。(本文来源于《华东理工大学》期刊2018-04-04）
王穆清[9]（2018）在《同类机上的在线分批排序问题》一文中研究指出排序论又称为时间表理论,是运筹学的一个分支,有深刻的实际背景和广阔的应用前景。是一类重要的组合最优化问题,广泛应用于管理学、工业制造、产品生产之中,在国内和国外都有相当重要的研究价值,是结合了数学、管理学、计算机、算法的一个重要问题。其中的在线分批排序是近年来比较新颖的排序问题,与现实中的生产加工的结合更加贴切,近十年来在一台及多台平行机的加工环境下的在线分批排序问题有很多研究成果,是实际生活中工厂的生产运作的缩影。本文主要研究了两台同类机的在线分批排序问题,其中两台同类机一台机器速度为1,一台机器速度为s(s≥1),该在线问题为时间在线,其信息(加工长度,到达时间)只有在到达时才能知悉,一台批加工机器可以同时容纳至多B个工件,在同一批中,所有工件同时开始加工并同时结束,完工时间等同于该批最大工件的完工时间,本文研究的是批容量为无界的情况,即一批可以容纳充分多个工件,目标是使最大完工时间极小化。问题用叁参数表示法为Q2|rj,pj,B=∞,on-lineCmax,文章分为叁章来叙述。第一章是引言,主要介绍了一些重要的定义,以及在线分批排序的背景及发展和国内外研究现状。并简单介绍了本人的研究成果以及创新之处。第二章就所研究的问题Q2|rj,pj,B=∞,on-line|Cmax,给出了一个在线算法,证明了算法的竞争比不超过2。第叁章给出了Q2|rj,pj,B=∞,on-line|Cmax的一个下界,用对手法证明其下界为αs+ 1,其中αs2+(1+1/s)αs=1/s°（0＜αs＜1)(本文来源于《曲阜师范大学》期刊2018-03-13）
刘文娟[10]（2018）在《MapReduce中同类机排序极小化最大完工时间问题》一文中研究指出MapReduce是一种流行的批处理框架,用于大规模数据集的并行运算,其主要作用是分布式集群节点分析、保持数据局部原则、使数据更加真实有效.本文主要研究h台同类机,reduce任务可中断和不可中断的MapReduce在线排序模型,目标函数是极小化工件的最大完工时间.本文结构安排如下:第一章主要介绍排序问题的基本知识、MapReduce的基本概念.第二章主要研究h台同类机reduce任务可中断的在线MapReduce排序问题,工件以over list释放.目标函数是极小化工件的最大完工时间.在MapReduce排序模型中有两个假设:一是MapReduce排序的map任务可以并行加工,而reduce任务不可并行加工.二是必须得等一个工件中的map任务加工完成之后才可以加工reduce任务.本章仍沿用这种假设,即假设map任务可以无限分割,即可并行加工,而reduce任务不可并行加工,但在本章中,工件的reduce任务可以中断,该模型假设为只有当map任务完成之后才可以知道reduce任务的信息,所以在本章中设计的算法为工件到达之后先将所有map任务分到h台机器上,使得加工完map任务的h台机器的完工时间相等,对于reduce任务可中断的情况,我们采用了文[26]提出的McNaughton’s around rule这一方法,该方法得到的机器的完工时间为Cmax=max(?),本章利用该方法设计了一个近似算法,给出了近似算法的竞争比的上界为2―(?),其中S1 ≥ S2 ≥...≥sh,其sj是机器j的加工速度,k0为使得Tk/Bk(1 ≤k≤h)达到最大值的机器的编号,h是机器台数,其中Tk = |r1| + |r2| +...+ |rk|,Bk=s1 + s2+…+sk,|r1|≥|r2|≥ …≥ |rm|,|ri| 是第i长reduce任务的长度.第叁章同样研究了h台同类机在线的MapReduce在线排序问题,与第二章不同的是:本章研究了 reduce任务不可中断的情况,工件以over list释放,目标为极小化工件的最大完工时间,同样假设一个工件的map任务完成之后才可以知道该工件reduce任务的信息,本章所采用的算法思想是:对于到达的工件将map任务放在h台机器上加工,使得加工完map任务的机器完工时间均相等,然后将reduce任务以LPT规则排序,依据经典排序的LPT规则,设计了近似算法,并得到了该近似算法的竞争比的上界.第四章是总结了全文主要内容,并对接下来的努力方向提供了参考.(本文来源于《曲阜师范大学》期刊2018-03-10）
同类机论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
研究了MapReduce系统中极小化最大完工时间的同类机排序问题.每个工件包含两类任务集:Map任务集和Reduce任务集.工件的Reduce任务必须在该工件的所有Map任务完成后才能开始加工.Map任务是可分的,即可以被任意分割并在多台机器上同时加工,而Reduce任务是不可分的.针对m台同类机离线模型,分别考虑了Reduce任务可中断和不可中断两种情形.对于可中断情形,设计了一个近似比为2-■的近似算法,其中g_1≥1,s_i为机器σ_i的加工速度且s_1≥s_2≥…≥s_m;对于不可中断情形,则给出了一个近似比为2+3~(1/2)/3的近似算法.上述结果是对已有文献的改进.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
同类机论文参考文献
[1].杨阳.同类机成本限制下的延迟时间优化调度[D].合肥工业大学.2019
[2].魏麒,吴用,蒋义伟.MapReduce同类机排序问题的改进算法[J].高校应用数学学报A辑.2019
[3].彭南南,张玉忠,柏庆国,王成飞.工件满足一致性的同类机在线分批排序问题[J].运筹学学报.2019
[4].周鹏程,刘朝晖.有服务等级约束的同类机在线排序问题的可分算法[J].华东理工大学学报(自然科学版).2018
[5].韩曙光,郑聪.叁台同类机MapReduce排序问题的最优算法[J].浙江理工大学学报(自然科学版).2019
[6].姜昆,杨峥,王吉波.具有学习效应的非同类机资源约束排序问题研究[J].数学的实践与认识.2018
[7].秦阳阳,张玉忠,任建峰.m台同类机上的分配博弈[J].曲阜师范大学学报(自然科学版).2018
[8].周鹏程.有服务等级约束的同类机在线排序问题的可分算法[D].华东理工大学.2018
[9].王穆清.同类机上的在线分批排序问题[D].曲阜师范大学.2018
[10].刘文娟.MapReduce中同类机排序极小化最大完工时间问题[D].曲阜师范大学.2018
论文知识图
