学位论文 > 优秀研究生学位论文题录展示

流程工业生产与运输协调物流调度理论研究

作　者: 关静
导　师: 唐立新
学　校: 东北大学
专　业: 系统工程
关键词: 生产调度生产运输协调最优性质分析算法复杂性分析最坏情况分析禁忌搜索算法动态规划算法
分类号: F426.31
类　型: 博士论文
年　份: 2008年
下　载: 228次
引　用: 0次
阅　读: 论文下载

内容摘要

传统的生产调度和运输调度是分开研究的,通常都是将生产放在首要位置而运输放在一个从属的地位,即先安排生产调度,然后再相应进行运输物流调度。然而在实际生产中,由于运输工具数量和能力的限制,而使工序之间物料的传递受到了限制,使得在不考虑运输情况的生产调度即使是最优调度也难以有效的执行。一个自然而合理的想法是将生产调度和运输物流调度协调进行研究,这样将有助于提高运输工具的利用率,使得生产与运输之间的时间衔接更加精确,从而有效地降低生产和运输的物流总费用。流程工业生产的各个工序之间都存在着运输问题,如典型的流程工业-钢铁工业中高炉到炼钢之间的铁水需要鱼雷车进行运输、炼钢到连铸之间的钢水需要用吊机和台车衔接进行运输,热轧工序中板坯和冷轧工序中的板卷都需要汽车进行运输到下游工序。由于流程工业中的被运件多数都具有温度高、单价大、各工序的送达时间由于连续运作而要求苛刻的特点,因此有效地对生产和运输物流调度进行协调,将有助于降低能耗、提高生产设备和运输工具的效率、保障实时性要求和生产的顺行。近年来,生产与运输协调物流调度越来越多的受到国际学术界的广泛关注。本论文以流程工业中典型的钢铁企业为例,从生产与运输的位置关系出发,在三个方面对生产运输协调物流调度问题进行研究：生产前运输、生产间运输、生产后运输。具体内容概括如下：1)生产前运输与生产协调调度问题研究(1)从彩涂板生产过程中提炼出一类单机生产前考虑原料运输的问题,分别考虑工件到达加工机器前的等待时间限制和运输过程车辆运输工件个数有限问题,工件加工前等待时间的限制使得问题难度与以往传统调度问题不同。考虑的目标函数为最小化传统调度目标与工件成批运输费用和。对于不同的目标函数分别给出等待时间受限制问题的强NP难证明,对于其中车辆运输工件数量有限的问题,分别针对不同的目标函数给出多项式时间最优算法。(2)从钢铁厂原料运输过程有多种运输模式可供选择的实际中,提炼出一类单机生产前带有运输模式选择的生产与运输协调问题,同时考虑工件加工前的等待时间限制。运输模式选择和等待时间限制这两个特点使得问题不同于以往文献研究的问题。目标函数分别为最小化传统目标函数与车辆启动费用之和。对于不同的目标函数分别证明问题是强NP难的,并针对最小化最大完成时间与车辆启动费用之和问题构造了禁忌搜索算法,同时给出问题的数值计算结果。(3)从热板坯运输过程中提炼出一类生产前运输热工件的生产运输协调调度问题,其中热工件的实际处理时间依赖于加工前等待时间,这使得问题不同于传统的工件处理时间不确定问题。考虑的目标函数为最小化所有工件最大完成时间。对于工件带有释放时间问题给出强NP难的证明,对于生产前运输车辆数量和运输能力不同的各种情况,分别给出了问题是强NP难的证明。特别地,对于车辆个数为1、容量为给定常数的情况提出了一个近似算法,并用数值实验验证了算法的有效性。(4)从钢管加工的实际中提炼出一类带有生产前运输的新型流水车间调度问题,工件依次从上游运输到加工机器上进行切割加工,对于这种新型的生产调度问题考虑出现运输前后问题难度的变化。对于不考虑生产前运输的最小化最大完成时间问题给出多项式时间最优算法。对于考虑机器间缓冲限制和生产前运输,目标函数为最小化最大完成时间问题给出问题是强NP难的证明。对于考虑机器间缓冲惩罚,目标函数为最小化最大完成时间与惩罚费用和问题,给出问题是一般意义NP难的证明。同时证明出现运输前可解问题的最优算法作为相关的NP难问题的启发式算法,最坏情况与问题最优解的比不会超过2,并给出数值实验。2)生产间运输与生产协调调度的问题的研究(1)从钢铁企业炼钢—精炼的生产实际中提炼出带有中间运输的两阶段生产与运输协调调度问题,考虑运输时间和工件加工前等待时间限制对生产的影响。对于其中一个特殊情况构造了一个界为2的近似算法,并进行了数值实验,对于这个特殊情况相关的一些可解情况进行了分析。同时把特殊情况的近似算法应用到更实际问题的禁忌搜索算法中,通过界分析方法对实际问题近似算法的有效性进行了理论验证,同时又通过数值实验对算法有效性做进一步验证。(2)在炼钢—精炼的背景下考虑生产与运输的协调,特别的考虑运输阶段存在两种不同运输工具相互衔接运输,这使得问题不同于以往研究的问题。对于一阶段生产后带有两个运输工具衔接运输问题,构造了问题的最优算法；接下来把一阶段生产后带有衔接运输的最优算法应用到两阶段生产间运输问题的禁忌搜索初始解的构造中,用禁忌搜索算法对生产中提炼出的复杂问题进行近似求解,对算法的有效的验证同样通过界分析和数值实验两种手段实现。(3)在炼钢—多重精炼的背景下研究更符合实际的生产运输协调调度问题,同样考虑不同生产设备之间的运输以及两种不同类型运输工具的协调。对此问题采用了炼钢—重精炼问题的性质来构造禁忌搜索算法,并通过界分析和数值实验验证算法的有效性。3)生产后运输与生产协调调度问题研究从热板坯生产后的运输过程中,提炼出一个单机生产后带有温降工件的成批运输问题,其中那些带有温降的工件等待运输时温度下降。通过温降函数的引入对调度过程中工件的能量损失进行了度量,这也使得离散最优化问题的目标函数中出现了连续函数。对于目标函数为传统调度目标与温降函数之和问题,给出问题是强NP难的证明。同时分析了该问题若干可解的特殊情况。把这个能量目标引入到考虑等待时间限制的炼钢精炼问题中,同样采用禁忌搜索算法对问题的最优解进行近似。对近似算法进行了界分析并进行了数值计算。

