An Evolutionary Algorithm for Uniform Parallel Machines Scheduling

Scheduling problems are very important for many (research) fields. However only for few instances there are polynomial time optimization algorithms, because the vast majority of scheduling problem instances is NP-hard. In such cases heuristic and/or stochastic algorithm are used which tend toward but do not guarantee the finding of optimal solution. The aim of our paper is to investigate the performance of stochastic algorithms, i.e. genetic algorithm, in solving scheduling problems. We present the results obtained for two instances of Q| |C_max scheduling problem. The obtained results were compared with results obtained by other optimization techniques, i.e. (another) genetic algorithm, simulated annealing, particle swarm optimization and multi-objective evolutionary algorithm. The comparison revealed that our genetic algorithm outperform the considered approaches because the results are very close (even equal) to the optimal solution.