Imagine um armazém logístico que opera 24 horas por dia. A cada hora, o número de pacotes a ser processado varia, tornando crucial ter o número correto de trabalhadores para garantir que tudo seja concluído a tempo. Contratar mais funcionários do que o necessário aumenta os custos. Por outro lado, ter poucos trabalhadores pode causar atrasos e insatisfação dos clientes.

Trabalhadores Permanentes vs. Temporários

As empresas dependem de dois tipos de trabalhadores:

• Trabalhadores Permanentes: Funcionários em tempo integral, com mais experiência e eficiência.

• Trabalhadores Temporários: Contratados conforme a necessidade, são mais caros e menos eficientes, mas oferecem flexibilidade.

O grande desafio é encontrar o equilíbrio ideal entre esses dois grupos para atender à demanda sem desperdiçar recursos.

Resolvendo o Problema com Modelos Matemáticos

Pesquisadores desenvolveram modelos matemáticos para determinar a melhor forma de dimensionar a força de trabalho. Eles utilizam uma técnica chamada programação linear inteira 0-1, que, em termos simples, representa decisões (como "alocar um trabalhador ou não") por meio de equações matemáticas.

Objetivos do Modelo

• Minimizar o número total de dias de trabalho, reduzindo os custos de mão de obra.

• Atender à demanda horária, garantindo trabalhadores suficientes para cada turno.

• Obedecer às restrições, como não exceder o número máximo de dias consecutivos de trabalho para empregados permanentes e evitar alocar um trabalhador para mais de um turno por dia.

Algoritmos Inteligentes para Otimização

Resolver esses modelos matemáticos na prática pode ser muito complexo, especialmente ao lidar com centenas ou milhares de trabalhadores e turnos. É aí que entram os algoritmos inteligentes:

• Algoritmo Genético: Inspirado pela evolução natural, cria múltiplas "soluções candidatas" e combina as melhores partes de cada uma para encontrar a solução ideal ao longo do tempo.

• Recozimento Simulado: Baseado no processo de aquecimento e resfriamento de metais, explora diferentes soluções, ocasionalmente aceitando as menos ideais para evitar ficar preso e, por fim, encontrar a melhor solução global.

Sistemas de Manufatura Reconfiguráveis

A otimização de escalas é essencial em fábricas modernas, especialmente naquelas que utilizam Sistemas de Manufatura Reconfiguráveis (RMS). Esses sistemas podem ser ajustados rapidamente para produzir diferentes produtos ou lidar com variações na demanda.

Desafios Adicionais

• Riscos no Local de Trabalho: Garantir a segurança dos trabalhadores, considerando riscos relacionados às máquinas, bem como experiência e treinamento dos funcionários.

• Preferências dos Trabalhadores: Oferecer escalas flexíveis pode aumentar a satisfação e a produtividade dos empregados.

Modelo Multiobjetivo

Para lidar com esses desafios, os pesquisadores desenvolveram um modelo com os seguintes objetivos:

• Minimizar o Tempo Total de Produção (Makespan): Garantir que os produtos sejam fabricados no menor tempo possível.

• Minimizar o Custo Total de Produção: Incluindo custos operacionais e de mão de obra.

• Maximizar a Sustentabilidade Social: Melhorando a segurança e a satisfação dos trabalhadores.

Soluções Avançadas com Algoritmos Evolutivos

Para resolver esse modelo complexo, são utilizados algoritmos evolutivos avançados:

• NSGA-II: Um algoritmo multiobjetivo que encontra soluções ótimas de forma eficiente, considerando múltiplas metas simultaneamente.

• AMOSA: Outro algoritmo multiobjetivo projetado para otimização eficaz em condições complexas.

Visão Geral do NSGA-II

Algoritmos genéticos (GAs) estão entre os métodos de otimização metaheurística mais amplamente utilizados e têm sido aplicados em diversos domínios. Eles fazem parte de uma classe de técnicas de inteligência computacional inspiradas em princípios evolutivos, representando potenciais soluções como estruturas semelhantes a cromossomos. Utilizando diversos operadores de reprodução, como cruzamento e mutação, os GAs preservam informações essenciais dentro de cada cromossomo enquanto geram novas soluções candidatas.

