导读:本文包含了分批排序论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:在线,工件,算法,时间,费用,多项式,竞争。
分批排序论文文献综述
李文华,翟威娜,柴幸,高超[1]（2019）在《具有两个不相容工件族单位工件的有界分批在线排序问题》一文中研究指出研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为■的最好可能的在线算法.(本文来源于《运筹学学报》期刊2019年04期）
王利博[2]（2019）在《线性退化工件的分批在线排序问题》一文中研究指出在许多工件加工的实际场景中,工件的加工时长随着其开工时间的增大而增大.这种现象称为工件的退化效应.本篇论文研究了具有线性退化效应的工件和工件集族的分批在线排序问题.工件Jj的加工时长为pj=αjt,其中αj>0为工件的退化率,t为工件的开工时间.工件的到达时间是未知的,工件的退化率只有在工件到达之后才能知道.分批是指一个批次能同时处理b个工件,在同一批次中加工的工件有相同的开工时间、加工时间和完工时间,批的加工时长为该批中工件的最大加工时长.根据一批内能容纳的工件个数,可以分为批容量无界(b>∞)和批容量有界(b<∞)两种情形.工件集族是指所有的工件都来自于某一个集族,且来自不同工件集族的工件不能放在同一批加工.第二章讨论了单机上退化工件的分批在线排序模型,目标是使得最大完工时间最小.对于批容量无界的情形,本章证明了该问题的下界并给出与下界匹配的在线算法,即给出竞争比为1+αmax的最好可能的在线算法,其中αmax为所有工件退化率的最大者.对于批容量有界且工件只有两个到达时间的情形,本章同样给出竞争比为1+αmax的最好可能的在线算法.第叁章讨论了单机上批容量无界的退化集族工件的在线排序,目标是使得最大完工时间最小.工件集族的个数f是提前知道的.本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为(1+αmax)f的最好可能的在线算法,其中αmax为所有工件退化率的最大者.第四章讨论了 m台恒同平行机上退化工件的在线分批排序,目标是使得最大完工时间最小.所有的工件有相同的退化率α,其中α>0.同样考虑了批容量无界和批容量有界两种情形.关于批容量无界的情形,本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为1+β的最好可能的在线算法,其中β满足(1+β)m = 1+α;关于批容量有界的情形,给出了竞争比为1+α的最好可能的在线算法.第五章讨论了 m台恒同平行机上批容量无界的退化集族工件的在线排序,目标是使得最大完工时间最小.所有的工件来自m个不同的工件集族.本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为1+αmax的最好可能的在线算法,其中αmax为所有工件的最大退化率.(本文来源于《郑州大学》期刊2019-04-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年04期）
何程,韩鑫鑫[5]（2018）在《同时最小化最大费用和最大完工时间的双代理无界平行分批排序》一文中研究指出有两个代理A和B,每个代理都各自有一个工件集.同一个代理的工件可以在同一批中加工,而且每一个代理都有一个需要最小化的函数.研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题,并给出一个算法,它可在多项式时间内找到关于这个问题的所有Pareto最优点.(本文来源于《运筹学学报》期刊2018年03期）
林浩,何程[6]（2018）在《关于最小化最大延迟的分批排序问题的一个动态规划算法的注解（英文）》一文中研究指出In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n~2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.(本文来源于《数学季刊(英文版)》期刊2018年02期）
何程,韩鑫鑫[7]（2018）在《具有一致性的双代理有界序列分批排序问题》一文中研究指出本文考虑带有两个代理工件的同时最小化A代理的时间表长和B代理的最大延迟的有界序列分批排序问题。不同代理的工件不可在同一批中加工,且不同代理的费用函数只和自身代理的工件有关。当工件的加工时间和工期具有一致性时,我们给出了找到该问题所有Pareto最优点的一个多项式时间算法。(本文来源于《安阳师范学院学报》期刊2018年02期）
邹柯[8]（2018）在《目标考虑权重和运输时间的在线分批排序》一文中研究指出排序论作为运筹学的重要研究方向,是运筹学学科中最热门的领域之一,同时也是组合最优化理论的重要组成部分.其中,大量不同的机器环境和工件特征以及不同目标函数所产生的排序模型,被国内外学者们广泛研究,得到了丰富的的理论成果.对于不同的排序模型,按照工件的性质可分为离线排序和在线排序.在离线排序模型中,所有工件的信息在安排前都已经获知;而在线排序模型中,工件的所有信息只有在其到达之后才知道.因此在线排序下,决策者只能依据当前已经到达工件的信息来做出决策.在具有前瞻区间的在线排序中,即Lookahead模型,在线算法在任意决策时刻i都能提前预知在时间区间(t,t +β]内所有工件的信息,从而使决策者做出更合理的决策.对于不同的分批排序模型,按照分批的方式可分为平行分批和继列分批.在平行分批模型中,一个机器可以把多个工件作为一批同时加工,该分批的加工时间等于该批中工件的最大加工时间,一个批中的所有工件具有相同的开工时间和完工时间.在继列分批模型中,一个机器可以把多个工件作为一批依次加工,该批的加工时间等于该批中所有工件的加工时间之和,一个批的完工时间等于该批中最后一个工件的完工时间.另外,排序模型按照分批的容量可分为批容量有界和批容量无界,这里分批的容量是指一个分批最多所能加工工件的数量.工件带有运输时间的在线排序,是指工件加工完成后可以让运输工具将其运输到目的地,进而考虑目标函数使得最小化最大运输完工时间.工件带有权重的排序模型,是指赋予工件一定的权重,即考虑工件单位时间的消耗,使其在完工时间内的总消耗达到最小,进而考虑目标函数使得最小化最大加权完工时间.本篇文章我们研究的是几种不同加工机器上带有批处理的分批在线排序问题,所研究的模型用排序叁参数法表示记为:(1)1|online,p-batch,pj =1,qj,b<∞,LKβ|Lmax.(2)Pm|online,p-batch,pj:= 1,b =-∞| max{wjCj}.(3)1|online,p-batch,pj = 1,b<∞,anti-agreeable(rj,wj),LKβ|max{wjCj}.模型(1)的基本概述:在该模型中,我们所研究的是带有运输时间和前瞻区间的单机有界平行分批在线排序问题,目标函数是最小化最大运输完工时间.在该模型中,假设工件具有相同的加工时间pj = 1,且考虑批容量有界.我们给出该模型的下界,并且提供了该模型的一个在线算法,证明了当0 ≤ 0 ≤ 1/6时,该在线算法是竞争比为1 + α的最好可能的在线算法,其中模型(2)的基本概述:在该模型中,我们所研究的是带有工件权重的多机无界平行分批在线排序问题,目标函数是最小化最大加权完工时间.在该模型中,所有工件按时在线到达,每个工件Jj都有一个到达时刻rj,且假设每个工件都有相同的加工时间p= 1.工件按照分批进行加工,每批可加工的工件个数不受限制,也就是说批容量无界.我们给出了该模型的下界,并且提供了一个在线算法,使得该在线算法的竞争比与该模型的下界相匹配,从而证明了该在线算法是一个最好可能在线算法.模型(3)的基本概述:在该模型中,我们所研究的是带有工件权重和前瞻区间的单机有界平行分批在线排序问题,目标函数是最小化最大加权完工时间.在该模型中,所有工件按时在线到达,每个工件Jj都有一个到达时刻rj,且假设每个工件都有相同的加工时间p=-1,每个工件的权重记为wj.工件按照分批进行加工,每批可加工的工件个数受到限制,也就是说批容量有界.在此模型中,我们考虑一种特殊情形,即使得工件的权重与工件的到达时间反一致化考虑.也就是说,对于任意两个工件Ji与Jj,当满足ri<rj时,要求满足wi≥wj.我们证明了对于该模型不存在在线算法的竞争比小于1 + α,其中α为方程α2 +(β+1)α+β-1 = 0的正根(0 ≤ β ≤ 1).最后我们提供了一个在线算法Hb(α*,β),证明了当0 ≤ β ≤ 1/6时,该算法的竞争比与所给出的模型下界相吻合,从而证明了在0≤β≤1/6时,该在线算法是一个最好可能的在线算法;而当β>1/6时,证明了该算法的竞争比为3/2.α是方程α2 +(β+1)α + β-1 = 0的一个正根;当β>1/6时,该在线算法的竞争比为3/2.(本文来源于《郑州大学》期刊2018-04-01）
孟凡晓[9]（2018）在《基于退化效应的可拒绝分批排序问题》一文中研究指出排序问题是一类典型的组合优化问题,是运筹学的一个重要分支.带退化效应及可拒绝分批排序是产生于实际的现代排序新模型.对于该模型,就极小化接收工件的最小化最大完工时间与拒绝工件的拒绝费用之和等目标问题,本文进行了算法设计与分析,并探讨了退化效应的两台机器流水作业可拒绝排序问题,具体如下:第一章简要介绍了排序问题的基本概念,比如问题的复杂性和近似算法等.同时,阐述了相关的几种排序模型以及相应的理论背景和实际应用前景.第二章主要介绍了带有退化效应的批容量有限的可拒绝批排序问题.对于工件具有统一到达时间情形,给出了基于动态规划的伪多项式时间算法并设计了该问题的全多项式时间近似方案(FPTAS).对于工件有8)个不同的到达时间的更为复杂的情况下,设计了伪多项式时间算法和2-近似算法并进行了算法分析.第叁章主要介绍了带有退化效应的批容量无限的可拒绝批排序问题.工件具有统一的到达时间.对于最小化接受工件的最大完工时间与拒绝工件的拒绝费用之和问题,我们给出了一个多项式时间算法.对于最小化接受工件的加权总完工时间与拒绝工件的拒绝费用之和问题,我们首先分析了问题的NP-困难性并设计了一个伪多项式时间动态规划算法,然后就权重相等的特殊情形设计了FPTAS.第四章讨论了在具有退化效应的工件在两台流水作业机器下的可拒绝排序问题,目标函数为接收工件的最小化最大完工时间与拒绝工件的拒绝费用之和时,我们分析了问题的计算复杂性,设计了动态规划算法并就特殊情况提出了多项式最优算法.(本文来源于《曲阜师范大学》期刊2018-03-28）
酒明珠,高园,原晋江[10]（2018）在《工件可自由下线最小化总完工时间的有界平行分批排序》一文中研究指出考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批■有一个开工时间S,那么包含在批■中的每一个工件乃的开工时间定义为S,而它的完工时间定义为S+p_j,这里p_j是工件J_j的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(n~(b(b-1))的动态规划算法.(本文来源于《运筹学学报》期刊2018年01期）
分批排序论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
在许多工件加工的实际场景中,工件的加工时长随着其开工时间的增大而增大.这种现象称为工件的退化效应.本篇论文研究了具有线性退化效应的工件和工件集族的分批在线排序问题.工件Jj的加工时长为pj=αjt,其中αj>0为工件的退化率,t为工件的开工时间.工件的到达时间是未知的,工件的退化率只有在工件到达之后才能知道.分批是指一个批次能同时处理b个工件,在同一批次中加工的工件有相同的开工时间、加工时间和完工时间,批的加工时长为该批中工件的最大加工时长.根据一批内能容纳的工件个数,可以分为批容量无界(b>∞)和批容量有界(b<∞)两种情形.工件集族是指所有的工件都来自于某一个集族,且来自不同工件集族的工件不能放在同一批加工.第二章讨论了单机上退化工件的分批在线排序模型,目标是使得最大完工时间最小.对于批容量无界的情形,本章证明了该问题的下界并给出与下界匹配的在线算法,即给出竞争比为1+αmax的最好可能的在线算法,其中αmax为所有工件退化率的最大者.对于批容量有界且工件只有两个到达时间的情形,本章同样给出竞争比为1+αmax的最好可能的在线算法.第叁章讨论了单机上批容量无界的退化集族工件的在线排序,目标是使得最大完工时间最小.工件集族的个数f是提前知道的.本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为(1+αmax)f的最好可能的在线算法,其中αmax为所有工件退化率的最大者.第四章讨论了 m台恒同平行机上退化工件的在线分批排序,目标是使得最大完工时间最小.所有的工件有相同的退化率α,其中α>0.同样考虑了批容量无界和批容量有界两种情形.关于批容量无界的情形,本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为1+β的最好可能的在线算法,其中β满足(1+β)m = 1+α;关于批容量有界的情形,给出了竞争比为1+α的最好可能的在线算法.第五章讨论了 m台恒同平行机上批容量无界的退化集族工件的在线排序,目标是使得最大完工时间最小.所有的工件来自m个不同的工件集族.本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为1+αmax的最好可能的在线算法,其中αmax为所有工件的最大退化率.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
分批排序论文参考文献
[1].李文华,翟威娜,柴幸,高超.具有两个不相容工件族单位工件的有界分批在线排序问题[J].运筹学学报.2019
[2].王利博.线性退化工件的分批在线排序问题[D].郑州大学.2019
[3].彭南南,张玉忠,柏庆国,王成飞.工件满足一致性的同类机在线分批排序问题[J].运筹学学报.2019
[4].王磊,柏庆国,徐健腾,任建峰.两代理具有可拒绝的单机分批配送排序问题[J].应用数学.2018
[5].何程,韩鑫鑫.同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J].运筹学学报.2018
[6].林浩,何程.关于最小化最大延迟的分批排序问题的一个动态规划算法的注解（英文）[J].数学季刊(英文版).2018
[7].何程,韩鑫鑫.具有一致性的双代理有界序列分批排序问题[J].安阳师范学院学报.2018
[8].邹柯.目标考虑权重和运输时间的在线分批排序[D].郑州大学.2018
[9].孟凡晓.基于退化效应的可拒绝分批排序问题[D].曲阜师范大学.2018
[10].酒明珠,高园,原晋江.工件可自由下线最小化总完工时间的有界平行分批排序[J].运筹学学报.2018
论文知识图
