Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin

Ong, Chung Sin (2013) Hybrid genetic algorithm with multi-parents recombination for job shop scheduling problems / Ong Chung Sin. Masters thesis, University of Malaya.

Preview

PDF (Full Text) Download (1441Kb) | Preview

Abstract

Job Shop Scheduling Problem (JSSP) is one of the well-known hard combinatorial scheduling problems and one of the most computationally difficult combinatorial optimization problems considered to date. This intractability is one of the reasons why the problem has been so widely studied. The problem was initially tackled by “exact methods” such as the branch and bound method, which is based on the exhaustive enumeration of a restricted region of solutions containing exact optimal solutions. Exact methods are theoretically important and have been successfully applied to benchmark problems, but sometimes they, in general are very time consuming even for moderate-scale problems. Metaheuristic is one of the “approximation methods” that is able to find practically acceptable solutions especially for large-scale problems within a limited amount of time. Genetic Algorithms (GA) which is based on biological evolution is one of the metaheuristics that has been successfully applied to JSSP. In this study an indirect representation incorporating a schedule builder that performs a simple local search to decode the chromosome into legal schedule called active schedule is proposed. The chromosomes are decoded into active schedules thus increasing the probability of obtaining near or optimal solution significantly. Crossover between two parents is traditionally adopted in GA while multiparents crossover (more than two parents) technique is still lacking. This research proposes extended precedence preservative crossover (EPPX) which uses multi-parents for recombination in the GA. This crossover operator attempts to recombine the good features in the multi-parents into a single offspring with the hope that the offspring iv fitness is better than all its parents. EPPX can be suitably modified and implemented with, in principal, unlimited number of parents. JSSP generates a huge search space. An iterative forward-backward pass which reduces search space has been shown to produce significant improvement in reducing makespan in other field of scheduling problem. The iterative forward-backward pass is applied on the schedules generated to rearrange their operation sequences to seek possible improvements in minimizing the total makespan. Reduction of the search space does not guarantee the optimal solution will be found. Therefore, a neighborhood search is embedded in the structure of GA and it acts as intensification mechanism that exploits a potential solution. This mechanism is restricted to search the possible solutions in a critical path. Modification on the path by using neighborhood search significantly reduces the total length of the makespan. The hybrid GA is tested on a set of benchmarks problems selected from literatures and compared with other approaches to ensure the sustainability of the proposed method in solving JSSP. The new proposed hybrid GA is able to produce 10 better or comparable solutions when compared to similar GA algorithms that employ two-parent crossover. In general this algorithm produces less than 6% deviation when compared to the best known solutions, especially in larger problems consisting of 20 jobs and 15 machines.

Actions (For repository staff only : Login required)