Parallel machine scheduling has received continued interests from wide range of production scheduling research enthusiasts and those coming from the academic and engineering fields 1. This growing attention can be attributed to the broad applications of parallel machine scheduling concepts and its variants in many modern manufacturing systems. Typical application areas of parallel machine scheduling include drilling operations for printed circuit board fabrication 2, 3, dicing operations for semiconductors wafer manufacturing, others include call centers, banking and transportation 4, 5, 6. The parallel machine scheduling problem discussed in this paper can be considered as a generalization case of the single machine scheduling problem. More so, the introduction of additional constraints to this problem gives rise to the formation of several other variants of the parallel machine scheduling problem of which the Unrelated Parallel Machines Scheduling Problem (UPMSP) is one these variants.
The UPMSP was defined in 7 as a problem model with a number of components involved. These components comprises of n jobs that are available at time zero, and have to be scheduled on m machines with different varying capabilities, which invariably results in the assigned jobs being processed at different rates 7. In order words, by assigning job j to machine k to process, the required time in which machine k would have to process job j is given as P_jk and this time is dependent on both job j and machine k respectively, while there is no relationship between the machine speed. Moreover, the UPMSP which is considered in this paper is a generalization of identical parallel machines problem. Real-world examples of UPMSP are problem instances arising from both production scheduling and manufacturing systems 2, 6. The sequence-dependent setup times S_(i,j,k) is considered for the proposed problem formulation, where the time required to setup job i after job j on machine k may differ if the two jobs are interchanged, which implies that invariably S_(i,j,k)?S_(j,i,k). In addition, each machine setup times comprises of different setup matrix, because the setup times are machine dependents. It is noteworthy to state that the type of problem model considered in this paper is regularly encountered in the industry and has both theoretical and practical relevance to different domains.
Plethora of research has been done on UPMSP, most of which resulted in the development of several interesting solution approaches for these types of problems by tackling variety of objectives 7, 8, 9, 10, 11, 12. The UPMSP has been classified as an NP-hard problem, since even for the flexible identical parallel machine scheduling problem with less than two machines is considered NP-hard problem 13, 14. For this categories of problems, it is much easier to find optimal solutions for small set of problems than for large problems using the gradient methods. Therefore, different metaheuristic algorithms have been proposed in the literature and quite a good number of them are able to find near-optimal solutions for the same problem within a reasonable time frame 15, 16, 17, 18, 19, 20, 21, 22. In this paper, an efficient firefly algorithm (FA), which is combined with a local search solution improvement technique is developed and presented to solve the NP-hard UPMSP. The main goal of this paper is therefore, to demonstrate the applicability of the FA algorithm to solve the UPMSP and to also show that the new hybrid FA is able obtain good-quality solutions that are closer to the optimal solutions when compared with other existing methods. Three other popular metaheuristic algorithms namely ant colony optimization (ACO), genetic algorithm (GA) and invasive weeds optimization (IWO) algorithm are implemented in parallel to test the superiority of the proposed hybrid FA with local search method.
The FA proposed in this paper is novel in the sense that its incorporates a robust local search solution improvement and a unique solution representation schemes. These two schemes make the new hybrid algorithm even more effective and efficient in handling the problem at hand. In addition, to present a fairer and unbiased comparisons among the different algorithms, number of fitness evaluation is used to measure the performance of each algorithms presented in this paper, that is aside the number of generation or iteration that are used in the related works to solve the same problem. The computational experiments carried out to evaluate the capability of the proposed algorithm on wide range of problem instances show that the performance of the FA approach is significantly superior to several other existing heuristics that have been used to solve the same benchmark problems. The test problems that were used to evaluate the performance of the improved FA comprises of 2, 4, 6, 8, 10, and 12 machines with 20, 40, 60, 80, 100, and 120 jobs, which makes up a total combinations of 1620 test instances. Moreover, the concluding remarks are very promising with future potential research direction suggested.
The technical contribution of this paper can be summarized as follows.
Demonstration of the applicability of firefly algorithm to solve the NP-hard UPMSP with sequence-dependent setup times by hybridizing the FA with a robust local search solution improvement schemes.
Implementation of a new solution representation and decoding procedure that is designed to make the FA more suitable for solving large instances of the problem at hand with high precisions and good quality solutions.
The rest of the paper is organized as follows: a brief review of related work on UPMSP is first presented in Section 2, and then the UPMSP mixed integer program formulation is presented in Section 3. Next, FA and its application to solve the problem at hand is described in Section 4, while computational study and results are further presented to evaluate the effectiveness and capability of the FA to solve the problem at hand. Finally, concluding remarks and future research directions are given in Section 6.