Study of initial guess influence on the quality of solutions on binary genetic algorithm in job shop scheduling problems

Abstract

The purpose of this study is to evaluate the influence of the initial guess to generate the Genetic Algorithm population of solutions of scheduling problems in relation to the quality and feasibility of the solutions. The scheduling problem is defined as to find the sequence of operations on the machines that optimize some performance measure as, for example, the use of resources and the total processing time (makespan). It is common to treat such problems with the use of metaheuristics as genetic algorithm mainly due to its computational complexity. This work carried out experiments with a set of literature instances, varying the sequencing rule used in the generation of initial solutions. Usual rules from the literature have been tested and identified a hybrid rule that generates a smaller number of non-feasible solutions and the number of instances that have reached the optimal makespan.