论文部分内容阅读
带设置时间的同顺序流水作业调度问题(permutation flowshop scheduling problem 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),因此在相同时间内完成的迭代次数大幅减少。以上表明多邻域局部搜索方法的鲁棒性不是很好,根据问题特征设计多邻域局部搜索方法是一个需要研究的内容。