导读:本文包含了平行机排序论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:算法,最坏,效应,时间,在线,情况,加工。
平行机排序论文文献综述
苟燕,戴秦,张新功[1]（2019）在《具有时间与位置相关的两类平行机排序问题》一文中研究指出研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O(n~(k+2))/((k-1)!).同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O((2n+m+n log n)n~(k-1))/((k-1)!).(本文来源于《运筹学学报》期刊2019年04期）
汪俐敏[2]（2019）在《平行机上半在线排序模型的算法性能分析》一文中研究指出本篇论文主要是研究半在线模型下的算法设计以及算法性能比分析。论文主要分为四章内容,第一章为绪论部分,首先介绍了组合优化问题的定义以及其研究意义,然后就组合优化问题中典型的排序问题进行背景、分类、研究现状等多方面叙述,最后引入近似算法的概念和基本思想并介绍Pm和本文我们所构造的S形算法。第四章是对整篇文章做了一个总结,并提出了今后研究工作可能的方向。主体内容将分别在第二章和第叁章中展开详细证明。第二章:我们构造了S形算法,证明了当m=2时,对于任意的工件序列L={J1,J2,…,Jn},加工时间非递增(p1 ≥ p2≥…≥ pn),工件具有相似的加工时长pj ∈[1,r](1 ≤ r ≤ 2)时,其最坏性能比为:而在Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet 1996年([20])给出的算法P(2)中,其最坏性能比为CmaxP2/CmaxOPT(L≤4/3,后证得即使加入工件具有相似的加工时长pj∈[1,r](r≥1)这一约束后该算法的最坏性能比仍不变,始终有supLCmaxP2/CmaxOPT(L)=4/3但是在S形算法中我们通过限定工件加工时长得到了更好的结果。第叁章:本章证明了对于任意的工件序列L={J1,J2,...,Jn},工件满足加工时长非递增,到达时间不都为零且非递减(即p1 ≥ p2 ≥...≥pn,r1≤r2≤...≤rn)时,Pm算法的最坏性能比为本章主要是对文献[11]做了相关的修正,并且优化了该算法的最坏性比能,从而得到了更加精确的结果。(本文来源于《湖南师范大学》期刊2019-05-01）
柴幸[3]（2019）在《带有工件约束的平行机排序问题的近似算法研究》一文中研究指出排序理论作为组合优化领域的一个重要组成部分,具有重要的理论意义和实际应用价值.排序实际是一种决策过程.在经典的离线排序中,决策者根据所有的信息进行决策.在线排序中,工件的所有信息是分阶段逐步释放给决策者的,并且决策者只能根据当前已有的信息来做决策和安排工件.本论文主要考虑几类工件带有约束的排序问题:工件带有链组约束关系是指工件间的序约束关系是一条链,每个工件在它的前任都完工后才可以加工;工件带有权重是指工件具有优先因子,一般表示该工件的重要性或紧急程度;工件带有限选机器集,是指每个工件只能在指定的部分机器上进行加工.此外在批处理机上,多个工件可以作为一批同时加工,此时批的加工长度等于该批中最长工件的加工长度.每批中至多可加工的工件个数称为批容量:当批容量B不小于需要被加工的工件总个数n时,称为批容量无界模型;反之称为批容量有界模型.第一章介绍了一些排序理论的知识,着重介绍了与本论文相关的排序研究的现状,并列举了一些主要结果.第二章中考虑m台平行机上工件带有链组约束的在线排序,工件具有相同的加工长度,目标是最小化最大完工时间.该问题在m=2时已经被解决,我们考虑m≥3的情形.首先证明该问题在线算法竞争比的下界为1+α_m,其中当3≤m≤5时,α_m是方程α_m~2+3α_m-1=0的唯一正根;当m≥6时,α_m是方程α_m~3+4α_m~2+5α_m-2=0的唯一正根.其次给出达到该竞争比的最好可能的在线算法.第叁章中考虑m台批处理机上工件带有链组约束的在线排序,工件具有相同的加工长度,目标是最小化最大完工时间.机器具有不小于2的有界批容量.我们指出该问题在线算法竞争比的下界为(?),并给出达到该竞争比的最好可能的在线算法.第四章中考虑m台一致批处理机上工件带有权重的在线排序,工件具有相同的加工长度,目标是最小化加权完工时间和.机器的批容量无界B≥n.在m台机器中,前λ(λ≥2)台机器的速度为s(s≥1),后m-λ台机器的速度为1.我们首先证明该问题在线算法竞争比的下界为ρ=min{1+θ,1+η},其中θ和η是分别是方程(1+θ)~(λ+1)=2+θ和(?)的唯一正根.其次给出达到该竞争比的最好可能的在线算法.第五章中考虑m台批处理机上最小化最大加权流程时间的在线排序.工件带有相同的加工长度以及在一给定范围内的权重w_j∈[1,w].首先当批容量无界B≥n时,我们证明该问题在线算法竞争比的下界为(?),并给出达到该竞争比的最好可能的在线算法;其次当批容量有界且不小于2时,对w=2情形给出竞争比为2的最好可能的在线算法.此外对于单台机上批容量有界2≤B<n时的一般情形w_j∈[1,w],我们证明该问题在线算法竞争比的下界为(?),并构造对应的在线算法.该在线算法在w∈[1,2]时,竞争比为(?),是最好可能的在线算法;在w∈(2,+∞)时,竞争比不大于w.第六章中考虑工件带有限选机器集的两个离线排序问题,机器具有有界的批容量,目标是最小化最大完工时间.对批处理机上工件带有嵌套关系的限选机器集的问题,我们给出强多项式时间算法,并证明该算法在机器批容量不同和相同时分别是2-近似的和(2-1/m)-近似的.该结果改进了已知的仅适用于批容量相同情形的(3-1/m)-近似的算法.对一致批处理机上工件带有树形关系的限选机器集的问题,当批容量不同时,我们给出了2-近似的快速算法.该结果改进了已知的仅适用于批处理机上工件带有包含关系的限选机器集的9/4-近似的算法.此外当批容量相同时,给出更好的(2-1/m)-近似的算法.(本文来源于《郑州大学》期刊2019-03-01）
岳娇[4]（2019）在《JIT系统中带学习效应和退化工件的平行机排序问题》一文中研究指出本文研究在JIT系统中工件加工受学习和退化影响的共同工期指派和平行机排序问题,论文分别对极小化提前、延误和1工期的加权和问题(minimize∑(αEj+βTj+γd))与极小化提前费用、加权误工工件数与工期费用之和的问题(minimize∑f(Ej)+∑ejUj+g(d),其中f、g分别是工件提前费用函数、工期费用函数)进行研究,目标是找到最优工期d*和最优排序π*,使目标函数f(d,π)最小.文章根据文献中的已有结论,先对问题的算法复杂性进行理论分析,然后为其特殊情况寻找多项式时间最优算法.首先,对于极小化提前与延误的加权和问题,本文分别研究了Pm|pj=(pj0+bsj)ra|∑(αEj+βTj)和Pm|pj=pj0raj+bsj|∑(αEj+βTj),证明了分别存在时间复杂度为O(nm log n)和O(nm+2)的最优算法.其次,对于极小化提前和误工工件数加权和∑(αEj+ejUj)的问题,分别对之前两种实际加工时间模型进行研究,通过转化为指派问题均能在O(nm+3)时间内给出最优解.最后,对带退化工件和加工等级限制的问题Pm |pj=pj0+bjtj,GOS|∑ejUj+γd给出一个全多项式时间近似方案(FPT AS),时间复杂度为O(n2m+2Lm+2/εm+1).对各问题的扩展形式也分别给出了相应的结论.(本文来源于《兰州大学》期刊2019-03-01）
程佳乐,李伟东[5]（2018）在《具有树和路约束的平行机排序问题》一文中研究指出考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论:在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。(本文来源于《计算机工程与科学》期刊2018年12期）
马春磊,胡觉亮,蒋义伟[6]（2019）在《带有装卸服务器的叁台平行机排序问题的LS算法》一文中研究指出针对一个装载服务器和一个卸载服务器的情形,研究叁台平行机上的排序问题。每个工件在加工前需要由装载服务器安装到机器上,加工结束后由卸载服务器进行卸载。装载和卸载时间均为单位时间,目标是极小化最大完工时间。该问题是NP-难问题,因此采用经典的List scheduling(LS)算法进行求解。通过引入块的概念对LS排序的结构进行分析,进而证明了LS算法的最坏情况界至多为17/9。(本文来源于《浙江理工大学学报(自然科学版)》期刊2019年01期）
赵晓成,李大刚[7]（2018）在《机器和工人都有加工资质约束的平行机排序问题研究》一文中研究指出研究一类新型的平行机排序问题,即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下,如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_(max).将研究工件加工时间均为单位时间的情况,通过建立网络流模型以及采用二分搜索技术,可以在多项式时间内精确地求解上述问题,算法复杂度为O(n~3logn).同时提供了一种基于双重动态柔性选择(DDFS)策略的启发式算法,可以获得较好的排序效果,算法复杂度为O(n~2).(本文来源于《运筹学学报》期刊2018年03期）
王超[8]（2018）在《一些新型平行机排序问题和路线问题的算法设计与性能分析》一文中研究指出本文主要研究了一些新型平行机排序问题和路线问题,包括工件有加工机器限制的排序问题、带有缓冲器的平行机排序问题、遍历每条边的修理员问题以及货运码头堆场排序问题。我们分析了这些问题的复杂性,设计了相应的算法,理论分析了这些算法的性能,并对部分算法进行数值模拟来验证算法的有效性。第一章介绍了组合优化问题的背景,阐述了一些本文涉及的理论知识,例如算法复杂性、NP完备理论、线性规划的舍入以及匹配的相关概念和定理,最后介绍了排序问题和路线问题的定义以及所研究问题的国内外研究状况。第二章研究了工件有加工机器限制的排序问题,给定m台机器和n个工件,每个工件Jj只能选择在给定的一个机器集合Mj上加工,加工时间为pj,目标是极小化时间表长。首先,当任意工件Jj均有|Mj| = 2时,我们给出了一个1.883-近似算法。然后我们分析了当工件的加工机器集合Mj为一个连续区间的情形:证明了当工件只有两种大小,且大工件大于1/2倍目标值时,这个问题是可解的;当所有工件的|Mj|均相等时,我们设计了一个PTAS。最后,我们给出一些负面结果.:考虑工件至多能在叁台变速机上加工,如果该问题有(2-ε)近似算法,则经典问题R||Cmax也会有(2-ε)-近似算法;考虑异速机上的Graph Balancing问题,如果该问题有(2-ε)-近似算法,则Unrelated Graph Balancing 问题也会有(2-ε)-近似算法。第叁章研究了带有缓冲器的平行机排序问题,目标是极小化完工时间之和。在该问题中,工件的顺序给定。如果没有缓冲器,我们只能按照这个顺序依次安排工件到机器上加工;如果工件在加工之前需进入容量为κ的缓冲器,我们可以在缓冲器中的κ个工件中随意挑选一个来加工,所以缓冲器可以让我们一定程度的修改工件顺序。首先,我们给出了反例,说明按照经典排序问题的排序规则无法得到最优解。然后当机器数量和缓冲器容量均给定的情况下,我们设计了一个多项式时间的动态规划算法。最后证明若机器数量是任意的,即使缓冲器容量为1,其加权完工时间和问题也是强NP-困难的。第四章考虑了一个路线问题。对一个图,我们从出发点开始寻找一条路线,使得该路线访问每条边至少一次,使得所有边的访问时间之和最小,这里每条边的访问时间可理解为边上有若干“点”的访问时间之和。该问题不同于经典的中国邮递员问题或者旅行售货员问题,是旅行修理员问题的一种特殊情形,我们称为遍历边的修理员问题。我们证明了这个问题无论在有向图还是无向图下均是NP-困难的,并设计了一个(?)近似算法。当图是二连通时,我们给出了一个4/3-近似算法。第五章我们研究了一个货运码头堆场排序问题,堆场上有多台取料机同时作业来完成任务,每台机器占据一条直线轨道,原材料成堆的存放在轨道两边,机器需要先移动到原材料的位置,然后开始加工采集。如何给机器分配加工任务和加工顺序,极小化时间表长。当机器允许同时加工同一位置上的原材料时,我们设计了一个FPTAS。当机器不允许同时加工同一位置的材料时,我们设计了一个2-近似算法,并对只有两台机器的情形,我们设计了一个3/2-近似算法,最后对这两个近似算法使用数值模拟来验证算法的有效性。第六章对本文进行总结,并提出一些今后可以继续研究的方向。(本文来源于《华东理工大学》期刊2018-04-10）
郭苗苗,刘桓,王吉波,牛玉萍[9]（2018）在《具有学习效应和加工时间可控的平行机排序问题》一文中研究指出本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n~(m+2)),最后也给出了相应的数值例子来阐述该问题。(本文来源于《运筹与管理》期刊2018年03期）
马春磊[10]（2018）在《带服务器的平行机排序问题研究》一文中研究指出带服务装置的平行机调度问题在现代柔性制造中有着重要的应用背景.本文主要研究带一个装载服务器和一个卸载服务器的平行机调度问题,都是以极小化最大完工时间作为我们的研究目标.分别在两台平行机和叁台平行机情形下,分析了经典的LS算法和LPT算法的最坏情况界的情况.全文共分五章:在第一章中,简要地介绍了调度问题的基本知识和本文所要研究的带服务器的调度问题的相关背景、这些问题的研究现状和我们在文中所要研究的问题.在第二、第叁章中,研究带有装、卸服务器的两台平行机调度问题.每个工件在加工之前需要由一个装载服务器装载到两台机器中的一台机器上,在加工完成之后再由卸载服务器把工件从平行机上卸载下来,这里的装、卸载的时间均为单位时间,目标是极小化最大完工时间.第二章中主要研究两台平行机情形的LS算法(List Scheduling)的最坏情况界问题,证明了该算法下的紧界为_7~(11).第叁章中主要研究两台平行机情形的LPT算法的最坏情况界,证明了该算法下最坏情况紧界为_6~7.上述结果改进了已有文献中的结果.在第四章中,研究带有装卸服务器的叁台平行机情形,分析了LS算法的最坏情况界至多为_9~(17).第五章对全文进行总结并提出相关问题以及进一步的研究方向.(本文来源于《浙江理工大学》期刊2018-03-12）
平行机排序论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本篇论文主要是研究半在线模型下的算法设计以及算法性能比分析。论文主要分为四章内容,第一章为绪论部分,首先介绍了组合优化问题的定义以及其研究意义,然后就组合优化问题中典型的排序问题进行背景、分类、研究现状等多方面叙述,最后引入近似算法的概念和基本思想并介绍Pm和本文我们所构造的S形算法。第四章是对整篇文章做了一个总结,并提出了今后研究工作可能的方向。主体内容将分别在第二章和第叁章中展开详细证明。第二章:我们构造了S形算法,证明了当m=2时,对于任意的工件序列L={J1,J2,…,Jn},加工时间非递增(p1 ≥ p2≥…≥ pn),工件具有相似的加工时长pj ∈[1,r](1 ≤ r ≤ 2)时,其最坏性能比为:而在Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vliet 1996年([20])给出的算法P(2)中,其最坏性能比为CmaxP2/CmaxOPT(L≤4/3,后证得即使加入工件具有相似的加工时长pj∈[1,r](r≥1)这一约束后该算法的最坏性能比仍不变,始终有supLCmaxP2/CmaxOPT(L)=4/3但是在S形算法中我们通过限定工件加工时长得到了更好的结果。第叁章:本章证明了对于任意的工件序列L={J1,J2,...,Jn},工件满足加工时长非递增,到达时间不都为零且非递减(即p1 ≥ p2 ≥...≥pn,r1≤r2≤...≤rn)时,Pm算法的最坏性能比为本章主要是对文献[11]做了相关的修正,并且优化了该算法的最坏性比能,从而得到了更加精确的结果。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
平行机排序论文参考文献
[1].苟燕,戴秦,张新功.具有时间与位置相关的两类平行机排序问题[J].运筹学学报.2019
[2].汪俐敏.平行机上半在线排序模型的算法性能分析[D].湖南师范大学.2019
[3].柴幸.带有工件约束的平行机排序问题的近似算法研究[D].郑州大学.2019
[4].岳娇.JIT系统中带学习效应和退化工件的平行机排序问题[D].兰州大学.2019
[5].程佳乐,李伟东.具有树和路约束的平行机排序问题[J].计算机工程与科学.2018
[6].马春磊,胡觉亮,蒋义伟.带有装卸服务器的叁台平行机排序问题的LS算法[J].浙江理工大学学报(自然科学版).2019
[7].赵晓成,李大刚.机器和工人都有加工资质约束的平行机排序问题研究[J].运筹学学报.2018
[8].王超.一些新型平行机排序问题和路线问题的算法设计与性能分析[D].华东理工大学.2018
[9].郭苗苗,刘桓,王吉波,牛玉萍.具有学习效应和加工时间可控的平行机排序问题[J].运筹与管理.2018
[10].马春磊.带服务器的平行机排序问题研究[D].浙江理工大学.2018
论文知识图
