改进迭代局部搜索算法求解多AGV柔性作业车间调度问题

针对受运输时间和运输资源约束的柔性作业车间调度问题，提出一种融合贪心启发式规则的改进迭代局部搜索算法。以最大完工时间为优化目标，建立多自动导引小车(AGV)柔性作业车间调度问题的数学模型，并采用工序串和机器串双层编码求解问题模型，解码时融入“先到先服务”的启发式规则来对每个运输任务分配最合适的AGV;生成初始解时考虑机器全局的工作负载平衡；设计了3种邻域结构用于随机邻域局部搜索，并采用精英解记忆库策略来指定当前解，有效利用历史搜索信息，保持算法集中性的同时扩大了搜索空间。采用最好解、相对标准差和算法平均运行时间3种性能指标，分别在小规模和大规模标准测试案例上对所提算法的有效性、稳定性和高效性进行测试，结果表明不管是在求解速度上还是求解质量上其表现都优于遗传禁忌搜索算法、带转移瓶颈的遗传禁忌搜索算法和延迟接受爬山算法。