基于改进迭代贪婪算法的预制构件调度研究

Research on Scheduling of Prefabricated Components Based on Modified Iterative Greedy Algorithm

摘要:

迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法,但由于传统迭代贪婪算法搜索范围过大,搜索效率有限,为了进一步提升传统迭代贪婪算法的搜索能力,考虑到阈值接受算法具有能缩小搜索范围的特点,提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题。该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略,并结合阈值接受算法的自适应接受准则用以跳出局部最优。经大量仿真实验结果显示,与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比,改进的迭代贪婪算法具有更好的求解质量和鲁棒性。

Abstract:

Iterative greedy (IG) algorithm is a meta-heuristic algorithm with strong local search ability, but due to the excessive search range of traditional iterative greedy algorithm and limited search efficiency, in order to further improve the search ability of traditional iterative greedy algorithm, considering the threshold acceptance algorithm has The characteristics of narrowing the search range, an improved iterative greedy algorithm is proposed to solve the problem of order acceptance and scheduling for prefabricated production in flow shop. The improved algorithm is to add a reconstruction strategy based on constructing heuristic rules after destroying the original scheduling sequence, and combined with the adaptive acceptance criterion of the threshold acceptance algorithm to jump out of the local optimum. A large number of simulation experiments show that the improved iterative greedy algorithm has better solution quality and robustness compared with the traditional iterative greedy algorithm, tabu search (TS) algorithm and genetic algorithm (GA).