Application of a kin selection based simulated annealing algorithm to solve a complex scheduling problem

摘要

In this article, a simulated annealing (SA) based heuristic approach is presented to provide a solution to an industrial scheduling problem encountered in an aluminium foundry. An endeavour to enhance the performance of conventional SA algorithms is made by the aid of a new operator namely the kin selection operator which is embedded in the SA algorithm. This operator is inspired by a phenomenon of the same name observed in evolutionary systems. By sacrificing a better solution for its 'kin', the heuristic ensures a more efficiently guided, thorough search in the neighbourhood of the best solution. Comprehensive theoretical and experimental analysis is provided to prove the new operator's efficacy in enhancing the SA's performance. In a scheduling problem related to a foundry unit, the proposed heuristic seeks the best processing sequence for a certain number of orders on parallel furnaces. After extensive computations, it is found that the proposed heuristic provides better solutions than that provided by other established combinatorial optimization tools.