Approximation and competitive online algorithms for scheduling problems

Abstract

In Scheduling Problems, the goal is to find the best distribution of jobs to be performed by machines, aiming to minimize some aspect of the production process. Many of these problems have great theoretical difficulty, as they are NP-Hard, which means that there is no algorithm able to find the optimal solution in polynomial time, unless P=NP. They also have great practical relevance, mainly due to applications from the areas of Computer Science and Operational Research.This scientific initiation project has the objective of studying approximation and competitive online algorithms for Scheduling Problems, as well as implementing and testing some of the studied algorithms. We are particularly interested in the problem of scheduling on identical machines with the goal of minimizing the makespan, but we may also consider other variants. Therefore, the candidate will be introduced to scientific research while deepens his knowledge in combinatorial optimization and techniques of design and analysis of algorithms, complementing his formation in Computer Science.