Abstract:
For decades combinatorial problems have been studied in numerous disciplines. The scheduling problem, in which finding the optimal solution cannot be defined in a polynomial time, belongs to this type of problem. Several methodologies for the scheduling problem have been described in order to obtain efficient results. This thesis employs a combination of two methods to solve the task-scheduling problem. The first method, known as list-based heuristics, finds a feasible solution to the problem quickly, but with no guarantee of obtaining the optimal solution. The second method is a very well known search technique called simulated annealing. The simulated annealing technique explores all feasible solutions and obtains better solutions. Also, simulated annealing accepts worse solutions with a probability. This acceptance probability avoids local minimums in the algorithm. Furthermore, this thesis introduces the concept of hardware acceleration in order to improve the final algorithm's overall execution time. By transferring software functionality to dedicated hardware, the design achieves a significant reduction in execution time.
