Em artigos anteriores, modelei e resolvi um problema de programação de uma única máquina. E se tivermos dois recursos que operam em uma sequência pré-determinada (mas não em paralelo) para processar um conjunto de tarefas semelhantes? Os chamados modelos de escalonamento “flow shop” focam nessas situações. Pode ser uma programação de produção dentro de uma fábrica. Ou pode ser o agendamento de serviços entre instalações e clientes dentro de uma cadeia de suprimentos. Assim, a programação flow shop tem inúmeras aplicações. Neste artigo, proponho um modelo simples para agendamento de flow shop em Python.

Modelando e resolvendo o problema de agendamento de flow shop em Python

Aqui, codifico o problema de decisão de acordo com as seguintes suposições e em relação aos elementos do ambiente de tomada de decisão:

As máquinas:

• Não pode realizar mais de uma tarefa por vez. (Sem multitarefa)
• Tenha um tempo de configuração antes de começar a realizar qualquer tarefa
• Não pode processar um trabalho após o outro imediatamente (exceto o primeiro)
• Operar em uma sequência predeterminada

As tarefas:

• Tenha um tempo de processamento específico em cada máquina
• Ter uma prioridade específica (peso) para sua conclusão
• São equivalentes a um único trabalho (ou seja, todas as tarefas
  consistem em um trabalho)
• Siga uma rota de processo predeterminada
• Siga a mesma sequência (permutação) em todas as máquinas

A hora:

• Começa do zero (para a primeira máquina)

O critério:

• É minimizar o tempo total de conclusão ponderada (TWCT) (para
  trabalhos que saem da última máquina na sequência)

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

#Developer: @KeivanTafakkori, 14 March 2022

def model(I,J,K,p,s,dispmodel="n",solve="y", dispresult="y"):
    m    = op.LpProblem("FlowShopSchedulingProblem", 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,k): op.LpVariable(f"c{j}{k}", 0, None, op.LpContinuous) for j,k in it.product(J, K)}
    maxi = {(j,k): op.LpVariable(f"maxi{j}{k}", 0, None, op.LpContinuous) for j,k in it.product(J, K)}
    objs = {0: sum(w[j]*c[(j,1)] for j in J)}
    cons = {0: {i: (sum(x[(i,j)] for j in J) == 1, f"eq0_{i}") for i in I},
            1: {j: (sum(x[(i,j)] for i in I) == 1, f"eq1_{j}") for j in K},
            2: {j: (c[(j,1)] >= sum(x[(i,j)]*p[1][i] for i in I) + maxi[(j,1)], f"eq2_{j}") for j in J if j!=0},
            3: {0: (c[(0,1)] == s[1] + sum(x[(i,0)]*p[1][i] for i in I) + c[(0,0)], "eq3_")},
            4: {j: (c[(j,0)] >= c[(j-1,0)] + sum(x[(i,j)]*p[0][i] for i in I), f"eq4_{j}") for j in J if j!=0},
            5: {0: (c[(0,0)] == s[0] + sum(x[(i,0)]*p[0][i] for i in I), "eq5_")},
            6: {j: (maxi[(j,1)] >= c[(j-1,1)], f"eq6_{j}") for j in J if j!=0},
            7: {j: (maxi[(j,1)] >= c[(j,0)], f"eq7_{j}") for j in J}}
    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 prioritário de cada trabalho
p = [[  7,   3,    9,    4],
     [  7,   3,    9,    4]] # Tempo de processamento de cada trabalho em cada máquina
s = [5, 2] # Tempos de setup das máquinas
I = range(len(p[0])) # Conjunto de trabalhos
J = range(len(I)) # Conjunto de posições
K = range(len(p)) # Conjunto de máquinas

Para resolver o modelo, utilizo o seguinte comando:

m, c, x = model(I,J,K,p,s) # Modele e resolva o problema

Felizmente, não há erros, o status é relatado como viável e ótimo, e os seguintes resultados são obtidos:

Status --- 
 Optimal
Objective --- 
 24.950000000000003
Decision --- 
 [('c00', 8.0), ('c01', 13.0), ('c10', 12.0), ('c11', 17.0), ('c20', 19.0), ('c21', 26.0), ('c30', 28.0), ('c31', 37.0), ('maxi01', 8.0), ('maxi11', 13.0), ('maxi21', 19.0), ('maxi31', 28.0), ('x02', 1.0), ('x10', 1.0), ('x23', 1.0), ('x31', 1.0)]

Portanto, a sequência obtida é: 2->4->1->3, que é semelhante para todas as máquinas. Por fim, uma visualização dos resultados pode ser a seguinte:

Observações finais

Neste artigo, criei um modelo simples e básico para agendamento de flow shop em Python e o resolvi usando PuLP, uma interface em Python, que por padrão usa o solver CBC de código aberto para modelos de programação inteira. Se você achou a descrição interessante, deixe-nos saber 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 se referir a ele da seguinte forma: Tafakkori, K. (2022). Agendamento de Flow shop com PuLP em Python. Análise de Dados da Cadeia de Suprimentos. url: https://www.supplychaindataanalytics.com/flow-shop-scheduling-with-pulp-in-python

Keivan Tafakkori M.Sc.

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!