单位工件平行机并行分批在线排序问题算法,这是一篇与工件论文范文相关的免费优秀学术论文范文资料,为你的论文写作提供参考。
工件论文参考文献：
摘 要：本文研究一类批容量有界的并行分批、平行机在线排序问题.模型中有n个相互独立的工件J等于{J1,等,Jn}要在m台批处理机上加工.批处理机每次可同时加工至多B（B 关键词：排序；并行批；最大完工时间；在线算法；竞争比 中图分类号：0225 文章标识码：A 文章编号：1007-3221（2015）01-0137-05 引言 分批排序问题是排序论的一个重要分支,兴起于90年代初应用背景极强的一类最优化问题.它的研究结果主要应用于大规模的现代化生产流水作业线如半导体生产、航空工业、钢铁铸造、制鞋业等等,研究并行分批排序问题具有十分重要的实际意义. 并行分批排序可以描述为：有n个相互独立的工件J等于{J1,等,Jn}待加工,工件Jj（1≤j ≤n）的到达时间记为rj,加工时间记为pj.有m台批处理机{M1,M2,等,Mm},批处理机每次可同时加工至多B（B称为机器的批容量）个工件,加工时间不同的工件可作为一批来加工,批的加工时间是此批中工件的加工时间的最大者.同一批中工件同时开工、同时完工.注意到当B等于l时,此问题即为经典排序问题.分批排序打破了经典排序一台机器在同一时间只能处理一个工件的约束,是经典排序问题的一种推广.根据批容量的特征,并行分批排序可分为两种类型：批容量无界,即B等于∞；批容量有界,即B 本文考虑一个批容量有界的在线并行分批排序问题：设有n个相互独立的工件J等于{J1,等,Jn}要在m台批处理机M等于{M1,等,Mm}上加工.工件Jj（1≤j≤n）的到达时间为r,,加工时间为1,即pj等于1,批处理机每次可同时加工至多B（B 衡量一个在线排序算法A的性能最常用的指标是它的竞争比RA,即把在线排序算法的结果和对相同工件运用离线排序算法得到的结果进行比较.对于最小化目标函数的在线排序问题,竞争比RA定义为对问题的所有实例运行该在线排序算法所得目标函数值和相应离线排序的最优值比值的上确界,即RA等于,其中CA（I）为实例,的在线排序算法A所得目标函数值,c*（I）为实例,的离线排序的最优值.显然,RA≥1.竞争比越小则在线近似算法越好. 对于排序问题等,Zhang G.C.等分别设计出了竞争比是l+a的算法,并证明该排序问题不存在竞争比小于l+a的在线算法,其中a满足等式a2+a等于1.Poon C.K.和Yu W.C.给出了一族竞争比为1+a的算法.上述算法都利用了等待的思想.不等待的算法竞争比不可能小于2,在FBLPT基础上会达到这个界.对于此问题的一些特殊情况,Richardand P.R.和Ridouard F.,Yuan J.J.和Nong Q.Q.给出了等待时间更少的算法. 对于排序问题等猜想l+a是最好下界.Zhang G.C.等证明了该问题竞争比的下界是1+a,对于工件只有两个到达时间的情形给出了竞争比达到最好可能的算法；对于有任意多个到达时间的一般情况给出了竞争比为2的算法.Poon C.K.和Yu W.C.给出了一个算法族,证明了这一族算法的竞争比均不超过2,并证明了其中一个算法对于B等于2的情形竞争比为. 对于排序问题等,Tian J.等分别给出了竞争比为l+am的在线算法,并证明该排序问题不存在竞争比小于1+a.的在线算法,其中Ol 算法背景 对于排序问题,Zhang G.C.等给出了一个竞争比为1+a的算法,并证明了该排序问题不存在竞争比小于l+a的在线算法.记U（t）为t时刻已到达但尚未加工的工件集合；r（t）为U（t）中最晚工件的到达时间；|U（t）|为U（t）中工件的数目.算法Ab（a）描述如下： 算法Ab（a） 若|U（t）|等于0,等待,更新U（t）； 若0<βU（t）| 若|U（t）|≥B且有机器空闲,则将U（t）中B个工件组成一批在最早可空闲的机器上加工这一批. 在算法中,处理0<|U（t）| 结论：关于对写作工件论文范文与课题研究的大学硕士、相关本科毕业论文什么是工件的安装论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。 关于单台批处理机在线排序 带强制工期双机开放车间排序问题 带交货期工件族生产和配送排序问题 有尺寸同型机分批排序问题近似算法
摘要：一台批处理机一次可以同时加工多个工件(称为一批)，每批工件有相同的开工和完工时间，加工时间等于其中最长工件的加工时间。本文研究单台批处理机。
摘要：讨论了强制工期相等的n个工件在双机开放车间加工。在允许机器空闲的条件下，寻找一个工件排序，使得最大提前完工时间最小。由于工件不允许延迟，问。
摘要：本文考虑了多个客户订购不同种类的工件，工件生产完后需要运输到客户的单机供应链排序问题。由于工件属于不同的种类，在加工不同种类工件前要有一个。
摘要：对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法。对于大工件（工件的体积严格大于机器容量的1 2）的加工时间不小于。