Para lidar com desafios de otimização multiobjetivo, os GAs requerem um sistema de ranqueamento baseado em vetores para identificar soluções eficazes. Um dos métodos de ranqueamento vetorial mais conhecidos combinados com GAs é o ordenamento não-dominado. Introduzido por Srinivas e Deb, essa abordagem — conhecida como NSGA — aplica o ordenamento não-dominado para resolver problemas multiobjetivo.

No entanto, o NSGA apresenta três principais limitações:

1. O processo de ordenamento não-dominado é demorado e computacionalmente caro.

2. Determinar os parâmetros de compartilhamento apropriados é desafiador.

3. A ausência de elitismo pode levar à perda de soluções de alta qualidade uma vez que tenham sido encontradas.

Para superar essas limitações, Deb desenvolveu o NSGA-II. As etapas principais do NSGA-II são descritas no seguinte algoritmo.

Durante a etapa de cruzamento, os genes dos cromossomos parentais são selecionados para criar novos descendentes. A abordagem mais simples envolve escolher um ponto de cruzamento aleatoriamente. Sem modificações adicionais, os valores dos cromossomos antes e depois desse ponto são diretamente transferidos para os descendentes, enquanto os valores entre os pontos escolhidos são trocados entre os pais correspondentes para produzir as novas soluções.

# Pseudocódigo para um algoritmo genético baseado em NSGA-II

# Parâmetros necessários:
# population_size, total_iterations, crossover_probability, 
# mutation_probability

# 1: Geração da solução inicial aleatória
population = generate_initial_population(population_size)

# 2: Avaliar valores objetivos
evaluate_population(population)

# 3: Atribuir rank baseado em Pareto
pareto_sort(population)

# 4: Gerar população de descendentes
offspring = generate_offspring(population, crossover_probability, 
                               mutation_probability)

# 5: Seleção por torneio binário
selected_parents = binary_tournament_selection(population)

# 6: Crossover e mutação
offspring = apply_crossover_and_mutation(selected_parents, 
                                         crossover_probability, 
                                         mutation_probability)

# 7: Início das iterações
for iteration in range(total_iterations):
    # 8: Para pais e filhos na população
    combined_population = population + offspring

    # 9: Regenerar nova população utilizando crossover e mutação
    offspring = apply_crossover_and_mutation(combined_population, 
                                             crossover_probability, 
                                             mutation_probability)

    # 10: Cálculo do valor de aptidão (fitness) de toda a população
    evaluate_population(combined_population)

    # 11: Ordenar soluções usando mecanismo de ordenação não-dominado
    pareto_fronts = non_dominated_sorting(combined_population)

    # 12: Adicionar soluções à próxima geração, partindo da primeira fronteira
    next_population = []
    for front in pareto_fronts:
        if len(next_population) + len(front) <= population_size:
            next_population.extend(front)
        else:
            next_population.extend(select_by_crowding_distance(front, 
                                                               population_size - 
                                                               len(next_population)))
            break

    # 14: Selecionar pontos da fronteira inferior com alta distância de aglomeração (já realizado acima)
    # 15: Criar próxima geração
    population = next_population

    # 16: Seleção por torneio binário
    selected_parents = binary_tournament_selection(population)

    # 17: Crossover e mutação
    offspring = apply_crossover_and_mutation(selected_parents, 
                                             crossover_probability, 
                                             mutation_probability)

# 18: Fim das iterações

Visão Geral do AMOSA

Bandyopadhyay introduziu uma técnica de otimização multiobjetivo baseada no recozimento simulado, conhecida como AMOSA. Esse método utiliza uma estrutura de arquivo para produzir um conjunto de soluções de compromisso. Os autores desenvolveram um procedimento inovador que leva em consideração o status de dominância para determinar a probabilidade de retenção de uma solução candidata recém-gerada. O pseudocódigo para a versão adaptada do AMOSA é apresentado no Algoritmo 2.

# Pseudocódigo para um Algoritmo de Otimização Multiobjetivo Baseado em Arquivo

