Green flexible jobshop scheduling problem with sequence flexibility and learning/deterioration effects

• Grant number: 22/16743-1
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Effective date (Start): June 01, 2023
• Effective date (End): March 31, 2024
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Ernesto Julián Goldberg Birgin
• Grantee: José Angel Riveaux Merino
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 18/24293-0 - Computational methods in optimization, AP.TEM

Abstract

The classical job shop (JS) problem consists of scheduling $n$ jobs on an environment with $m$ machines. Each job is composed by several operations with a linear precedence structure and has a predetermined route through the machines. The flexible job shop scheduling (FJS) problem 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 of each operation on each machine is known and no preemption is allowed. The objective is to decide on which machine each operation will be processed, and in what order the operations will be processed on each machine, so that a certain criterion is optimized.The FJS problem with sequencing flexibility is a variant of the classical FJS in which the precedence between operations is given by an acyclic digraph instead of by a set of disjoint linear orders. The latter case occurs when there are jobs, each composed of a set of operations, and the operations of the same job have a linear order in which they must be executed. The flexibility of sequencing appears when, within a job, there is no linear order among the operations that compose it. For example, if the job is to produce a book, it may consist of independent operations that consist of printing different parts of the book that subsequently need to be glued together to form the book. The printing operations may also have a common operation preceding them, such as a diagramming step. This example is not a random example, as the FJS problem with sequencing flexibility has recently gained prominence within the printing industry. While scheduling problems have traditionally been defined according to metrics based on economic or productivity issues, recent studies in the field 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 emission.In classical scheduling problems, the processing time of an operation on a given machine is a fixed input data. In problems with learning or deterioration effect, the processing time of an operation on a given machine is a function that may depend on the position of the operation on the machine (first to be processed, second, etc.) or on the sum of the processing times of the operations that have already been processed by the machine. The function can be an exponential and can even be discontinuous if it includes some kind of truncation. The learning effect may be related to the acquisition of experience by the machine operator, while the deterioration effect may be related to machine fatigue. Such a feature helps to approximate the problem addressed to problems encountered in real applications.The FJS problem with sequencing flexibility is NP-hard, since it has the JS problem (that is known to be NP-hard as a particular case. Due to its complexity, the number of publications concerned with the exact solution of the FJS problem is very small. In line with recent literature, in this project we aim to develop heuristic methods to deal with the FJS with sequencing flexibility. In particular, we are interested in a variant that includes two ingredients: (i) learning and deterioration effects on the processing time of operations and (ii) a cost function in line with current concerns with sustainability and environment.