最小化总加权延迟作业车间调度问题的离散差分进化算法研究

摘要

作业车间调度问题广泛存在于工业领域。尤其在高效的生产业与制造业领域中，该问题备受关注。随着我国市场经济的飞速发展，工业规模越来越大，客户对于作业完成的效率要求也越来越高。合理的作业调度安排可以极大地提高作业完成的效率，不仅为企业节省了成本，而且提高了客户的满意度。因此，如何合理的安排作业调度顺序，备受各大生产企业的关注。解决作业车间调度问题的算法作为一项提高资源利用率的关键性技术，在节约资源、促进生产效率方面有着非常重要的意义。
　　传统的作业车间调度问题主要关注最后作业的最早完成时间，旨在减少生产时间并提高资源的利用率。至今为止已有许多学者对这个问题进行了大量的研究并且其结果已经得到足够的优化。然而，在现代制造业和操作管理中，作业的及时交付已经成为提高客户满意程度的重要因素。因此，本研究考虑目标为最小化总加权延迟时间的作业车间调度问题，并设计了一个离散差分进化算法，期望能更好的优化该问题的解。
　　本文基于连续值优化的著名进化算法—差分进化算法，提出了适用于离散优化的离散差分进化算法。本文对适用于连续值操作的差分进化算法的具体步骤，进行了适用于离散问题优化的差分进化操作设计。为了增加算法的搜索能力，提升算法的搜索效率，本文在离散差分进化算法中混合了基于调度关键路径的局部搜索算法。并且，本文提出了关于群体多样性的定义，加入了基于群体多样性的迁移操作，以跳离局部最优，加大搜索范围，从而提高解的质量。在本文的最后，将以本算法的结果和目前在这个问题上所提出算法的结果进行比较，来凸显该研究的研究意义和应用价值。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究意义

1．3 研究内容

1．4 研究现状

1．5 本文的内容安排

第二章 最小化总加权延迟作业车间调度问题

2．1 问题描述

2．2 问题的数学模型

第三章 进化算法

3．1 进化计算的基本概念

3．2 差分进化算法

3．2．1 差分进化算法简介

3．2．2 差分进化算法框架

第四章 离散差分进化算法

4．1 解的向量编码

4．2 解向量解码与评价函数

4．3 种群离散度的定义

4．4 初始种群的生成

4．5 差分进化信息重定义

4．5．1 差分信息列表

4．5．2 差分信息列表在TWT-JSSP的示例

4．6 种群个体杂交操作

4．7 基于关键路径的局部搜索

4．8 种群迁移操作

4．9 离散差分进化DDE算法

第五章 实验结果与分析

5．1 TWT-JSSP测试样例构成

5．2 DDE算法参数初始化

5．3 TWT-JSSP的算法结果比对

5．3．1 解质量比较

5．3．1 运行时间比较

5．4 DDE与HDE的比较

5．5 DDE算法的参数比较

5．4．1 平滑因子F的取值比较

5．4．2 杂交概率CR的取值比较

第六章 总结与展望

参考文献

致谢

攻读硕士期间发表的论文