# Parâmetros necessários:
# Tmax, Tmin, iter, α (alpha), temp = Tmax
# É necessário também uma razão de perturbação (perturbation ratio)
# Archive: coleção de pontos (soluções) já conhecidos

Current_points = random_selection_from(Archive)
temp = Tmax

while temp > Tmin:
    for i in range(iter):
        New_points = perturb(Current_points)

        # Se Current_points domina New_points
        if dominates(Current_points, New_points):
            # New_points = Current_points com alguma probabilidade
            if should_replace():
                New_points = Current_points

        # Se Current_points e New_points não dominam um ao outro
        if non_dominating(Current_points, New_points):

            # Se New_points é dominado por k pontos no Archive
            if dominated_by_k_points_in_archive(New_points, Archive):
                # New_points = Current_points com alguma probabilidade
                if should_replace():
                    New_points = Current_points

            # Se nenhum ponto no Archive domina New_points
            if no_point_in_archive_dominates(New_points, Archive):
                New_points = Current_points
                add_to_archive(New_points, Archive)
                remove_dominated_by(New_points, Archive)

        # Se New_points domina Current_points
        if dominates(New_points, Current_points):
            New_points = Current_points
            add_to_archive(New_points, Archive)
            remove_dominated_by(New_points, Archive)

    temp = temp * α

return Archive

• AUGMECON-R: Um método exato projetado para ajudar a identificar o conjunto de soluções eficientes (fronteira de Pareto) para problemas multiobjetivo.

  
  

lbk denota o limite inferior do k-ésimo objetivo, rk representa a faixa do k-ésimo objetivo, gk indica o número de intervalos para o k-ésimo objetivo, e sk é a variável de folga associada ao k-ésimo objetivo. O parâmetro EPS é um número muito pequeno, geralmente escolhido dentro do intervalo (10⁻⁶, 10⁻³), e F representa a região viável. A cada iteração do algoritmo, os coeficientes de passagem bi = int(si / stepi) são calculados.

Se si ≥ stepi, então a iteração subsequente para bi', onde ei' = si - stepi, geraria a mesma solução. Uma vez que si' = si - stepi, essa iteração pode ser considerada redundante. Em outras palavras, o coeficiente de passagem bi dita quantas iterações devem ser puladas.

Durante cada iteração do loop principal, o algoritmo mantém uma matriz de bandeira, flag[(g2 + 1) × (g3 + 1) × ... × (gp + 1)]. Inicialmente, essa matriz é definida como zero. O algoritmo verifica a entrada da matriz antes de realizar qualquer otimização: se a entrada atual é zero, prossegue com a otimização; se não, pula o número de iterações especificadas pelo valor não zero na matriz para o loop mais interno.

Exemplo Simples Usando um Solver de Código Aberto

Descrição do Problema

Objetivo: Minimizar o número total de dias de trabalho utilizados.

Trabalhadores:

• Trabalhadores Permanentes: Funcionários em tempo integral com restrições sobre os dias consecutivos de trabalho.

• Trabalhadores Temporários: Contratados conforme necessário, sem restrições sobre os dias consecutivos de trabalho.

Demandas:

• Variação diária na demanda por trabalhadores.

• Necessidade de atender à demanda para cada dia operacional.

Restrições:

• Cada trabalhador pode trabalhar um máximo de um turno por dia.

• Os trabalhadores permanentes não podem trabalhar mais de 7 dias consecutivos.

• Limites nas horas trabalhadas por dia e por semana.

Modelagem em Python

Aqui, usamos o modelo diretamente para resolver o problema, uma vez que lidamos com um pequeno número de trabalhadores.

from pyomo.environ import *
from pyomo.opt import SolverFactory
import pandas as pd

# Dados do problema
dias = list(range(14))  # 14 dias
trabalhadores_permanentes = list(range(5))  # 5 trabalhadores permanentes
demanda = [8, 6, 7, 9, 10, 11, 9, 8, 6, 7, 9, 10, 6, 8]  # Demanda por dia
custo_permanente = 100  # Custo por dia de um trabalhador permanente
custo_temporario = 150  # Custo por dia de um trabalhador temporário

