带有交货时间窗的提前/拖期调度问题研究

摘要

目前JIT(just in time)生产模式被越来越多地应用于实际的建造和生产环境中，单机的提前/拖期调度问题也被更多学者重视。本论文为了对提前/拖期调度问题进行细致而深入的研究，主要从三个方面对该问题进行了研究：单机的提前/拖期调度问题；单个时间窗的提前/拖期问题；所有交货期均为时间窗的提前/拖期问题。
　　本论文首先研究了最基础的情形——单机的提前/拖期调度问题。本文在最优开工时间算法的基础上提出了劣序剔除规则，该剔除规则解决了任意工序的调度问题，对劣序列进行了筛选和剔除，提高了问题的收敛性。此外本文还提出了改进的遗传算法，将最优开工时间算法以及劣序剔除规则与遗传算法相结合，运用改进的遗传算法对港珠澳大桥建造过程中的实际需求计划进行了调度，并且通过对遗传算法和改进的遗传算法进行多组对比实验证明了改进的遗传算法在成本和收敛速度上都有所改进，进而证明了劣序剔除规则的有效性。
　　然后本论文对单个时间窗的提前/拖期调度问题进行了研究。对于该问题，本文从两个方向进行了研究：分析时间窗对总成本和最优开工时间的影响；对于单个工件的交货期为时间窗的问题进行建模分析。通过分析对时间窗的范围以及时间窗对于调度方案的开工时间以及成本的影响进行了讨论，并得出了相应的结论。
　　最后对于所有工件的交货期均为时间窗的问题，本文运用遗传算法与禁忌搜索算法结合的混合策略进行求解。通过对遗传算法和混合策略的多组对比实验，我发现混合策略在迭代次数与总成本上都明显优于遗传算法，并且随着工件数量的增加，优势愈加明显，证明了混合策略的有效性。
　　总而言之，本文对单机器的提前/拖期调度问题进行了全面而深入的研究，但是后续仍有许多问题亟待解决和研究。

目录

声明

1 绪论

1.1 研究背景

1.2 研究目的和意义

1.3 论文的研究内容

1.4 论文的组织结构

2 国内外研究综述

2.1 提前/拖期问题的研究现状

2.2 带有交货时间窗的单机提前/拖期问题的研究现状

2.3 相关算法研究现状

3 单机的提前/拖期调度问题

3.1 问题描述与建模

3.2 最优开工时间算法

3.3 劣序剔除规则

3.4 基于启发式规则的改进遗传算法

3.5 案例分析

3.6 本章小结

4 单个时间窗的提前/拖期问题

4.1 单个时间窗问题的描述与分类

4.2 时间窗的影响与调度方案

4.3 数学模型建立

4.4 时间窗对算法的影响

4.5 案例分析

4.6 本章小结

5 所有交货期均为时间窗的提前/拖期问题

5.1 问题描述与建模

5.2 禁忌搜索算法

5.3 遗传算法与禁忌搜索算法结合的混合策略

5.4 案例分析

5.5 本章小结

6 总结与展望

6.1 总结

6.2 展望

致谢

参考文献

附录1 攻读硕士学位期间发表的学术论文

附录2 攻读硕士学位期间参加的科研项目