Non-Exact Optimization Algorithms for Sequencing Problems

• Grant number: 10/08434-1
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: August 01, 2010
• End date: December 31, 2011
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Débora Pretti Ronconi
• Grantee: Celso Satoshi Sakuraba
• Host Institution: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

There are optimization problems that represent a challenge even for the best optimization softwares available currently. Examples of these problems considered difficult can be found inside the class NP-hard, frequently approached using heutistic and metaheutistic methods, especially when we deal with instances with a large number of variables. This project aims the development of metaheuristics for two combinatorial optimization problems: the linear ordering problem and a flowshop scheduling problem. Previous works from the author present algorithms that can reach locally optimal solutions efficiently, performing a local search for the linear ordering problem in a smaller computational time than algorithms proposed in the literature, or finding an optimal schedule for a given sequence of jobs in linear time. Based on these algorithms, we expect to apply the framework of metaheuristics to obtain better results in terms of computational time and solution quality.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

SAKURABA, CELSO S.; RONCONI, DEBORA P.; BIRGIN, ERNESTO G.; YAGIURA, MUTSUNORI. Metaheuristics for large-scale instances of the linear ordering problem. EXPERT SYSTEMS WITH APPLICATIONS, v. 42, n. 9, p. 4432-4442, JUN 1 2015. (13/07375-0, 10/08434-1, 13/05475-7, 10/10133-0, 13/03447-6)