基于连续批加工的生产运输协同调度研究

摘要

随着网络技术和全球经济一体化的不断发展，供应链之间的竞争越来越激烈。更多的供应链成员意识到需要通过加强与其他成员之间的合作来提高供应链的竞争力，从而能够降低各自的生产运营成本。物联网技术的发展正好为供应链成员之间的合作提供了信息基础，它不仅能够将生产和运输信息实时反馈到各自成员的管理中心，而且能够及时将这些信息分享给其他合作成员。物联网技术将供应链成员之间的合作推进到一个新的层面，利用好这些信息能够低生产成本、增加利润和提高客户满意度，从而增强整体供应链竞争力，同时能够进一步拓宽了生产运输协同调度问题的理论研究领域。因此，如何将该信息价值转化为经济和社会效益，运用物联网信息获得高效的生产运输协同方案成为关键性问题。本文以铝制品制造供应链为背景，从调度角度出发研究了物联网环境下供应链成员之间的生产运输协同调度问题。
　　本文围绕挤压厂的连续批处理机加工过程，系统性分析了多种情形下的多阶段生产运输协同调度问题。分别考虑了运载车辆有限情形、工件动态到达情形、工件加工时间恶化情形、机器发生故障情形以及分布在不同地理位置的多制造商情形的协同调度问题。由于这些问题均为NP难，本文致力于分析最优调度方案的性质，并基于这些性质设计高效的启发式和智能算法。另一方面，本文为这些问题推导了问题下界，这些下界可以用于评价算法的精确度。本文对基于连续批的生产运输协同调度问题的研究成果概括如下:
　　(1)研究了运载车辆有限情形下的生产运输协同调度问题，调度目标为最小化制造跨度时间。基于运载车辆有限等约束条件，建立了数学模型。根据批次在供应商和制造商之间的运输时间和工件在制造商机器上加工时间的关系，将问题划分为两种情形。针对两种情形，分别设计了两种启发式算法及问题下界。基于问题下界推导出该启发式算法最坏情形性能比例。考虑工件数量规模，分别设计了大量的小规模和大规模随机数据实验。仿真实验结果表明，当工件数量为1000时，所构造的两种启发式算法的平均相对差距分别收敛到0.48％和0.80％，均明显优于现有FOE and SPT算法和LOE and LPT算法。
　　(2)研究了工件动态到达情形下的生产运输协同调度问题，调度目标为最小化制造跨度时间。基于工件动态到达等约束条件，建立了数学模型。分析了最优调度方案中关于工件动态到达时间的相关性质，讨论了工件同时到达特殊情形最优调度方案和批次数量之间的关系。基于以上问题性质，构造了两阶段TP-H启发式算法，并证明TP-H算法最坏情形性能比例为7/2。分别通过松弛工件到达时间和假设制造商机器上没有额外空闲时间得出两个问题下界。基于不同的机器能力设计了仿真实验，大量仿真实验结果验证了TP-H算法的有效性。当工件数量为1000时，所构造的TP-H算法的平均相对差距收敛到0.21％，优于现有MBF算法和MFF算法。
　　(3)研究了工件加工时间恶化的生产运输协同调度问题。分析了工件加工恶化情形下的几类单机调度问题，目标函数分别为最小化制造跨度时间、最小化延迟工件数量、最小化工件总完工时间，设计了相应的最优化算法。基于单机调度问题，考虑了有缓存区情形下的生产运输协同调度问题，建立了相应的数学模型，目标函数为最小化制造跨度时间。分析了最优调度方案中组批及批次排序性质，构建了一种最优化算法。另外研究了无缓存区情形下的生产运输协同调度问题，建立了基于无缓存区约束的数学模型，目标函数为最小化制造跨度时间。分析了最优解性质，推导出新的问题下界，构建了一种启发式算法。仿真实验结果表明当工件数量大于260时，该启发式算法的平均和最大相对差距比例均小于0.01％。
　　(4)研究了考虑机器故障的生产运输协同调度问题。基于两个平行制造商机器可能发生故障的情形建立了数学模型，目标函数为最小化制造跨度时间。分析了最优调度方案性质，推导出问题下界。分别构建了两种情形下的调度规则，基于这些调度规则，设计了新的启发式算法。大量的仿真实验结果说明了该启发式算法能够高效地解决不同规模的问题。
　　(5)研究了分布在不同地理位置多制造商的生产运输协同调度问题，基于不同地理位置的多制造商等特点建立了相应的数学模型，目标函数为最小化整个制造过程的跨度时间。分析了该问题的最优解性质。提出了新颖的MGSA算法，设计了编码修正策略、初始化种群方法和最优种群保存策略，提出了插入操作、互换操作和变异操作。针对工件组批问题，构建了动态规划与启发式规则结合的DP-H混合算法。大量的仿真实验结果表明MGSA算法优于现有的GA和PSO算法。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景