全文目录

摘要  5-8
Abstract  8-12
目录  12-16
第一章绪论  16-31
  1.1 问题的研究目的及意义  16-18
    1.1.1 问题来源及研究目的  16-17
    1.1.2 问题背景及研究意义  17-18
  1.2 流程工业生产与运输协调调度问题的来源与研究现状  18-27
    1.2.1 生产与运输协调物流调度问题描述  19-20
    1.2.2 生产与运输协调物流调度的一般理论方法  20
    1.2.3 生产运输协调物流调度问题的背景  20-25
    1.2.4 生产运输协调物流调度问题的研究现状  25-27
  1.3 本文的研究路线及主要工作  27-31
    1.3.1 本文的研究路线  27-29
    1.3.2 本文的主要工作  29-31
第二章单机考虑生产前运输费用的调度  31-39
  2.1 引言  31-32
  2.2 问题的描述  32-33
  2.3 F=C_(max)问题  33-34
  2.4 F=ΣC_j问题  34-35
  2.5 F=L_(max)问题  35-37
  2.6 F=ΣT_j问题  37
  2.7 F=ΣU_j问题  37-38
  2.8 小结  38-39
第三章单机生产前带有运输模式选择的协调调度  39-48
  3.1 引言  39-40
  3.2 问题的描述  40-41
  3.3 复杂性理论分析  41-44
  3.4 近似算法  44-45
  3.5 实验与数值计算结果  45-47
  3.6 小结  47-48
第四章考虑生产前运输的单机带有恶化工件的协调调度  48-63
  4.1 引言  48-50
  4.2 带有释放时间的单机等待时间相关恶化工件调度  50-52
  4.3 考虑生产前运输的单机带有恶化工件的协调调度  52-62
    4.3.1 问题的描述  52-53
    4.3.2 复杂性理论分析  53-59
    4.3.3 近似算法  59-61
    4.3.4 实验与数值计算结果  61-62
  4.4 小结  62-63
第五章新型流水车间带有生产前运输的协调调度  63-84
  5.1 引言  63-66
  5.2 无限缓冲的分解类型调度问题  66-75
  5.3 缓冲空间带有容量限制的分解类型调度问题  75-77
  5.4 带有缓冲惩罚的分解类型调度问题  77-80
  5.5 带有前运输的工件分解类型调度问题  80-81
  5.6 实验与数值计算结果  81-83
  5.7 小结  83-84
第六章炼钢-精炼间带有运输的生产调度  84-102
  6.1 引言  84-86
  6.2 考虑中间产品运输时间的二机流水问题  86-90
    6.2.1 问题的描述  86
    6.2.2 近似算法  86-87
    6.2.3 算法的界分析  87-88
    6.2.4 实验与数值计算结果  88-90
  6.3 几种可解情况分析  90-93
    6.3.1 运输工具从中间交货点出发  90-91
    6.3.2 运输工具从上下游的机器处出发  91-93
  6.4 考虑台车运输时间与等待时间约束的炼钢精炼问题  93-101
    6.4.1 问题的描述  93-94
    6.4.2 数学模型  94-96
    6.4.3 禁忌搜索算法  96-97
    6.4.4 算法的界分析  97-99
    6.4.5 实验与数值计算结果  99-101
  6.5 小结  101-102
第七章炼钢-精炼间带有能量损失的生产调度  102-117
  7.1 引言  102-104
  7.2 单机生产后带有一个运输工具协调调度问题  104-114
    7.2.1 复杂性理论分析  104-108
    7.2.2 几种可解情况分析  108-114
  7.3 考虑等待能量损失与等待时间约束的炼钢精炼问题  114-116
  7.4 小结  116-117
第八章炼钢-精炼带有台车吊机连运的生产调度  117-138
  8.1 引言  117-118
  8.2 问题的描述  118-119
  8.3 数学模型  119-121
  8.4 可行的吊机算法  121-123
  8.5 禁忌搜索算法  123-133
    8.5.1 禁忌搜索初始解构造  123-132
    8.5.2 禁忌搜索邻域与禁忌表  132-133
  8.6 算法的界分析  133-134
  8.7 实验与数值计算结果  134-137
  8.8 小结  137-138
第九章炼钢-多重精炼带有台车吊机连运的生产调度  138-149
  9.1 引言  138-139
  9.2 问题的描述  139-140
  9.3 数学模型  140-142
  9.4 性质和统治规则  142-143
  9.5 禁忌搜索算法  143-144
  9.6 算法的界分析  144-146
  9.7 实验与数值计算结果  146-148
  9.8 小结  148-149
第十章结束语  149-151
参考文献  151-160
致谢  160-161
作者博士期间发表和录用的论文  161-162
作者博士期间科研情况  162-163
个人简历  163

流程工业生产与运输协调物流调度理论研究

内容摘要

全文目录

相似论文