Approximation and competitive online algorithms for scheduling problems

• Grant number: 20/06106-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2020
• End date: December 31, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: João Victor Mendes Freire
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

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.