ALGORITMI GENETICI E RICERCA LOCALE PER IL PROBLEMA JOB-SHOP

You are viewing the theme
[Voti: 0    Media Voto: 0/5]

Job Shop Scheduling Problem is a strongly NP-hard problem of combinatorial optimisation and one of the most well-known machine scheduling problem.

Job Shop Scheduling Problem is a strongly NP-hard problem of combinatorial optimisation and one of the most well-known machine scheduling problem. Taboo Search is an effective local search algorithm for the job shop scheduling problem, but the quality of the best solution found depends on the initial solution used. To overcome this problem in this thesis we present a new approach that uses a population of Taboo Search runs in a Genetic Algorithm framework: GAs localise good areas of the solution space so that TS can start its search with promising initial solutions. The peculiarity of the Genetic Algorithm we propose consists in a natural representation, which covers all and only the feasible solution space and guarantees the transmission of meaningful characteristics. The results show that this method outperforms many others producing good quality solutions in less time.