导读:本文包含了在线和半在线排序论文开题报告文献综述及选题提纲参考文献，主要关键词:半在线排序,批处理机,机器故障,运输时间
在线和半在线排序论文文献综述
周燕[1]（2019）在《带有机器故障的半在线排序问题》一文中研究指出排序理论是运筹学中一个非常活跃的分支.通常,我们将排序问题分为离线排序和在线排序.本文研究了带有机器故障的半在线排序问题,是指在排序之前,工件的到达时间,加工时间,运输时间等信息均已获知,但机器故障何时发生何时结束等信息是无法提前知道的,决策者只能根据到达工件的所有信息给出决策方案.本文我们研究了两类排序问题,一类是带有机器故障和运输时间的单机半在线排序问题,一类是带有机器故障的平行批单机半在线排序问题.其中,平行分批排序是多个工件可以放在同一批,在一台机器上加工,每批里面的工件同时开始加工同时完工,每批的加工时间是该批中所有工件的最大加工时间.批容量(7是指每批可以最多加工(7个工件,一般分为有界和无界两种情形.工件带有运输时间的在线排序,是指工件加工完成后需要用运输工具将其运输到目的地.一般,我们假设运输工具有无数多个,工件一旦被加工完就可以立刻被安排运输,因此送货(运输完工)时间就等于工件的完工时间与其运输时间之和.针对这两类排序问题,我们主要研究两个模型.我们研究的第一类模型是单机带有机器故障,带有运输时间的半在线排序问题,目标函数是最小化最大送货(运输完工)时间,用叁参数法表示为:(1)1,?1|?|_(max);(2)1,?1|_(5))|_(max).在本文的第二章节,我们首先找出了该问题的下界是3?2,对于问题1,?1|?|_(max)我们给出了一个在线算法并证明竞争比为(?).在(?)条件下,对于问题(?)给出了一个竞争比为(3?2+)的在线算法,当<1?2时,竞争比小于2.我们研究的第二类模型是单机带有机器故障的批容量有界的平行批半在线排序问题,目标函数是最小化最大完工时间,用叁参数法表示为:(?).在本文的第叁章节,我们找出了问题的下界是3?2,给出了一个最好可能的在线算法,并证明了该算法的竞争比是3?2.(本文来源于《中国矿业大学》期刊2019-05-01）
邵晶晶[2]（2017）在《两个带机器准备时间的半在线排序》一文中研究指出研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.(本文来源于《广西科技师范学院学报》期刊2017年06期）
唐峰,聂劲[3]（2016）在《平行机上订单半在线排序的LS算法的性能比分析》一文中研究指出对于在m台平行机上工件有单调非减的到达时间和单调非增的加工时间的半在线排序问题进行了研究,其目标函数是要令所有机器中最大完工时间达到最小。对任意半在线工件序列和任意m台机器,证明了3/2-1/2 m为LS算法的最坏性能比的上界。(本文来源于《系统工程》期刊2016年06期）
姬赛[4]（2016）在《两类半在线排序模型的算法性能分析》一文中研究指出本文主要分为两部分内容,分别对两类半在线模型的算法性能比进行了分析。第一部分：He and Zhang在1999([12])年提出了一个半在线的排序模型：对任意的工件序列L={J1,J2,….Jn),工件具有相似的加工时长pj∈[1,r](r≥1).将这些工件安排在两台平行机上。得到对任意满足该模型的实例L在LS算法下的最坏性能比为本文在其工件具有相似的加工时长pj∈[1,r](r≥1)的基础上,加入了到达时间非递减且r1≤r2≤…≤rn这一约束,与([12])的到达时间为零这一模型相比,本章的模型更为复杂,分析过程要考虑的因素也更多,从而得到该模型在LS算法下其最坏性能比为这是一个紧界,并且LS算法是解决此模型的最好的近似算法。这一部分内容将在第二章展开详细证明。第二部分：Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet在1996([24])年给出了一个模型：工件到达时间都为零,且加工时长非递增。并给出了解决这一模型的算法Pm。算法(在本文中暂称为Pm算法,与([24])中的称呼保持一致)且证明了对任意满足该模型的实例L在Pm算法下的性能比为本文在其模型的基础上,增加了一个约束条件,即当工件的到达时间不都为零且满足非递减(即r1≤r：≤…≤rn)。并证明了对于任意满足条件的工件序列L,在Pm算法的最坏性能比为虽然单看性能比数值比之前要大,但是本章的模型是([24])的一个推广,模型更为复杂,应用的范围也更加广泛。这一部分内容将在第叁章展开详细证明。第一章介绍了组合优化问题、近似算法以及排序问题的研究进展。第四章对整篇文章做了一个总结,并指出了未来的研究方向。(本文来源于《湖南师范大学》期刊2016-06-01）
荣建华,彭丽,张玲玲,侯丽英[5]（2016）在《一个可中断叁台可拒绝平行机半在线排序问题》一文中研究指出研究了工件带有拒绝费用的3台平行机半在线算法。工件逐个到达,当工件到达时可以被接收加工,消耗一定的加工时间,也可以被拒绝,但此时要付出一定的拒绝费用。进一步假定工件的加工时间与拒绝费用事先成固定比例α(α≥0)。目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小。针对工件加工可中断情形,设计出半在线算法ARH,并证明算法ARH的竞争比为关于参数α的分段函数,且为紧界。(本文来源于《重庆师范大学学报(自然科学版)》期刊2016年03期）
孙立娟[6]（2015）在《工件加工时间有界的两台同类机半在线排序问题研究》一文中研究指出本文从下界和算法的角度对带服务等级的两台同类机半在线排序问题进行了研究,目标函数为最小化时间表长。问题中的机器和工件都被赋予了不同的服务等级,只有当一个工件的服务等级不低于一台机器的服务等级时,这个工件才被允许在该台机器上加工。在半在线排序问题中,工件按照一个给定列表中的顺序依次到达,在工件到达之前,排序者已知工件的部分信息。我们考虑的是已知工件加工时间上下界的情形。第二章研究了工件加工时间有界的两台同类机半在线排序问题,其中第二台机器速度是第一台的s(0<s≤1)倍,而且只能加工部分等级的工件。设所有工件的加工时间上下界之比为t(t≥1),即1≤p≤t。目前关于该问题下界及算法的研究,仍然有面积约为0.2的(s,t)区域没有得到解决。我们对没有解决的(s,t)区域作出了进一步的研究,分析了部分(s,t)区域的下界,并设计了一个算法A,该算法A在这些(s,t)区域上达到了最优。本文研究结果将未解决的(s,t)区域面积缩小到了0.007。(本文来源于《华东理工大学》期刊2015-08-29）
周昊[7]（2015）在《已知总和的可中断半在线排序算法》一文中研究指出文章研究了平行机上的一个半在线排序问题.假定预先已知所有工件的加工时间总和,工件的加工可中断,目标是极大化最小的机器完工时间和极小化最大的机器完工时间.针对这两种目标情形,分别给出了竞争比为1的半在线算法,从而是最优的.(本文来源于《浙江树人大学学报(自然科学版)》期刊2015年01期）
闵啸,刘静,朱俊蕾,姜明[8]（2014）在《拒绝可缓冲的2台同类机半在线排序问题的近似算法》一文中研究指出研究了2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2,速度分别为1和s∈[1,+∞),加工不允许中断,工件Jj按照列表在线到达,每个工件带有2个参数:加工长度tj、拒绝罚值pj(模型1中)或拒绝获益pj(模型2中),当工件到达时,可以被接受并分给某台机器加工,也可以被拒绝,需付出一定的罚值(模型1)或取得一定的收益(模型2),目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和;第2个模型中要求极大化机器最小负荷和总收益之和.此外,在接受或拒绝的决策环节上提供一个缓冲区B,其容量为k≥1,任一时刻至多可以存放k个工件,当工件到达时,若缓冲区未饱和,则可暂时存入B;若已饱和,则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策.本模型所研究的是经典可拒绝模型中的一个松弛问题,属半在线可拒绝模型.最后针对以上2个模型,分别给出了s在区间[1,+∞)上的近似算法,并证明了各自关于s的参数竞争比.(本文来源于《浙江大学学报(理学版)》期刊2014年04期）
李蒙,孙秋媚,封汉颖[9]（2011）在《预知两种信息带准备时间的两台同型机半在线排序》一文中研究指出研究了P2,r_j/decr,opt/Cmax问题,即预知工件大小非增排列decr和最优目标值opt的两台同型机的带准备时间的半在线问题,并给出了竞争比为7/6的半在线算法.(本文来源于《数学的实践与认识》期刊2011年20期）
侯丽英[10]（2011）在《具有服务等级的在线和半在线排序及其相关问题》一文中研究指出排序问题是运筹学与组合优化领域中的一类重要问题.对排序理论的研究具有重要的理论意义和广阔的实际应用前景.具有服务等级的排序问题是现代工业生产中出现的一个新的组合优化模型,近年来受到了许多学者的关注.本文主要研究具有服务等级的在线和半在线排序问题.全文共分为五章.在第一章中,我们首先介绍了排序问题的基本概念和基本理论,然后给出了具有服务等级的平行机排序问题的描述以及该问题近年来取得的研究进展.在第二章中,我们主要研究了具有两个服务等级的m台同类机上的在线和半在线负载问题.在该模型中,工件按序在线到达且是可分的.其中,k(1≤k≤m-1)台机器的速度为s,服务等级为1,能加工所有的工件,另外的m-k台机器的速度为1,服务等级为2,只能加工服务等级为2的工件.对于目标为最大化最小完工时间的不可分模型,我们证明了不存在具有有界竞争比的在线算法,因此我们研究工件可分模型.对于目标为最大化最小完工时间的可分模型,我们设计了竞争比为(2ks+m-k)/(ks+m-k)(0<s<∞)的最好可能的在线算法.对于目标为最小化最大完工时间的可分模型,我们设计了竞争比为的最好可能的在线算法.对于已知所有工件的加工时间总和(sum)的目标为最小化最大完工时间的可分模型,我们给出了最优的在线算法(即竞争比为1的算法).在第叁章中,我们主要研究了具有两个服务等级的m台同类机上的在线排序问题.在该模型中,工件按序在线到达且是不可分的.其中,k(1≤k≤m-1)台机器的速度为s,服务等级为1,能加工所有的工件,另外的m-k台机器的速度为1,服务等级为2,只能加工服务等级为2的工件.对0<s<1和s≥1两种情形,我们分别给出了在线算法.当0<s<1时,我们给出的算法的竞争比为当s≥1时,我们给出的算法的竞争比为其中,s1∈(0,1)是方程k2s3+k(2m-2k-1)s2+(m-k)(m-2k)s-(m-k)2=0的实根,s2是方程ks2-(2k-1)s-(m-k)=0的正根.当k=1且m=2时,这两个算法都是最好可能的.我们还给出了一些特殊情形时的问题的下界.在第四章中,我们主要研究了具有服务等级的两台恒同机上的在线排序问题,其中工件的到达方式是按时在线到达.首先我们证明了任何在线算法的竞争比都至少是3/2,接着我们给出了一个竞争比为1+(?)/2的在线算法.在第五章中,我们主要研究了机器有到达时间的在线和半在线排序问题,其中工件的到达方式是按序在线到达.对机器有到达时间且允许重排的两台恒同机上的在线排序问题,我们研究了两种不同的模型,允许重排任意k个工件的模型和允许重排每台机器上的最后一个工件的模型.对这两种模型我们分别给出了竞争比为4/3和(?)的最好可能的在线算法.对于具有服务等级且机器有到达时间的两台恒同机上的在线和半在线排序问题,我们分别给出了修正的在线算法,并且这两个算法都是最好可能的.(本文来源于《上海大学》期刊2011-04-01）
在线和半在线排序论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
在线和半在线排序论文参考文献
[1].周燕.带有机器故障的半在线排序问题[D].中国矿业大学.2019
[2].邵晶晶.两个带机器准备时间的半在线排序[J].广西科技师范学院学报.2017
[3].唐峰,聂劲.平行机上订单半在线排序的LS算法的性能比分析[J].系统工程.2016
[4].姬赛.两类半在线排序模型的算法性能分析[D].湖南师范大学.2016
[5].荣建华,彭丽,张玲玲,侯丽英.一个可中断叁台可拒绝平行机半在线排序问题[J].重庆师范大学学报(自然科学版).2016
[6].孙立娟.工件加工时间有界的两台同类机半在线排序问题研究[D].华东理工大学.2015
[7].周昊.已知总和的可中断半在线排序算法[J].浙江树人大学学报(自然科学版).2015
[8].闵啸,刘静,朱俊蕾,姜明.拒绝可缓冲的2台同类机半在线排序问题的近似算法[J].浙江大学学报(理学版).2014
[9].李蒙,孙秋媚,封汉颖.预知两种信息带准备时间的两台同型机半在线排序[J].数学的实践与认识.2011
[10].侯丽英.具有服务等级的在线和半在线排序及其相关问题[D].上海大学.2011