Literature on parallel machine scheduling problems has been extensively studied 23, 23, 24, 25, 26, 27. However, research that considered the UPMSP with machine-dependent and job-sequence dependent setup times, as it relates to the current problem, which is addressed in this paper is still inadequate. More so, dozens of metaheuristics for solving the UPMSP with sequence-dependent setup times, have been proposed by Anagnostopoulos and Rabadi 7 using simulated annealing (SA), Arnaout et al. 22, 36 using ant colony optimization (ACO), Lin et al. 28 using artificial bee colony (ABC) algorithm, Chang and Chen 29 using hybrid genetic algorithm, Eroglu et al. 30 using genetic algorithm (GA) with local search improvement, Vallada and Ruiz 31 using genetic algorithm (GA), Al-Salem 32 using partitioning heuristics (PH), Helal et al. 33 using tabu search (TS) heuristic, Rabadi et al. 34 using meta-heuristic for randomized priority search (Meta-RaPS), Ying et al. 35 using restricted simulated annealing (RSA). Even though, the new FA algorithm belongs to the same family of metaheuristics with ACO, ABC and GA in terms of them being population based, the motivation and uniqueness of the current study greatly depends on the new solution representation and decoding schemes discussed in the later part of this paper.

Studies on related literatures show that almost all the existing work on UPMSPs that addressed the same problem failed to deal with the problem in the manner suggested by Allahverdi et al. 37 and Zhu and Wilhelm 38. Arnaout et al. 22, 36 also stated that most of the existing methods that were used to solve the UPMSPs only performed well for small problem instances and that most of the scheduling methods, which did not follow the required steppes highlighted in 37, 38 performed poorly for large problems. For example, Al-Salem 32, Helal et al. 33 and Rabadi et al. 34 proposed different heuristics to solve large instance of the UPMSP with sequence-dependent setup times. However, even though each of these authors claimed high performance superiority for their proposed methods over the existing ones, only the Meta-RaPS showed some level of significant improvement in obtaining good quality solutions for large problems, because the Meta-RaPS outperformed its competitors.

Anagnostopoulos and Rabadi 7 proposed a SA heuristic for the UPMSP with setup times and with the objective of minimize makespn. The effectiveness of the SA algorithm was tested by comparing its solution quality with that of the optimal solutions obtained from an exact algorithm for small test problems. The quality of results from the computational experiment conducted demonstrated that the SA algorithm is only capable of obtaining near optimal solutions for small test problems and failed for large problems. In 35, a restricted simulated annealing RSA algorithm was also applied to solve the UPMSP with sequence dependent setup times. In this case, SA algorithm is hybridized with a restricted search mechanism to improve the solution quality of the classical SA algorithm and also with the common objective of minimizing makespan. This scheduling approach can be seen as an improvement over the basic SA method presented in 7, because the computational results obtained by the RSA for large problem sets indicate that it competed favorably well with other state-of-the-art scheduling algorithms from literature. However, since SA can be viewed as a search process that would always attempt to move from one current solution to another in its neighborhood solutions, it has high probability of easily getting trapped into local minimal and in addition it has a very high tendencies of incurring additional computational cost.

A hybrid genetic algorithm (HGA) with local search implementation was used to solve the UPMSP with the objective of minimization makespan in 30. The proposed hybrid GA solution mechanism involves the enhancement of chromosomes structure using random key numbers. The computational results of the HGA, which was tested on a set of problem that were taken from literature showed that the HGA competed fairly well with other methods. Similarly, in 31, a genetic algorithm that includes a fast local search and a local search enhanced crossover operator was proposed. An exhaustive computational and statistical analysis tests carried out by the authors in 31 over a comprehensive benchmark instances, revealed the effectiveness of the GA with local search method. Similarly, a novel genetic algorithm that integrated a set of dominance properties to further improve the solution quality of the UPMSP with machine and job sequence dependent setup times was introduced in 29. The numerical results presented in 29 showed that the hybrid GA with dominance properties (GADP) was able to obtain all optimal solutions for small test problems and outperformed the solutions of other competing algorithms in both effectiveness and efficiency for larger test problems.

In 22, ACO algorithm was used to solve the UPMSP with machine and job sequence dependent setup times. The computation result obtained showed that the preliminary results generated by the ACO outperformed those of the PH and TS algorithms introduced in 32, 33. In another development, a more detailed view of the ACO algorithm with some level of improvements from the initial ACO discussed in 22 was presented in 36 and it was shown by the authors that under optimized parameters the solution quality of the ACOII appears to be much better than the results presented in 22, 32, 33. Therefore, due to the consistent increase in the search for a better optimization solution approach for the UPMSP with setup times and more so, as a result of the development of several new better metaheuristic algorithms with each having a promising performance profile, this study presents a novel hybridized firefly algorithm with robust solution representation mechanisms that is capable of solving large instances of the problem at hand.