A parallel “Go with the winners” algorithm for some scheduling problems

We consider an approach to solving permutation scheduling problems using graphics accelerators. A parallel evolutionary algorithm based on the iterated random local search and the “Go with the winners” algorithm is proposed. A computational experiment was carried out on test instances of the classic Flow Shop problem and one applied production scheduling problem with time windows. The results show high computing speed and good accuracy of obtained solutions in comparison with various variants of the genetic algorithm and Gurobi solver. The proposed approach is easy to implement and convenient for adaptation to particular features of graphics computing and can be used to solve practical problems. Tab. 3, bibliogr. 18.