双机流水车间外包与调度联合优化问题的混合变邻域搜索算法

来源：计算机集成制造系统杂志2019年第5期北京时间：

作者：刘乐,朱洪利

单位：1.济南大学商学院2.山东工商学院工商管理学院

摘要：针对最小化内部完工期与总外包费用的双机流水车间外包与调度联合优化问题,开发了一种混合变邻域搜索算法。在该算法中,采用工件剔除型启发式方法产生初始联合决策解;基于3种新型邻域结构提出了最佳改进式局部搜索规程;引入概率式准则来决定下轮迭代的目标搜索邻域。通过算法校准实验分析,探索出合适的邻域变更次序和温度参数的计算方式。通过与CPLEX软件、隐枚举测试程序对比显示,对于工件数不超过30的算例,校准后所提算法求得最优解的耗用时间更少。通过与遗传算法、模拟退火算法、和声搜索3种对比算法在工件数不少于100的算例上进行对比发现,所提算法经校准后,在求解质量和解的鲁棒性上均具有显著优势。

关键词：调度,双机流水车间,外包,混合变邻域搜索算法

基金资助：国家自然科学基金资助项目(71501083);教育部人文社科研究青年基金资助项目(14YJCZH098,17YJC630238);山东省自然科学基金资助项目(BS2015ZZ002,ZR2016GQ07);山东省社会科学规划资助项目（18CJJJ25）。