求解置换流水车间调度问题的Memetic算法

针对以最小化最大完工时间为目标的置换流水车间调度问题,建立了0-1型混合整数线性规划模型。在对模型进行Benders分解的基础上,提出了问题的求解策略,进而设计了一种Memetic调度算法,并探讨了基于组合规则的种群初始化方法和混合遗传操作。为了提高算法的搜索效率,采用了更加高效的适应度值计算方法以及两种邻域搜索方法。最后,基于Benchmark算例的仿真实验结果表明了该算法的有效性,可以找到26个算例中的17个最优解(65.38%),且其平均相对误差的均值仅为0.88%。