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

Improved iterative local search algorithm for solving multi-AGV flexible job shop scheduling problem

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

For flexible job shop scheduling problems with the constraints of transportation time and transportation resources,an Improved Iterative Local Search(IILS)algorithm mixed with greedy heuristic rules was proposed.The mathematical model of multiple Automated Guided Vehicle(AGV)flexible job shop scheduling problem was established with makespan as the optimization objective.The solution was represented by double-layer coding of process string and machine string,and the heuristic rule“first-arrive,first-serve”was incorporated to assign the most appropriate AGV to each transportation task in the decoding phase.The global workload balance of the machines was taken into account when the initial solution had been generated.Four kinds of neighborhood structures were designed for random neighborhood local search,and the elite solution memory-bank was used to specify the current solution,which made effective use of the historical search information,kept the intensification of the algorithm and expanded the search space at the same time.Tests were carried out on small-scale and large-scale standard test cases.Three performance indicators of the algorithm that were the best solution,relative standard deviation and average computing time were used to verify the effectiveness,stability,and efficiency of the proposed algorithm,and the results showed that IILS performed better than the comparison algorithms GATS,GTSB and LAHC both in the convergence speed and the solution quality.