导读:本文包含了平行机论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:批处理,算法,差异,机器,工件,权重,容量。
平行机论文文献综述
苟燕,戴秦,张新功[1]（2019）在《具有时间与位置相关的两类平行机排序问题》一文中研究指出研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O(n~(k+2))/((k-1)!).同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O((2n+m+n log n)n~(k-1))/((k-1)!).(本文来源于《运筹学学报》期刊2019年04期）
蒋义伟,周萍,马春磊[2]（2019）在《带有装卸服务器的两台平行机调度问题的LS和LPT算法》一文中研究指出研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章主要分析LS和LPT两个经典的启发式算法,分别证明了这两个算法的紧界为11/7和7/6改进了已有结果.(本文来源于《系统科学与数学》期刊2019年08期）
汪俐敏[3]（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）
叶拥军[4]（2019）在《带有潜在扰动的平行机问题》一文中研究指出现代工业生产经常在一个动态的,不确定的环境中运行,在这种环境中,有时会发生意外事件.如果预期事件发生中断,它们可能会导致某些资源(机器或设备)在某一段时间内无法使用,这将直接影响资源的利用和任务完成情况.在生产过程中发生的破坏性事件比比皆是,如机器故障,电源故障,恶劣天气(台风、雪灾),运输耽误和原材料的短缺,这些情况将会使机器中断,但中断的开始时间大约是己知的(会发生):然而中断的持续时间是未知的.因此带有潜在扰动状况的研究具有重要的理论价值和实际意义.本文主要研究带有潜在扰动的平行机问题.在工件恶化及维修区间限制下,考虑了工件加工状况为不可恢复和可恢复的情况.1.带有潜在扰动的平行机问题(不可恢复情况).机器在某一个特殊时刻会发生扰动,工件的实际加工时间会随着机器的磨损程度增加,即工件退化.在发生扰动的机器上会随机的采取一次维修服务且维修是在某个工件加工完工之后进行,维修之后的机器的磨损程度会清除,即此时的机器的状态与新的机器是一样的,针对工件的加工状况为不可恢复,使目标函数为带有期望的总完工时间最小,基于SPT规则对加工序列的优化,提出了拟多项式时间算法并给出了算法时间复杂度.2.带有潜在扰动的平行机问题(可恢复情况).工件的加工状况为可恢复情况,即被扰动中断的加工工件可接着己加工的部份继续加工,对维修区间分叁种情况考虑:维修区间在扰动区间之前,维修区间与扰动区间有重迭的部份或者是连续的,维修区间在扰动区间之后.针对每种情况提出了拟多项式时间算法,给出了相应的时间复杂度的证明.(本文来源于《重庆师范大学》期刊2019-05-01）
张家宝,许志军[5]（2019）在《部分机器需要周期维护的混合型平行机调度问题的数学规划模型》一文中研究指出对于部分机器需要周期维护,其余机器在所考虑的时间范围内一直可用的混合型平行机调度问题,分别采用基于机器拆分的建模思想和基于机器拼接的建模思想构建该调度问题的数学规划模型。(本文来源于《佳木斯大学学报(自然科学版)》期刊2019年02期）
柴幸[6]（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）
张晗[7]（2019）在《最小化总完工时间的差异平行机批调度算法研究》一文中研究指出生产调度问题是一个相对复杂的组合优化问题,存在于许多应用领域,如铸造业、金属加工业、物流业、通信业等。生产调度的主要任务是在生产过程中通过合理地分配资源,从而提升资源利用率以及生产效率。随着时代发展和技术革新,生产调度问题变得越来越复杂,针对此类问题的研究逐渐拓展到批调度问题。批调度问题是经典调度问题的拓展,其复杂性在于批处理机一次可以加工多个工件。虽然在批调度问题的求解过程中需要同时考虑工件的分组与调度,增加了问题求解难度,但这极大地提高了生产系统的生产率。本文首先简单介绍了生产调度问题的相关研究背景,然后按照批调度问题的机器运行环境进行分类介绍,并简要介绍了求解批调度问题的常用算法,包括精确求解算法、启发式算法和元启发式算法。本文接着针对在差异容量的并行批处理机上加工差异尺寸工件的问题进行研究,以最小化工件的总加权完工时间。在描述所研究问题后给出问题的混合整数规划模型,随后提出了一个求解下界的算法,以评价算法的有效性,并提出了一个启发式算法对问题进行求解。然后,分别基于蚂蚁系统和最大最小蚂蚁系统设计改进算法来解决该问题。在蚂蚁构建解的过程中,采用基于工件权重的首工件选择策略,同时为了降低解构建过程的复杂度,根据当前批的剩余容量构建候选列表以缩小搜索范围。为了有效地指导蚂蚁搜索解,本文基于已构建的候选列表设计了一种新的启发式信息。对于蚂蚁构建解,利用提出的邻域搜索策略进行优化,进一步提高解的质量。大量的仿真实验对本文提出的算法进行验证,并与两种已有的元启发式算法即随机密钥遗传算法(Random keys genetic algorithm,RKGA)和粒子群算法(Particle swarm optimization,PSO),进行对比。为了比较机器容量设置对算法性能的影响,本文分别在两种和叁种不同机器容量的测试实例上对算法性能进行测试。然后在叁种容量的机器上,针对不同容量的机器数组合进行测试,以分析机器容量的分布对算法性能的影响。此外,仿真实验对所提算法中采用的不同策略的有效性进行了验证。最后对本文的研究工作进行总结,并对未来开展的研究工作做了进一步展望。(本文来源于《安徽大学》期刊2019-03-01）
李亚杰[8]（2019）在《考虑拒绝成本的双目标差异容量平行机批调度算法研究》一文中研究指出在日常的生产活动中,生产调度问题扮演一个很重要的角色。作为一类典型的组合优化问题,生产调度问题有很广泛的应用背景,比如港口货物装卸、物流运输业及通信领域等。研究生产调度问题的意义就是通过合理分配有限资源达到利益最大化,提高资源利用率及企业竞争力。随着社会的发展和科技的进步,生产调度问题也日益复杂,经典调度问题已经满足不了飞速发展的需求,人们将关注和研究的重心转移至批处理机调度问题,一般简称为批调度问题。批调度问题是从经典调度问题发展而来的,它们的主要区别在于批调度问题中一台机器可以同时加工多个工件,工件以成批的形式在机器上进行加工。批调度问题的问题背景比经典调度问题更复杂,涉及到的约束条件更多,也更趋向于现实中的生产情况。批调度问题的复杂性导致其难度更高,很多单机环境下的批调度问题都已经是NP难问题了,所以研究者们还在寻找更高效简便的解决问题的方法。首先,本文简要介绍了生产调度问题的研究背景及意义,然后采用经典的叁参数表示法介绍了如何对调度问题进行描述,介绍了批调度问题的主要特点及研究现状,并从单机、多机、差异机器容量、拒绝成本、目标数等五个方面对批调度问题的研究成果做了简要概述。然后,针对批调度问题,简要介绍了几种求解算法。将这些算法基本分为叁类,确定性算法、启发式算法以及元启发式算法。后又具体介绍了叁类算法的特点、框架及几个有代表性算法的描述。接着研究了考虑机器差异容量、带有拒绝的,最小化制造跨度及拒绝成本的双目标平行批调度问题。先对研究的问题进行了描述,然后提出了用于解决问题的基于帕累托的蚁群优化算法FPACO。提出了基于弱约束的首工件选择算法,并根据问题特征设计了两个候选列表来提高蚁群的搜索效率,设计启发式信息和信息素来指导蚁群的搜索行为。为了进一步改善解的质量,提出了一种基于交换的局部优化算法。最后对FPACO算法进行了详细的描述。随后简要介绍了所用的对比算法,对实验和参数的设置进行了介绍,采用仿真实验来验证所有算法的性能的优劣,通过覆盖率、解空间等四种评价指标来衡量和分析算法性能。通过实验结果可以看出,本文所提算法FPACO的算法性能明显优于其他四种对比算法。为了更直观的比较五种算法,还绘制了一些实例上解的分布图。最后一部分对本文所研究的考虑拒绝成本的弱约束双目标批调度问题以及提出来的解决算法进行了总结,并指明了未来进一步研究的方向。(本文来源于《安徽大学》期刊2019-03-01）
霍思云[9]（2019）在《差异容量平行机环境下生产与运输集成调度算法研究》一文中研究指出生产调度问题作为一类复杂的组合优化问题,广泛存在于多个应用领域,如金属工业、制药工业等。这类问题的求解主要通过合理地对有限资源进行整合与分配,以期得到最优的解决方案,从而凸显企业的竞争力。对生产调度问题的研究,逐渐从经典调度问题转变成批调度问题。现如今,企业从获得长久效益角度出发,将产品的生产与运输紧密结合,可以进一步提高客户服务水平,也因此促进了生产与运输集成调度问题的研究。生产与运输集成调度问题同时考虑产品的生产与运输两个阶段,进一步拓展了批调度问题,简称为集成调度问题。本文针对差异容量平行机环境下的集成调度问题展开研究,以最小化工件总加权运输时间。单机批调度问题已被证明是NP难问题,而两阶段集成调度问题相对更加复杂,因此本文研究的问题也是NP难的,其求解对于制造企业的生产管理与决策具有重要的指导意义。本文首先介绍了集成调度问题的研究背景及意义,再概述了批调度和集成调度问题的研究现状。然后阐述了批调度问题的基本概念及其分类,并介绍了求解批调度问题的方法,包括精确算法和近似算法。随后本文介绍了集成调度问题,并对差异容量平行机环境下的集成调度问题展开研究。首先描述了本文研究的问题,并提出了下界算法LB作为评估其他算法性能的基准,再根据机器的差异容量提出了两种启发式算法H1和H2。然后,针对本文研究的问题提出了基于蚁群优化的生产与运输集成调度算法ISACO(Integrated Scheduling Ant Colony Optimization)。在算法ISACO中,本文设计了叁类候选列表来降低搜索空间,基于平均批权值改变的启发式信息能够有效的控制蚂蚁的搜索方向,并通过局部优化策略进一步提高解的质量。接着,通过一系列仿真实验,对本文所提各算法的性能进行验证。基于下界算法LB求得的下界,将算法Hl、H2、ISACO与已有文献中的粒子群算法PSO(Particle Swarm Optimization)进行对比,从解的质量、算法运行时间两个角度衡量算法的性能,结果显示ISACO算法的性能优于其他几种算法。最后,对本文研究的差异容量平行机环境下的集成调度问题及提出的算法进行总结,并对今后的研究方向进行展望。(本文来源于《安徽大学》期刊2019-03-01）
严建海[10]（2019）在《蚁群优化算法在模糊平行机批调度问题中的应用与研究》一文中研究指出生产调度问题是一类有着极强应用背景的组合优化问题。该类问题存在于许多领域中,如:港口码头轮船的进出港顺序、物流运输、金属加工、制造业等。生产调度问题是将有限的资源进行合理的利益最大化的分配。高效合理的调度方案,将会促进企业的发展,提高了企业在同行业中的竞争力。经典调度问题随着社会高速的发展和变革,拓展为批调度问题。批调度与经典调度是不相同的,批调度是指机器在同一时刻可以加工多个工件,工件依据前期设定好的规则先构成批而后在机器上处理,批的加工时间等于批中所有工件处理时间的最大值,由于批调度问题具有复杂性和灵活性,使得求解批调度相关问题成为许多学者和专家研究的方向。现有的针对批调度问题的研究大多都建立在确定性的环境下,工件的时间参数和一些约束条件的数值事先预知,然而在现实生产环境下,由于机器的处理环境、人为因素等的影响,使得许多信息无法提前确定,存在模糊性。本文是将确定性批调度问题从理想的环境延伸到接近现实的模糊环境。模糊批调度问题作为批调度问题的重要分支,具有很强的研究价值和实际意义。首先,本文介绍了研究背景及意义,再分别对调度问题进行了描述和分类以及阐述了批调度问题和模糊批调度问题,接着又详述了单机环境、平行机环境、模糊批调度的研究现状。第二,本文介绍了求解批调度问题的常见算法,即确定性算法、启发式算法和元启发式算法叁类。同时,本文还介绍了模糊批调度问题的数学基础,包括模糊理论、模糊数、模糊数的运算。随之,本文阐述了模糊调度问题的研究方法。第叁,本文考虑了模糊工件加工时间的不相同容量平行批处理机调度,求解制造跨度最小化的问题。首先,根据该问题建立了数学模型,用叁角模糊数来表示时间参数,接着针对问题提出了下界算法。随后,提出了与决策变量乐观系数相结合的蚁群优化算法来解决该问题。通过对问题的分析,本文介绍了两个候选列表来缩短蚁群的搜索空间,同时,也介绍了解的构建方式。此外,还提出了一种局部优化策略来提高解的质量。最后,给出了针对该问题所提出的完整的算法框架。第四,为了验证针对问题所提算法的有效性,本文通过仿真实验与已有的两种算法在解的质量、时间和稳定性方面做了对比,分析了实验结果,实验的结果表明所提的算法在合理的时间范围内能够找到比其他所有算法更好的解,具有一定的优越性。同时,本文还采用了统计分析方法验证了算法得到的解具有统计学意义。第五,本文对差异机器容量和差异工件尺寸的模糊批调度问题和针对该问题所提出的算法进行了总结,同时,也阐述了未来进一步的研究方向。(本文来源于《安徽大学》期刊2019-03-01）
平行机论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章主要分析LS和LPT两个经典的启发式算法,分别证明了这两个算法的紧界为11/7和7/6改进了已有结果.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
平行机论文参考文献
[1].苟燕,戴秦,张新功.具有时间与位置相关的两类平行机排序问题[J].运筹学学报.2019
[2].蒋义伟,周萍,马春磊.带有装卸服务器的两台平行机调度问题的LS和LPT算法[J].系统科学与数学.2019
[3].汪俐敏.平行机上半在线排序模型的算法性能分析[D].湖南师范大学.2019
[4].叶拥军.带有潜在扰动的平行机问题[D].重庆师范大学.2019
[5].张家宝,许志军.部分机器需要周期维护的混合型平行机调度问题的数学规划模型[J].佳木斯大学学报(自然科学版).2019
[6].柴幸.带有工件约束的平行机排序问题的近似算法研究[D].郑州大学.2019
[7].张晗.最小化总完工时间的差异平行机批调度算法研究[D].安徽大学.2019
[8].李亚杰.考虑拒绝成本的双目标差异容量平行机批调度算法研究[D].安徽大学.2019
[9].霍思云.差异容量平行机环境下生产与运输集成调度算法研究[D].安徽大学.2019
[10].严建海.蚁群优化算法在模糊平行机批调度问题中的应用与研究[D].安徽大学.2019
论文知识图
