导读:本文包含了流水作业排序问题论文开题报告文献综述及选题提纲参考文献，主要关键词:重新排序,流水作业,错位,最大完工时间
流水作业排序问题论文文献综述
王丹丹[1]（2019）在《流水作业排序与重新排序的相关问题研究》一文中研究指出排序即为应用一定的资源以及机器,以实现任务能够最优完成.需在一定的约束下执行其工作,例如,工件的加工顺序、错位的约束等,最优完成工作即为使目标函数最优化的一种任务安排.在实际生活中,排序问题广泛存在,大量现实中的问题可归结为排序问题.因而,排序问题对资源合理利用,效率有效提高,有着重大意义.重新排序是决策者在对原始的工件集进行最优排序后,将新到的工件一起进行重新排序的过程.流水作业排序是对每个工件在每台处理机上按照相同顺序进行加工的排序过程.以下是本文研究的内容:1、我们分别考虑在四种错位约束,机器相容,工件反相容或相容下,目标函数是最大完工时间的两台机器流水作业的重新排序模型.本部分对这些模型的性质进行了分析,设计了其对应算法,且对算法的最优性及可行性进行了证明.2、我们分别考虑在四种错位约束,机器反相容,工件反相容下,目标函数是最大完工时间的两台机器流水作业的重新排序模型.本部分对这些模型的性质进行了分析,设计了其对应算法,且对算法的最优性及可行性进行了证明.3、我们分别考虑对在原始工件的最大完工时间限制下,使新工件的最大完工时间最小的两台处理机流水作业重新排序模型.本部分对这些模型的性质进行了分析,设计了其对应算法,且对算法的最优性及可行性进行了证明.(本文来源于《河南工业大学》期刊2019-05-01）
王吉波,郭苗苗,刘桓,李琳,王丹[2]（2016）在《具有依赖开工时间恶化工件的流水作业排序问题研究综述》一文中研究指出具有恶化工件的排序问题是制造业、运筹学、管理科学与工程中的一类重要问题,在钢铁工业、塑料工业、军事以及医疗等方面有着广泛的应用。分析了带有依赖开工时间恶化工件的流水作业排序问题的特点,目标函数主要包括时间表长、总完工时间、总加权完工时间、最大延误、总延误时间等。然后就带有依赖开工时间恶化工件流水作业排序问题进行了全面的综述,并指出了存在的不足和许多尚未解决的问题。最后,提出了具有恶化工件的流水作业排序工作进一步研究的问题。(本文来源于《沈阳航空航天大学学报》期刊2016年03期）
魏麒[3]（2014）在《应用于图形处理的一个混合流水作业排序问题的多项式时间近似策略》一文中研究指出由于早期的图形处理器浮点运算能力不强,所以在处理图形问题时一般由中央处理器处理数据运算环节,然后再由图形处理器进行图像处理.但是最近几年图形处理器的浮点运算能力得到很大提高,相信很快就能胜任原先只有中央处理器才能完成的图形问题中的数据运算任务,为此前瞻性的研究在这样一种新情况下如何合理调度中央处理器和图形处理器来更快的处理图形问题是很有必要的.事实上该问题其实相当于一个两阶段两台处理器的混合流水作业问题:有两台处理器和一批需要加工的工件,每个工件都包含两个任务,前一个任务是为第二个任务做准备的.第一个任务可以选择在任何一台处理器上处理,而第二个任务则必须当第一个任务完成后,在第二台处理器上处理,目标是尽可能早的处理完所有工件.对于该问题,设计了一个多项式时间近似策略(PTAS)来给出最优调度方案.(本文来源于《高校应用数学学报A辑》期刊2014年01期）
时凌,程学光[4]（2012）在《带单服务器和相同加工时间的流水作业排序问题》一文中研究指出研究带单服务器和相同加工时间的两台机器的流水作业排序问题,证明该问题是强NP-困难的,引入一个简单的贪婪算法证明其紧界是3/2.(本文来源于《数学物理学报》期刊2012年06期）
闻振卫[5]（2011）在《一种可控的两台机流水作业排序问题》一文中研究指出在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.(本文来源于《数学的实践与认识》期刊2011年22期）
杨名[6]（2011）在《若干流水作业排序问题的算法研究》一文中研究指出本文主要从讨论问题下界和设计算法的角度,对排序问题中的在线和半在线流水作业以及单机问题进行了研究。我们首先考虑了工件带到达时间(over time)和工件逐个到达(over list),目标为最小化最大完工时间的在线和半在线流水作业问题。然后分别考虑了机器有使用限制的单机和流水作业问题。全文由六个部分组成,在第一章我们首先给出了组合优化和排序问题的基本概念和定义,然后介绍在线和半在线排序的研究近况,最后给出机器有使用限制的排序问题的一些概念和研究现状。第二章研究了可中断的二台机器流水作业排序问题,目标为最小化最大完工时间,工件实时到达(over time),工件信息在工件到达之前不可知。我们首次给出了该在线问题的一个下界1.137,并对问题设计了一个在线算法。针对只有两个到达时间的特殊情况,我们证明了该在线算法是3/2竞争的算法。第叁章主要讨论了两台机器流水作业的半在线排序问题。我们分别研究了不可中断和可中断两种情况。对于不可中断的排序模型,我们研究了已知工件工序最大及最小加工时间,工序的总加工时间以及最优值的半在线情形,分别对这些问题给出了问题的下界,并为已知最优值的半在线问题设计了一个竞争比为3/2的在线算法。而对于可中断的情况,我们也分别对上述的半在线情形进行了分析,同样给出了问题的下界,同时对已知第一道工序加工时间和以及已知最优值的问题分别给出了竞争比为3/2的在线算法。第四章研究的是机器带使用限制的两台机器流水作业问题,工件加工可以被不可用时间段中断,目标为最小化最大完工时间。我们知道若第二台机器上存在有多个不可用时间段,问题不存在常数性能比的近似算法。利用Kubzin等人的算法思想,对于两台机器上均存在多个不可用时间段问题的可近似情况,我们得到了一个性能比为3/2的近似算法。第五章主要研究了机器有使用限制的半在线流水作业排序问题,其中工件是逐个到达的(over list),目标为最小化最大完工时间。对于第一台机器上存在不可用时间段的情形,我们讨论了一类新的半在线模型,即已知第一道工序的最大加工时间amax与不可用时间段的开始时间s之间关系的半在线问题。我们分别证明了叁种不同的情况：amax>s,amax<s,或amax＝s,问题的下界均为2,同时证明LS算法即为一个最优的半在线算法。我们还证明了若在第二台机器上存在不可用时间段,问题不存在常数竞争比的在线算法。在本章的最后,我们讨论了第二台机器上存在不可用时间段的已知最优值Cmax*的半在线问题,并对不可用时间段的结束时间t不超过1/2Cmax*的特殊情况给出了一个竞争比为3/2的在线算法。第六章主要研究了机器有使用限制的单机在线和半在线问题,工件是逐个到达的,目标为最小化最大完工时间。我们考虑的是工件被不可用时间段中断后要重新再加工的情形(non-resumable),机器只有一个不可用时间段。对于该模型的在线问题,证明了问题的下界是2,且LS算法即为该问题的最优算法。对于半在线问题,我们考虑的是已知工件最大加工时间的半在线模型。通过比较最大加工时间pmax与不可用时间段的开始时间s的大小关系,分别考虑了pmax>s,Pmax<s,和pmax=s的情况。证明了前两种情况的下界分别为(?)和3/2,并且若pmax=s,问题是可解的。我们对pmax>s的情况给出了一个竞争比为(?)的最优半在线算法,对于pmax<s的情况也给出了一个竞争比为3/2的最优半在线算法。最后我们还证明了,若单机上存在有多个不可用时间段,在线问题不存在常数竞争比的在线算法。(本文来源于《华东理工大学》期刊2011-09-28）
徐春[7]（2010）在《带参数的平行机和流水作业排序问题的复杂性及算法研究》一文中研究指出平行机及流水作业排序问题是多处理机排序问题的一种情况，其研究在理论和应用上都有重要意义．本文考虑四个排序问题，并且讨论它们的复杂性及启发式算法．第一个问题：研究带单服务器的两台平行机排序问题的复杂性．每个工件在机器加工之前，必须由服务器先进行安装，在同一时刻每一个服务器只能安装一个工件，目标是使最大完工时间达到最小．在工件具有准备时间且所有加工时间等于1的条件下，证明该问题是强NP困难的；第二个问题：研究两台机器情况下的流水作业排序问题的复杂性，目标函数为使最大完工时间达到最小．同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内，存在称为运输时间的时间间隔，所有的运输时间均由自动机完成，自动机在同一时间内最多运输一个工件，证明该特殊情况下的此问题是强ⅣP困难的；第叁个问题：研究两台机器情况下的流水作业排序问题的复杂性，目标函数为使加权完工时间总和达到最小．证明该特殊情况下的此问题是强ⅣP困难的，并给出一个启发式算法，证明它的紧界为3/2；第四个问题：研究带准备时间的两台机器情况下的流水作业排序问题的复杂性，目标函数为使加权完工时间总和达到最小．工件有一个准备时间rl，证明该特殊情况下的此问题是强Np难的，并给出一个启发式算法，证明它的紧界为3/2．(本文来源于《湖北民族学院》期刊2010-06-30）
时凌,徐春[8]（2010）在《流水作业排序问题的启发式算法》一文中研究指出研究了n个工件在2台机器下的流水作业排序问题,目标是使加权完工时间最小.同一工件在一台机器上完工后与在另一台机器上开工前存在一定的时间间隔,将其定义为运输时间,所有运输过程均由单自动机完成.讨论了该排序问题的复杂性,并引入了一种启发式算法,证明了该问题是强NP困难的,该算法的紧界为3/2.(本文来源于《华中科技大学学报(自然科学版)》期刊2010年05期）
李晓峰,赵海,杜洪军,刘小勇[9]（2009）在《柔性流水作业排序问题的贪心算法求解》一文中研究指出柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题,给出了求解柔性流水作业排序问题近似解的贪心算法,并对其性能进行了分析测试。结果表明,虽然该贪心算法求出的近似解与最优解相比有一定误差,但由于其时间复杂度较小,因此对求解车间作业调度问题仍有一定的现实意义。(本文来源于《吉林大学学报(信息科学版)》期刊2009年06期）
程明宝,孙世杰,张毕西[10]（2009）在《机器具有优势关系下的工件加工时间可控的流水作业排序问题(英文)》一文中研究指出本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.(本文来源于《运筹学学报》期刊2009年02期）
流水作业排序问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
具有恶化工件的排序问题是制造业、运筹学、管理科学与工程中的一类重要问题,在钢铁工业、塑料工业、军事以及医疗等方面有着广泛的应用。分析了带有依赖开工时间恶化工件的流水作业排序问题的特点,目标函数主要包括时间表长、总完工时间、总加权完工时间、最大延误、总延误时间等。然后就带有依赖开工时间恶化工件流水作业排序问题进行了全面的综述,并指出了存在的不足和许多尚未解决的问题。最后,提出了具有恶化工件的流水作业排序工作进一步研究的问题。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
流水作业排序问题论文参考文献
[1].王丹丹.流水作业排序与重新排序的相关问题研究[D].河南工业大学.2019
[2].王吉波,郭苗苗,刘桓,李琳,王丹.具有依赖开工时间恶化工件的流水作业排序问题研究综述[J].沈阳航空航天大学学报.2016
[3].魏麒.应用于图形处理的一个混合流水作业排序问题的多项式时间近似策略[J].高校应用数学学报A辑.2014
[4].时凌,程学光.带单服务器和相同加工时间的流水作业排序问题[J].数学物理学报.2012
[5].闻振卫.一种可控的两台机流水作业排序问题[J].数学的实践与认识.2011
[6].杨名.若干流水作业排序问题的算法研究[D].华东理工大学.2011
[7].徐春.带参数的平行机和流水作业排序问题的复杂性及算法研究[D].湖北民族学院.2010
[8].时凌,徐春.流水作业排序问题的启发式算法[J].华中科技大学学报(自然科学版).2010
[9].李晓峰,赵海,杜洪军,刘小勇.柔性流水作业排序问题的贪心算法求解[J].吉林大学学报(信息科学版).2009
[10].程明宝,孙世杰,张毕西.机器具有优势关系下的工件加工时间可控的流水作业排序问题(英文)[J].运筹学学报.2009