平行批处理机上不相容族工件的在线排序问题

论文摘要

排序是指把每个工件的加工时长全部分配到一台机器或多台机器的一个或多个加工时间段上.排序问题的含义是决策者找到一个排序算法满足特定的限制条件,使得目标函数达到最优.通常情况下,排序问题分为离线排序问题和在线排序问题.本文考虑在线排序问题.在在线排序问题中,只有工件到达了,决策者才知道该工件的所有信息.批处理问题是指把己到达且未被加工的工件分组成批,并安排这些批次的加工顺序以及对应的加工机器.平行分批是指机器可以同时加工一个批次中的所有工件,即同一个批次的工件有相同的开工时间.批次的加工时间为该批次中所有工件的最大加工时间,故批次中所有工件有相同的开工时间,加工时长和完工时间.由于不同工件族中工件是不相容的,从而不同工件族中工件不能在同一个批次中加工.批容量是指在一台机器上能够同时加工工件的最大数目,一般用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

分类: 基础科学

专业: 数学

单位: 郑州大学

分类号: O223

总页数: 46

文件大小: 2172K

下载量: 13

相关论文文献

• [1].目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报 2019(04)
• [2].具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报 2019(04)
• [3].基于Flexsim的零件加工排序仿真实现方法研究[J]. 新技术新工艺 2020(02)
• [4].总加权误工损失的两个代理单机排序问题[J]. 湖北民族学院学报(自然科学版) 2019(01)
• [5].机器带周期性维护时段的加工与运输协同排序问题[J]. 浙江理工大学学报(自然科学版) 2016(06)
• [6].带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报 2016(04)
• [7].具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J]. 沈阳航空航天大学学报 2016(06)
• [8].关于工期分配与加权误工数的双指标排序问题（英文）[J]. 工程数学学报 2017(01)
• [9].带有交货期窗口和加工时间可控的排序问题[J]. 沈阳师范大学学报(自然科学版) 2016(04)
• [10].具有学习效应和遗忘效应的单机排序问题研究[J]. 枣庄学院学报 2017(02)
• [11].资源定时投放的单机排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(02)
• [12].有公共交货期的单机分批排序问题（英文）[J]. 重庆师范大学学报(自然科学版) 2017(02)
• [13].在退化维修活动下具有多窗口及退化效应的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)
• [14].一类资源费用可变的平行机排序问题[J]. 上海第二工业大学学报 2017(02)
• [15].数学规划与约束规划整合下的多目标分组排序问题研究[J]. 运筹学学报 2016(01)
• [16].具有学习效应的排序问题的某些新进展[J]. 沈阳师范大学学报(自然科学版) 2014(04)
• [17].有界平行批处理机的在线排序问题[J]. 河南师范大学学报(自然科学版) 2015(05)
• [18].集思[J]. 福建教育 2020(25)
• [19].高中数学一道数列典型题解法的探究[J]. 数学学习与研究 2016(23)
• [20].单机排序问题的研究[J]. 数学学习与研究 2017(24)
• [21].一个排序问题的解决[J]. 中等数学 2009(07)
• [22].具有多个制造商和分批配送的同类机排序问题[J]. 系统科学与数学 2019(09)
• [23].工件具有加工位置上限最小化加权总误工量的单机排序问题（英文）[J]. 运筹学学报 2020(02)
• [24].具有恶化效应与可控加工时间的工期指派排序问题研究[J]. 沈阳航空航天大学学报 2019(05)
• [25].优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报 2016(04)
• [26].具有公共流、退化效应与维护和资源分配的单机窗口排序问题[J]. 沈阳航空航天大学学报 2016(05)
• [27].关于总误工损失的两个代理单机排序问题[J]. 运筹学学报 2017(01)
• [28].具有不同生产时区费用的单机可拒绝排序问题[J]. 数学的实践与认识 2017(04)
• [29].具有柔性维护周期的单机误工排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(03)
• [30].带有多个工期窗口及退化维护的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)

标签：在线算法论文;  平行分批论文;  不相容工件族论文;  最小化时间表长论文;