# Modelo
modelo = ConcreteModel()

# Variáveis
modelo.x = Var(dias, trabalhadores_permanentes, domain=Binary)  # Permanentes
modelo.y = Var(dias, domain=NonNegativeIntegers)  # Temporários

# Função objetivo: Minimizar custos
modelo.objetivo = Objective(
    expr=sum(custo_permanente * modelo.x[d, s] for d in dias 
             for s in trabalhadores_permanentes) +
         sum(custo_temporario * modelo.y[d] for d in dias),
    sense=minimize
)

# Restrições de demanda
modelo.restricao_demanda = ConstraintList()
for d in dias:
    modelo.restricao_demanda.add(
        sum(modelo.x[d, s] for s in trabalhadores_permanentes) + 
      modelo.y[d] >= demanda[d]
    )

# Restrição de no máximo 7 dias consecutivos para permanentes.
modelo.restricao_consecutivos = ConstraintList()
for s in trabalhadores_permanentes:
    for d in range(len(dias) - 7):
        modelo.restricao_consecutivos.add(
            sum(modelo.x[d + k, s] for k in range(8)) <= 7
        )

# Resolução
solver = SolverFactory('glpk')
resultado = solver.solve(modelo)

# Processamento dos resultados
custo_total = modelo.objetivo()

# Escalonamento de permanentes
escalonamento_permanentes = {
    f"Trabalhador {s + 1}": [int(modelo.x[d, s].value) for d in dias]
    for s in trabalhadores_permanentes
}

# Número de temporários por dia
temporarios = [int(modelo.y[d].value) for d in dias]

# Apresentar os resultados
print("Resultado da otimização:")
print(f"Custo total mínimo: R$ {custo_total:.2f}\n")

print("Escalonamento dos trabalhadores permanentes:")
for s in trabalhadores_permanentes:
    print(f"Trabalhador {s+1}: {escalonamento_permanentes[f'Trabalhador {s+1}']}")

print("\nNúmero de trabalhadores temporários por dia:")
for d in dias:
    print(f"Dia {d+1}: {temporarios[d]} temporários")

# DataFrame com o resultado final
resultado_df = pd.DataFrame(escalonamento_permanentes)
resultado_df["Temporários"] = temporarios
resultado_df["Demanda"] = demanda

print("\nTabela final:")
print(resultado_df)

Saída:

Esses resultados mostram que o modelo sempre utilizou todos os 5 trabalhadores permanentes para os máximos dias consecutivos permitidos. Quando foi necessário dar a eles uma pausa coletiva (para evitar exceder o limite de trabalho consecutivo de 7 dias), ele se apoiou fortemente em trabalhadores temporários durante esse dia de descanso. Isso resultou em um padrão onde muitos trabalhadores temporários foram necessários em certos dias (por exemplo, Dia 7) e poucos ou nenhum em outros, atendendo à demanda, mas de uma forma concentrada e menos realista do ponto de vista operacional.

Segue um exemplo de código Python + Pyomo semelhante ao anterior, mas forçando uma abordagem de agendamento mais realista. Para conseguir isso, adicionamos restrições atribuindo dias de descanso específicos para cada trabalhador permanente (em vez de permitir que o solver decidisse livremente, o que anteriormente levava todos os trabalhadores a tirar o mesmo dia de folga). Com essas restrições, cada trabalhador tem um dia de descanso escalonado, evitando que todos os trabalhadores permanentes precisem descansar simultaneamente.

• Trabalhador 1 descansa no Dia 4

• Trabalhador 2 descansa no Dia 5

• Trabalhador 3 descansa no Dia 6

• Trabalhador 4 descansa no Dia 7

• Trabalhador 5 descansa no Dia 8

from pyomo.environ import *
from pyomo.opt import SolverFactory
import pandas as pd

# Dados do problema
dias = list(range(14))  # 14 dias
trabalhadores_permanentes = list(range(5))  # 5 trabalhadores permanentes
demanda = [8, 6, 7, 9, 10, 11, 9, 8, 6, 7, 9, 10, 6, 8]  # Demanda por dia
custo_permanente = 100  # Custo por dia de um trabalhador permanente
custo_temporario = 150  # Custo por dia de um trabalhador temporário

