限选机器上的在线排序问题

发布时间：2020-05-07 13:19

【摘要】：在恒同机中每台机器都有相同的速度,这里我们假设所有机器的速度为1.这样工件的加工时间与机器没有关系,仅与它自身的长度有关.限选机器是指机器因功能不同导致工件在选择机器加工时受到限制,从而工件只能在允许加工的特殊机器子集上加工.将允许加工工件的机器组成的集合称为加工集.在线排序是指只有在工件到达之后才能知道工件的信息,甚至它的存在性.工件按到达方式可分为按时在线和按序在线两类.在本文第二章中,我们主要探讨了 m台限选恒同机上的在线分批排序问题.平行分批是指一台机器一次可以同时加工B个工件.当B ≥ n时,我们称该分批为无界平行批.当Bn时,我们称它为有界平行批.其中n表示工件数目.在这里工件是按时到达的(即当有工件出现时,我们可以选择立即加工或等待),且所有工件的加工长度都相同.目标函数是最小化所有工件被运输完成的时间.我们假定有充分多的运输工具.即工件一旦完工便可被运输.对于工件具有嵌套加工集的情形,我们分别讨论了批容量有界和批容量无界两种情况.其中嵌套的定义为:对任意两个工件J和Jj的加工集Mi和Mj有Mi(?)Mj或Mj(?)Mi或Mi(?)Mj=(?)当批容量无界时,可用三参数法表示为Pm|Mj(nested),pj=,p,qj,P-batch,B ≥ n,online|Lmax.我们给出了竞争比为(?)的最好可能的在线算法.当批容量有界时,我们考虑运输时间有如下限制:对任意两个工件Ji和Jj的加工集M和Mj,若Mi(?)Mj,则有qi≥qj成立.对Pm|Mj(nested),pj=p,rj,qj,P-ba]ch,Bn,Online|Lmax,我们给出竞争比为(?)的最好可能的在线算法.另外,我们考虑了工件具有分层加工集(即任意两个工件的加工集具有包含与被包含的关系)的情形,即问题Pm|Mj(GOS),pj =p,rj,qj,P-batch,5n,online|Lmax.此处运输时间的限制于第三节中的限制相同.当B ≥ 2时,问题的在线算法的竞争比的下界也是(?),上述嵌套情形的算法对该问题亦是最好可能的.当B = 1时,我们证明该问题的下界是3/2,同时给出竞争比为3/2的最好可能的在线算法.在本文第三章中,我们研究了 m台恒同机上工件长度在固定区间内取值的在线排序问题,且工件具有两层加工集(即g = 2).所有工件的加工长度属于[1,β](β1).目标函数是最大化最小机器装载量,用三参数表示法表示为P|GOS(q = 2),pj ∈1l,β],online,over-list|Cnmin.这里的工件是按顺序到达的,只有当前已经到达的工件被安排之后,下一个工件才会到达.工件到达之后会被立即安排.在本章中机器被分为两层.第一层机器可以加工所有的工件,但第二层机器只能加工特定的工件.我们给出了竞争比为1+kβ的最好可能的在线算法,其中= 1或k = m-1.其中k表示第一层机器的数目.
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O223

【相似文献】

相关期刊论文 前10条

1 韩飞;;高中数学一道数列典型题解法的探究[J];数学学习与研究;2016年23期

2 豆俊梅;孙彩贤;;单机排序问题的研究[J];数学学习与研究;2017年24期

3 胡觉亮;杨佳雯;苏晓彤;董建明;;机器带周期性维护时段的加工与运输协同排序问题[J];浙江理工大学学报(自然科学版);2016年06期

4 仲维亚;马晓茹;;带有运输且加工具有灵活性的无等待流水作业排序问题[J];运筹学学报;2016年04期

5 隋楠;罗成新;;具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J];沈阳航空航天大学学报;2016年06期

6 林浩;何程;;关于工期分配与加权误工数的双指标排序问题（英文）[J];工程数学学报;2017年01期

7 赵传立;张蕾;;带有交货期窗口和加工时间可控的排序问题[J];沈阳师范大学学报(自然科学版);2016年04期

8 王申重;杜海龙;;具有学习效应和遗忘效应的单机排序问题研究[J];枣庄学院学报;2017年02期

9 陈蕾;张安;陈永;陈光亭;;资源定时投放的单机排序问题[J];杭州电子科技大学学报(自然科学版);2017年02期

10 窦文卿;范静;;一类资源费用可变的平行机排序问题[J];上海第二工业大学学报;2017年02期

相关会议论文 前10条

1 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

2 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 胡荣;吕绪华;;3TMF排序问题的计算复杂性及分支定界法[A];中国运筹学会第八届学术交流会论文集[C];2006年

8 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 吴翠连;;有尺寸的单机分批排序问题的近似算法[A];中国企业运筹学[2011（1）][C];2011年

相关重要报纸文章 前3条

1 杨文波;浅谈方位词“东、西、南、北”的词语排序问题[N];语言文字周报;2018年

2 山东 赵玉勇;小博士编程[N];电脑报;2004年

3 何靖;全国计算机应用技术证书考试（NIT）[N];中国电脑教育报;2003年

相关博士学位论文 前10条

1 沈佳煜;不确定情形下若干排序问题的研究[D];南京理工大学;2017年

2 高园;新型排序问题的计算复杂性研究[D];郑州大学;2018年

3 殷娜;依赖于资源分配的排序问题研究[D];上海大学;2015年

4 李好好;若干排序问题研究[D];浙江大学;2014年

5 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

6 罗润梓;平行机半在线排序问题[D];上海大学;2005年

7 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

8 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

9 李文华;关于分批排序问题的研究[D];郑州大学;2006年

10 赵洪銮;窗时排序问题中的最优化算法研究[D];山东大学;2007年

相关硕士学位论文 前10条

1 王穆清;同类机上的在线分批排序问题[D];曲阜师范大学;2018年

2 王晓连;模糊数空间上的排序问题[D];杭州电子科技大学;2018年

3 李丹;两类资源受限的排序问题研究[D];杭州电子科技大学;2018年

4 张洁;按外包工件个数不同折扣率的单机排序问题[D];郑州大学;2018年

5 周松涛;带约束的单机双代理排序问题[D];郑州大学;2018年

6 朱月娟;限选机器上的在线排序问题[D];郑州大学;2018年

7 孙振霞;机器具有不可用区间且工件可拒绝的排序问题[D];郑州大学;2018年

8 陈耀宁;与资源有关的多次维修和加工时间可变的排序问题研究[D];重庆师范大学;2018年

9 孟凡晓;基于退化效应的可拒绝分批排序问题[D];曲阜师范大学;2018年

10 潘婷婷;带资源、学习效应、恶化效应、维护活动和工期窗口的排序问题的研究[D];苏州大学;2018年

，

本文编号：2653034