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

Abstract

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.

Keywords:

• Kin selection
• Simulated annealing

Acknowledgement

The authors wish to express their most sincere thanks to the learned referees for their constructive criticisms that led to considerable improvement to the earlier version of the text. We also wish to put on record our indebtedness to the managing editor, Dr S. T. Newman, for timely help and giving us an opportunity to revise the text. Support rendered by the NIFFT administration is gratefully acknowledged.