A Simulated Annealing and Variable Neighborhood Search Hybrid for Sequencing Interrelated Activities

Determining an appropriate sequence of interrelated activities is one of the keys to developing a complex product. One of the approaches used to sequence activities consists of solving the feedback length minimization problem (FLMP). Several metaheuristic algorithms for this problem have been reported in the literature. However, they suffer from high computational costs when dealing with large-scale problem instances. To address this research gap, we propose a fast hybrid heuristic for the FLMP, which integrates the simulated annealing (SA) technique with the variable neighborhood search (VNS) method. The local search component of VNS relies on a fast insertion neighborhood exploration procedure performing only O(1) operations per move. Using rigorous statistical tests, we show that the SA-VNS hybrid is superior to both SA and VNS applied individually. We experimentally compare SA-VNS against the insertion-based simulated annealing (ISA) heuristic, which is the state-of-the-art algorithm for the FLMP. The results demonstrate the clear superiority of SA-VNS over ISA. The SA-VNS hybrid technique produces equally good or better results across all tested problem instances. In particular, SA-VNS is able to find better solutions than ISA on all instances of size 150 or more. Moreover, SA-VNS requires two orders of magnitude less CPU time than the ISA algorithm. Thus, SA-VNS achieves excellent performance regarding solution quality and running time.