与资源相关加工时间可变的单机排序问题

与资源相关加工时间可变的单机排序问题

论文摘要

排序理论有时也被叫做时间表理论,因其广泛的实用性逐渐成为运筹学中一个分支学科。如工厂生产设备时涉及到的进程调度,机场管理过程中也需要用到排序知识来调度。传统意义上的调度问题研究一般基于工件或任务的加工时间恒定不变情况进行的。然而在实际生产过程当中,有些任务的加工时间可能会因某些效应影响或资源有限等因素而发生变化。本文针对上述现象共讨论下面几类问题:第一部分简要介绍研究排序问题用到的相关知识和符号,阐述了单机排序问题的研究背景以及发展历程,最后描述本文的主要工作及贡献。第二部分从简单问题着手,首先研究带有退化效应加工时间可变的的单机排序问题。本节建立的加工时间模型共享同一段时间作为交货期窗口,并带有凸资源分配。工件的加工时间与工件所处位置、派发给工件的负荷量、不可再生资源总数量相关。分析两种问题,第一种是在添加了资源约束的条件下,极小化因存在交货期窗口而产生提前惩罚、延误惩罚、交货期窗口大小等一系列费用和问题。第二种是在第一种问题启发下,从反向思考,假定任务生产过程中,关于交货期窗口的一系列费用受到限制,从而使总资源量达到最小。在文末给出两个问题的最优多项式时间算法及相应的算法复杂度。第三部分中进一步讨论带有学习效应和退化效应的加工时间模型,考虑到如果对与任务所处位置关联的学习效应不加控制,则排在后面的任务加工时间会迅速趋近于零,故而增加截断控制因子,以保证所研究模型的实用性。本部分中所有工件仍具有同一个交货期窗口并分别讨论如下两种模型。第一种首先对资源总量开启限制模式,从而极小化因存在交货期窗口而导致的提前或延误惩罚、共同交货期窗口起始时刻和规模、总完工时间绝对差、总完工时间的费用和。第二种对上述总费用加以限制,在求出最优任务排序方式,最优交货期窗口的位置及规模后,来极小化总资源量。针对上述两个问题,经证明均为多项式时间可解,进而化为指派问题,并相应给出两个最优算法及一个算例。第四部分在前三部分基础上添加准备时间,即任务集中每一个工件开始加工之前都需要一段时间准备。本部分依旧在凸资源消费函数的大背景下研究目标函数,所有工件共享同一段时间作为交货期窗口,工件的实际加工时间会因设备保管不善而带有退化现象,并取决于派发给工件待完成的任务量以及不可再生资源数量。此外,每个工件还有一个可控的准备时间,同样依赖派发的不可再生资源数量。目标是在资源总量有限的情况下,通过确定最优排序方式,资源配置方式,交货期窗口位置及规模来极小化带有提前和延误惩罚费用、公共交货期窗口起始时刻,交货期窗口规模一系列总费用。最后将研究问题推导转为匹配问题,并给出一个启发式算法及近优解。最后,归纳全文并进一步提出今后研究侧重点。

论文目录

  • 摘要
  • abstract
  • 第一章 引言
  •   一、预备知识
  •   二、排序问题的国内外研究现状
  •   三、本文主要内容及结果
  • 第二章 具有退化效应以及凸资源分配的单机排序问题
  •   一、引言
  •   二、问题描述
  •   三、最优算法
  • 第三章 具有截断控制学习效应和凸资源分配单机调度问题
  •   一、引言
  •   二、问题描述
  •   三、问题最优解
  • 第四章 具有准备时间的加工时间可变的单机排序问题
  •   一、引言
  •   二、问题描述
  •   三、问题近优解
  • 结论
  • 参考文献
  • 致谢
  • 个人简历
  • 在校期间研究成果和发表的学术论文
  • 文章来源

    类型: 硕士论文

    作者: 李石

    导师: 罗成新

    关键词: 排序,资源分配,指派问题,学习效应,退化效应

    来源: 沈阳师范大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 沈阳师范大学

    分类号: O223

    总页数: 42

    文件大小: 1278K

    下载量: 37

    相关论文文献

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

    猜你喜欢