A Comparative Study Between a Genetic Algorithm and Tabu Search for Scheduling Problems on a Single Machine

Abstract

In this paper, we will present a comparative study between a genetic algorithm and tabu search for solving scheduling problems on a single machine to minimize the weighted sum of the task’s end dates; since this problem is NP-hard in the strong sense; exact methods require a computational effort that increases exponentially with the size of the problem. Approximate algorithms enable the solution of this problem reasonably. In this farm, we present a genetic algorithm and tabu search metaheuristics, aiming to find an approximate solution to the problem under consideration. The results obtained are applicable in economics and industry.