带有工件约束的平行机排序问题的近似算法研究

论文摘要

排序理论作为组合优化领域的一个重要组成部分,具有重要的理论意义和实际应用价值.排序实际是一种决策过程.在经典的离线排序中,决策者根据所有的信息进行决策.在线排序中,工件的所有信息是分阶段逐步释放给决策者的,并且决策者只能根据当前已有的信息来做决策和安排工件.本论文主要考虑几类工件带有约束的排序问题:工件带有链组约束关系是指工件间的序约束关系是一条链,每个工件在它的前任都完工后才可以加工;工件带有权重是指工件具有优先因子,一般表示该工件的重要性或紧急程度;工件带有限选机器集,是指每个工件只能在指定的部分机器上进行加工.此外在批处理机上,多个工件可以作为一批同时加工,此时批的加工长度等于该批中最长工件的加工长度.每批中至多可加工的工件个数称为批容量:当批容量B不小于需要被加工的工件总个数n时,称为批容量无界模型;反之称为批容量有界模型.第一章介绍了一些排序理论的知识,着重介绍了与本论文相关的排序研究的现状,并列举了一些主要结果.第二章中考虑m台平行机上工件带有链组约束的在线排序,工件具有相同的加工长度,目标是最小化最大完工时间.该问题在m=2时已经被解决,我们考虑m≥3的情形.首先证明该问题在线算法竞争比的下界为1+αm,其中当3≤m≤5时,αm是方程αm2+3αm-1=0的唯一正根;当m≥6时,αm是方程αm3+4αm2+5αm-2=0的唯一正根.其次给出达到该竞争比的最好可能的在线算法.第三章中考虑m台批处理机上工件带有链组约束的在线排序,工件具有相同的加工长度,目标是最小化最大完工时间.机器具有不小于2的有界批容量.我们指出该问题在线算法竞争比的下界为（?）,并给出达到该竞争比的最好可能的在线算法.第四章中考虑m台一致批处理机上工件带有权重的在线排序,工件具有相同的加工长度,目标是最小化加权完工时间和.机器的批容量无界B≥n.在m台机器中,前λ（λ≥2）台机器的速度为s（s≥1）,后m-λ台机器的速度为1.我们首先证明该问题在线算法竞争比的下界为ρ=min{1+θ,1+η},其中θ和η是分别是方程（1+θ）λ+1=2+θ和（?）的唯一正根.其次给出达到该竞争比的最好可能的在线算法.第五章中考虑m台批处理机上最小化最大加权流程时间的在线排序.工件带有相同的加工长度以及在一给定范围内的权重wj∈[1,w].首先当批容量无界B≥n时,我们证明该问题在线算法竞争比的下界为（?）,并给出达到该竞争比的最好可能的在线算法;其次当批容量有界且不小于2时,对w=2情形给出竞争比为2的最好可能的在线算法.此外对于单台机上批容量有界2≤B<n时的一般情形wj∈[1,w],我们证明该问题在线算法竞争比的下界为（?）,并构造对应的在线算法.该在线算法在w∈[1,2]时,竞争比为（?）,是最好可能的在线算法;在w∈（2,+∞）时,竞争比不大于w.第六章中考虑工件带有限选机器集的两个离线排序问题,机器具有有界的批容量,目标是最小化最大完工时间.对批处理机上工件带有嵌套关系的限选机器集的问题,我们给出强多项式时间算法,并证明该算法在机器批容量不同和相同时分别是2-近似的和（2-1/m）-近似的.该结果改进了已知的仅适用于批容量相同情形的（3-1/m）-近似的算法.对一致批处理机上工件带有树形关系的限选机器集的问题,当批容量不同时,我们给出了2-近似的快速算法.该结果改进了已知的仅适用于批处理机上工件带有包含关系的限选机器集的9/4-近似的算法.此外当批容量相同时,给出更好的（2-1/m）-近似的算法.

论文目录

文章来源

类型: 博士论文

作者: 柴幸

导师: 李文华

关键词: 链组约束,权重,限选机器集,分批排序,近似算法,竞争比

来源: 郑州大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 郑州大学

分类号: O223

总页数: 121

文件大小: 1657K

下载量: 61

相关论文文献

• [1].莱芜煤机公司师傅刘义(右)与徒弟张龙哲探讨交流工件加工工艺改进技术[J]. 中国工会财会 2019(06)
• [2].具有错位限制且工件可退化的单机重新排序问题[J]. 系统科学与数学 2018(04)
• [3].工件加工工序的自由度分析[J]. 企业科技与发展 2008(10)
• [4].薄环工件加工过程易产生变形问题的探讨[J]. 硅谷 2008(23)
• [5].机械加工中振动对工件的影响[J]. 辽宁省交通高等专科学校学报 2018(05)
• [6].工件具有子工件工期的排序问题[J]. 运筹学学报 2019(02)
• [7].深小孔类工件加工工艺研究[J]. 制造技术与机床 2020(05)
• [8].带有固定区间的单机双代理可中断总误工问题[J]. 运筹学学报 2019(01)
• [9].利用振动时效技术解决薄壁半圆形工件加工变形[J]. 金属加工(热加工) 2010(16)
• [10].机械加工中工件变形的原因及预防措施探微[J]. 山东工业技术 2019(03)
• [11].专用于环形工件的新型电火花机床打磨设备的设计及其功能研究[J]. 宁波工程学院学报 2019(03)
• [12].基于几何特征的工件加工能耗预测研究[J]. 组合机床与自动化加工技术 2017(11)
• [13].工件可拒绝的有限等待置换流水车间调度算法[J]. 控制与决策 2019(03)
• [14].单机上简单线性退化工件的随机在线调度问题[J]. 信阳师范学院学报(自然科学版) 2018(04)
• [15].考虑工件移动和成本的多目标柔性作业车间调度问题优化研究[J]. 现代制造工程 2019(07)
• [16].航天阀门壳体工件专用夹具设计[J]. 制造技术与机床 2017(10)
• [17].差异容量平行批机器环境下基于弱选择约束的调度算法[J]. 控制与决策 2018(08)
• [18].带恶化工件的不相关并行机调度优化[J]. 系统仿真学报 2019(05)
• [19].基于普通立式加工中心的磨削工艺[J]. 科技资讯 2015(03)
• [20].实现更高效的框架结构工件加工[J]. 现代制造 2020(19)
• [21].解决大重型工件加工难题[J]. 金属加工(冷加工) 2011(09)
• [22].高速铣削中薄壁工件加工振动的研究[J]. 煤矿机械 2008(06)
• [23].柱形工件加工存取系统研究[J]. 工业仪表与自动化装置 2019(06)
• [24].大尺寸高精度锥轴工件精加工过程检测及补偿方法研究[J]. 制造技术与机床 2019(01)
• [25].机械加工中工件变形的原因及预防措施探讨[J]. 中外企业家 2019(28)
• [26].铣削加工平面类工件的注意事项和装夹技巧[J]. 现代制造技术与装备 2018(08)
• [27].制造执行中订单投放顺序与工件加工批量集成决策[J]. 北京理工大学学报 2008(09)
• [28].弧面类工件加工辅助治具的设计与制作[J]. 同煤科技 2020(03)
• [29].基于S7-1200 PLC的工件装配自动化生产线控制系统设计[J]. 韶关学院学报 2019(03)
• [30].某异形薄壁工件加工工艺研究[J]. 制造技术与机床 2019(06)

标签：链组约束论文;  权重论文;  限选机器集论文;  分批排序论文;  近似算法论文;  竞争比论文;