摘要
针对最小化内部完工期与总外包费用的双机流水车间外包与调度联合优化问题,开发了一种混合变邻域搜索算法。在该算法中,采用工件剔除型启发式方法产生初始联合决策解;基于3种新型邻域结构提出了最佳改进式局部搜索规程;引入概率式准则来决定下轮迭代的目标搜索邻域。通过算法校准实验分析,探索出合适的邻域变更次序和温度参数的计算方式。通过与CPLEX软件、隐枚举测试程序对比显示,对于工件数不超过30的算例,校准后所提算法求得最优解的耗用时间更少。通过与遗传算法、模拟退火算法、和声搜索3种对比算法在工件数不少于100的算例上进行对比发现,所提算法经校准后,在求解质量和解的鲁棒性上均具有显著优势。
Aiming at the two-machine flow shop outsourcing and scheduling integrated optimization problem of minimizing the sum of in-house makespan and total outsourcing cost, a Hybrid Variable Neighborhood Search (HVNS) algorithm was proposed. In this algorithm, the initial joint decision solutions were obtained by performing problem-specific job removal-related heuristic approach. Based on three novel neighborhood structures, a best-improvement local- search procedure was designed to improve the resulted solutions through shaking. Besides, the probabilistic moving criterion was introduced to decide the target neighborhood in the next iteration. The appropriate selections for the changing sequence of neighborhoods and the way of calculating temperature parameter were achieved via extensive calibration experiments. The comparison results with CPLEX optimizer and the Implicit Enumeration Testing Procedure (IETP) showed that the calibrated HVNS was capable of finding the optimal solutions to the instances with n≤30 and much less computation time. In comparison with three algorithms by respectively using the genetic algorithm, simulated annealing and harmony search techniques, the calibrated HVNS showed significant superiority over three compared ones in terms of both solution quality and robustness.
作者
刘乐
朱洪利
LIU Le;ZHU Hongli(School of Business,University of Jinan,Jinan 250022,China;School of Business Administration,Shandong Technology and Business University,Yantai 264005,China)
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2019年第5期1202-1222,共21页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金资助项目(71501083)
教育部人文社科研究青年基金资助项目(14YJCZH098,17YJC630238)
山东省自然科学基金资助项目(BS2015ZZ002,ZR2016GQ07)
山东省社会科学规划资助项目(18CJJJ25)~~
关键词
调度
双机流水车间
外包
混合变邻域搜索算法
scheduling
two-machine flow shop
outsourcing
variable neighborhood search algorithm
