Advanced discrete firefly algorithm with adaptive mutation-based neighborhood search for scheduling unrelated parallel machines with sequence-dependent setup times

The unrelated parallel machine scheduling problem with sequence-dependent setup times is addressed in this paper with the objective of minimizing the elapsed time between the start and finish of a sequence of operations in a set of unrelated machines. The machines are considered unrelated because the processing speed is dependent on the job being executed and not on the individual machines. Generally, the problem is considered NP-hard, as it presents additional complexity to find an optimal solution in terms of minimum makespan. An advanced firefly metaheuristic optimization algorithm is introduced to solve this problem. The proposed method, called the FAII algorithm, aims to improve the standard firefly algorithm's performance by incorporating an enhanced global best solution update mechanism and adaptive mutation-based local and global neighborhood search scheme to improve the quality of the proposed algorithm's generated solution. Several experiments were conducted to compare and validate the proposed algorithms' performance on small and large-scale benchmarked problem instances with up to 12 machines and 120 job combinations. Moreover, the performance of the FAII was also compared with eight other metaheuristic algorithms, which were implemented in parallel with the FAII method. Furthermore, the numerical results of the FAII algorithm were compared with the scheduling results of six other well-known metaheuristics from the literature. The comparison results backed with a comprehensive statistical analysis showed the superiority of the enhanced FA-style scheduling optimization over other metaheuristic methods to find good quality solutions or minimum average makespan.

Automated summary

This paper addresses the unrelated parallel machine scheduling problem with sequence-dependent setup times by introducing an advanced firefly metaheuristic optimization algorithm, the FAII algorithm. Through several experiments, it was demonstrated that the FAII algorithm outperforms eight other metaheuristic algorithms and six well-known metaheuristic scheduling algorithms in terms of finding high-quality solutions or minimum average makespan, showcasing its superior performance.