Job shop scheduling problem (JSSP) is an NP-hard problem, and one of the most intractable combinatorial optimization problems considered to date. This intractability and importance for industrial engineering in terms of improving machine utilization and reducing cycle-time, made it so widely studied for more than fifty years.
GA has gained a well-earned reputation in being one of the best methods in solving JSSP, but it still has its own shortcomings like premature convergence, and the lack of intensification capabilities, i.e. searching in the small regions of the search space that are likely close to the optimal solutions. Various approaches have been developed during the last 4 decades to overcome these shortcomings, the most common ones include multi-population parallel GA such as island model GA (IMGA) for delaying the premature convergence and improving the diversification capabilities, and hybrid GA with local search (memetic algorithm) for adding intensification capabilities.
For solving JSSP with a single objective function, it has been shown that island model memetic algorithm (IMMA), which is a hybrid IMGA with a local search method (such as tabu search), is an effective approach because it can strike a better balance between diversification and intensification of search space.
Multi-objective JSSP (MOJSSP) has recently gained more interest than single-objective one. This is because of the fact that it better addresses real life problems when the decision maker has to measure the fitness of a solution against multiple objectives, even so, the amount of literature on it is very scarce.
With the objective of improving the general framework of IMMA and solving MOJSSP more effectively, Professor Mohamed Kurdi at Adnan Menderes University in Turkey, proposed an improved version of IMMA and extended its application to MOJSSP. The main contributions of the work are as follows.
- A new naturally inspired cooperation phase strategy for improving the exploitation capabilities, which is based on the following novel idea. Individuals who have recently performed self-adaptation phases (local search) do not exchange their knowledge about the search space just randomly; instead, they firstly divide their current knowledge into two parts: already existed knowledge and recently acquired knowledge, and secondly exchange their knowledge in favor of the recently acquired one. This is simulated by means of a new version of the well-known uniform crossover called the informed uniform crossover. In the proposed crossover, instead of generating the mask vector that determines the genetic materials exchanged between parents randomly, it is generated according to the evolution performed by parents, by identifying the new traits among the old ones, and favoring the new ones while maintaining a fixed mixing ratio.
- Several straightforward but effective techniques for improving the exploration capabilities such as a diversity-based initial population creation method, an incest prevention-based tournament selection method, and a similarity-and-quality based replacement method.
The improved IMMA has been tested on 72 benchmarks instance, with the proposed new components and without them using the traditional alternatives, and also compared with other similar algorithms reported recently in the literature. Computational results verify the improvements accomplished by the proposed new components, and show the superiority of the proposed algorithm over the other compared algorithms in terms of solution quality in the multi-objective case, and the single objective cases (makespan and total weighted tardiness) as well, which implies that the improved IIMMA can be considered as an effective and robust method for solving JSSP in the multi-objective case using the weighting approach, and single cases as well.
The idea of applying the history of parents’ local search in determining the genetic material exchanged during a crossover could be integrated in any memetic algorithm framework. The general framework of the improved IMMA developed by Professor Mohamed Kurdi can be applied on other combinatorial problems.
The research work is published in peer-reviewed journal, Computers & Industrial Engineering.
Mohamed Kurdi. An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problem. Computers & Industrial Engineering, issue 111 (2017), pages 183–201.
Go To Computers & Industrial Engineering