Existem muitos casos de uso de pesquisa operacional (OR) em que o problema de decisão é encontrar uma sequência ótima ao longo do tempo. Por exemplo, podemos estar interessados em alocar um recurso (por exemplo, uma máquina, um ser humano, uma instalação, um avião, um computador em nuvem) horas extras para realizar um conjunto de tarefas (por exemplo, fabricação, projeto, separação de pedidos, voo, Aprendendo). Portanto, muitos profissionais envolvidos em gerenciamento de aeroportos, gerenciamento de projetos, fabricação, etc., estão interessados em criar cronogramas de alta qualidade. Neste artigo, descrevo como se pode codificar um problema de decisão usando a linguagem de programação Python e o PuLP como interface de otimização. Em outras palavras, os leitores aprenderão programação em Python.
1. Modelando e resolvendo o problema de agendamento em Python
Primeiramente, codifico o problema de decisão de acordo com as seguintes suposições sobre os elementos do ambiente de tomada de decisão:
A máquina:
- Não pode realizar mais de uma tarefa por vez. (Sem multitarefa)
- Tem um tempo de configuração antes de começar a realizar qualquer tarefa.
- Processa um trabalho após o outro imediatamente.
As tarefas:
- Tenha um tempo de processamento específico.
- Tenha uma prioridade específica (peso).
- São equivalentes a um único trabalho (ou seja, todas as tarefas consistem em um trabalho).
O tempo:
- Começa do zero
O critério:
- É minimizar o tempo total de conclusão ponderada (TWCT).
Aqui, forneço um código que modela o problema de decisão, satisfazendo as suposições mencionadas:
import pulp as op import itertools as it #Desenvolvedor: @KeivanTafakkori, 8 March 2022 def model(I,J,p,s,dispmodel="y",solve="y", dispresult="y"): m = op.LpProblem("SingleMachineSchedulingProblem", op.LpMinimize) x = {(i,j): op.LpVariable(f"x{i}{j}", 0,1, op.LpBinary) for i,j in it.product(I, J)} c = {j: op.LpVariable(f"c{j}", 0, None, op.LpContinuous) for j in J} objs = {0: sum(w[j]*c[j] for j in J)} cons = {0: {i: (sum(x[(i,j)] for j in J) == 1, f"eq1_{i}") for i in I}, 1: {j: (sum(x[(i,j)] for i in I) == 1, f"eq2_{j}") for j in J}, 2: {j: (c[j] >= c[j-1] + sum(x[(i,j)]*p[i] for i in I), f"eq3_{j}") for j in J if j!=0}, 3: {0: (c[0] == s + sum(x[(i,0)]*p[i] for i in I), "eq4_")}} m += objs[0] for keys1 in cons: for keys2 in cons[keys1]: m += cons[keys1][keys2] if dispmodel=="y": print("Model --- \n",m) if solve == "y": result = m.solve(op.PULP_CBC_CMD(timeLimit=None)) print("Status --- \n", op.LpStatus[result]) if dispresult == "y" and op.LpStatus[result] =='Optimal': print("Objective --- \n", op.value(m.objective)) print("Decision --- \n", [(variables.name,variables.varValue) for variables in m.variables() if variables.varValue!=0]) return m, c, x w = [0.1, 0.4, 0.15, 0.35] #Peso de prioridade de cada trabalho p = [ 7, 3, 9, 4] #Tempo de processamento de cada trabalho s = 5 #Tempo de configuração da máquina I = range(len(p)) #Set of jobs J = range(len(I)) #Set of positions
Ainda assim, preciso resolver o modelo, então adiciono o seguinte trecho de código:
m, c, x = model(I,J,p,s) #Modele e resolva o problema
Por fim, os resultados após a implementação são os seguintes:
Status ---
Optimal
Objetivo ---
18.25
Decisão ---
[('c0', 8.0), ('c1', 12.0), ('c2', 19.0), ('c3', 28.0), ('x02', 1.0), ('x10', 1.0), ('x23', 1.0), ('x31', 1.0)]
[2, 4, 1, 3]
2. Visualização dos resultados
Mesmo que o trecho de código acima tenha produzido os resultados necessários, compreensíveis por um especialista, ele não é suficiente para as necessidades de uma empresa. Os resultados são geralmente difíceis de entender nesta forma. Assim, a visualização dos resultados obtidos é importante. Eu adiciono o seguinte trecho de código para facilitar a compreensão dos resultados:
seq = []
for j in J:
for i in I:
if x[(i,j)].varValue==1:
seq.append(i+1)
print(seq)O código acima cria uma lista representando a sequência sugerida pelo modelo de otimização. E se pudéssemos ter um gráfico de Gantt para facilitar a revisão dos resultados? Como todos sabemos, uma figura vale sempre mais que um texto. Então eu adiciono o seguinte código:
import matplotlib.pyplot as plt import numpy as np fig, gnt = plt.subplots() gnt.set_xlabel('Minutes since start') gnt.set_ylabel('Machine') gnt.set_xlim(0, c[len(J)-1].varValue) gnt.set_ylim(0, 50) gnt.set_yticks([15, 25, 35]) gnt.set_yticklabels(['', '1', '']) gnt.grid(True,color='k',linestyle='-.', alpha=0.2) process = [(c[j-1].varValue,c[j].varValue) for j in J if j!=0] process.insert(0, (0,s)) process.insert(1, (s,c[0].varValue)) np.random.seed(3) l = [] for j in J: l.append(tuple(np.random.choice(range(0, 2), size=3))) gnt.broken_barh(process, (20, 9),color=l) for j in J: if j!=0: for i in I: if x[(i,j-1)].varValue==1: gnt.annotate(f"J{i+1}", (process[j][0],15)) else: gnt.annotate("Setup", (0,15)) for i in I: if x[(i,len(J)-1)].varValue==1: gnt.annotate(f"J{i+1}", (process[len(J)][0],15)) gnt.annotate(["TWCT",sum(w[j]*c[j].varValue for j in J)], ((c[len(J)-1].varValue-s)/2,10)) plt.savefig("gantt1.png")
O código cria um gráfico de Gantt, atribui cores aleatórias a cada parte e as anota. Assim, a seguinte figura é feita:
Observações finais
Neste artigo, apresentei como um problema de escalonamento de máquina única é resolvido via PuLP, uma interface para otimização, na linguagem de programação Python. Os leitores interessados podem visitar artigos anteriores sobre interfaces e solucionadores para saber mais sobre eles. Por fim, se você estiver interessado no conteúdo que publicamos, informe-nos comentando abaixo deste artigo!
Se este artigo for usado em pesquisa ou outros métodos de publicação, você pode citá-lo como Tafakkori (2022) (no texto) e referir-se a ele da seguinte forma: Tafakkori, K. (2022). Escalonamento de máquina única com PuLP em Python. Análise de Dados da Cadeia de Suprimentos. URL: https://www.supplychaindataanalytics.com/single-machine-scheduling-with-pulp-in-python
Engenheiro industrial com foco no aproveitamento de métodos de otimização e tecnologias de inteligência artificial usando várias linguagens de programação para capacitar uma empresa a atingir seus objetivos!
Leave a Reply