计算机应用研究

作者：李杰,李艳武,

单位：重庆三峡学院电子与信息工程学院,重庆404100；

关键词：零空闲流水车间问题,最大完工时间,内部迭代,迭代贪婪算法,

基金：重庆市三峡库区地质环境监测与灾害预警重点实验室开放基金资助项目(YB2020C0102)；重庆市教育委员会科学技术研究项目(KJQN202001224)；；

零空闲流水车间问题（NIFSP）是流水车间问题中带有约束条件的典型NP-hard问题，在大多数现实场景下，零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此，以最小化最大完工时间为目标，提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段，使用改进的FRB5产生初始解，提高了FRB5的效率，在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段，通过增加对移除工件块数量的内部迭代，从而灵活调整参数值。VIIA增大了邻域搜索，以适应不同规模的算例。为了验证VIIA算法的性能，将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性，并且在最优解的搜索上，性能明显优于对比算法。

来源：2022年第12期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2022年第12期