在线排序问题论文-刘巍巍,杨浩,刘慧芳

在线排序问题论文-刘巍巍,杨浩,刘慧芳

导读:本文包含了在线排序问题论文开题报告文献综述及选题提纲参考文献,主要关键词:混流装配线,排序,SGRASP-LP算法,GRASP算法

在线排序问题论文文献综述

刘巍巍,杨浩,刘慧芳[1](2019)在《基于SGRASP-LP算法的混流装配线排序问题》一文中研究指出针对实际混流装配线上工作站工作过载过大、无效时间过长导致的装配线运行效率低下问题,在保留基本模型约束条件的基础上引入"保持生产混合"和"作业自主中断"两个约束条件,建立以"最小化工作过载和无效时间"为目标的混流装配线排序问题优化模型。在基本GRASP算法的初始解构造阶段增加阈值参数选择机制,并将改进后的GRASP算法与线性规划方法结合,设计了模型的SGRASP-LP求解算法。以某汽车企业的底盘装配线为例,将SGRASP-LP算法分别与GRASP算法和企业解决该类问题常用的MILP算法相比较。结果表明,SGRASP-LP算法运算速度更快,所求方案更优,是解决相关排序问题的有效算法。(本文来源于《组合机床与自动化加工技术》期刊2019年09期)

甘雅文,侯亮,徐昌华,张炜,陈鼎[2](2019)在《考虑产品切换的客车混流装配线排序问题》一文中研究指出针对主客观因素交互影响下混合装配线的排序问题,建立以最小化工作站堵塞时间与最小化产品切换次数为目标的交互排序模型,并依据客车在实际加工过程中的传统排序方案与模型所得排序方案的结果进行对比分析。模型构建从客观因素出发,优化堵塞时间即"重构"作业框架,以达到对负荷高峰时期进行削峰处理的目的,并进一步在主观因素层面上,考虑线上操作者的作业惯性,降低线上操作者对频繁切换产品的出错率,保持较高熟练度时操作的方便与流畅性。引入主客观优化评价算法对模型进行计算,决策出最优任务调度方案。对比分析结果表明,模型获得的最优排序改善了装配线的生产堵塞时间,同时兼顾主观因素主导下的产品切换频率问题,对于节省装配过程中有限的时间资源和释放有限的空间资源具有很大的作用。(本文来源于《计算机集成制造系统》期刊2019年07期)

康帆[3](2019)在《汽车混流装配线排序问题研究》一文中研究指出随着人们生活水平的提高,对于产品的多样化、个性化的需求越来越高,汽车制造业也面临同样的问题。针对这一情况,汽车制造企业改变了传统的生产模式,传统的大批量生产已经不再符合当前的发展需要,多品种的中小批量生产应运而生。与此同时,为了降低企业的生产成本,避免产线的重复铺设,能够同时生产多种产品的混流装配线就成为了大多数汽车制造企业的首选。本文对汽车混流装配线的排序问题进行了探究。(本文来源于《时代汽车》期刊2019年08期)

