Work Shift Optimization

Select Language

English

Dec 8, 2024

Work Shift Optimization

Imagine a logistics warehouse that operates 24 hours a day. Every hour, the number of packages to process varies, making it crucial to have the right number of workers to ensure everything is completed on time. Hiring more staff than necessary increases costs. On the other hand, having too few workers can lead to delays and customer dissatisfaction.

Permanent vs. Temporary Workers

Companies rely on two types of workers:

Permanent Workers: Full-time staff with more experience and efficiency.
Temporary Workers: Hired as needed, they are more expensive and less efficient but provide flexibility.

The major challenge is to find the ideal balance between these two groups to meet demand without wasting resources.

Solving the Puzzle with Mathematical Models

Researchers have developed mathematical models to determine the best way to scale the workforce. They use a technique called 0-1 integer linear programming, which, simply put, is a way to represent decisions (such as "assign a worker or not") using mathematical equations.

Model Objectives

Minimize the total number of worker-days to reduce labor costs.
Meet hourly demand, ensuring sufficient workers for each shift.
Adhere to constraints, such as not exceeding the maximum consecutive working days for permanent employees and avoiding scheduling a worker for more than one shift per day.

Smart Algorithms for Optimization

Solving these mathematical models in practice can be very complex, especially when dealing with hundreds or thousands of workers and shifts. This is where intelligent algorithms come in:

Genetic Algorithm: Inspired by natural evolution, it creates multiple "candidate solutions" and combines the best parts of each to find the optimal solution over time.
Simulated Annealing: Based on the process of heating and cooling metals, it explores different solutions, occasionally accepting less optimal ones to avoid getting stuck and ultimately find the best global solution.

Reconfigurable Manufacturing Systems

Scheduling optimization is crucial in modern factories, especially those using Reconfigurable Manufacturing Systems (RMS). These systems can be quickly adjusted to produce different products or handle variations in demand.

Additional Challenges

Workplace Risks: Ensuring worker safety by considering machine-related risks, as well as employee experience and training.
Worker Preferences: Offering flexible schedules can increase employee satisfaction and productivity.

Multi-Objective Model

To address these challenges, researchers have developed a model aimed at:

Minimizing Total Production Time (Makespan): Ensuring products are made in the shortest possible time.
Minimizing Total Production Cost: Including operational and labor costs.
Maximizing Social Sustainability: Improving worker safety and satisfaction.

Advanced Solutions with Evolutionary Algorithms

To solve this complex model, advanced evolutionary algorithms are employed:

NSGA-II: A multi-objective algorithm that efficiently finds optimal solutions considering multiple goals simultaneously.
AMOSA: Another multi-objective algorithm designed for effective optimization under complex conditions.

Overview of NSGA-II

Genetic algorithms (GAs) rank among the most widely used metaheuristic optimization methods and have been applied to a variety of domains. They belong to a group of computational intelligence techniques inspired by evolutionary principles, encoding potential solutions into chromosome-like structures. By employing several reproductive operators, such as crossover and mutation, GAs preserve key information within each chromosome while generating new candidate solutions.

To tackle multi-objective optimization challenges, GAs require a vector-based ranking system to identify effective solutions. One of the most prominent vector ranking methods combined with GAs is non-dominated sorting. Introduced by Srinivas and Deb, this approach—referred to as NSGA—applies non-dominated sorting to address multi-objective problems.

However, NSGA faces three main drawbacks:

The non-dominated sorting procedure is time-consuming and computationally expensive.
Determining appropriate sharing parameters is challenging.
The lack of elitism can result in the loss of high-quality solutions once they have been found.

To overcome these limitations, Deb developed NSGA-II. The principal steps of NSGA-II are outlined in the following algorithm.

During the crossover stage, the genes from parent chromosomes are selected to create new offspring. The simplest approach involves choosing a crossover point at random. Without any modifications, the chromosome values before and after this point are directly passed on to the offspring, while the values in between the chosen points are swapped between the corresponding parents to produce the new solutions.

# 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

Overview of AMOSA

Bandyopadhyay introduced a multi-objective optimization technique grounded in simulated annealing, known as AMOSA. This method employs an archive structure to produce a set of compromise solutions. The authors devised an innovative procedure that factors in the dominance status to determine the probability of retaining a newly generated candidate solution. The pseudocode for the adapted AMOSA is presented in Algorithm 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: An exact method designed to help identify the set of efficient solutions (Pareto frontier) for multi-objective problems.

lbk denotes the lower bound of the k-th objective, rk represents the range of the k-th objective, gk indicates the number of intervals for the k-th objective, and sk is the slack variable associated with the k-th objective. The parameter EPS is a very small number, generally chosen within the interval (10⁻⁶, 10⁻³), and F stands for the feasible region. At each iteration of the algorithm, the bypass coefficients bi = int(si / stepi) are computed.

If si ≥ stepi, then the subsequent iteration for bi', where ei' = si - stepi, would yield the same solution. Since si' = si - stepi, that iteration can be considered redundant. In other words, the bypass coefficient bi dictates how many iterations should be skipped.

During each iteration of the main loop, the algorithm maintains a flag matrix, flag[(g2 + 1) × (g3 + 1) × ... × (gp + 1)]. Initially, this matrix is set to zero. The algorithm checks the matrix entry before conducting any optimization: if the current entry is zero, it proceeds with the optimization; if not, it skips the number of iterations specified by the nonzero value in the matrix for the innermost loop.

Simple Example Using an Open Source Solver

Problem Description

Objective: Minimize the total number of worker-days used.

Workers:

Permanent Workers: Full-time employees with restrictions on consecutive working days.
Temporary Workers: Hired as needed, with no restrictions on consecutive working days.

Demands:

Daily variation in the demand for workers.
Need to meet the demand for each operational day.

Constraints:

Each worker can work a maximum of one shift per day.
Permanent workers cannot work more than 7 consecutive days.
Limits on hours worked per day and per week.

Modeling in Python

Here, we use the model directly to solve the problem, as we are dealing with a small number of workers.

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)

Output:

These results show that the model always used all 5 permanent workers for the maximum allowed consecutive days. When it was necessary to collectively give them a break (to avoid exceeding the 7-day consecutive work limit), it heavily relied on temporary workers during that rest day. This resulted in a pattern where many temporary workers were required on certain days (e.g., Day 7) and few or none on others, meeting demand but in a concentrated and less realistic way from an operational perspective.

Below is an example of Python + Pyomo code similar to the previous one, but forcing a more realistic scheduling approach. To achieve this, we added constraints assigning specific rest days for each permanent worker (instead of allowing the solver to decide freely, which previously led to all workers taking the same day off). With these constraints, each worker has a staggered rest day, preventing all permanent workers from needing to rest simultaneously.

Worker 1 rests on Day 4
Worker 2 rests on Day 5
Worker 3 rests on Day 6
Worker 4 rests on Day 7
Worker 5 rests on Day 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)

Output:

Referências:

XU, Karl; DU PREEZ, Johan; DAVARI, Hossein. Towards the digital twin: a semi-automatic approach for point cloud-based factory modelling. 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. Optimization of Worker Scheduling at Logistics Depots Using Genetic Algorithms and Simulated Annealing. 2024. Disponível em: https://arxiv.org/pdf/2405.11729.

#Workforce scheduling optimization

Blog

About

Forum

Contact

Dec 8, 2024