It is well known that GAs are not well suited for fine-tuning structures that are very close to optimal solutions and that it is essential to incorporate local search methods, such as neighborhood search, into GAs. In addition, in solving combinatorial problems such as job-shop-scheduling problem (JSSP) by GAs, efficient parameter settings that provide optimal solutions are usually difficult to construct. This thesis presents an improved approach to Genetic Algorithm (GA) with Local search techniques (LS) in the hybridization Genetic Local Search (GLS) algorithm. GLS attempts to solve the JSSP with the objective of minimizing the makespan value, this can be achieved using effective parameter setting and ideal neighbourhood structure, in GLS algorithm framework. The proposed algorithm consists of three main parts. In the first one, an indirect representation incorporating a schedule builder that performs simple LS is proposed to decode the
chromosome into a legal schedule called active schedule. The chromosomes are then decoded into active schedules to significantly increase the probability of obtaining near or optimal solution. In the second part, Multi-Step Crossover Fusion (MSXF) with the intuition of generating a child from the path re-linking technique is used. MSXF, an extended version of LS, utilizes a neighborhood structure and a distance measure in its procedure. In this study, Nowicki and Smutnicki (NS) neighborhood search is used to increase the effectiveness of the algorithm in producing better solutions. By using this type of crossover, a solution or child is generated between both parents using through a search path joining parent solutions. The third part is accomplished by using multi-step mutation fusion as the supplementary search to improve GLS performance. Computational experiments are carried out on the proposed algorithm, which yields better results for most benchmark problems compared with JSSP obtained from the literature. Experiment results indicate that a set of effective GLS parameter settings (population size
= 1 0; roulette wheel selection; MSXF crossover; and probability of crossover = 0.5 with mutation operator) exists. The combination of these settings is synergistic, i.e., they collectively enable the procedure to be fast and robust. Meanwhile, NS neighborhood search significantly reduces the total length of the makespan and decrease the computational time. Providing an effective parameter setting facilitates the use of GLS, rendering it suitable for wide-ranging real-time, practical applications in computer science, industries, and all other fields requiring the minimization of costs, delays, etc.
