首页> 正文

具有相同设备的Job Shop调度问题的研究

2020-12-02阅读(520)

具有相同设备的Job Shop调度问题的研究

论文摘要

车间作业调度问题(Job Shop Scheduling Problem, JSSP)是一类具有时间约束、次序约束和资源约束的组合优化问题。理论上已经证明,JSSP是NP难问题,没有一个有效的算法能在多项式时间内求出其最优解。本文所研究的具有相同设备的车间作业调度问题是指能够加工同一道工序的设备不唯一,即存在一设备子集,其中的任意一台设备都能加工该道工序。显然,此类调度问题放宽了资源(设备)约束条件,扩大了寻优空间,增加了问题的难度。本文的研究目标是在满足约束条件的情况下,如何找到一种合适的排序,确定每道工序的开始加工时间,使得总的加工时间尽可能小。首先对具有相同设备的单产品Job Shop调度问题进行建模,将单产品映射为加工树;然后,确定所构造加工树的关键路径,并将关键路径上的工序入栈,对栈中工序进行遍历寻找叉点工序,并依据所找到的叉点工序对加工树进行分段,根据段内工序的特点将工序分为相关工序和独立工序,并采用前沿贪心规则和最优适应规则对段内工序制定相应的目标函数;最后根据段内工序的特点和相同设备资源之间的互补性对不同类型的工序采用不同的优化策略。同时,提出了一种以根对齐的方式将多产品或动态加入的产品构造成虚拟加工树的方法,从而对多产品或动态产品调度问题进行简化。对于动态Job Shop调度问题,当动态产品到达时,应对初始时刻到达的产品工序进行判断,以确定初始时刻产品的剩余工序,然后将初始时刻产品的剩余工序构造成一棵加工树,并将其与动态到达的产品构造成一棵新的虚拟加工树,将用来存放初始时刻产品工序的栈和队列清空,重新确定所构造的新虚拟加工树的关键路径,并按本文所制定的目标函数和调度策略对加工树进行处理。通过实例验证、比较,算法具有令人满意的复杂度,且近优效果好。因此,算法具有一定的理论和现实意义。

