Job shop com minimização da duração total da programação (makespan) - solução por meio do resolvedor CP Optimizer
O problema de programação da produção em ambiente job shop, ambiente também conhecido como leiaute por processo, é um dos problemas mais tradicionais da gestão de produção. Ele envolve a programação de um conjunto de tarefas (lotes ou jobs), onde cada tarefa consiste em uma sequência de operações que precisam ser processadas em recursos específicos (máquinas), em uma ordem pré-determinada [1] . A complexidade do problema surge da necessidade de otimizar a alocação de recursos para melhorar algum indicador de nível de serviço da operação, como a duração total da programação (makespan), o tempo médio de espera ou outros critérios de desempenho.
A programação job shop é amplamente reconhecida por sua dificuldade computacional, sendo classificada como um problema NP-difícil. Isso significa que a solução ótima pode ser difícil de encontrar à medida que o número de tarefas e de máquinas aumenta.
Para abordar a complexidade do problema de job shop, são utilizadas várias abordagens, incluindo métodos exatos, como algoritmos de programação linear inteira e por restrições e métodos heurísticos e meta-heurísticos, como regras de despacho e algoritmos genéticos.
Neste tutorial o problema de job shop será resolvido usando um modelo de programação por restrições com o resolvedor CP Optimizer. Essa abordagem é particularmente eficaz para lidar com a complexidade e as numerosas restrições características deste tipo de problema. A programação por restrições permite modelar de forma direta e natural as restrições de precedência das operações, a disponibilidade das máquinas e outras especificações próprias do ambiente de produção job shop.
O CP Optimizer, em particular, pode explorar o espaço de soluções possíveis de problemas de otimização por meio de técnicas de propagação de restrições. Isso resulta em uma capacidade competitiva para encontrar soluções viáveis em tempo razoável, tornando-se uma ferramenta poderosa e prática para a programação da produção eficaz em ambientes industriais.
Importanto as bibliotecas necessárias
Uma recomendação é a instalação do pacote anaconda da linguagem Python [2] que possui a maioria das bibliotecas necessárias para a modelagem. Além disso, é necessária a instalação do software IBM ILOG CPLEX Optimization Studio [3] que possui o resolvedor CP Optimizer, necessário para resolver os modelos CP desenvolvidos. Durante a instalação do resolvedor será solicitada a instalação da biblioteca docplex que será utilizada no presente tutorial.
- Link de download do pacote Anaconda Python: https://www.anaconda.com/download/success (gratuito e de código aberto)
- Link de download do resolvedor CP Optimizer: https://academic.ibm.com/ (gratuito para fins acadêmicos - cadastrar o email acadêmico > acessar a guia Data Science > realizar o download do IBM CPLEX ILOG Optimization Studio)
from docplex.cp.model import CpoModel # Importando o construtor de modelos
import docplex.cp.utils_visu as visu # Importando funções para a construção de gráficos de gantt das soluções
import numpy as np # Importando a biblioteca numpy para manipulação de matrizes
Parâmetros do problema
O problema consiste na programação da produção em ambiente job shop, onde cada tarefa (ou lote) possui um tempo de processamento em cada máquina e cada tarefa possui uma sequência de processamento nas máquinas específica.
-
Exemplo de instância: programar 6 tarefas ($n=6$) em 6 máquinas ($m=6$). Cada tarefa possui uma rota de operações especificas. O objetivo é minimizar a duração total da programação (makespan).
-
Tempos de processamento:
| $$p_{ij}$$ | $$J_1$$ | $$J_2$$ | $$J_3$$ | $$J_4$$ | $$J_5$$ | $$J_6$$ |
|---|---|---|---|---|---|---|
| $$M_1$$ | 3 | 8 | 5 | 5 | 3 | 1 |
| $$M_2$$ | 7 | 10 | 9 | 9 | 3 | 3 |
| $$M_3$$ | 6 | 10 | 4 | 5 | 5 | 4 |
| $$M_4$$ | 1 | 5 | 1 | 3 | 4 | 3 |
| $$M_5$$ | 6 | 10 | 8 | 5 | 1 | 9 |
| $$M_6$$ | 3 | 4 | 7 | 8 | 9 | 10 |
- Sequência de máquinas de cada tarefa (sequência das operações):
| $$MAC_{jk}$$ | $$O_1$$ | $$O_2$$ | $$O_3$$ | $$O_4$$ | $$O_5$$ | $$O_6$$ |
|---|---|---|---|---|---|---|
| $$J_1$$ | $$M_3$$ | $$M_1$$ | $$M_2$$ | $$M_4$$ | $$M_6$$ | $$M_5$$ |
| $$J_2$$ | $$M_2$$ | $$M_3$$ | $$M_5$$ | $$M_6$$ | $$M_1$$ | $$M_4$$ |
| $$J_3$$ | $$M_3$$ | $$M_4$$ | $$M_6$$ | $$M_1$$ | $$M_2$$ | $$M_5$$ |
| $$J_4$$ | $$M_2$$ | $$M_1$$ | $$M_3$$ | $$M_4$$ | $$M_5$$ | $$M_6$$ |
| $$J_5$$ | $$M_3$$ | $$M_2$$ | $$M_5$$ | $$M_6$$ | $$M_1$$ | $$M_4$$ |
| $$J_6$$ | $$M_2$$ | $$M_4$$ | $$M_6$$ | $$M_1$$ | $$M_5$$ | $$M_3$$ |
Definição dos parâmetros do problema em matrizes da biblioteca numpy em python:
m = 6 # Número de máquinas
n = 6 # Número de tarefas
p = np.array(
[[ 3, 8, 5, 5, 3, 1],
[ 7, 10, 9, 9, 3, 3],
[ 6, 10, 4, 5, 5, 4],
[ 1, 5, 1, 3, 4, 3],
[ 6, 10, 8, 5, 1, 9],
[ 3, 4, 7, 8, 9, 10]]) # Tempos de processamento
MAC = np.array(
[[2, 0, 1, 3, 5, 4],
[1, 2, 4, 5, 0, 3],
[2, 3, 5, 0, 1, 4],
[1, 0, 2, 3, 4, 5],
[2, 1, 4, 5, 0, 3],
[1, 3, 5, 0, 4, 2]]) # Sequência de máquinas das operações de cada tarefa
Premissas do problema
- Cada máquina processa apenas uma tarefa por vez.
- Cada tarefa tem uma sequência de máquinas a ser seguida.
- Objetivo: minimizar a duração total da programação.
Job shop clássico com minimização do makespan - Modelo CP Optimizer
Modelo CP com notação CP Optimizer:
$$ \begin{align}
\text{min} & \nonumber \\
& \underset{\forall j}{\max} \texttt{ endOf}(x_{[MAC_{jm},j]}) \label{fo_cp_ex_job} \\
\text{st} \nonumber&\\
& \texttt{noOverlap}(\Gamma_i), & \forall i\label{c1_ex_job}\\
& \texttt{endBeforeStart}(x_{[MAC_{jk-1}, j]}, x_{[MAC_{jk}, j]}), & \forall j, k>1 \label{c2_ex_job}\\
& \texttt{interval}\texttt{ } x_{ij},\texttt{ }\texttt{ } \texttt{size}=p_{ij}, &\forall i, j\label{c3_ex_job}\\
& \texttt{sequence}\texttt{ } \Gamma_i,\texttt{ }\texttt{ } \texttt{on} \left [ x_{ij}\right ]_{j \in {1, 2, …, 6}}, & \forall i\label{c4_ex_job}
\end{align}
$$
Construção do modelo com a biblioteca docplex:
mdl = CpoModel()
Variável intervalar que representa a operação das tarefas nas máquinas:
$\texttt{interval}\texttt{ } x_{ij},\texttt{ }\texttt{ } \texttt{size}=p_{ij}, \quad \forall i, j$
x = [[mdl.interval_var(size=p[i, j], name=f'M{i}-J{j}') for j in range(n)] for i in range(m)]
Variável de sequência que representa a ordem das tarefas processadas em cada máquina:
$\texttt{sequence}\texttt{ } \Gamma_i,\texttt{ }\texttt{ } \texttt{on} \left [ x_{ij}\right ]_{j \in {1, 2, …, 6}}, \quad \forall i$
Gamma = [mdl.sequence_var([x[i][j] for j in range(n)], name=f'M{i}') for i in range(m)]
Minimização da duração total da programação (makespan):
$\text{min} \texttt{ } \underset{\forall j}{\max} \texttt{ } \texttt{endOf}(x_{[MAC_{jm},j]})$
mdl.add(
mdl.minimize( mdl.max( mdl.end_of(x[MAC[j, m-1]][j]) for j in range(n) ) )
)
Cada máquina processa apenas uma tarefa por vez:
$\texttt{noOverlap}(\Gamma_i), \quad \forall i$
mdl.add(
mdl.no_overlap( Gamma[i] ) for i in range(m)
)
Cada tarefa tem uma sequência de máquinas a ser seguida:
$\texttt{endBeforeStart}(x_{[MAC_{jk-1}, j]}, x_{[MAC_{jk}, j]}), \quad \forall j, k>1$
mdl.add(
mdl.end_before_start(x[MAC[j, k-1]][j], x[MAC[j, k]][j]) for j in range(n) for k in range(m) if k>0 # python índice 0
)
Resolução do modelo com resolvedor o CP Optimizer:
res = mdl.solve()
! --------------------------------------------------- CP Optimizer 22.1.1.0 --
! Minimization problem - 42 variables, 36 constraints
! Initial process time : 0.01s (0.01s extraction + 0.00s propagation)
! . Log search space : 186.1 (before), 186.1 (after)
! . Memory usage : 510.2 kB (before), 510.2 kB (after)
! Using parallel search with 16 workers.
! ----------------------------------------------------------------------------
! Best Branches Non-fixed W Branch decision
0 42 -
+ New bound is 47
! Using iterative diving.
* 79 73 0.02s 1 (gap is 40.51%)
* 72 145 0.02s 1 (gap is 34.72%)
* 61 217 0.02s 1 (gap is 22.95%)
* 60 331 0.02s 1 (gap is 21.67%)
* 55 708 0.02s 1 (gap is 14.55%)
55 708 1 1 F -
+ New bound is 55 (gap is 0.00%)
! ----------------------------------------------------------------------------
! Search completed, 5 solutions found.
! Best objective : 55 (optimal - effective tol. is 0)
! Best bound : 55
! ----------------------------------------------------------------------------
! Number of branches : 139857
! Number of fails : 6009
! Total memory usage : 7.7 MB (7.6 MB CP Optimizer + 0.1 MB Concert)
! Time spent in solve : 0.03s (0.02s engine + 0.01s extraction)
! Search speed (br. / s) : 7769833.3
! ----------------------------------------------------------------------------
print(f'A programação possui um makespan de: {res.get_objective_value()} u.t.')
A programação possui um makespan de: 55 u.t.
Plotagem da solução em um gráfico de gantt:
visu.timeline('Solution for job-shop example instance')
visu.panel('Machines')
for i in range(m):
visu.sequence(name=f'$M_{{{i+1}}}$',
intervals=[(res.get_var_solution(x[i][j]), j, f'$J_{{{j+1}}}$') for j in range(n)])
visu.panel('Jobs')
for j in range(n):
visu.sequence(name=f'$J_{{{j+1}}}$',
intervals=[(res.get_var_solution(x[MAC[j, k]][j]), j, f'$M_{{{MAC[j, k]+1}}}$') for k in range(m)])
visu.show()
Referências
[1] Pinedo, M. Scheduling: theory, algorithms, and systems. Prentice-Hall. New York. 2016.
[2] Anaconda Software Distribution. Computer software. Vers. 2024.02-1. Anaconda, Feb. 2024.
[3] CPLEX, IBM ILOG. “V22.1.0: User’s Manual for CPLEX.” International Business Machines Corporation 46.53. 2022.
Para citar esse artigo (bibtex)
@misc{lrabreu,
author="Abreu, L. R.",
title="Job shop com minimização da duração total da programação (makespan) - solução por meio do resolvedor CP Optimizer",
year=2024,
url=http://www.opl.ufc.br/pt/post/jobshop/,
note = "[Online; acessado em 20-06-2024]"
}
