Advanced search
Start date
Betweenand

Approximation and competitive online algorithms for scheduling problems

Grant number: 20/06106-9
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): August 01, 2020
Effective date (End): December 31, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Mário César San Felice
Grantee:João Victor Mendes Freire
Home 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.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Please report errors in scientific publications list by writing to: cdi@fapesp.br.