Scheduling problems with a cost function aligned with current concerns about sustainability and the environment

• Grant number: 24/21718-1
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
• Start date: March 01, 2025
• End date: July 31, 2029
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Ernesto Julián Goldberg Birgin
• Grantee: Kennedy Corrêa da Silva Júnior
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 23/08706-1 - Numerical optimization, AP.TEM

Abstract

The classic job shop (JS) problem consists of scheduling n jobs in an environment with m machines. Each job is made up of several operations with a linear precedence structure and has a predetermined route through the machines. The flexible job shop scheduling problem (FJS) is a generalization of the JS problem in which there may be several machines, not necessarily identical, capable of processing each operation. The processing time for each operation on each machine is known and no preemption is allowed. The goal is to decide in which machine each operation will be processed and in what order the operations will be processed in each machine, so that a certain criterion is optimized. The FJS problem with non-linear routes is a variant of the classic FJS in which the precedence between operations is given by an acyclic digraph instead of a set of disjoint linear orders. For example, if the job is to produce a book, it might consist of independent operations that consist of printing different parts of the book which then need to be glued together to form the book. The printing operations may also have a common operation before them, such as a diagramming step. Although scheduling problems have traditionally been defined according to metrics based on economic or productivity issues, recent studies in the area have begun to incorporate environmental issues into the problem, giving rise to so-called green scheduling problems. In these problems, it is common to consider a trade-off between productivity and energy consumption or CO2 emissions. The FJS problem with non-linear routes is NP-hard. In line with recent literature, in this project we aim to develop heuristic methods to deal with FJS with non-linear routes. In particular, we are interested in variants that include a cost function in line with current concerns about sustainability and the environment. There is a wide variety of ways of considering ``sustainability and the environment'', each with its own peculiarities. In this project, we intend to analyze and compare various possibilities and then delve into those that best adapt to reality and present theoretical and practical challenges to be overcome. (AU)