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

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

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)