1．2 研究目的和意义

1．3 论文研究内容及结构安排

1．3．1 论文研究内容

1．3．2 论文结构安排

第二章 文献综述

2．1 基本的批调度问题

2．1．1 工件同时到达情形下的批调度问题

2．1．2 工件动态到达情形下的批调度问题

2．2 基于批次的生产运输协同调度问题

2．2．1 单机情形下基于批次的生产运输协同调度问题

2．2．2 多机情形下基于批次的生产运输协同调度问题

2．3 本章小结

第三章 运载车辆有限情形下的生产运输协同调度问题

3．1 引言

3．2 问题描述

3．3 问题建模

3．4 启发式算法及性能分析

3．4．1 算法设计

3．4．2 问题下界

3．4．3 最坏情形性能比例分析

3．5 仿真实验及分析

3．6 本章小结

第四章 工件动态到达情形下的生产运输协同调度问题

4．1 引言

4．2 问题描述

4．3 问题建模

4．4 问题分析

4．4．1 一般问题的最优解性质

4．4．2 特殊情况的最优解性质

4．5 两阶段启发式算法

4．5．1 算法设计

4．5．2 最坏情形分析

4．5．3 下界计算

4．6 仿真实验及分析

4．7 本章小结

第五章 工件加工时间恶化的生产运输协同调度问题

5．1 引言

5．2 考虑加工恶化情形下的单机调度问题

5．2．1 问题描述

5．2．2 参数定义

5．2．3 最小化制造跨度时间问题

5．2．4 最小化延迟工件数量

5．2．5 最小化工件总完工时间

5．3 考虑缓存区情形下的生产运输协同调度问题

5．3．1 问题描述

5．3．2 问题建模

5．3．3 最优解性质

5．4 无缓存区情形下的生产运输协同调度问题

5．4．1 问题建模

5．4．2 问题性质分析

5．4．3 启发式算法

5．4．4 问题下界

5．4．5 仿真实验及分析

5．5 本章小结

第六章 考虑机器故障的生产运输协同调度问题

6．1 引言

6．2 问题描述

6．3 问题建模

6．4 问题性质及下界

6．4．1 问题性质

6．4．2 问题下界

6．5 新颖的启发式算法日

6．6 仿真实验

6．7 本章小结

第七章 基于不同地理位置的多制造商的生产运输协同调度问题

7．1 引言

7．2 问题描述

7．3 问题建模及复杂度分析

7．3．1 问题建模

7．3．2 复杂度分析

7．4 最优解性质及下界分析

7．4．1 最优解性质

7．4．2 问题下界

7．5 改进的引力搜索算法

7．5．1 引力搜索算法

7．5．2 改进的引力搜索算法关键步骤

7．5．3 工件组批机理

7．5．4 改进的引力搜索算法的整体结构

7．6 仿真实验及分析

7．7 本章小结

第八章 总结与展望

8．1 全文总结

8．2 研究展望

参考文献

攻读博士学位期间的学术活动及成果情况