带有机器故障的半在线排序问题

带有机器故障的半在线排序问题

论文摘要

排序理论是运筹学中一个非常活跃的分支.通常,我们将排序问题分为离线排序和在线排序.本文研究了带有机器故障的半在线排序问题,是指在排序之前,工件的到达时间,加工时间,运输时间等信息均已获知,但机器故障何时发生何时结束等信息是无法提前知道的,决策者只能根据到达工件的所有信息给出决策方案.本文我们研究了两类排序问题,一类是带有机器故障和运输时间的单机半在线排序问题,一类是带有机器故障的平行批单机半在线排序问题.其中,平行分批排序是多个工件可以放在同一批,在一台机器上加工,每批里面的工件同时开始加工同时完工,每批的加工时间是该批中所有工件的最大加工时间.批容量(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.

论文目录

  • 致谢
  • 摘要
  • abstract
  • 变量注释表
  • 1 绪论
  •   1.1 研究背景
  •   1.2 排序问题的基本概述
  •   1.3 研究现状
  •   1.4 论文结构
  • 2 带有机器故障和运输时间的半在线排序问题
  •   2.1 排序模型的介绍
  •   2.2 问题的下界
  •   2.3 算法及证明
  • 3 带有机器故障的平行批半在线排序问题
  •   3.1 排序模型的介绍
  •   3.2 问题下界
  •   3.3 算法及证明
  • 4 总结与展望
  • 参考文献
  • 作者简历
  • 学位论文数据集
  • 文章来源

    类型: 硕士论文

    作者: 周燕

    导师: 付乳燕

    关键词: 半在线排序,批处理机,机器故障,运输时间,竞争比

    来源: 中国矿业大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 中国矿业大学

    分类号: O223

    总页数: 42

    文件大小: 1198K

    下载量: 17

    相关论文文献

    • [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)

    标签:;  ;  ;  ;  ;  

    带有机器故障的半在线排序问题
    下载Doc文档

    猜你喜欢