Programação de máquina única com PuLP em Python

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:

Schedule generated by Python

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

Leave a Reply

Deixe um comentário

O seu endereço de e-mail não será publicado.

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.

Close

Meta