迭代局部搜索在带设置时间的同顺序流水作业中的应用研究

摘要

带设置时间的同顺序流水作业调度问题(permutation flowshop schedulingproblem with sequence dependent setup times，SDST-PFSP)在经典的同顺序流水作业调度问题(PFSP)基础上，考虑了制造领域常见的设置时间约束，更接近实际生产需要。对于该问题，传统方法很难进行有效求解。如何快速地制定一份高效的调度方案，已经成为现在制造业急需解决和充满挑战的问题。本文针对这一问题展开讨论。
　　迭代局部搜索算法(iterated local search，ILS)是一类简单而高效的元启发式算法，成功地应用于诸多组合优化问题。在求解最小化总流程时间的PFSP问题上，ILS算法已经有了很大发展。本文将ILS算法应用于SDST-PFSP问题，研究影响算法性能的扰动方法和局部搜索过程。主要研究内容如下:
　　(1)在现有算法基础上提出ILS_D算法，求解最大完工时间(Makespan)、总加权延误时间(TWT)和总流程时间(TFT)三种目标。在基于Taillard数据集的基准算例上，ILS_D算法与求解SDST-PFSP问题当前最优的IG_RS算法进行对比。在PFSP问题中取得很好求解效果的ILS_PR和IG_PR算法也被移植并参与比较。实验结果表明，提出的ILS_D算法在所有目标上都优于IG_RS算法，在多数情况下，也明显优于ILS_PR和IG_PR算法。
　　(2)将精英池策略与邻位交换（ADJ）、插入(INS)和破坏-构造(DC)三种扰动方法相结合，提出了ILS_ADJ、ILS_INS和ILS_DC三种扩展算法。所提ILS算法与ILS_D算法的性能比较表明，精英池策略具有很强的鲁棒性，能够有效地提高算法求解SDST-PFSP问题的性能。根据求解目标的不同要求，上述扰动方法分别适合求解TWT、Makespan和TFT目标的问题。
　　(3)改造了基于两种邻域结构的增强ILS算法(Enhanced ILS，EILS)，根据使用的扰动方法的不同，将改造的算法记为EILS_INS和EILS_DC。实验结果表明，在TWT和TFT求解目标上，使用多邻域结构的增强ILS算法的求解质量均没有明显改进;在Makespan目标上，所提EILS算法的求解性能明显劣，造成这个现象的一个原因是算法复杂度从一次迭代的O(mn2)增加到了O(mn3)，因此在相同时间内完成的迭代次数大幅减少。以上表明多邻域局部搜索方法的鲁棒性不是很好，根据问题特征设计多邻域局部搜索方法是一个需要研究的内容。

目录

声明

致谢

摘要

1 引言

1．1 研究背景及意义

1．2 研究现状

1．2．1 国外研究现状

1．2．2 国内研究现状

1．3 迭代局部搜索算法简介

1．4 研究内容及组织结构

1．4．1 主要研究内容

1．4．2 本文组织结构

2 带设置时间的同顺序流水作业调度问题

2．1 SDST-PFSP问题描述

2．2 求解目标

2．3 相关算法

3 迭代局部搜索算法求解SDST-PFSP问题

3．1 初始解的生成

3．2 局部搜索过程

3．3 扰动方法

3．4 提出的ILS算法

3．5 实验结果与分析

3．5．1 求解SDST-PFSP-Cmax问题

3．5．2 求解SDST-PFSP-TWT问题

3．5．3 求解SDST-PFSP-TFT问题

3．6 本章小结

4 基于精英池策略的ILS算法

4．1 扰动方法

4．1．1 常见的扰动方法

4．1．2 基于精英池策略的扰动方法

4．2 基于精英池策略的ILS算法

4．3 实验结果与分析

4．3．1 求解SDST-PFSP-Cmax问题

4．3．2 求解SDST-PFSP-TWT问题

4．3．3 求解SDST-PFSP-TFT问题

4．4 本章小结

5 基于多邻域的ILS算法的应用研究

5．1 局部搜索过程

5．2 基于多邻域的ILS算法

5．3 实验结果与分析

5．3．1 EILS_DC算法与ILS_DC算法对比

5．3．2 EILS_INS算法与ILS_INS算法对比

5．3．3 EILS_INS算法与EILS_DC算法对比

5．4 本章小结

6 结论与展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集