Uma abordagem multiobjetivo para o problema de sequenciamento e alocação de trabalhadores
1 Introdução
O mercado mundial está cada vez mais competitivo
e exigente. Além disso, as crises mundiais e a ameaça
de uma recessão na Europa ameaçam a saúde
financeira das empresas. Diante desse cenário, as
empresas necessitam reduzir o seu custo produtivo.
Uma forma de reduzir este custo é pelo uso otimizado
dos fatores de produção. Entre os diversos fatores de
produção, um dos que possuem maior impacto nos
custos produtivos é a mão de obra. Isto se deve aos
recentes aumentos dos salários acima da inflação,
adicionados aos encargos sociais e benefícios. Logo,
as empresas procuram a redução do número de
funcionários sem afetar os prazos de entrega.
Esse problema enfrentado pelas empresas é
conhecido como o problema de sequenciamento com
alocação de trabalhadores (scheduling problem with
worker allocation – SPWA). O problema consiste em
alocar as tarefas aos trabalhadores de uma empresa,
minimizando o instante de término da última tarefa
executada (makespan) e o número de funcionários
utilizados.
Em geral, a maioria dos trabalhos encontrados na
literatura, trata esse problema como um problema
monobjetivo. Isto significa que a função de avaliação
multiobjetivo é transformada em uma função
de avaliação monobjetivo. Essa transformação,
geralmente, é feita atribuindo diferentes pesos aos
diferentes objetivos. Trabalhos como o de Abensur
(2012) utilizam esta abordagem. Ele utilizou a
programação por metas para tratar um problema
de otimização multiobjetivo. Dessa forma, ele
converteu os múltiplos objetivos em um único.
Porém, os objetivos são conflitantes entre si,
ou seja, não existe uma solução única que otimize
todas elas ao mesmo tempo. De fato, quanto menor
o número de funcionários, maior o tempo necessário
para executar todas as tarefas, o contrário também
é verdade. Logo, adotando o método de resolução
monobjetivo, temos apenas uma única solução, que
privilegia um objetivo em detrimento do outro.
Além disso, na prática, os gestores responsáveis
pela designação dos trabalhadores e sequenciamento
das tarefas, convivem, diariamente, com a mudança
no número de funcionários disponíveis e de tarefas
que precisam ser executas. Por isso, os gestores
necessitam de uma solução flexível. Ela deve ser
capaz de absorver as repentinas mudanças nos
parâmetros de forma rápida, mantendo o sistema
otimizado.
A otimização multiobjetivo, busca um conjunto
de soluções eficientes, o que torna o sistema mais
flexível, uma vez que ele apresenta soluções
diferentes. O gestor, ao resolver o problema,
adotando este método, tem à sua disposição diversas
soluções, cada uma utilizando um número diferente
de funcionários. As soluções disponíveis, obtidas
pelo método multiobjetivo, estão mais próximas da
realidade, tornando a tarefa do gestor mais rápida
e flexível. Ou seja, ele consegue responder à falta
de um funcionário sem precisar resolver o modelo
novamente, economizando tempo.
Para a resolução de problemas multiobjetivos, os
métodos variam entre métodos exatos e heurísticos.
Para a abordagem exata, tem-se a certeza de uma
solução ótima, mas, para problemas complexos,
geralmente o tempo despendido é superior ao tempo
disponível para a tomada de decisão. A utilização
de métodos heurísticos é recomendada quando
é procurada uma boa solução em tempo hábil.
Entretanto, esse método não garante a otimalidade
da solução para o problema. A partir dessas
observações feitas no setor industrial e de serviços,
principalmente em pequenas e médias empresas,
observamos que, geralmente, estas empresas
possuem um número de funcionários e tarefas
reduzido. Logo, este trabalho propõe uma abordagem
de resolução multiobjetivo para o SPWA, utilizando
métodos exatos e heurísticos. Estes devem gerar
soluções flexíveis que possam ser implementadas.
Entre os diversos métodos exatos para a resolução
de um problema multiobjetivo, este trabalho foca os
modelos de Programação Matemática utilizando o
método de peso variável e o método épsilon-restrito
(e-restrito). Pois, segundo Coello et al. (2002), estes
métodos são os mais utilizados. Além disso, segundo,
Tan et al. (2009), o SPWA é um problema NP-difícil,
ou seja, para problemas com dimensões maiores, não
é possível encontrar a solução ótima global em tempo
computacional hábil. Logo, um modelo heurístico
multiobjetivo baseado no algoritmo Variable
Neighborhood Search – VNS também é proposto.
O presente trabalho está organizado como
segue. Na seção 2, descreve-se o problema em
estudo. Na seção 3, o referencial teórico. Na seção
4, apresentam-se os modelos de Programação
Matemática utilizados. Na seção 5, é apresentado
o algoritmo VNS-Multiobjetivo proposto. As
apresentações dos problemas testes e dos resultados
são feitas na seção 6. A conclusão é apresentada na
seção 7.
2 O problema de sequenciamento com alocação de trabalhadores
O problema de sequenciamento com alocação
de trabalhadores também é conhecido como
scheduling problem with worker allocation (SPWA).
O problema é composto por um conjunto de
trabalhadores, Worker, e um conjunto de tarefas, Job.
Ele consiste em alocar as tarefas aos trabalhadores e
propor uma sequência de execução, respeitando as
restrições de qualificação. Ou seja, um trabalhador só
pode executar uma tarefa se ele for qualificado. Além
disso, cada trabalhador, para executar uma mesma
tarefa, necessita de tempos diferentes de acordo com
suas habilidades. O objetivo do SPWA é minimizar
o instante de término da última tarefa executada e
minimizar o número total de funcionários utilizados.
Neste trabalho, consideramos as seguintes
restrições: Todas as tarefas devem ser executadas.
Não consideramos o tempo de deslocamento
dos funcionários ou o tempo de espera em fila.
O horizonte de planejamento da alocação dos
trabalhadores é fixo. Cada tarefa é executada
por apenas um único funcionário. O excesso de
trabalho para os trabalhadores não é considerado,
ou seja, não consideramos que os trabalhadores
ficarão sobrecarregados com excesso de trabalho.
Todas as tarefas têm o mesmo nível de esforço.
Os trabalhadores, que são utilizados, possuem
uma taxa de utilização máxima e mínima. Todos
os funcionários possuem o mesmo custo (salário).
Cada colaborador possui uma habilidade diferente,
ou seja, cada um executa a mesma tarefa com um
tempo diferente.
O SPWA pode ser considerado como um caso
especial do problema de job shop scheduling. Tal
problema, em sua forma mais geral, é caracterizado
pela alocação de tarefas a algum tipo de recurso
necessário para sua execução. Este recurso
geralmente é uma estação de trabalho ou algum
tipo de máquina.
Na literatura, diversos trabalhos tratam do
problema job shop scheduling, tais como, Silva &
Rentes (2012), Tavares Neto & Godinho Filho (2013)
e Mello & Ferreira (2014).
O trabalho de Silva & Rentes (2012) apresenta um
novo modelo de otimização do problema job shop
por meio da otimização do arranjo físico e o aplica
em algumas empresas do setor metal mecânico.
O objetivo do modelo consiste em desenvolver
alternativas que estejam em harmonia com conceitos
e princípios da filosofia de produção enxuta.
Tavares Neto & Godinho Filho (2013) utilizam
um método formado por dois estágios para tratar
do job shop em um ambiente de uma máquina com
possibilidade de terceirização. No primeiro estágio,
propõe-se que as tarefas sejam sequenciadas,
utilizando-se a regra SPT (Shortest Processing
Time). No segundo estágio, é proposto um algoritmo
baseado em ACO (Ant Colony Optimization).
Mello & Ferreira (2014) abordam o problema
job shop, com a minimização do makespan. Eles
utilizaram modelos de simulação computacional
de um sistema de manufatura com dois cenários
diferentes. No primeiro, eles não consideram a
utilização de máquinas alternativas, no segundo,
eles adotam a inserção de máquinas alternativas para
executar as mesmas tarefas.
Segundo Osawa & Ida (2007), a principal
diferença entre o SPWA e o job shop clássico, é a
utilização do recurso mão de obra, considerando
diferentes níveis de qualificação e uma baixa
taxa de utilização. Esta baixa taxa de utilização
pode ser atribuída à queda de rendimento devido
ao cansaço, às condições ambientais do local de
trabalho (temperatura e iluminação, por exemplo),
além das leis trabalhistas que garantem o direito
do trabalhador ao descanso durante a jornada de
trabalho.
Na literatura, encontramos alguns trabalhos
que abordam o SPWA. Iima & Sannomiya (2001)
propuseram uma heurística para resolução do SPWA
fundamentada no Algoritmo Genético chamada
Module Type Genetic Algorithm (MTGA). Osawa
& Ida (2005) utilizaram um Algoritmo Genético,
porém propuseram um novo método de seleção
da população sobrevivente. Osawa & Ida (2007)
adotaram o algoritmo proposto por Osawa & Ida
(2005). Entretanto, eles consideraram que cada
trabalhador possui um nível de habilidade diferente
para cada máquina utilizada.
Todos os trabalhos citados anteriormente
adotaram abordagens mono-objetivas. Entretanto,
encontramos na literatura, diversos trabalhos que
adotaram métodos multiobjetivos, em sua maioria,
utilizando meta-heurísticas para a resolução do
problema job shop.
Ishibushi & Murata (1998) propuseram um
Algoritmo Genético de busca local. Este consiste na
inserção de soluções não dominadas na população
(conjunto de soluções) a partir do método proposto,
buscando uma população mais adaptada. Suresh &
Mohanasundaram (2004) propuseram um algoritmo
multiobjetivo, ao qual chamaram de Pareto Archived
Simulated Annealing (PASA). Neste algoritmo,
foi utilizado um novo método de perturbação das
soluções para encontrar soluções vizinhas, chamado
Segment-Randon Service (SRI).
Garcia et al. (2004) adotaram um método
heurístico e um exato. O método heurístico é
baseado em um algoritmo evolutivo multiobjetivo.
O modelo de programação matemática é não linear
e o método de resolução utilizado é o épsilon-restrito. Seus resultados mostraram que ambas
as técnicas alcançaram soluções similares e são
capazes de evitar ótimos locais. Iima (2005) propôs
um Algoritmo Genético com uma nova forma de
seleção da população mais adaptada e um novo
operador de mutação baseados em distribuições
de probabilidade. Lei & Wu (2005) utilizaram
um algoritmo evolutivo multiobjetivo (CMOEA).
Este é baseado na crowding mesure, ou distância
de multidão. Ele faz uso da distância de multidão
para ajustar a população externa e atribuir aptidão
diferente para as pessoas. Eles consideraram dois
objetivos, minimizar o makespan e o atraso total da
data de entrega.
Xia & Wu (2005) utilizaram um algoritmo
evolutivo baseado na otimização por enxame de
partícula. Tal algoritmo imita o comportamento
de pássaros voando e seus meios de troca de
informações. Ele combina tal algoritmo com a
busca local, utilizando o algoritmo Simulated
Annealing. Quian et al. (2006) desenvolveram um
algoritmo baseado no Algoritmo Memético com
base em evolução diferencial chamado MADE.
Neste algoritmo, primeiro, uma regra é utilizada
para converter o problema de modo que a evolução
diferencial possa ser aplicada. Em segundo lugar,
um mecanismo de evolução paralela é aplicado
para explorar a vizinhança, executando uma busca
local. Além disso, o conceito de dominância de
Pareto é utilizado para seleção das soluções. Eles
consideraram como objetivos minimizar o atraso
máximo.
Li et al. (2010) desenvolveram um método híbrido
multiobjetivo que combina duas meta-heurísticas,
Busca Tabu e Variable Neighborhood Search
(VNS). Este trabalho propõe um algoritmo híbrido
de Busca Tabu (HTSA) considerando três objetivos
de minimização: o tempo máximo de conclusão
(makespan), a carga horária total do equipamento
e da carga de trabalho da máquina. A estrutura
de vizinhança proposta combina dois critérios de
adaptação, uma para o método de busca local, outra
para a seleção das máquinas. Em seguida, um método
de designação de tarefas é executado. Além disso, um
algoritmo VNS é utilizado adotando três estruturas
de vizinhanças.
Ruiz et al. (2012) basearam-se em um
Algoritmo Genético Multiobjetivo chamado Elitist
Non-Dominated Sorting Genetic Algorithm (NSGA-II). Eles consideraram três objetivos: minimizar o
makespan, o custo de energia e acidentes de trabalho.
3 Referencial teórico
O SPWA é composto por dois objetivos conflitantes
(minimizar o número de funcionários e o instante
de término da última tarefa executada). Assim,
não existe uma solução única que otimize todas
elas ao mesmo tempo. Em vista disso, encontrar
soluções viáveis que otimizem simultaneamente
todos os objetivos é o maior desafio da otimização
multiobjetivo.
Para autores como Zitzler (1999), Fonseca &
Fleming (1995) e Arroyo (2002), para a resolução
de problemas dessa natureza deve-se, assim, buscar
um conjunto de soluções eficientes. Neste caso,
a tomada de decisão será de responsabilidade do
gestor, que poderá escolher a solução que melhor se
adapta às necessidades dentre as soluções eficientes.
Este critério será utilizado pelo responsável, ou
gestor, para a tomada de decisão, ou seja, ele poderá
ponderar entre as diferentes soluções conflitantes.
O conjunto de soluções eficientes também
é conhecido como soluções Pareto-ótimas. Por
definição, um conjunto de soluções S é Pareto-ótimo
se não existe outro conjunto de soluções viáveis
S* que possa melhorar algum objetivo sem causar
uma piora em pelo menos outro objetivo. Em outras
palavras, uma solução s pertence ao conjunto de
soluções Pareto-ótimo S se não existe solução s*
que domine s.
Considerando um problema de minimização,
temos:
• s domina s* se, e somente se, s = s* para todos
os objetivos;
• s e s* são indiferentes ou possuem o mesmo
grau de dominância se, e somente se, s não
domina s* e s* não domina s.
Para os problemas multiobjetivos, os métodos
convencionais de otimização monobjetivo não são
eficientes (COELLO et al., 2002). Portanto, a busca
por novos métodos de otimização que consigam
vencer o grande desafio deste tipo de problema
tornou-se necessária. Uma forma de vencer este
desafio é a utilização dos métodos exatos de
otimização multiobjetivo. Estes métodos surgiram da
necessidade de encontrar soluções com prioridades,
ou pesos, associados aos objetivos. Entre os métodos
exatos clássicos utilizados, para resolver esta
gama de problemas destacamos: Método da soma
ponderada e Método épsilon-restrito (e-restrito).
O método da soma ponderada consiste na
transformação do problema multiobjetivo em um
problema monobjetivo por meio da atribuição de
pesos para cada objetivo. Para se alcançar as soluções
Pareto-ótimas, este problema deve ser resolvido
iterativamente. Ou seja, a cada iteração, novos
pesos são atribuídos aos diferentes objetivos. Sendo,
geralmente, a soma dos pesos igual a 1.
Segundo Arroyo (2002), a principal desvantagem
deste método é que ele não consegue gerar todas as
soluções Pareto-ótimas quando o espaço objetivo
é não convexo. O método de programação por
metas, semelhante ao método da soma ponderada,
também consiste na transformação do problema
multiobjetivo em um problema monobjetivo. Isto se
dá pela atribuição de pesos para cada objetivo. Para
esse método, considera-se que cada meta possui uma
importância diferente na otimização representada por
meio de pesos. Quanto maior a importância da meta,
maior será o seu peso.
O método exato épsilon-restrito foi inicialmente
proposto por Ritzel et al. (1994). Ele consiste
na otimização do objetivo mais importante,
representado pela Equação 1, sujeitando-se às
restrições dos outros objetivos, representadas pela
Equação 2.
Considerando, em um problema de minimização,
f1 como sendo o objetivo mais importante, temos:
minimizar
Sujeito a:
<formula/>
no qual, ei é o limite superior do objetivo i e q o
número de objetivos.
Para construir o conjunto Pareto-ótimo, mesmo
quando o espaço objetivo é não convexo, deve-se
apenas variar o limite superior. Porém, se este
limite não é adequado, o subconjunto de possíveis
soluções obtido pode ser vazio, ou seja, não existe
solução viável.
Outra forma de resolver problemas multiobjetivos
é por métodos heurísticos. Entre os inúmeros
trabalhos relacionados à abordagem heurística
multiobjetivo, destacam-se, como os mais utilizados,
os Algoritmos Genéticos, os quais são baseados
na teoria da evolução. Nos Algoritmos Genéticos
Multiobjetivos, a cada geração, ou iteração, tem-se
um conjunto de indivíduos, ou soluções-pais. Para
gerar uma nova população (soluções-filho), os
operadores genéticos (tais como recombinação e
mutação) são aplicados sobre as soluções-pai. Dessa
forma, obtêm-se uma nova população de soluções
formada pelas soluções-pai e soluções-filho. No
final de cada iteração, os indivíduos mais aptos
sobrevivem e o restante é descartado. Entre os
inúmeros Algoritmos Genéticos Multiobjetivos,
destacamos: VEGA, MOGA, NPGA, SPEA e
NSGA.
No Vector Evaluated Genetic Algorithm (VEGA),
proposto por Schaffer (1985), a cada geração, um
grupo de indivíduos que supera os demais de acordo
com um dos n objetivos é selecionado, até que n
grupos sejam formados. Então os n grupos são
misturados conjuntamente e os operadores genéticos
são aplicados para formar a próxima geração.
No Multiobjective Genetic Algorithm (MOGA),
proposto por Fonseca & Fleming (1993), cada
indivíduo i é classificado em um nível de acordo
com o número de indivíduos que esse indivíduo i
domina. Todos os indivíduos não dominados são
classificados no nível 1. A aptidão de cada indivíduo
é atribuída de acordo com uma interpolação entre
o melhor e o pior nível. A aptidão final atribuída a
todos os indivíduos de um mesmo nível é a mesma
e igual à média da aptidão do próprio nível. Dessa
forma, todos os indivíduos do mesmo nível são
indiferentes entre si.
No Niche Pareto Genetic Algorithm (NPGA),
proposto por Horn et al. (1994), a seleção dos
indivíduos se dá por meio de um torneio baseado no
conceito de dominância de Pareto. Dois indivíduos
são selecionados e comparados com um subconjunto
da população de soluções, sendo selecionado para
a próxima geração aquele que não for dominado.
No algoritmo Non-dominated Sorting Genetic
Algorithm (NSGA), proposto por Srivivas & Deb
(1995), os indivíduos são classificados em níveis de
acordo com seu grau de dominância, tal como nos
algoritmos anteriores. Entretanto, é atribuído um
valor de aptidão a cada indivíduo de acordo com seu
nível e sua distância em relação às outras soluções
do mesmo nível, a chamada distância de multidão. A
seleção é feita por meio de torneios utilizando o valor
de aptidão até que todas as vagas para a próxima
geração sejam preenchidas.
No algoritmo Strength Pareto Evolutionary
Algorithm (SPEA) proposto por Zitzler (1999), é
utilizada a seleção baseada na relação de dominância
para avaliar e selecionar as soluções. Para avaliar
essa relação de dominância e classificar os indivíduos
em níveis de dominância, o SPEA usa um conjunto
adicional da população. Porém, ao contrário
dos algoritmos anteriores, os quais descartam
os indivíduos não selecionados, ele utiliza os
indivíduos não dominados da população da geração
anterior para determinar a aptidão dos indivíduos da
população corrente.
Apesar de serem os mais utilizados, os Algoritmos
Genéticos nem sempre são os mais recomendados
(GUIMARÃES et al., 2007). Além destes, também
encontramos outras heurísticas para problemas
Multiobjetivos, tais como o procedimento Busca
Tabu Multiobjetivo (BTM) proposto por Arroyo
(2002). Além da heurística Busca Tabu, inicialmente
proposta para problemas mono-objetivos, outras
também podem ser utilizadas tais como os métodos
heurísticos VNS e Variable Neighborhood Descent
(VND).
O método heurístico VNS, exemplificado pelo
Quadro 1, proposto por Mladenovic & Hansen
(1997), é um método que consiste em explorar o
espaço de soluções por meio de trocas sistemáticas
das estruturas de vizinhança. Contrariamente às
outras meta-heurísticas baseadas em métodos de
busca local, o método VNS não segue uma trajetória.
Ele explora vizinhanças diferentes da solução
corrente e focaliza a busca em torno de uma nova
solução se e somente se um movimento de melhora
é realizado.
O VNS também inclui um procedimento de
busca local a ser aplicado sobre a solução corrente.
No presente trabalho, adotou-se o método VND,
exemplificado pelo Quadro 2 para fazer a busca local,
também utilizado pelo VNS original.
O VND é uma técnica usada para o refinamento de
soluções iniciais. Isto é feito pela análise da região de
soluções factíveis por meio de trocas sistemáticas nas
estruturas da vizinhança de uma solução corrente.
Este método aceita apenas as soluções de melhora
da solução corrente, retornando à primeira estrutura
quando uma solução melhor é encontrada.
Entre os inúmeros VNS aplicados à otimização
multiobjetivo, destacamos Geiger (2004),
denominado MOVNS. Neste procedimento, a
estrutura de vizinhança e a solução a ser explorada
são escolhidas de forma aleatória, mudando a
cada iteração. Uma solução, entre as soluções não
dominadas, é selecionada. A partir desta solução,
novas soluções vizinhas são geradas.
Quadro 1. Heurística VNS.
Em Ottoni et al. (2011), os autores tratam o
problema job shop scheduling em que n tarefas
devem ser processadas em uma única máquina,
que pode processar uma tarefa de cada vez. Eles
propuseram a incorporação de um novo método de
intensificação ao algoritmo MOVNS, proposto por
Geiger (2004). Esta intensificação consiste em uma
perturbação na solução, gerando novas soluções.
Arroyo et al. (2011) também tratam do problema
job shop scheduling, considerando uma máquina
com janelas de tempo com tempo de preparação de
máquina. Os autores consideraram dois objetivos,
o primeiro é minimizar os atrasos e adiantamentos
das tarefas, e o segundo é minimizar o fluxo total.
Para resolver o problema, foi proposto um novo
algoritmo MOVNS combinado com um processo de
perturbação, diferente do proposto por Ottoni et al.
(2011).
4 Modelos de programação matemática
4.1 Método épsilon-restrito
Para a resolução do SPWA utilizando o método
épsilon-restrito, adotamos como objetivo principal
o instante de término da última tarefa executada.
O número de funcionários é tido como objetivo
secundário, por isso, a cada execução do modelo
matemático proposto, o número máximo de
funcionários que pode ser utilizado (e) é reduzido.
Para este modelo, consideramos os seguintes
parâmetros de entrada:
Job : Conjunto de tarefas.
Worker : Conjunto de trabalhadores.
Tij : Tempo necessário para o funcionário j executar a tarefa i.
e : Número máximo de trabalhadores.
H : Horizonte de planejamento.
Tui : Taxa de utilização máxima do trabalhador i.
Tli : Taxa de utilização mínima do trabalhador i.
Sejam as seguintes variáveis de decisão:
s : Instante de término da última tarefa executada.
xij : 1 se o funcionário executa a tarefa .
0casocontrário.
yi : 1 se o funcionário éutilizado.
0casocontrário.
O modelo de programação matemática proposto
relativo ao SPWA é apresentado pelas Equações 3
a 10:
Função Objetivo:
A Equação 3 visa minimizar o instante de término
da última tarefa.
<equação>
Sujeito às restrições:
A Equação 4 garante que toda tarefa j será
executada apenas uma vez por um único trabalhador i.
<equação>
A Equação 5 estipula o número máximo de
trabalhadores i que podem ser utilizados. O valor
de e é reduzido a cada iteração do modelo proposto.
<equação>
A Equação 6 determina o instante de término da
última tarefa j executada pelo operador i.
<equação>
A Equação 7 define se o trabalhador i está
executando alguma tarefa j.
<equação>
As Equações 8 e 9 definem o intervalo para a taxa
de utilização trabalhador i que está sendo utilizado.
<equação>
<equação>
As Equações 10 a 12 asseguram o domínio das
variáveis de decisão.
<equação>
<equação>
<equação>
Quadro 2. Heurística VND.
4.2 Método das somas ponderadas
Para a resolução do SPWA, utilizando o método
das somas ponderadas, adotamos como objetivos
o instante de término da última tarefa executada
(makespan) e o número de funcionários utilizados.
Neste método, a cada iteração k, o valor da penalidade
(wk) da função objetivo é alterado. Inicialmente ele
assume o valor 1, e a cada iteração, seu valor é
decrescido segundo a Equação 13. Nesta equação, a
cada iteração, o novo valor de wk é igual ao valor da
penalidade da iteração anterior, wk–1, menos o valor
da divisão de 1 pelo número de soluções adotado.
Dessa forma, a cada iteração, altera-se o espaço de
busca privilegiando algum objetivo.
<equação>
Sendo:
wk: Penalidade da função objetivo na iteração k.
NSol : Número de soluções.
As variáveis de decisão e os parâmetros são os
mesmos do modelo anterior, exceto pela retirada
do parâmetro (número máximo de trabalhadores)
e pela inclusão do parâmetro w (penalidade do
objetivo). O modelo de programação matemática
proposto, para o método das somas ponderadas,
é semelhante ao método da seção 4.1, porém eles
diferem pela substituição da Equação 3, referente à
função objetivo, pela Equação 14 e pela exclusão da
restrição representada pela Equação 5.
Função Objetivo
A Equação 14 visa minimizar o instante de
término da última tarefa.
<equação>
5 Algoritmo proposto
Para uma gama de problemas, encontrar a solução
ótima global de problemas de grande dimensão pode
ser inviável. Para problemas desta natureza, como
o SPWA, o uso de métodos exatos se torna bastante
restrito. Este é o motivo pelo qual inúmeros trabalhos
concentram esforços na utilização de heurísticas para
solucionar problemas desse nível de complexidade.
Heurísticas podem ser definidas como sendo uma
técnica que procura boas soluções, ou seja, próximas
do ótimo global.
Logo, também apresentamos um modelo
heurístico multiobjetivo baseado no algoritmo VNS
exemplificado pelo Quadro 1 na seção 3.
O algoritmo proposto chamado de
VNS-Multiobjetivo (VNSM), exemplificado pelo
Quadro 3, começa sua execução partindo de um
conjunto de soluções iniciais S0. Este conjunto é
gerado por meio de um procedimento parcialmente
guloso, utilizando um torneio binário. O número
de soluções (NSol) do conjunto S0 foi definido de
forma empírica, considerando a complexidade do
problema.
Depois desse passo, cada solução sl . S0 é
avaliada segundo uma função de avaliação com
pesos variáveis. O valor do peso de cada objetivo
varia a cada iteração, dessa forma, a cada iteração
um objetivo possui maior ou menor importância para
determinar uma solução.
Em seguida, a primeira solução, s1, do conjunto
S0 é selecionada e seleciona-se aleatoriamente um
vizinho s1’ dentro da vizinhança N(1)(s1) da solução
s1 corrente. Esse vizinho s1’ é então submetido a um
procedimento de busca local retornando à solução
s1’’. Se a solução ótima local, s1’’, for melhor que
a solução s1 corrente, a busca continua de s1’’,
recomeçando da primeira estrutura de vizinhança
N(1)(s1’’).
Caso contrário, continua-se a busca a partir da
próxima estrutura de vizinhança N(k+1)(sl). Esta
etapa é repetida até que se obtenha um número
máximo de iterações sem melhora, It_SM, definido
empiricamente. Ao final desta etapa, a melhor
solução encontrada é adicionada ao conjunto de
soluções finais S.
Quadro 3. Heurística VNS-Multiobjetivo.
Depois do final da etapa anterior, o procedimento
retorna ao seu início, selecionando a próxima solução
sl do conjunto S0 e repete-se todo o procedimento
anterior. O algoritmo é repetido para todas as
soluções si do conjunto de soluções iniciais S0.
5.1 Representação de uma solução
Uma solução pode ser representada por uma
matriz (sl)[Worker×(Job+1)]. Dessa forma, os
movimentos das estruturas de vizinhança se tornam
mais simples e naturais. Assim, o algoritmo torna-se
menos complexo e a avaliação das soluções é
facilitada. O conjunto de soluções S é formado
pela união de todas as NSol (número de soluções)
matrizes sl.
A Tabela 1 exemplifica uma possível solução
sl. A primeira coluna apresenta os trabalhadores. A
coluna “Util” indica se o funcionário i realiza uma
tarefa j qualquer. As colunas “Tarefas” indicam as
tarefas alocadas a cada trabalhador e sua respectiva
sequência.
No exemplo da Tabela 1, o valor 1 da primeira
linha (Trabalhador 1) e coluna “Util” indica que o
funcionário 1 está sendo utilizado. Os valores das
outras colunas indicam que o funcionário 1 executará
as tarefas 1, 3 e 4, nesta ordem. O valor 0 na segunda
linha (Trabalhador 2), coluna “Util”, indica que o
trabalhador 2 está ocioso. Logo ele não executará
nenhuma tarefa. Para o trabalhador 4 temos que ele
executará as tarefas 2 e 5, nesta ordem.
5.2 Geração da solução inicial
A solução inicial gera NSol matrizes sl por meio
de um procedimento parcialmente guloso utilizando
um torneio binário. Para cada matriz solução sl,
a cada iteração do procedimento, uma tarefa j é
selecionada. Além disso, dois funcionários também
são escolhidos aleatoriamente. Aquele funcionário
que executar a tarefa j selecionada em menor
tempo é escolhido. Por exemplo, para a tarefa 1
são escolhidos os funcionários 2 e 4. O funcionário
2 executa a tarefa 1 em 3 horas e o funcionário 4
em 2 horas. Neste caso, a tarefa j será executa pelo
funcionário 4.
Este procedimento é executado até que todas as
tarefas sejam atribuídas a algum funcionário i para
todas as matrizes sl . S.
5.3 Avaliação de uma solução
Uma solução Sl . S é avaliada segundo a função
de avaliação f(sl). Esta função busca minimizar o
número de funcionários e o makespan por meio
de penalidades. A função de avaliação f(sl) é
exemplificada pela Equação 15.
<formula/>
Sendo:
wl: Penalidade da solução sl.
s : makespan.
t : Número de trabalhadores utilizado.
Ds : Fator de correção para o parâmetro s.
Dt : Fator de correção para o parâmetro t.
O valor de wl é alterado a cada iteração do
algoritmo VNSM para cada solução sl avaliada.
Inicialmente ele assume o valor 1, e a cada iteração,
para cada solução sl, seu valor é decrescido segundo
a Equação 16. Nesta equação, a cada iteração, o novo
valor de sl é igual ao valor da penalidade da iteração
anterior, wl-1, menos o valor da divisão de 1 pelo
número de soluções adotado. Dessa forma, a cada
iteração, altera-se o espaço de busca privilegiando
algum objetivo.
<formula/>
Na função de avaliação, Equação 16, também
adotamos fatores de correção, D. Estes fatores
garantem que as varáveis de decisão t e s estejam
dentro da mesma ordem de grandeza.
5.4 Estruturas de vizinhança
Para explorar o espaço de soluções do problema,
ou seja, para encontrar uma solução sl’, dita vizinha
de sl, foram utilizados dois movimentos apresentados
a seguir:
Movimento Realoca Tarefa, NRT(sl): Este
movimento consiste em escolher aleatoriamente um
trabalhador i que está sendo utilizado. Em seguida, a
última tarefa j é selecionada e realocada para outro
trabalhador escolhido aleatoriamente. Na Tabela 2,
o trabalhador 1 é selecionado e a tarefa 4 é realocada
para o trabalhador 4.
Tabela 1. Representação de uma solução sl.
Movimento Trabalhador, NT(sl): Este movimento
consiste em escolher aleatoriamente um trabalhador
i que está sendo utilizado e realocar todas as suas
tarefas para os demais trabalhadores, aleatoriamente.
Na Tabela 3, o trabalhador 1 é selecionado, a tarefa
3 é realocada para o trabalhador 4 e a tarefa 1 é
realocada para o trabalhador 2.
5.5 Busca local
A busca local é aplicada a todas as soluções
sl . S. Ela consiste na aplicação do VND (vide
Quadro 3). Inicialmente, considera-se um conjunto
de r = 2 vizinhanças distintas, cada qual definida
por um dos tipos de movimentos definidos na seção
5.4. Na sequência, a partir de uma solução sl’, um
determinado número de vizinhos sl’’ da primeira
vizinhança é analisado.
Em seguida, parte-se para a segunda estrutura de
vizinhança. Novamente, um determinado número de
vizinhos é analisado. O vizinho sl’’ que apresentar
maior melhora, em relação à sl’, segundo a função
de avaliação da seção 5.3, é escolhido, e encerra-se
a busca local.
6 Resultados
Para testar os modelos propostos, foram utilizados
4 problemas testes, que podem ser encontrados
em <http://www.4shared.com/zip/m7xmUfpi/Instance_-_SPWA.html>. Eles diferem entre si pelo
número de trabalhadores e de tarefas. A Tabela 4
apresenta algumas características dos problemas. As
colunas Worker e Job mostram, respectivamente,
o número de trabalhadores e o número de tarefas que
precisam ser executadas.
Os modelos de programação matemática
desenvolvidos na Seção 4 foram implementados no
aplicativo de otimização LINGO 10.0, interfaceando
com planilhas do EXCEL 2010. O algoritmo VNSM
proposto foi desenvolvido na linguagem C, usando
o compilador C++ Builder 5.0 da Borland. Todos os
testes foram realizados em um PC Pentium Core 2
Duo, com 2,4 GHz e 4 GB de RAM sob plataforma
Windows 7.
6.1 Resultados do modelo exato
O conjunto de soluções S, Pareto-ótimas,
encontrado, utilizando o método e-restrito, para o
Problema 1, é apresentado na Tabela 5. A coluna
Épsilon apresenta o valor adotado para e, que
representa o número máximo de funcionários. A
coluna Worker apresenta o número de funcionários
utilizados. A coluna makespan apresenta, em
minutos, o instante de término da última tarefa.
De acordo com a Tabela 5, para o Problema
1, podemos observar que obtivemos os mesmos
resultados para os dois métodos exatos, ambos com
5 soluções diferentes cada. Na solução 1, adotamos
o valor e = 0. Utilizaremos 5 trabalhadores que
executarão todas as tarefas em 8 minutos. Para a
solução 5, adotamos o valor e = 4. Utilizaremos
1 trabalhador que executará todas as tarefas em
43 minutos.
Tabela 2. Movimento Realoca Tarefa, NRT(sl).
Tabela 3. Movimento Trabalhador, NT(sl).
A Tabela 6 apresenta o conjunto de soluções
Pareto-ótimas, utilizando o método e-restrito e
das somas ponderadas, respectivamente, para o
Problema 2. Neste problema adotamos 10 soluções
diferentes. O valor de e varia de 0 a 9 (número
máximo de funcionários disponíveis).
A Tabela 7 apresenta os resultados do modelo
exato para o Problema 3. O conjunto de soluções
Pareto-ótimas é formado por 7 soluções diferentes.
O valor de e varia de 0 a 14, sendo reduzido em duas
unidades para cada solução.
Os resultados do modelo exato, para o Problema
4, é apresentado na Tabela 8. Neste problema
adotamos 10 soluções diferentes. O valor de e varia
de 0 a 24, sendo reduzido em três unidades para
cada solução.
Para o Problema 4, ao contrário dos demais
problemas (1, 2 e 3), não se encontrou um conjunto
de soluções Pareto-ótimas. Isto se deve ao fato de o
problema SPWA ser NP-difícil (TAN et al., 2009).
Ou seja, para problemas com dimensões maiores,
não é possível encontrar a solução ótima global em
tempo computacional hábil. Neste caso, adotamos
como tempo máximo de execução 900 segundos
para cada solução gerada. Para ambos os métodos
exatos, somente para as soluções 1 e 10 (primeira e
última solução), conseguimos resolver o problema e
encontrar uma solução em menos de 900 segundos,
sendo: para o método épsilon-restrito, o tempo de
execução para a solução 1 de 41 segundos, e para a
solução 2 de 24 segundos; e para o método das somas
ponderadas, o tempo de execução para a solução 1
de 39 segundos, e para a solução 2 de 28 segundos.
Tabela 4. Características dos problemas testes.
Tabela 5. Resultado do Método Exato para o Problema 1.
Tabela 6. Resultados Método Exato para o Problema 2.
Tabela 7. Resultados Método Exato para o Problema 3.
Tabela 8. Resultados Método Exato para o Problema 4.
Tabela 9. Tempo de execução em segundos.
Figura 1. Resultados do VNSM.
6.2 Resultados do VNSM
Inicialmente o algoritmo proposto foi submetido
a uma bateria preliminar de testes para calibrar os
diversos parâmetros existentes. Tais parâmetros
são: o número de iterações de cada execução
(It_SM), número de soluções (NSol), a penalidade
da solução sl (wl) e o valor dos fatores de correção
(Ds e Dt). Depois da determinação dos parâmetros, o
algoritmo foi submetido a uma bateria de testes com
100 execuções para cada problema teste.
O gráfico da Figura 1 mostra os resultados obtidos
depois de 100 execuções do VNSM e dos métodos
exatos. O eixo das abscissas representa o tempo
total gasto para executar todas as tarefas. O eixo
das ordenadas representa o número de trabalhadores
utilizados. O gráfico apresenta o melhor conjunto de
soluções encontrado entre as execuções do VNSM.
Neste gráfico, notamos que, para o problema teste
1, o VNS e os dois métodos exatos (épsilon-restrito
e soma ponderada) obtiveram o mesmo resultado.
Para os outros problemas testes, observamos que os
resultados dos métodos exatos foram semelhantes e
que o VNS foi capaz de encontrar soluções próximas
às dos métodos exatos.
A Tabela 9 mostra o tempo gasto, em segundos,
pelos métodos utilizados para a resolução do
SPWA. Para os VNSM, na linha Menor, tem-se
o menor tempo gasto entre as 100 execuções. Na
linha Médio, mostra-se o tempo médio e, na linha,
Maior tem-se o Maior tempo gasto pelo algoritmo
proposto. Podemos observar que o método exato
das somas ponderadas, para todos os problemas,
obteve um desempenho melhor ou igual, que o
épsilon-restrito.
7 Conclusões
Este trabalho apresentou dois modelos
exatos de programação matemática e um
algoritmo multiobjetivo para a resolução do
problema de sequenciamento com alocação de
trabalhadores (scheduling problem with worker
allocation – SPWA).
Os modelos de programação matemática
propostos foram baseados em dois métodos
clássicos de resolução de problemas multiobjetivos:
o método de resolução multiobjetivo e-restrito,
que se baseia na otimização do objetivo mais
importante sujeitando-se às restrições dos outros
objetivos; e o método iterativo da soma ponderada,
que consiste na transformação do problema
multiobjetivo em um problema monobjetivo por
meio da atribuição de pesos para cada objetivo.
O algoritmo multiobjetivo proposto (VNSM) foi
baseado na heurística VNS combinada com o
algoritmo de busca local VND.
Os resultados mostram que é possível otimizar
o número de funcionários e o tempo máximo
de execução das tarefas utilizando a abordagem
multiobjetivo. Os dois métodos exatos obtiveram
resultados semelhantes, sendo que o método da
soma ponderada obteve melhor desempenho quanto
ao tempo computacional. O VNSM foi capaz de
encontrar soluções próximas às dos métodos exatos,
provando ser uma boa opção, principalmente para
problemas mais complexos.
Ao apresentar várias soluções atendendo a
diferentes objetivos, disponibilizam-se, ao gestor,
alternativas para sua tomada de decisão. Dessa
forma, é possível escolher a solução que melhor se
adapta à realidade operacional da empresa.