BrBRCEEn0104-530X2016000100132

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.