周燕[4](2019)在《带有机器故障的半在线排序问题》一文中研究指出排序理论是运筹学中一个非常活跃的分支.通常,我们将排序问题分为离线排序和在线排序.本文研究了带有机器故障的半在线排序问题,是指在排序之前,工件的到达时间,加工时间,运输时间等信息均已获知,但机器故障何时发生何时结束等信息是无法提前知道的,决策者只能根据到达工件的所有信息给出决策方案.本文我们研究了两类排序问题,一类是带有机器故障和运输时间的单机半在线排序问题,一类是带有机器故障的平行批单机半在线排序问题.其中,平行分批排序是多个工件可以放在同一批,在一台机器上加工,每批里面的工件同时开始加工同时完工,每批的加工时间是该批中所有工件的最大加工时间.批容量(7是指每批可以最多加工(7个工件,一般分为有界和无界两种情形.工件带有运输时间的在线排序,是指工件加工完成后需要用运输工具将其运输到目的地.一般,我们假设运输工具有无数多个,工件一旦被加工完就可以立刻被安排运输,因此送货(运输完工)时间就等于工件的完工时间与其运输时间之和.针对这两类排序问题,我们主要研究两个模型.我们研究的第一类模型是单机带有机器故障,带有运输时间的半在线排序问题,目标函数是最小化最大送货(运输完工)时间,用叁参数法表示为:(1)1,?1|?|_(max);(2)1,?1|_(5))|_(max).在本文的第二章节,我们首先找出了该问题的下界是3?2,对于问题1,?1|?|_(max)我们给出了一个在线算法并证明竞争比为(?).在(?)条件下,对于问题(?)给出了一个竞争比为(3?2+)的在线算法,当<1?2时,竞争比小于2.我们研究的第二类模型是单机带有机器故障的批容量有界的平行批半在线排序问题,目标函数是最小化最大完工时间,用叁参数法表示为:(?).在本文的第叁章节,我们找出了问题的下界是3?2,给出了一个最好可能的在线算法,并证明了该算法的竞争比是3?2.(本文来源于《中国矿业大学》期刊2019-05-01)

王利博[5](2019)在《线性退化工件的分批在线排序问题》一文中研究指出在许多工件加工的实际场景中,工件的加工时长随着其开工时间的增大而增大.这种现象称为工件的退化效应.本篇论文研究了具有线性退化效应的工件和工件集族的分批在线排序问题.工件Jj的加工时长为pj=αjt,其中αj>0为工件的退化率,t为工件的开工时间.工件的到达时间是未知的,工件的退化率只有在工件到达之后才能知道.分批是指一个批次能同时处理b个工件,在同一批次中加工的工件有相同的开工时间、加工时间和完工时间,批的加工时长为该批中工件的最大加工时长.根据一批内能容纳的工件个数,可以分为批容量无界(b>∞)和批容量有界(b<∞)两种情形.工件集族是指所有的工件都来自于某一个集族,且来自不同工件集族的工件不能放在同一批加工.第二章讨论了单机上退化工件的分批在线排序模型,目标是使得最大完工时间最小.对于批容量无界的情形,本章证明了该问题的下界并给出与下界匹配的在线算法,即给出竞争比为1+αmax的最好可能的在线算法,其中αmax为所有工件退化率的最大者.对于批容量有界且工件只有两个到达时间的情形,本章同样给出竞争比为1+αmax的最好可能的在线算法.第叁章讨论了单机上批容量无界的退化集族工件的在线排序,目标是使得最大完工时间最小.工件集族的个数f是提前知道的.本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为(1+αmax)f的最好可能的在线算法,其中αmax为所有工件退化率的最大者.第四章讨论了 m台恒同平行机上退化工件的在线分批排序,目标是使得最大完工时间最小.所有的工件有相同的退化率α,其中α>0.同样考虑了批容量无界和批容量有界两种情形.关于批容量无界的情形,本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为1+β的最好可能的在线算法,其中β满足(1+β)m = 1+α;关于批容量有界的情形,给出了竞争比为1+α的最好可能的在线算法.第五章讨论了 m台恒同平行机上批容量无界的退化集族工件的在线排序,目标是使得最大完工时间最小.所有的工件来自m个不同的工件集族.本章证明了该问题的下界并给出与下界匹配的在线算法,即给出了竞争比为1+αmax的最好可能的在线算法,其中αmax为所有工件的最大退化率.(本文来源于《郑州大学》期刊2019-04-01)

高焰红[6](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)

彭南南,张玉忠,柏庆国,王成飞[7](2019)在《工件满足一致性的同类机在线分批排序问题》一文中研究指出研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,叁元素法分别表示为Q_2|r_i<r_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_i<r_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.(本文来源于《运筹学学报》期刊2019年01期)

周鹏程,刘朝晖[8](2018)在《有服务等级约束的同类机在线排序问题的可分算法》一文中研究指出研究了一类有四个服务等级的可分排序问题,在一定条件下改进了下界,并且提出了一种最优算法。在该问题中,工件和机器都带有各自的服务等级约束,当且仅当工件的服务等级比机器的服务等级高或者相同时,该机器才被允许对该工件进行加工,并且每个工件都被允许在所有机器之间按照任意的比例分割后进行加工,同一个工件的各个部分被允许同时放在各台机器上进行加工,优化目标是找到最小时间表长。(本文来源于《华东理工大学学报(自然科学版)》期刊2018年06期)

闵啸,朱俊蕾,刘静[9](2018)在《两台带服务等级的可拒绝同型机排序问题的在线算法》一文中研究指出两台同型机M_1,M_2,加工速度一致,但拥有不同的加工能力,用其服务等级表示,M_1的服务等级为1,M_2的服务等级为2.工件j按列表在线到达,每个工件带有叁个参数:长度t_j,等级g_j=1或2,罚值p_j.当j到达时,可以被拒绝,但要付出相应的罚值p_j,也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工,等级为2的工件可以分给M_1或M_2加工,加工不允许中断.目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和.对于该问题给出了一个在线算法,其竞争比为11/6,以及问题一个下界5/3.(本文来源于《运筹学学报》期刊2018年03期)

徐佳[10](2018)在《带有加工机器约束的若干在线排序问题研究》一文中研究指出本文主要研究的是带有加工机器约束的平行机在线排序问题。在此问题中,每个工件都对应一个到达时间rj,一个加工时间pj和一个加工机器集合Mj,工件只能在时刻rj之后被安排到Mj中的某个机器上加工,加工需要占用pj个单位时间。我们考虑这个问题的在线情形。也就是说,只有在此工件到达之后,我们才能得到这个工件的完整信息,甚至包括它是否存在。而在此工件到达后,我们可以选择立刻安排它,或者将此工件推迟到之后的某个时间再进行安排。我们的目标是最小化时间表长。我们考虑的是此问题的四种特殊情形:嵌套加工机器集合、包含加工机器集合、树型加工机器集合以及区间加工机器集合。在第二章,我们考虑的是嵌套加工机器集合的情形。在我们的问题中,机器数目是任意的且工件都带有相同的加工时间。对于此问题,我们给出算法H1,在此算法中,我们将工件安排在时刻αp+kp(α=(?)/2,k= 0,1,2,...)加工,并且在任意时刻,我们优先安排带有最小|Mj|的工件。算法H1的竞争比为(?)/2并且此算法是该问题的最优在线算法。在第叁章,我们考虑的是包含加工机器集合的情形。首先我们考虑的问题是所有工件带有相同的加工时间且机器数是任意的。对于此问题,我们给出算法H2。H2与H1较为类似,不同的是我们不仅将工件安排在αp+kp时刻加工,还将工件安排在2αp + kp时刻加工,其中α =(?)-1,k= 0,1,2,...。我们证明了算法H2的竞争比为(?)并且它是此问题的最优在线算法。之后我们考虑的问题是机器数为2且工件的加工时间是任意的。同样我们给出了此问题的最优在线算法。在第四章,我们考虑的是树型加工机器集合。首先我们考虑的是机器数为3且工件的加工时间为任意的情形。我们证明了此问题的下界为3/2,并给出了此问题的最优在线算法。之后,我们考虑了树型图的一种特殊情形:星型图。我们考虑的是机器数为任意且工件都带有相同加工时间的情形。我们证明了此问题的下界为(?)并给出了此问题的最优在线算法。在第五章,我们考虑的是区间加工集合的情形。在我们考虑的问题中,工件的加工时间都相同且只有两种不同的加工机器集合。我们给出了此问题的下界为3/2,并给出了此问题的最优在线算法。(本文来源于《华东理工大学》期刊2018-04-10)

在线排序问题论文开题报告

(1)论文研究背景及目的

此处内容要求:

首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。

写法范例:

针对主客观因素交互影响下混合装配线的排序问题,建立以最小化工作站堵塞时间与最小化产品切换次数为目标的交互排序模型,并依据客车在实际加工过程中的传统排序方案与模型所得排序方案的结果进行对比分析。模型构建从客观因素出发,优化堵塞时间即"重构"作业框架,以达到对负荷高峰时期进行削峰处理的目的,并进一步在主观因素层面上,考虑线上操作者的作业惯性,降低线上操作者对频繁切换产品的出错率,保持较高熟练度时操作的方便与流畅性。引入主客观优化评价算法对模型进行计算,决策出最优任务调度方案。对比分析结果表明,模型获得的最优排序改善了装配线的生产堵塞时间,同时兼顾主观因素主导下的产品切换频率问题,对于节省装配过程中有限的时间资源和释放有限的空间资源具有很大的作用。

(2)本文研究方法

调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。

实证研究法:依据现有的科学理论和实践的需要提出设计。

定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。

定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。

跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。

模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

在线排序问题论文参考文献

[1].刘巍巍,杨浩,刘慧芳.基于SGRASP-LP算法的混流装配线排序问题[J].组合机床与自动化加工技术.2019

[2].甘雅文,侯亮,徐昌华,张炜,陈鼎.考虑产品切换的客车混流装配线排序问题[J].计算机集成制造系统.2019

[3].康帆.汽车混流装配线排序问题研究[J].时代汽车.2019

[4].周燕.带有机器故障的半在线排序问题[D].中国矿业大学.2019

[5].王利博.线性退化工件的分批在线排序问题[D].郑州大学.2019

[6].高焰红.平行批处理机上不相容族工件的在线排序问题[D].郑州大学.2019

[7].彭南南,张玉忠,柏庆国,王成飞.工件满足一致性的同类机在线分批排序问题[J].运筹学学报.2019

[8].周鹏程,刘朝晖.有服务等级约束的同类机在线排序问题的可分算法[J].华东理工大学学报(自然科学版).2018

[9].闵啸,朱俊蕾,刘静.两台带服务等级的可拒绝同型机排序问题的在线算法[J].运筹学学报.2018

[10].徐佳.带有加工机器约束的若干在线排序问题研究[D].华东理工大学.2018

标签:;  ;  ;  ;  

在线排序问题论文-刘巍巍,杨浩,刘慧芳
下载Doc文档

猜你喜欢