论文目录

  • 摘要
  • Abstract
  • 第1章 绪论
  • 1.1 课题研究的目的和意义
  • 1.2 国内外研究现状及分析
  • 1.3 课题来源及本文主要内容
  • 1.3.1 课题来源
  • 1.3.2 本文研究的主要内容
  • 1.4 论文结构
  • 第2章 车间作业调度问题概述
  • 2.1 JOB SHOP 调度问题的背景
  • 2.2 JOB SHOP 调度问题的含义
  • 2.3 JOB SHOP 调度问题中的概念和模型表示
  • 2.3.1 Job Shop 调度问题中的基本概念
  • 2.3.2 Job Shop 调度问题中的主要模型
  • 2.4 JOB SHOP 调度问题的特点
  • 2.5 JOB SHOP 调度问题的分类
  • 2.6 JOB SHOP 调度问题的分派规则和调度性能
  • 2.6.1 Job Shop 调度问题的分派规则
  • 2.6.2 Job Shop 调度问题的调度性能
  • 2.7 JOB SHOP 调度问题的研究方法
  • 2.8 JOB SHOP 调度中所存在问题的分析及发展趋势
  • 2.9 本章小结
  • 第3章 具有相同设备的单产品JOB SHOP 调度算法
  • 3.1 引言
  • 3.2 单产品JOB SHOP 调度问题描述
  • 3.3 单产品JOB SHOP 调度问题的目标函数及调度策略
  • 3.4 单产品JOB SHOP 调度算法
  • 3.5 算法复杂性分析
  • 3.6 调度实例及比较
  • 3.7 本章小结
  • 第4章 具有相同设备的多产品JOB SHOP 调度算法
  • 4.1 引言
  • 4.2 多产品JOB SHOP 调度问题描述
  • 4.3 多产品JOB SHOP 调度问题的分析
  • 4.4 算法设计
  • 4.4.1 目标函数
  • 4.4.2 算法描述
  • 4.4.3 多产品Job Shop 调度问题算法流程图
  • 4.5 算法复杂性分析
  • 4.6 多产品调度实例对比
  • 4.7 本章小结
  • 第5章 具有相同设备的动态JOB SHOP 调度算法
  • 5.1 引言
  • 5.2 动态JOB SHOP 问题描述
  • 5.3 动态JOB SHOP 调度问题分析
  • 5.4 算法设计
  • 5.4.1 目标函数
  • 5.4.2 算法描述
  • 5.4.3 动态Job Shop 调度问题算法流程图
  • 5.5 算法复杂性分析
  • 5.6 动态调度实例对比
  • 5.7 本章小结
  • 结论
  • 参考文献
  • 攻读硕士学位期间所发表的学术论文
  • 致谢

    • 相关论文文献

    • [1].建模分析外卖送餐员的调度问题[J]. 数理天地(初中版) 2020(04)
    • [2].求解调度问题的粒子群算法编码方法研究[J]. 武汉科技大学学报 2010(01)
    • [3].基于“实时智能”方法的港口物流调度问题研究[J]. 物流技术 2009(12)
    • [4].基于二分图匹配的一类多机调度问题研究[J]. 软件导刊 2009(07)
    • [5].带模糊排序的移动瓶颈法求解不确定调度问题[J]. 机械制造 2011(02)
    • [6].空间调度问题的非线性规划分析求解方法[J]. 计算机集成制造系统 2010(06)
    • [7].关于柔性制造系统调度问题的研究[J]. 牡丹江师范学院学报(自然科学版) 2010(02)
    • [8].工件有尺寸的单机批调度问题的在线算法[J]. 山东大学学报(理学版) 2009(12)
    • [9].飞机调度系统的数学模型设计[J]. 数码世界 2018(09)
    • [10].带有单服务器的并行机调度问题[J]. 沈阳大学学报(自然科学版) 2012(04)
    • [11].基于组合拍卖的多主体单机调度问题[J]. 计算机集成制造系统 2013(01)
    • [12].同型机在线调度问题研究进展[J]. 计算机集成制造系统 2012(03)
    • [13].粮食应急运输调度问题研究[J]. 河南工业大学学报(社会科学版) 2008(01)
    • [14].调度问题中的算法[J]. 中国信息技术教育 2020(11)
    • [15].基于多智能体的混合发电机组调度问题研究[J]. 陕西电力 2014(04)
    • [16].针对资源受限工程调度问题的一种局部优化算法[J]. 计算机应用与软件 2010(09)
    • [17].车间物料搬运系统多载量小车配送调度问题研究综述[J]. 科技风 2020(31)
    • [18].锁定初始调度的紧急工作单机重调度问题[J]. 东北大学学报(自然科学版) 2013(05)
    • [19].蚁群算法求解非等同并行机调度问题的研究[J]. 计算机工程与应用 2012(29)
    • [20].并行机调度问题粒子群优化研究[J]. 机械设计与制造 2010(10)
    • [21].求解定制物流调度问题的动态微粒群算法[J]. 计算机应用与软件 2011(08)
    • [22].物流调度问题的优化方法评述[J]. 商业研究 2009(05)
    • [23].多星监测调度问题的建模与仿真研究[J]. 飞行器测控学报 2009(04)
    • [24].钢铁行业可中断Jop-Shop调度问题研究[J]. 物流技术 2008(12)
    • [25].同类机环境下不同尺寸工件的分批调度问题[J]. 计算机集成制造系统 2012(01)
    • [26].带有并行机的混合Job Shop调度问题[J]. 中国管理信息化 2010(14)
    • [27].一种类微粒群算法及其在混流装配线调度问题中的应用[J]. 数学的实践与认识 2009(02)
    • [28].求解卫星地面站调度问题的演化学习型蚁群算法[J]. 系统工程与电子技术 2012(11)
    • [29].求解船体分段堆场调度问题的改进遗传算法[J]. 计算机集成制造系统 2012(12)
    • [30].解模糊交货期多机并行调度问题的改进量子遗传算法[J]. 计算机系统应用 2011(09)

    标签：;  ;  ;  ;  ;  

    具有相同设备的Job Shop调度问题的研究
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5