导读:本文包含了批处理机排序论文开题报告文献综述及选题提纲参考文献，主要关键词:在线算法,平行分批,不相容工件族,最小化时间表长
批处理机排序论文文献综述
高焰红[1]（2019）在《平行批处理机上不相容族工件的在线排序问题》一文中研究指出排序是指把每个工件的加工时长全部分配到一台机器或多台机器的一个或多个加工时间段上.排序问题的含义是决策者找到一个排序算法满足特定的限制条件,使得目标函数达到最优.通常情况下,排序问题分为离线排序问题和在线排序问题.本文考虑在线排序问题.在在线排序问题中,只有工件到达了,决策者才知道该工件的所有信息.批处理问题是指把己到达且未被加工的工件分组成批,并安排这些批次的加工顺序以及对应的加工机器.平行分批是指机器可以同时加工一个批次中的所有工件,即同一个批次的工件有相同的开工时间.批次的加工时间为该批次中所有工件的最大加工时间,故批次中所有工件有相同的开工时间,加工时长和完工时间.由于不同工件族中工件是不相容的,从而不同工件族中工件不能在同一个批次中加工.批容量是指在一台机器上能够同时加工工件的最大数目,一般用b来表示.按批容量划分,分批排序模型可分为有界分批模型(b<∞)和无界分批模型(b=∞).本文研究的是平行分批处理机上不相容族工件的在线排序问题,其中一旦机器开工,决策者就不能反悔,而且也不能中断工件的加工.目标是找到一个在线算法,使得在它所生成的排序中时间表长尽可能的小,也即所有工件的最大完工时间尽可能的小.由于平行分批在线排序问题一直是个难题,所以本文作如下限制:属于同一工件族的工件有相同的加工时长.本文主要研究的是该在线排序模型在两个环境下的几个问题:(1)KRT环境(KRT限制下的在线环境)和(2)一般环境(一般到达时间限制下的在线环境).KRT的英文表达是:“kind release time”,它的具体解析是:批处理机在加工的过程中不会有新工件到达,也即新工件只能在机器空闲的时候或者某个批次完工的时刻到达.本文首先研究单台有界的批处理机上f(f≥ 2)个不相容族工件在KRT环境下的在线排序问题,其中属于同一个工件族的工件有相同的加工长度.对于这个模型,第二章首先证明:当b≥f时,该模型在线算法的下界为1十αf,其中是方程fαf2+2αf+1-f=0的正根,然后给出一个最好可能的在线算法.一般环境是指工件可在任何时刻到达的在线环境,即该环境对工件的到达时间不作任何要求.本文研究了单台有界的批处理机上f(f≥ 2)个不相容族工件在该环境下的在线排序问题,其中属于同一个工件族的工件有相同的加工长度.对于此模型,在第叁章中首先证明:当b≥f+1时,在线算法的竞争比的下界为1+αf',其中αf'=满足等式f·αf2'+αf'=0.接着给出一个在线算法,并通过分析得出该算法的竞争比是,从而当b≥f+1时该算法就是最好可能的.本文还研究了f台无界的批处理机上f(f≥ 2)个不相容族工件在一般环境下的在线排序问题,其中属于同一个工件族的工件有相同的加工长度.对于这个模型,第四章首先证明:该模型在线算法的下界为1+θ,其中是方程θ2+θ-1=0的正根,然后给出一个最好可能的在线算法。(本文来源于《郑州大学》期刊2019-04-01）
李文杰,熊建栋,翟红村[2]（2017）在《最大化接收工件总权值的批处理机在线排序》一文中研究指出研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p>0,一个到达时间r_j≥0,一个权值w_j>0,一个必须交货期d_j>0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).(本文来源于《河南师范大学学报(自然科学版)》期刊2017年01期）
刘其佳,冯琪[3]（2015）在《有界平行批处理机的在线排序问题》一文中研究指出主要研究的是在线运输排序问题,即研究m台有界平行批处理机上考虑工件运输的在线排序问题.工件按时间在线到达,即一个工件只有在被释放之后才能知道它的一切信息.这些工件首先要在平行批处理机上分批加工,然后加工完成的工件再被一个运输车辆运送给某个顾客.当车辆的容量是充分大的时候,给出一个最好可能的在线算法,其竞争比为(5(1/2)+1)/2;当车辆的容量有限时,给出一个竞争比为(5(1/2)+3)/2的在线算法.(本文来源于《河南师范大学学报(自然科学版)》期刊2015年05期）
岳雅娟,赵玉芳,许尉[4]（2013）在《到达时间与工期同序的串行批处理机排序问题》一文中研究指出笔者考虑的工件带有到达时间,且到达时间与工期同序、目标函数为加权误工工件数的单台串行批处理机排序问题是NP-难的,其中批处理机的容量无限。当同一批中的工件都到达后,此批才可以开始加工。同一批中工件的开始加工时间相同,批的加工时间为此批中所有工件的加工时间之和,且完工时间也相同,为这批中最后一个工件的完工时间;每批开始加工之前都有一个固定的调整时间,而批内工件间无调整时间,在批的调整时间内机器不能加工任何工件。研究工件带有2个不同到达时间,且到达时间与工期同序的情况。对于目标函数为加权误工工件数问题,分析了其最优解的性质,给出了拟多项式动态规划算法及其时间复杂性。(本文来源于《沈阳师范大学学报(自然科学版)》期刊2013年02期）
岳雅娟[5]（2013）在《到达时间与工期同序的串行批处理机排序问题》一文中研究指出在芯片等电子产品制造系统中，常常把前一道工序加工完的工件放到货盘里，把同一货盘中的工件作为一批，一起放到处理机上依次加工，这就相当于在本道工序中工件是动态到达的。只有当一批中的工件都到达后，此批才可以开始加工。当一个新批形成的时候，有一个固定的安装时间，而批内工件间无安装时间，在批的安装时间内机器不能加工任何工件。同一批中的工件有相同的开始加工时间和完工时间。一批的加工时间为此批中所有工件的加工时间之和，一批的完工时间为此批中最后一个工件的完工时间。当货盘中的所有工件都加工完后才可以交货，本文在工件的到达时间与工期同序的情况下，对不同的目标函数进行了研究，具体内容概括如下：1.所有工件只有两个不同的到达时间，而工件的工期、加工时间及权可以有多个不同的值，对于目标函数为加权误工工件数问题是NP-难的，分析了其最优解的性质，给出了求解此问题的拟多项式动态规划算法以及算法复杂性，并通过数值例子进一步表明算法的有效性。2.对于工件有多个不同的到达时间，而工件的加工时间都相同的情况，研究了两个不同的目标函数：(1)当工件的工期给定时，本文考虑了按时完工工件的最大完工时间以及误工工件的总误工惩罚，目标是使两者之和最小，分析了此问题最优解的性质，给出了一个拟多项式动态规划算法，讨论了算法复杂性，并用数值例子说明了此算法的计算过程。(2)讨论了误工工件数问题，此问题是多项式可解的。分析了其最优解的性质，给出一个动态规划算法，时间复杂性为O (n3)，并用数值例子进一步解释此算法。(本文来源于《沈阳师范大学》期刊2013-03-10）
林烈青,郑睿[6]（2011）在《优化批处理机排序方案的启发式算法研究》一文中研究指出为优化带有链式先后关系约束的批处理机排序方案,对求解该方案的最优解性质进行了研究,设计了两种启发式算法。首先分析了排序方案的目标函数即为最小化加权完工时间和,然后根据最优解的性质设计了贪婪算法和优选算法。将随机生成的算例分别输入到贪婪算法、优选算法和文献已有的满批算法中进行仿真求解,验证了这些算法的有效性,并通过对仿真结果的汇总和对比分析,确认叁种算法中优选算法的效果最好,可以作为实际应用中的首选。(本文来源于《制造业自动化》期刊2011年14期）
卫志刚[7]（2011）在《可自由离线批处理机最小化加权完工时间和排序》一文中研究指出批处理排序是排序领域中一类重要问题.批处理是指处理机可以同时将b个工件作为一批,在相同的批开工时间同时加工.对于输入的n个工件,要求将n个工件安排到若干批中,并且决定这些批的开始加工时间：使得给定的目标函数值最小在本文中,工件具有自由离线的性质,目标函数是总加权完工时间.工件可自由离线(item-availability)是指,同一批中的每个工件完工时间等于该批的开工时间与该工件的加工时间之和.本文对完工工件可自由离线的单台批处理机最小化加权完工时间和排序的在线和离线情况分别做了研究.在线情形下,对于批容量无限(b=+∞)的模型,给出了一个竞争比是2+α的柔性算法(α=(?)-1/2),并证明了该竞争比是紧的(tight)对于容量有限(b<n)的模型,给出了一个(4+ε)近似的在线算法.离线情形下,首先证明了批容量无限(b=+∞),且工件到达时间(release-date)不全相同的批排序问题是NP-困难的,然后给出一个全多项式近似方案(FPTAS)对于工件加工时间的种类为固定常数的情形,给出了一个多项式时间的动态规划算法.对于批容量有限的模型,对工件到达时间不全相同且所有的工件加工时间都相同的情形,证明了可在多项式时间找到一个最优排序.对工件到达时间相同且工件权重全相同的情形：设计出一个2-近似的算法.(本文来源于《郑州大学》期刊2011-05-01）
郑睿[8]（2009）在《钢铁生产中的批处理机作业排序问题算法研究》一文中研究指出本文所研究的是以钢铁制造中的批处理机生产系统为原型的作业排序问题。钢铁工业是我国国民经济的支柱行业,其生产制造系统结构非常复杂,因此所包含的作业排序问题极具挑战性。本文以“宝钢宽厚板车间周分日生产作业排序项目”为背景,从宽厚板生产的轧前加热和热处理两道工序中,提炼出了几类family jobs类型的批处理机排序问题,并对此展开了问题特点和求解算法的研究。全文共分为6章,第1章介绍了论文研究的背景和意义,第2章介绍了排序的基本知识以及文献综述。通过文献综述可以发现,现有的文献对于family jobs类型的批处理机排序问题的研究尚不够充分,还存在包括本文主要研究内容在内的许多空白点。所以本文对这些问题进行的研究不仅符合排序问题的研究发展趋势,而且能够填补这些研究的空白点,具有重要的理论价值。论文第3章以宽厚板生产中的轧前加热工序为背景,提取出了排序问题1|p—batch,family—jobs,s_(fg)|f。论文分析了该问题的特点,给出了一些最优解的性质,并据此提出了叁种动态规划算法:求解任意常规目标函数的伪多项式时间的正向动态规划算法、求解两类目标函数的多项式时间的逆向动态规划算法和求解延误工件数最小化问题的多项式时间的正向动态规划算法。最后还针对加权完工时间和最小化问题提出了一系列启发式算法。论文第4章则是对于上述问题批量有限制的情况进行了研究。针对目标函数为加权完工时间和最小化的问题,首先给出了一个分支定界算法,然后又给出了一系列的启发式算法。其中包括结合传统启发式算法的混合遗传算法,以及一种求解排序问题的新思路一拍卖算法。论文第5章以宽厚板生产中的热处理工序为背景,提取出了工件可重入的批处理机排序问题,然后把该问题转化成了相应的带工件链式先后关系约束的批处理机排序问题,即问题1|p—batch,family—jobs,chains|∑_(i=1)~m∑_(j=1)~(n_i) w_(ij)C_(ij)。对于这个问题,论文提出了求解的分支定界算法和启发式算法。而论文第6章则是总结了全文的主要内容及创新点,并分析了文章的不足和后续研究方向。论文运用了运筹学的数学规划理论以及启发式算法思想,结合了计算机科学的理论和技术,采用了“理论分析建模-模型求解-仿真实验求证”的研究方法。对于所研究的每个问题,都建立了整数规划模型,分析了问题的特点,提出了相应的求解算法,并在最后利用计算机模拟仿真实验,验证了这些算法的有效性。论文的研究成果不但从理论上填补了对于family jobs类型的批处理机排序问题研究的部分空白点,而且还为钢铁工业企业的生产作业排序提供了有效的借鉴和参考,具有较高的应用价值。(本文来源于《复旦大学》期刊2009-12-24）
焦李超,朱路宁,张玉忠[9]（2009）在《一台串行批处理机上的一类有主次指标的排序问题》一文中研究指出考虑一类带机器安装时间的单机双目标串行分批排序问题.对这样两个问题1,s|s-batch,B≥n,Cmax≤u|∑Cj和1,s|s-batch,B≥n,∑Cj≤v|Cmax,通过动态规划给出了多项式时间最优算法.(本文来源于《曲阜师范大学学报(自然科学版)》期刊2009年03期）
刘朝晖[10]（2009）在《批处理机上有就绪和截止时间的等长度工件排序》一文中研究指出一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间。本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表。就该问题,B aptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广G arey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法。算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策。(本文来源于《重庆师范大学学报(自然科学版)》期刊2009年03期）
批处理机排序论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p>0,一个到达时间r_j≥0,一个权值w_j>0,一个必须交货期d_j>0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
批处理机排序论文参考文献
[1].高焰红.平行批处理机上不相容族工件的在线排序问题[D].郑州大学.2019
[2].李文杰,熊建栋,翟红村.最大化接收工件总权值的批处理机在线排序[J].河南师范大学学报(自然科学版).2017
[3].刘其佳,冯琪.有界平行批处理机的在线排序问题[J].河南师范大学学报(自然科学版).2015
[4].岳雅娟,赵玉芳,许尉.到达时间与工期同序的串行批处理机排序问题[J].沈阳师范大学学报(自然科学版).2013
[5].岳雅娟.到达时间与工期同序的串行批处理机排序问题[D].沈阳师范大学.2013
[6].林烈青,郑睿.优化批处理机排序方案的启发式算法研究[J].制造业自动化.2011
[7].卫志刚.可自由离线批处理机最小化加权完工时间和排序[D].郑州大学.2011
[8].郑睿.钢铁生产中的批处理机作业排序问题算法研究[D].复旦大学.2009
[9].焦李超,朱路宁,张玉忠.一台串行批处理机上的一类有主次指标的排序问题[J].曲阜师范大学学报(自然科学版).2009
[10].刘朝晖.批处理机上有就绪和截止时间的等长度工件排序[J].重庆师范大学学报(自然科学版).2009