独立任务分配的贪婪随机自适应搜索过程

Greedy randomized adaptive search procedure for independent tasks assignment

提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解,再通过变邻域下降算法来改进这个解,在变邻域下降算法中,为增强算法的空间勘探能力,外层局部搜索采用允许接收劣质解的策略,使用禁忌表来防止迂回搜索,使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能。

A greedy randomized adaptive search procedure is presented to tackle the independent tasks assignment problem in heterogeneous environments. A randomized min-min complete time algorithm is used to construct an initial solution, and then a variable neighborhood descent algorithm is used to improve the solution. In order to improve its exploration ability, bad solution is accepted in the outer local search. Tabu list is used to keep the algorithm from cycling search. Using those strategies, the proposed algorithm get good balance between diversification and intensification. The simulation results comparing with typical algorithm in the fields show that the proposed algorithm produces good results.