带周期性维护时间的平行机排序问题研究

带周期性维护时间的平行机排序问题研究

论文摘要

本文研究了带有维护时间(单个或周期性)的平行机排序问题。该问题可以描述为:给顶一个相互独立的工件序列J={J1,J2,…,Jn},每个工件的加工时间(长度)是pi,i=1,…,n,且需要把它们分配到一台(或多台)平行机上进行不可中断地加工。在加工过程中,需要对机器进行维护,而工件在维护时段内不能加工。工件和机器在零时刻都处于就绪状态。全文共分为三章。第一章是绪论部分,主要介绍排序问题相关的一些概念和预备知识。第二章介绍了带单个维护时段的单机排序问题,分两种情况:维护时段固定、维护时段可选择。第三章讨论了带周期性维护时间的平行机排序问题。本章证明了LS算法是P1|periodic-mainten ance|Cmax在线情况的最优算法,算法竞争比为2。证明了两台机P2|periodic-maintenance|Cmax情况下,不存在常数界多项式时间算法。此外,给出了一个离线算法的参数界。

论文目录

  • 摘要
  • Abstract
  • 第一章 绪论
  • 1.1 平行机排序问题
  • 1.2 离线、在线、半在线问题和算法性能分析
  • 1.3 论文概述
  • 第二章 带单个维护时段的单机排序问题研究
  • 2.1 引言
  • 2.2 维护时段固定的情况
  • 2.2.1 维护时段前后机器加工速率不改变
  • 2.2.2 维护时段前后机器加工速率改变
  • 2.3 维护时段可选择的情况
  • 第三章 带周期性维护时间的平行机排序问题研究
  • 3.1 引言
  • 3.2 单台机的最优在线算法
  • 3.2.1 复杂性证明
  • 3.2.2 LS算法的竞争比
  • 3.2.3 在线情形问题下界
  • 3.3 两台机问题讨论
  • 3.3.1 复杂性证明
  • 3.3.2 一般情况下不存在常数界多项式时间算法
  • 3.3.3 离线算法及其参数界
  • 参考文献
  • 致谢
  • 相关论文文献

    • [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文档

    猜你喜欢