A Makespan Optimization Scheme for NP-Hard Gari Processing Job Scheduling Using Improved Genetic Algorithm

摘要

An optimization scheme for minimizing makespan of Gari processing jobs using improved initial population Genetic Algorithm (GA) is proposed. GA with initial population improved by using job sequencing and dispatching rules of First Come First Served (FCFS), Shortest Processing Time (SPT), Longest Processing Time (LPT), and Modified Johnson’s Algorithm for -machines in order to obtain better schedules than is affordable by GA with freely generated initial population and by individual traditional sequencing and dispatching rules was used. The traditional GA crossover and mutation operators as well as a custom-made remedial operator were used together with a hybrid of elitism and roulette wheel algorithms in the selection process based on job completion times. A test problem of 20 jobs with specified job processing and arrival times was simulated through the integral 5-process Gari production routine using the sequencing and dispatching rules, GA with freely generated initial population, and the improved GA. Comparisons based on performance measures such as optimal makespan, mean makespan, execution time, and solution improvement rate established the superiority of the improved initial population GA over the traditional sequencing and dispatching rules and freely generated initial population GA.