# Modelo
modelo = ConcreteModel()

# Variáveis
modelo.x = Var(dias, trabalhadores_permanentes, domain=Binary)  # Permanentes
modelo.y = Var(dias, domain=NonNegativeIntegers)  # Temporários

# Função objetivo: Minimizar custos
modelo.objetivo = Objective(
    expr=sum(custo_permanente * modelo.x[d, s] for d in dias for s in trabalhadores_permanentes) +
         sum(custo_temporario * modelo.y[d] for d in dias),
    sense=minimize
)

# Restrições de demanda
modelo.restricao_demanda = ConstraintList()
for d in dias:
    modelo.restricao_demanda.add(
        sum(modelo.x[d, s] for s in trabalhadores_permanentes) + 
      modelo.y[d] >= demanda[d]
    )

# Restrição de no máximo 7 dias consecutivos para permanentes
modelo.restricao_consecutivos = ConstraintList()
for s in trabalhadores_permanentes:
    for d in range(len(dias) - 7):
        modelo.restricao_consecutivos.add(
            sum(modelo.x[d + k, s] for k in range(8)) <= 7
        )

# Restrições para forçar folgas escalonadas
# Dia 4 (índice 3) trabalhador 1 não trabalha
modelo.fix_folga_1 = Constraint(expr=modelo.x[3, 0] == 0)
# Dia 5 (índice 4) trabalhador 2 não trabalha
modelo.fix_folga_2 = Constraint(expr=modelo.x[4, 1] == 0)
# Dia 6 (índice 5) trabalhador 3 não trabalha
modelo.fix_folga_3 = Constraint(expr=modelo.x[5, 2] == 0)
# Dia 7 (índice 6) trabalhador 4 não trabalha
modelo.fix_folga_4 = Constraint(expr=modelo.x[6, 3] == 0)
# Dia 8 (índice 7) trabalhador 5 não trabalha
modelo.fix_folga_5 = Constraint(expr=modelo.x[7, 4] == 0)

# Resolução
solver = SolverFactory('glpk')
resultado = solver.solve(modelo)

# Processamento dos resultados
custo_total = modelo.objetivo()

# Escalonamento de permanentes
escalonamento_permanentes = {
    f"Trabalhador {s + 1}": [int(modelo.x[d, s].value) for d in dias]
    for s in trabalhadores_permanentes
}

# Número de temporários por dia
temporarios = [int(modelo.y[d].value) for d in dias]

# Exibição dos resultados
print("Resultado da otimização:")
print(f"Custo total mínimo: R$ {custo_total:.2f}\n")

print("Escalonamento dos trabalhadores permanentes:")
for s in trabalhadores_permanentes:
    print(f"Trabalhador {s+1}: {escalonamento_permanentes[f'Trabalhador {s+1}']}")

print("\nNúmero de trabalhadores temporários por dia:")
for d in dias:
    print(f"Dia {d+1}: {temporarios[d]} temporários")

# DataFrame com o resultado final
resultado_df = pd.DataFrame(escalonamento_permanentes)
resultado_df["Temporários"] = temporarios
resultado_df["Demanda"] = demanda

print("\nTabela final:")
print(resultado_df)

Saída:

Referências:

XU, Karl; DU PREEZ, Johan; DAVARI, Hossein. Rumo ao gêmeo digital: uma abordagem semi-automática para modelagem de fábrica baseada em nuvem de pontos. International Journal on Interactive Design and Manufacturing (IJIDeM), [S.l.], 2024.
Disponível em: https://doi.org/10.1007/s12008-024-02010-x.

WU, Haixin; CHENG, Yu; YANG, Xin; SU, Yuelong; XU, Jinxin; WANG, Liyang; FU, Xintong. Otimização do Agendamento de Trabalhadores em Depósitos Logísticos Usando Algoritmos Genéticos e Aquecimento Simulado. 2024. Disponível em: https://arxiv.org/pdf/2405.11729.