导读:本文包含了最大完工时间论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:在线,时间,算法,效应,流水作业,分枝,处理机。
最大完工时间论文文献综述
刘鹏,王小丽[1]（2019）在《加工时间与位置相关的最小化最大完工时间两人合作排序博弈》一文中研究指出【目的】针对加工时间与加工位置相关的两人合作排序博弈问题开展研究。【方法】工件加工时间与加工位置相关可以描述为工件加工时间随着加工序列中工件加工位置的改变而呈现出递增或递减的函数变化。两个人必须合作加工一批工件,两人各自都有一台机器可用于加工这批工件,且他们的加工成本定义为各自的最小完工时间。目标是使得他们的合作收益最大化,为了使这两个人的合作总收益最大化,需对这批工件进行一个划分,把工件分配给两台机器。【结果】提出了该问题有正整数解的充分必要条件。【结论】证明了该问题是多项式可解的。(本文来源于《重庆师范大学学报(自然科学版)》期刊2019年06期）
张新功,陈娟[2]（2019）在《两阶段供应链下极小化最大完工时间的单机系列批排序》一文中研究指出【目的】考虑单机情况下的加工和运输两阶段的供应链排序问题。【方法】在生产阶段,将所有工件在加工之前划分成批,在一台有限批容量的机器上加工,工件的实际加工时间是关于该工件退化率和加工位置的函数;在运输阶段,有一辆运输车,且每次只能运输一批工件,即车的容量等于批的容量。通过分析用运输车的车容量限制与工件个数的关系。【结果】由最优算法得到了一个最优排序和最小化最大完工时间。【结论】首先给出最大完工时间问题的一个下界,然后指出在当工件个数小于等于运输车的容量限制时,提供出来一个最优算法。对于当工件个数大于运输车的容量限制时,证明了当工件满足一定条件时,该问题也存在最优算法。(本文来源于《重庆师范大学学报(自然科学版)》期刊2019年04期）
慕运动,王丹丹[3]（2019）在《两台机器流水作业在序列错位下最小化最大完工时间重新排序》一文中研究指出重新排序是决策者在对原始的工件集进行最优排序后,将新到的工件一起进行重新排序的过程.流水作业排序是对每个工件在每个处理机上按照相同顺序进行加工的排序过程.研究在序列错位条件下,最小化最大完工时间的两台机器流水作业的重新排序问题,对两个模型进行分析并设计出了对应的算法.(本文来源于《周口师范学院学报》期刊2019年02期）
何程,韩鑫鑫[4]（2018）在《同时最小化最大费用和最大完工时间的双代理无界平行分批排序》一文中研究指出有两个代理A和B,每个代理都各自有一个工件集.同一个代理的工件可以在同一批中加工,而且每一个代理都有一个需要最小化的函数.研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题,并给出一个算法,它可在多项式时间内找到关于这个问题的所有Pareto最优点.(本文来源于《运筹学学报》期刊2018年03期）
刘文娟[5]（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）
臧西杰,李士生,王曦峰[6]（2017）在《最小化最大加权完工时间重新排序研究》一文中研究指出重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.(本文来源于《系统科学与数学》期刊2017年11期）
姚永辉[7]（2017）在《最小化最大运输完工时间和最大流程的在线排序问题》一文中研究指出排序论是运筹学中最有活力的领域之一,大量不同机器环境下的排序模型已经被学者们广泛研究.我们根据工件的不同特点,排序问题分为离线排序和在线排序.在离线排序问题中,工件的所有信息是在排序之前就已经知道的.而本文所要研究的是按时在线排序问题,也就是指工件的到达时刻,加工时间等只有在到达之后才被了解,决策者只能根据当前已到达工件的信息来进行排序决策.在LKβ模型下,在时刻t,在线算法能预见到将在时间区间(t,t + β]内到达的所有工件的信息;不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工.分批排序模型按分批方式的不同分两大类:平行分批排序模型和继列分批排序模型.平行分批排序是指多个工件可以放在同一批在一台机器上同时开工同时完工,每一批的加工时间等于该批中工件的最大加工时间.继列分批排序是指一批中的工件是相继加工的,它们的完工时间等于批中最后一个工件的完工时间.每批的加工时间等于该批中所有工件的加工时间之和.批容量b是指每批至多可以加工b工件,一般分为有界和无界两种情形.本文我们研究的是几种特殊的在线分批排序问题,研究的模型用叁参数法表示记为:(1) 1|online, p-batch,pj = 1,b = ∞, LKβ|Dmax(= maxj{Cj + qj});(2) 1|online,p-batch,pj = 1,b = ∞,f-family|Dmax(= maxj{Cj + qi});(3) Pm|on-line, s-batch|Fmax(= maxj{Cj - rj})模型(1)的基本描述:在该问题中,我们研究的是具有前瞻区间和运输时间的单机无界平行分批在线排序问题,工件具有相同的加工时间,目标是最小化最大运输完工时间.对于我们研究的模型,在本文第二章中给出了该问题的一个在线算法:当0 ≤ β ≤1/6时,该算法是竞争比为1+α*的最好可能的在线算法,其中α*= α是方程α2 + (β + 1)α +β-1 = 0的正根;当β> 1/6,该算法的竞争比为3/2.模型(2)的基本描述:在该问题中,我们研究的是具有f个互不相容工件组和运输时间的单机无界平行分批在线排序问题,工件具有相同的加工时间,目标是最小化最大运输完工时间.对于我们研究的模型.在本文第叁章中给出了一个竞争比为1 + αf的最好可能的在线算法,其中αf是方程fαf2 + αf - f = 0的正根.模型(3)的基本描述:我们讨论了最小化最大流程时间的继列分批在线排序问题.在本文第四章中证明了当m ≥ 2时,问题Pm|on-line,s-batch|Fmax不存在竞争比小于1 + αm的在线算法,其中αm为方程αm2 + (m+ 1)αm = 1的正根;当m = 1时,问题1|on-line,s-batch|Fnax不存在竞争比小于1 + α的在线算法,其中α = (?);同时我们也证明了问题Pm|on-line,s-batch,pj=1|Fmax不存在竞争比小于1 +βm的在线算法,其中βm为方程(s + 1)βm2+(ms + m + s + 2)βm - s = 0 (βm > 0)的正根.在本章4.3节中我们尝试给出m = 1时的一个在线算法H1,并证明该算法的竞争比为2,说明了这个算法的界是紧的,在m ≥ 2时,在线算法就变得较为复杂,目前无法得知比2更好的在线算法.(本文来源于《郑州大学》期刊2017-05-01）
农庆琴,范国强,赵婷[8]（2015）在《最大加权完工时间排序博弈问题的协调机制》一文中研究指出研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制。相应的排序博弈模型中,有m台平行机和n个工件,工件j的加工时间为pj,权重为ωj。每个工件可自主选择机器进行加工,它的目标是最小化自身的完工时间,全局的目标是最小化最大加权完工时间。本文针对该问题设计协调机制,证明该机制的纳什均衡存在且唯一,并证明该机制的无秩序代价为2-1/m。(本文来源于《中国海洋大学学报(自然科学版)》期刊2015年07期）
林琳[9]（2015）在《基于分枝定界的动态流水车间最大完工时间问题研究》一文中研究指出在流水车间中,每个工件必须在不同机器上按照相同的加工路径进行加工,目标是确定使得目标函数最优的工件的加工序列,在任何时刻,每台机器至多可加工一个工件,且每个工件至多可在一台机器上进行加工,所有机器按照相同的机器顺序加工工件,当某个工件在某台机器上进行加工时,该过程不可以被中断。流水车间调度问题广泛存在于工业生产中,且大部分流水车间调度问题被证明是无法在多项式时间内求得最优解的NP难问题。即使是求解小规模的流水车间调度问题也是比较困难的。本文针对叁类动态流水车间调度问题,以极小化最大完工时间为目标函数进行了研究,分别提出了相应的分枝定界算法以获得小规模问题的最优解。最后通过数值实验仿真验证了算法的有效性。论文的主要内容概括如下:首先,针对带有到达时间的流水车间极小化最大完工时间问题,提出对应的分枝定界算法,同时,提出分枝定界算法的分枝策略、剪枝规则、下界等。最后,通过数值实验进行仿真,将分枝定界算法与CPLEX软件中的算法进行对比,验证了分枝定界算法在解决带有到达时间的流水车间极小化最大完工时间问题时具有较好的性能。其次,针对阻塞流水车间极小化最大完工时间问题,提出对应的分枝定界算法。同时,提出分枝定界算法的剪枝规则、下界等。最后,通过数值实验进行仿真,将分枝定界算法与CPLEX软件中的算法进行对比,验证了分枝定界算法在解决小规模的阻塞流水车间极小化最大完工时间问题时的有效性。再次,针对带有学习效应的流水车间极小化最大完工时间问题,提出对应的分枝定界算法,同时,提出分枝定界算法的分枝策略、剪枝规则、下界等。最后,通过数值实验进行仿真,将分枝定界算法与CPLEX软件中的算法进行对比,验证了分枝定界算法在学习效应分别为线性函数、幂函数和指数函数时的有效性。最后,总结了本文所做的主要工作,对未来的研究方向进行了展望。(本文来源于《东北大学》期刊2015-06-01）
柴幸[10]（2015）在《最小化最大加权完工时间的平行分批在线排序问题》一文中研究指出在经典的离线排序问题中,在排序之前已经知道工件的所有信息.本文主要研究的是按时在线排序.也就是指工件的各种信息在加工之前并不清楚,而是随着时间推移逐个到达之后才被了解.在本文中,主要研究平行分批在线排序的若干问题.平行分批排序是排序研究领域中一类非常重要的问题.平行机排序模型中共有m台机器.一台分批机器可以一批同时加工至多b个工件.批的加工时长由该批中的最长工件决定.按照批的容量,可以分为两类平行分批排序：有界的情形和无界的情形.在第二章中,对单机上最小化最大加权完工时间的分批在线排序问题,当批容量为1时,给出竞争比为2的最好可能的在线算法.在第叁章中,考虑平行机上单位长度工件最小化最大加权完工时间的分批在线排序问题.对批容量有界情形,引用叁参数表示法可以表示为：Pm|online,p-batch,b<∞,Pj= 1|WCmax我们给出竞争比为攀#≈1.618的最好可能的在线算法.同时证明了该问题稠密算法竞争比的下界为2,给出了达到该竞争比的稠密算法.批容量无界时,对问题Pm|online,p-batch,prec,b=∞,Pj=1|WCmax和Pm|online,p-batch,prec,b=∞,Pj=1|∑wjcj,我们给出竞争比为(?)的最好可能的稠密算法,这个结果在工件间无序约束关系时同样成立.在第四章中,考虑平行机上权重相同的单位工件具有不相容工件组和前瞻区间的无界分批在线排序问题.具有前瞻区间表示,在时刻t,在线算法可以看到在㈦t+序]时间内到达的工件信息.不相容工件组表示来自不同工件组的工件不可以在同一批次加工.当所有工件的权重相同时,最大加权完工时间即转化为最大完工时间.对问题Pm|online,p-batch,b= ∞,Pj=1,LKβ,f-families,β≥[f/m]Cmax,我们给出最优的在线算法.对问题Pm|online, p-batch,b=∞,Pj=1,LKβk,f_families,f=km,βk∈[k-1,k)|Cmax,我们给出竞争比为1+α七的最好可能的在线算法,其中α七是方程kαk2+αk(βk+1)+βk-k=0的正根.对更一般的情形,我们证明了稠密算法的下界,并给出了最好可能的稠密算法.(本文来源于《郑州大学》期刊2015-05-01）
最大完工时间论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
【目的】考虑单机情况下的加工和运输两阶段的供应链排序问题。【方法】在生产阶段,将所有工件在加工之前划分成批,在一台有限批容量的机器上加工,工件的实际加工时间是关于该工件退化率和加工位置的函数;在运输阶段,有一辆运输车,且每次只能运输一批工件,即车的容量等于批的容量。通过分析用运输车的车容量限制与工件个数的关系。【结果】由最优算法得到了一个最优排序和最小化最大完工时间。【结论】首先给出最大完工时间问题的一个下界,然后指出在当工件个数小于等于运输车的容量限制时,提供出来一个最优算法。对于当工件个数大于运输车的容量限制时,证明了当工件满足一定条件时,该问题也存在最优算法。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最大完工时间论文参考文献
[1].刘鹏,王小丽.加工时间与位置相关的最小化最大完工时间两人合作排序博弈[J].重庆师范大学学报(自然科学版).2019
[2].张新功,陈娟.两阶段供应链下极小化最大完工时间的单机系列批排序[J].重庆师范大学学报(自然科学版).2019
[3].慕运动,王丹丹.两台机器流水作业在序列错位下最小化最大完工时间重新排序[J].周口师范学院学报.2019
[4].何程,韩鑫鑫.同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J].运筹学学报.2018
[5].刘文娟.MapReduce中同类机排序极小化最大完工时间问题[D].曲阜师范大学.2018
[6].臧西杰,李士生,王曦峰.最小化最大加权完工时间重新排序研究[J].系统科学与数学.2017
[7].姚永辉.最小化最大运输完工时间和最大流程的在线排序问题[D].郑州大学.2017
[8].农庆琴,范国强,赵婷.最大加权完工时间排序博弈问题的协调机制[J].中国海洋大学学报(自然科学版).2015
[9].林琳.基于分枝定界的动态流水车间最大完工时间问题研究[D].东北大学.2015
[10].柴幸.最小化最大加权完工时间的平行分批在线排序问题[D].郑州大学.2015
论文知识图
