Production scheduling

Production scheduling problems are common in most companies. Given a set of tasks, the problem consists of determine the sequence in which they will be processed in a set of machines available in order to optimize some performance indicator.

Common goals are: minimizing the makespan, which corresponds to the total time to perform all tasks; and the **minimization of the total tardiness, which corresponds to the sum of task delays in relation to the due date.

Programming tasks on machines is a difficult problem to solve in practice, because it involves the computational evaluation of a incredibly large quantity of possible sequences. For example, given 10 tasks to run on just one machine, there is a total of 3628800 possible sequences. The likelihood of finding the best sequence simply by trial and error (as often happens in practice) is very small, equivalent to “winning the lottery”.

Additionally, the number of possible sequences grows exponentially with the number of tasks, which prevents the use of a computer to test all sequences by “brute force”. For example, for 100 tasks, the number of possible sequences is on the order of $10^{157}$ (1 followed by 157 zeroes), greater than the number of particles in the universe, estimated on the order $10^{80}$.

On the other hand, it is still possible to obtain optimal solutions using smart algorithms. In this project, exact and heuristic algorithms are developed for production scheduling problems. Currently, we have focused on hybrid flow shop and open shop environemnts. These are multi-machine production environments, even more difficult problems than the simple machine problem.

The main technologies used in this project are the IBM CPLEX solver, and the programming languages Python and Julia.

The project has the collaboration of Prof. Marcelo Seido Nagano, from the Department of Industrial Engineering at University of São Paulo (EESC), and with the international collaboration of Prof. Jose M. Framinan, from the University of Seville.

This project has financing from Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq.