求解柔性作业车间调度问题的两级邻域搜索混合算法

针对柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP),以优化最大完工时间为目标,提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法,构造邻域结构,对关键路径上的关键工序进行移动,实现邻域搜索,以改进当前解;设计针对FJSP问题特点的两级邻域搜索方式,第一级邻域搜索为跨机器移动工序,将工序移动到除当前加工机器之外的其他可选机器上,第二级邻域搜索为同机器移动工序,将工序在当前加工机器上进行移动;给出两级邻域搜索相应的保证可行解工序移动条件;兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力,利用遗传算法实现全局搜索,两级邻域搜索实现局部搜索;采用国际通用的FJSP问题基准算例进行测试,验证了所提方法的有效性。