批运输排序与物流调度的算法研究

论文摘要

排序问题又称为调度问题,关注的是稀缺资源的优化配置,是组合优化领域的一个重要分支.作业调度实质上是要解决如何按时间的先后,将有限的资源分配给不同的作业任务,使预期的目标最优化的问题.调度问题在实际生活中有着广泛的应用,例如在机械制造过程中的批作业调度、供应链管理中加工运输协调、互联网领域的节能、生产线上的流水作业、飞机航班的排序等等.由于生产加工和运输的资源有限,如何安排加工顺序以及怎样运输的问题日益引起许多学者的关注.本文分别研究了带批运输的两阶段流水作业批量调度、三台机器的流水作业排序和分批排序与物流调度等问题.针对这三个问题,我们分别提出了多项式时间算法和启发式算法并分析了算法的有效性.文章具体组成如下:首先,介绍了本文的研究背景及研究意义,回顾了排序理论的发展历程,简述了课题研究现状及本文的具体工作安排.对排序理论、算法和计算复杂性的基本概念做了简单的描述,给出一些预备知识,为本文的研究内容提供了基本知识储备.其次,研究了两阶段流水作业批量调度问题.尺寸不同的工件首先在第一台机器上批量加工,半成品由单个运输车分批运输到第二台机器上进行单个加工.运输车的容量为c,这意味着在一个运输批次中工件的总大小不能超过运输车的容量.该问题的目标在于如何选择工件的加工顺序使最大完工时间最小.针对带批运输的两阶段流水作业批量调度问题,我们设计了启发式算法,分析了算法的最坏性能比,并用数值例子验证了算法的有效性.第三,研究了考虑带运输的三台机器流水作业调度问题.所有的工件必须首先在机器M1上进行加工,然后由一辆运输车运输到机器M2上进一步加工,最后由另一个车辆运输到第三台机器进行最后的处理.问题的研究目标是找到n个作业加工及运输方案使最大完工时间最小.已知问题是NP-难的,我们分别针对几种情况建立模型,给出了近似算法,并分析了其最坏性能比.第四,研究了从加工生产工件到将成品交付客户的物流调度问题.问题分为两个阶段:第一阶段是加工阶段,不同权重的工件在一台机器上分批加工;第二阶段是运输阶段,完工的工件可以通过多种运输方式批量交付给各种预先指定的目的地.研究的目标是使加权完工时间和运输费用的总和达到最小.我们对几种特殊情况下的问题复杂性做了一个全面的描述,提出了多项式可解情形的算法.同时,我们也提供了一般的情况下的近似算法,并对算法的性能进行了复杂性分析.

论文目录

文章来源

类型: 博士论文

作者: 李岩

导师: 史少云

关键词: 流水作业,批运输,分批排序,近似算法

来源: 吉林大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 吉林大学

分类号: O223

总页数: 89

文件大小: 3250K

下载量: 158

相关论文文献

• [1].考虑倒垛情况的场吊调度问题研究[J]. 交通运输工程与信息学报 2017(02)
• [2].一种电网经济调度问题的分布式对偶优化解法[J]. 山西建筑 2016(33)
• [3].云制造调度问题研究综述[J]. 计算机集成制造系统 2017(06)
• [4].水电混合网络经济调度问题的分布式优化算法设计与分析（英文）[J]. 电子科技大学学报 2020(05)
• [5].考虑维护且原材料易变质的单机调度问题[J]. 黑龙江工业学院学报(综合版) 2020(07)
• [6].混合并行机调度问题的多目标优化模型及算法[J]. 控制理论与应用 2014(11)
• [7].建模分析外卖送餐员的调度问题[J]. 数理天地(初中版) 2020(04)
• [8].求解调度问题的粒子群算法编码方法研究[J]. 武汉科技大学学报 2010(01)
• [9].基于“实时智能”方法的港口物流调度问题研究[J]. 物流技术 2009(12)
• [10].考虑空载能耗的双代理单机调度问题[J]. 电子世界 2020(10)
• [11].浅谈公共自行车调度问题[J]. 科技风 2015(21)
• [12].基于二分图匹配的一类多机调度问题研究[J]. 软件导刊 2009(07)
• [13].航空器着陆调度问题的一种新型元启发式方法（英文）[J]. Transactions of Nanjing University of Aeronautics and Astronautics 2020(02)
• [14].综合考量借还车需求与调度成本的公共自行车调度优化模型[J]. 中国公路学报 2019(07)
• [15].考虑行为特征的分布式流水线调度问题研究[J]. 信息通信 2019(06)
• [16].大数据背景下集群调度结构与研究进展[J]. 计算机研究与发展 2018(01)
• [17].具有负载依赖型维护时长和弹性维护开始时刻的单机调度问题[J]. 江西科学 2017(01)
• [18].考虑设备定周期预防性维护的单批处理机调度问题研究[J]. 电子世界 2020(15)
• [19].带模糊排序的移动瓶颈法求解不确定调度问题[J]. 机械制造 2011(02)
• [20].空间调度问题的非线性规划分析求解方法[J]. 计算机集成制造系统 2010(06)
• [21].关于柔性制造系统调度问题的研究[J]. 牡丹江师范学院学报(自然科学版) 2010(02)
• [22].工件有尺寸的单机批调度问题的在线算法[J]. 山东大学学报(理学版) 2009(12)
• [23].考虑成本的最大延迟时间同类机调度问题[J]. 运筹与管理 2019(12)
• [24].微电子生产过程调度问题基于指标快速预报的分解算法[J]. 控制与决策 2020(01)
• [25].配网调度精细化管理对策[J]. 低碳世界 2018(10)
• [26].基于优先规则的复杂并行机调度问题研究[J]. 系统工程理论与实践 2016(03)
• [27].飞机调度系统的数学模型设计[J]. 数码世界 2018(09)
• [28].带有单服务器的并行机调度问题[J]. 沈阳大学学报(自然科学版) 2012(04)
• [29].混合离散教与学算法求解复杂并行机调度问题[J]. 自动化学报 2020(04)
• [30].基于调度池的共享单车调度研究[J]. 交通信息与安全 2019(05)

标签：流水作业论文;  批运输论文;  分批排序论文;  近似算法论文;