UM ALGORITMO HEURÍSTICO PARA OTIMIZAÇÃO DO … · o algoritmo utiliza um decodificador que preenche as lacunas da escala de modo que os custos sejam mínimos. Ohki, Morimoto e

UM ALGORITMO HEURÍSTICO PARA OTIMIZAÇÃO DO PROBLEMA DE ESCALONAMENTO DE ENFERMEIROS

Ademir Aparecido Constantino

Departamento de Informática Universidade Estadual de Maringá

Maringá-PR [email protected]

Everton Luiz de Melo

Universidade Estadual de Maringá [email protected]

Douglas Baroni Rizzato

Universidade Estadual de Maringá [email protected]

Wesley Romão

Departamento de Informática Universidade Estadual de Maringá

[email protected]

RESUMO O Problema de Escalonamento de Enfermeiros consiste em gerar escalas de trabalho para enfermeiros considerando as preferências pelos turnos, declaradas através de um custo para cada turno de cada dia da escala. As restrições envolvem regras impostas pela legislação trabalhista e características desejáveis em uma escala. Neste trabalho é proposto um novo algoritmo heurístico baseado na resolução de sucessivos Problemas de Atribuição. O método trata o problema como um Problema de Atribuição Multinível e trabalha em duas fases. Na primeira fase é construída uma solução inicial. Na segunda fase são aplicados dois procedimentos de melhoramento. Testes computacionais são realizados utilizando instâncias de uma base de dados de referência. Em geral, os resultados alcançados foram melhores em comparação com a literatura que utiliza a mesma base de dados. Além disso, os experimentos computacionais mostram que o algoritmo proposto é robusto e eficiente.

PALAVRAS-CHAVE: Problema do Escalonamento de Enfermeiros. Problema de Atribuição. Heurística. Otimização Combinatória.

ABSTRACT

The Nurse Scheduling Problem consists in generating work schedules for nurses considering the preference for shifts, declared by the association of a cost for each shift in each day of the schedule. The constraints involve rules imposed by labor laws and desirable characteristics on a schedule. A new heuristic algorithm based on the successive resolutions of the Assignment Problem is proposed in this work. The method treats the problem as a Multilevel Assignment Problem and works in two phases. In the first phase the algorithm constructs an initial solution. In the second phase two improvement procedures are applied. Computational tests are carried out using instances from a standard benchmark dataset. In general, the results were better when compared to results from works of the literature that use the same dataset. Furthermore, the computational experiments show that the proposed algorithm is robust and efficient.

KEYWORDS: Nurse Scheduling Problem. Assignment Problem. Heuristic. Combinatorial Optimization.

XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento Pág. 2783

1. O Problema de Escalonamento de Enfermeiros O Problema de Escalonamento de Enfermeiros (PEE), ou Nurse Scheduling Problem (NSP),

é classificado por Osogami e Imai (2000) como NP-Difícil. Ele consiste em elaborar escalas de trabalho para equipes de enfermeiros de modo que as preferências dos trabalhadores pelos turnos no decorrer dos dias sejam atendidas da melhor maneira possível. O problema envolve restrições rígidas e restrições flexíveis que devem ser observadas na elaboração de cada jornada. As restrições rígidas se relacionam a impedimentos impostos pela legislação trabalhista e as restrições flexíveis representam aspectos potencialmente desejáveis em uma jornada. Elas são descritas a seguir.

Restrições rígidas: Proibição do turno da tarde ser sucedido pelo turno da manhã; e Proibição do turno da noite ser sucedido pelo turno da manhã ou pelo turno da tarde.

Restrições flexíveis: Imposição de um mínimo de dias trabalhados no período; Imposição de um máximo de dias trabalhados no período; Imposição de um mínimo de atribuições consecutivas; Imposição de um máximo de atribuições consecutivas; Imposição de um mínimo de atribuições de um mesmo tipo de turno; Imposição de um máximo de atribuições de um mesmo tipo de turno; Imposição de um mínimo de atribuições consecutivas de um mesmo tipo de turno; e Imposição de um máximo de atribuições consecutivas de um mesmo tipo de turno.

As preferências dos enfermeiros são declaradas antecipadamente associando um custo a cada possibilidade de turno para cada dia da escala a ser elaborada. Cada não atendimento de uma restrição implica na inclusão de uma penalidade no custo total da solução. Dessa forma, o PEE é um problema de minimização dos custos associados às preferências e às penalidades.

Mais detalhadamente, o PEE pode ser definido como a necessidade de se escalonar um conjunto N de enfermeiros em um período D de dias designando, a cada um deles, uma jornada. Em cada um dos dias compreendidos pelo período D, os enfermeiros devem ser escalados para um dos S turnos possíveis. Assim, se tem:

N: Conjunto de enfermeiros, índice i (i=1, ..., n); D: Conjunto de dias do período de escalonamento, índice j (j=1, ..., d); S: Conjunto de turnos, índice k (k=1, ..., s). Nesse contexto, o termo turno se refere ao horário de trabalho, usualmente se enquadrando

em matutino, vespertino, noturno ou folga. Uma jornada equivale a uma seqüência de d turnos. Tarefa é a necessidade de haver um certo turno em um determinado dia da escala.

Uma maneira de resolver esse problema é elaborar os padrões das possíveis sequências de turnos para depois os atribuir aos enfermeiros, como em Maenhout e Vanhoucke (2007). O modelo matemático de tal abordagem segue:

Minimizar ∑∑= =

n

i

f

l

ilil

i

xp1 1

. (1)

Sujeito a: ,11

=∑=

if

l

ilx

ni ,...,1= (2)

,.1 1

jk

n

i

f

l

iljkl Cxai

∑∑= =

≥ skdj ,...,1,,...,1 == (3)

{ }1,0∈ilx (4)

Nesse modelo, pil representa o custo de atribuir o padrão l ao enfermeiro i; fi é o número de padrões possíveis ao enfermeiro i; Cjk é o número mínimo de enfermeiros exigidos no turno k do dia j; xil assume 1 se é feita a atribuição do padrão l ao enfermeiro i e 0, caso contrário; e ajkl

assume 1 se o padrão de turno l cobre o turno k no dia j e 0, caso contrário. A função-objetivo (1) minimiza o custo total. A restrição (2) garante que um único padrão de

turnos seja atribuído a cada enfermeiro. A restrição (3) assegura que, no mínimo, um número


previamente definido de trabalhadores seja escalado para cada um dos turnos de cada um dos dias. A restrição (4) exige que as variáveis envolvidas assumam apenas os valores 0 ou 1.

Para a resolução do PEE, Maenhout e Vanhoucke (2007) propõem o uso de uma metaheurística baseada na Lei de Coulomb denominada Eletromagnetic Meta-heuristic (EM). Essa metaheurística opera com diversas soluções distribuídas pelo espaço, sendo que cada uma exerce certas forças sobre as demais. A ideia é que soluções de alto custo, exercendo força de repulsão, evitem que as demais soluções efetuem buscas em regiões não promissoras. Além da EM, o algoritmo utiliza Busca Local (BL) para encontrar um padrão mais apropriado a um dado enfermeiro e para efetuar trocas de partes de padrões de turnos entre enfermeiros. Também usa BL e o método húngaro para readequar a distribuição dos turnos em um dado dia.

Um algoritmo que resolve o PEE se baseando em Busca Dispersa (BD) é apresentado por Maenhout e Vanhoucke (2006). O método envolve a geração de diversas soluções iniciais que são utilizadas em um processo de intensificação de busca, enquanto uma certa diversificação é mantida. Para isso, dois grupos de soluções são reservados. Um deles é composto pelas melhores soluções e o outro, por soluções que visam garantir a diversidade. Então, um método iterativo de geração, recombinação e melhoramento de soluções é empregado até que o critério de parada seja alcançado.

As recombinações trabalham com a alteração de soluções iniciais que são conduzidas por soluções guias. Para esse fim são executados movimentos envolvendo a vizinhança de um dia ou de um enfermeiro. O melhoramento é feito pelo uso de métodos de BL idênticos aos utilizados em Maenhout e Vanhoucke (2007). As soluções criadas são avaliadas e podem substituir membros no grupo das melhores soluções ou no grupo das soluções que propiciam diversificação.

Além desses, a literatura ainda apresenta diversos métodos para a resolução do PEE. Aickelin e Dowsland (2004) utilizam um Algoritmo Genético (AG) indireto para a obtenção de escalas factíveis ou com o mínimo de violações de restrições a partir de soluções incompletas. Para tanto, o algoritmo utiliza um decodificador que preenche as lacunas da escala de modo que os custos sejam mínimos. Ohki, Morimoto e Miyake (2006) apresentam um AG cooperativo que emprega um operador para evitar a estagnação em ótimos locais dos quais os operadores de cruzamento e mutação sozinhos não escapariam. Ohki, Uneme e Kawano (2008) fazem uso do mesmo princípio de AG cooperativo mas realizam o processamento paralelamente em diversas CPUs. O PEE é resolvido por Kawanaka et al. (2003) com um AG que evita a geração de soluções infactíveis no processo de cruzamento. A permuta de genes é realizada de modo que, apesar dos cromossomos filhos terem o máximo de características dos pais, os mesmos não incorporam as violações que seriam herdadas em um cruzamento sem tal tratamento. Tsai e Li (2008) resolvem o PEE com um AG de dois estágios. Primeiramente são criadas escalas que obedeçam à legislação trabalhista e à demanda exigida. Depois, o AG tenta encontrar a melhor escala para cada enfermeiro.

Na literatura também são encontrados trabalhos que empregam Busca Tabu (BT) para a elaboração de escalas de enfermeiros. Oughalime et al. (2008) alegam que devido à alta quantidade de restrições envolvidas no PEE, muitas metaheurísticas não são capazes de produzir soluções factíveis para o problema, o que não ocorre com a BT. O algoritmo implementado pelos autores executa movimentos explorando três vizinhanças distintas que envolvem alterações em jornadas, turnos vespertinos e padrões de turnos matutinos. Ferland et al. (2001) apresentam um algoritmo baseado em BT que trabalha com múltiplos objetivos e emprega métodos específicos para a diversificação da vizinhança de busca de soluções do PEE.

Um algoritmo Bayesiano é proposto por Li e Aickelin (2003). Ele parte de um grupo inicial de soluções promissoras e utiliza um conjunto de regras para chegar a novas soluções. Kundu e Acharyya (2008) modelam o PEE como um Problema de Satisfação Booleana (SAT) e aplicam um algoritmo que incorpora uma lista tabu para sua resolução. Tal método, conforme os autores, supera as performances de outros algoritmos baseados em AG e em Simulated Annealing (SA). Burke et al. (2008) utilizam um algoritmo híbrido que mescla um método de ordenação dos turnos com maior dificuldade estimada de escalonamento e Variable Neighbourhood Search


(VNS). Os resultados, comparados a um pacote comercial que emprega AG, são favoráveis à nova proposta. Bard e Purnomo (2005) utilizam geração de colunas na resolução do PEE ao abordarem o PEE como um Problema de Cobertura de Conjuntos (PCC). Na resolução é utilizada Programação Inteira (PI) mesclada com procedimentos heurísticos. Bellanti et al. (2004) trabalham com padrões de turnos semanais e empregam uma busca míope na vizinhança sem permitir soluções infactíveis.

2. Algoritmo Proposto

O PEE envolve a elaboração de jornadas de trabalho para um número definido de enfermeiros em um horizonte determinado em dias. Para cada trabalhador, um turno deve ser designado por dia. Sendo assim, a proposta deste trabalho é modelar o PEE como um Problema de Atribuição Multinível (PAM), no qual cada dia representa um nível do problema. Então, a solução é alcançada através de sucessivas resoluções do Problema de Atribuição (PA) envolvendo apenas dois níveis. Isso é feito efetuando cortes na escala que dividem cada uma das jornadas em duas partes que são recombinadas sob a menor soma total de custos.

O PA equivale ao emparelhamento perfeito de custo mínimo em um grafo bipartido. Assim, dada uma matriz de custos de dimensões n×n, o problema consiste em associar cada linha i a uma coluna j sob um custo cij, de modo que a soma dos custos seja a menor possível. Tal problema pode ser formulado da seguinte maneira:

Minimizar ∑∑= =

n

i

n

j

ijij xc1 1

. (5)

Sujeito a: ,11

=∑=

n

i

ijx nj ,...,1= (6)

,11

=∑=

n

j

ijx ni ,...,1= (7)

{ },1,0∈ijx njni ,...,1;,...,1 == (8)

A atribuição de uma linha i a uma coluna j faz com que xij assuma valor 1 ou que assuma 0, caso contrário. A função-objetivo (5) minimiza o custo da soma das atribuições entre linhas e colunas; a restrição (6) exige que para cada linha haja uma coluna associada; a restrição (7) garante que a cada coluna seja designada uma linha; a restrição (8) permite que as variáveis envolvidas assumam apenas o valor 0 ou 1.

O algoritmo trabalha em duas fases e ambas se baseiam em resoluções sucessivas de PAs de dois níveis. Na primeira fase uma solução inicial é construída. Na segunda fase procedimentos são empregados buscando o melhoramento da solução inicial. Para a resolução do problema foi implementado o algoritmo de Carpaneto e Toth (1987) que garante a obtenção da solução ótima para o PA e tem complexidade O(n3). Esse algoritmo combina o procedimento shortest

augmenting path com o método húngaro.

2.1. Fase Construtiva A fase construtiva consiste em gerar um grafo multipartido, onde cada jornada de trabalho

corresponde a um caminho da primeira à última camada. Considere o grafo G=(T,A), onde T é o conjunto de vértices, representando as tarefas, e A, o conjunto de arestas que representam a possibilidade de uma tarefa suceder outra no dia seguinte. Considere ainda que os vértices são dispostos em camadas, onde cada camada representa um dia da escala. Assim, o conjunto de vértices T é composto por subconjuntos de vértices, T1, T2,..., Td , sendo d o número de camadas, portanto, o número de dias de cada jornada.

A construção da solução inicial se faz pela resolução de um PA para cada dia, ou camada do PAM. Cada PA é definido pela matriz de custos quadrada C=[cik] de ordem n, onde n é o número


total de enfermeiros, na qual cik associa o custo do enfermeiro i receber, no dia j, uma dada tarefa de índice k. Como no problema em questão a quantidade de enfermeiros é sempre maior ou igual ao número de tarefas exigidas pela demanda, pode ser preciso completar a matriz C com tarefas fictícias até que o número de colunas, representando as tarefas, atinja o número de enfermeiros, representados nas linhas. O cálculo do custo de uma dada tarefa para um determinado enfermeiro em um certo dia é dado pela função f(i,j,k). A Figura 1 ilustra tal matriz.

Figura 1: Estrutura da matriz de custos C.

A matriz C pode ser dividida em dois blocos. No bloco I constam as tarefas que atendem a demanda de escala daquele dia. No bloco II estão presentes as tarefas fictícias que precisam ser incorporadas para que a matriz C se torne quadrada, caso no dia em questão o número de enfermeiros seja maior que o número de tarefas demandadas. Numa tarefa fictícia, algum turno é atribuído ao enfermeiro. Como o atendimento à demanda é garantido pelo bloco I da matriz, a atribuição de qualquer turno é permitida, incluindo o turno folga, para o qual não há demanda. No bloco II, os elementos de cada linha recebem o valor do turno de menor custo do enfermeiro correspondente naquele dia.

Inicialmente todas as jornadas estão vazias. Então, a matriz C correspondente à primeira camada é gerada e um PA é resolvido. Tem-se então uma tarefa escalonada para cada um dos enfermeiros no primeiro dia de suas jornadas. Em seguida, a matriz C relacionada à segunda camada deve ser gerada. A partir dessa camada, a função f(i,j,k), além de fornecer o custo da tarefa k no dia j para o enfermeiro i, também acrescenta uma penalidade caso o referido turno implique em uma violação de restrição. Obtida a nova matriz, outro PA é resolvido para se obter as tarefas do segundo dia da escala. O processo segue até que todas as camadas sejam resolvidas e todas as jornadas estejam completas.

Uma visão geral da fase construtiva é apresentada a seguir:

Início;

Inicialize os dados;

Para j=1 até d fazer:

Gere a matriz de custo C correspondente ao dia j;

Resolva o PA da matriz C;

Aloque as tarefas aos enfermeiros conforme o resultado obtido;

Fim.

2.2. Fase de Melhoramento

A fase de melhoramento possui dois procedimentos distintos pelos quais a minimização do custo total da solução é buscada. O primeiro, denominado Procedimento de Cortes e Recombinações (PCR), efetua um corte entre duas camadas e divide cada uma das n jornadas em duas jornadas parciais, ficando um trecho à esquerda e outro trecho à direita do corte. Em seguida é calculado o custo de se associar cada um dos n trechos de jornada à esquerda do corte a cada um dos n trechos de jornada à sua direita. Cada recombinação entre jornadas parciais à esquerda

I II

Enfermeiros cik=f(i,j,k) cik=Mín f(i,j,k);

k=1,...,s

Tarefas Tarefas Fictícias


e à direita do corte determina o valor de um elemento da matriz de custos E, de dimensões n×n. Nessa matriz, os trechos de jornada à esquerda são indicados pelas linhas e os trechos à direita, pelas colunas. Cada elemento eij representa o custo de se associar a jornada parcial à esquerda i com a jornada parcial à direita j. Nesse cálculo, o algoritmo verifica quais tarefas fictícias podem ser substituídas para que a recombinação tenha seu custo reduzido. Isso é feito sequencialmente através das camadas da jornada no mesmo sentido em que são feitos os cortes. No valor de eij

também se incluem penalidades, se houver violações de restrições. Obtida a matriz E, o PA correlato é resolvido e os trechos são recombinados, formando novas

jornadas. Como o algoritmo que resolve o PA de dois níveis é exato e garante a solução ótima, o custo total da solução diminui ou se mantém a cada corte e recombinação, nunca piora. Uma iteração do PCR consiste em realizar d-1 cortes e recombinações entre as camadas, além de uma recombinação entre cada um dos n enfermeiros e cada uma das n jornadas completas. Assim, uma iteração corresponde a d cortes e recombinações. A sequência desses cortes no grafo G pode ser feita tanto da esquerda para a direita quanto no sentido inverso. A Figura 2 apresenta um exemplo de escala elaborada pelo procedimento de construção de solução inicial, constituída com setas contínuas, bem como os locais onde o PCR efetua os cortes. Entre os dias 1 e 2, as setas pontilhadas mostram as possibilidades de recombinação entre as jornadas parciais à esquerda e à direita do corte 2. Em cada vértice do grafo está indicado o tipo de tarefa e o turno atribuído. As letras minúsculas d e f antes da barra indicam, respectivamente, se uma tarefa é exigida pela demanda ou se é uma tarefa fictícia. As letras maiúsculas M, T, N e F após a barra indicam o tipo de turno, respectivamente, manhã, tarde, noite e folga.

Figura 2: Posições dos cortes na solução inicial e as possíveis recombinações em um deles.

Após os custos das recombinações serem calculados e o PA correspondente ser resolvido, a escala é alterada. A Figura 3 mostra o resultado de uma recombinação de jornadas parciais a partir de um corte entre os dias 1 e 2. Após esse corte, algumas tarefas fictícias tiveram seus turnos substituídos por propiciarem redução no custo total. No exemplo, isso ocorreu no dia 5 com a nova jornada do enfermeiro 2. Em outros casos, a substituição de tarefas fictícias pode permitir a exclusão de violações às restrições.

Figura 3: Escala após corte e recombinação do PCR. Segue a descrição desse procedimento:

Cortes:

Dia 1 Dia 2

d/N

d/M

f/T

d/M

Enfermeiro 1

Enfermeiro 2

Enfermeiro 3

Enfermeiro 4

Dia 3 Dia 4 Dia 5 Dia 6

f/M

f/F

d/T

f/F

f/F

f/F

d/T

d/M

Dia 7

d/T

d/M

d/N

f/F

d/M

d/T

f/F

d/N

f/F

d/T

d/T

d/N

d/M

d/T

f/F

d/N

1 2 3 4 5 6 7

Cortes:

Dia 1 Dia 2

d/N

d/M

f/T

d/M

Enfermeiro 1

Enfermeiro 2

Enfermeiro 3

Enfermeiro 4


f/T

f/F

d/T

f/F

f/F

f/F

d/T

d/M

Dia 7

d/T

d/M

d/N

f/F

d/M

d/T

f/F

d/N

f/F

d/T

d/T

d/N

d/M

d/T

f/F

d/N

1 2 3 4 5 6 7


Início;


Efetue uma divisão na posição de corte 1;

Gere a matriz E que relaciona os enfermeiros às jornadas;

Resolva o PA da matriz E;

Recombine as jornadas aos enfermeiros conforme o resultado obtido;

Para l=1 até d fazer:

Efetue uma divisão na posição de corte l;

Gere a matriz de custo E que relaciona as jornadas parciais;

Resolva o PA da matriz E;

Recombine as jornadas parciais conforme o resultado obtido;

Fim.

O segundo procedimento da fase de melhoramento, denominado Procedimento de Redistribuição de Tarefas (PRT), objetiva diminuir o custo total da solução pela redistribuição das tarefas entre os enfermeiros em um único dia. Como o PEE envolve custos relacionados a preferências, uma mesma tarefa executada por pessoas diferentes poder incorrer em diferentes custos. Outra possibilidade é que tal redistribuição subtraia algumas violações de restrições. O procedimento consiste em selecionar uma camada e associar cada uma das n tarefas desse dia a cada uma das n jornadas. O custo de cada associação se torna um elemento da matriz F=[fij]. Nela, as tarefas são dadas pelas linhas e as jornadas, pelas colunas. A exemplo do PCR, o cálculo de tais custos envolve tanto a investigação de tarefas fictícias menos custosas às jornadas quanto à inclusão de penalidades para violações de restrições. A Figura 4 apresenta um exemplo de escala que sofre tal redistribuição na camada 4. As setas pontilhadas mostram as possíveis associações das tarefas desse dia com cada jornada.

Gerada a matriz F, o PA é resolvido relacionado é resolvido e a solução é alterada através de trocas de tarefas do dia em questão entre os enfermeiros. A Figura 5 exibe um exemplo dessa alteração.

Figura 4: Associação entre as tarefas de um dado dia e todas as jornadas.

Figura 5: Escala após redistribuição de tarefas em um dia.

Cortes:

Dia 1 Dia 2

d/N

d/M

f/T

d/M

Enfermeiro 1

Enfermeiro 2

Enfermeiro 3

Enfermeiro 4


f/T

f/F

d/T

f/F

f/F

f/F

d/T

d/M

Dia 7

d/T

d/M

d/N

f/F

d/M

d/T

f/F

d/N

f/F

d/T

d/T

d/N

d/M

d/T

f/F

d/N

1 2 3 4 5 6 7

Cortes:

Dia 1 Dia 2

d/N

d/M

f/F

d/M

Enfermeiro 1

Enfermeiro 2

Enfermeiro 3

Enfermeiro 4


f/T

f/F

d/T

f/M

f/F

f/F

d/T

d/M

Dia 7

d/T

d/M

d/N

f/F

d/M

d/T

f/F

d/N

f/F

d/T

d/T

d/N

d/M

d/T

f/F

d/N

1 2 3 4 5 6 7


Semelhantemente ao PCR, esse processo faz com que o custo da solução seja reduzido ou, não sendo possível, que se mantenha. Uma iteração desse procedimento se faz redistribuindo as tarefas das d camadas da escala, do primeiro ao último dia, ou no sentido contrário. Os princípios de tal procedimento são apresentados na sequência:

Início;


Para k=1 até d fazer:

Gere a matriz F que relaciona as tarefas do dia k às jornadas;

Resolva o PA da matriz F;

Redistribua as tarefas às jornadas conforme o resultado obtido;

Fim.

Os procedimentos de melhoramento são executados intercaladamente percorrendo as

camadas em ambos os sentidos. Isso segue até que não haja melhoria por um número determinado de iterações ou até que um limite de iterações seja alcançado. Após a etapa de melhoramento, caso existam violações às restrições, as mesmas são eliminadas. Essas eliminações são feitas pela substituição dos turnos que geram violações. Para tanto a demanda pode deixar de ser atendida, sendo que cada tarefa não atendida implica na inclusão de uma penalidade. Dessa forma, na solução final, as restrições rígidas e flexíveis sempre são atendidas.

3. Resultados e Análise

O algoritmo proposto foi implementado utilizando a linguagem Pascal e os testes foram realizados em um Athlon 64 de 1,8GHz com 512 MB de RAM executando o sistema operacional Windows XP. As instâncias utilizadas foram obtidas na biblioteca NSPLib, disponível na página da universidade belga Ugent. Como o PEE envolve muitas variáveis, existe a tendência de que cada trabalho use instâncias com muitas singularidades. Essa falta de padrão dificulta a comparação entre diferentes trabalhos. Por esse motivo, a NSPLib foi proposta por Maenhout e Vanhoucke (2005) visando permitir que diferentes métodos pudessem ser avaliados sob os mesmos parâmetros.

A biblioteca possui um grupo de instâncias que envolvem escalas semanais de 7 dias. São problemas que trabalham com 25, 50, 75 e 100 enfermeiros. Para cada um dos 4 tamanhos de problema existem 7290 arquivos com diferentes demandas por dia e diferentes custos de preferência num total de 29160 arquivos. Os arquivos ainda apresentam diversidade de distribuição dos custos de preferência e diferentes condições de atendimento às restrições. Existem ainda 8 diferentes casos com os quais cada um dos arquivos pode ser combinado. Cada caso possui diferentes valores para as restrições do problema. Assim, para esse grupo, existem 233280 possibilidades de se instanciar problema. O outro grupo é utilizado para gerar escalas mensais de 28 dias e possui problemas com 30 e 60 enfermeiros. São 960 arquivos para cada tamanho de problema e 8 casos com os quais cada um deles pode se associar. Nesse grupo são 15360 possibilidades de instanciação do problema. Considerando ambos os grupos, a NSPLib oferece um universo de 248640 possibilidades de se instanciar o PEE. Cada possibilidade foi testada pelos autores utilizando os algoritmos baseados na EM, Maenhout e Vanhoucke (2007), e também em BD, Maenhout e Vanhoucke (2006), ambos trabalhando com o critério de parada de geração de 5000 escalas. Dessas execuções são disponibilizados o custo da melhor solução obtida, o tempo de processamento e a quantidade de restrições violadas.

3.1. Instâncias Utilizadas

Neste trabalho, a realização dos testes abrangeu tanto instâncias para escalas de 7 dias quanto instâncias para escalas de 28 dias e envolveu problemas de todas quantidades de enfermeiros disponíveis. Para as escalas de 7 dias os problemas tinham 25, 50, 75 ou 100 enfermeiros. O conjunto de restrições ao qual cada um desses 29160 arquivos foi associado foi o caso de número 1. Os testes com escalas de 28 dias foram feitos com problemas envolvendo tanto 30 quanto 60


enfermeiros e neles os 1920 arquivos foram combinados com o caso 9. A penalidade pela violação de uma restrição recebeu valor igual a 100, o mesmo aplicado em Maenhout e Vanhoucke (2006) e em Maenhout e Vanhoucke (2007). Esses autores sempre utilizam como relaxação a desobediência à demanda, que incorre no acréscimo de uma penalidade. Já no método do presente trabalho, tanto na fase construtiva quanto na fase de melhoramento, a demanda sempre é obedecida. Nessas fases, as penalizações advêm por outros tipos de violação. Então, ao final da etapa de melhoramento, a solução é adequada para que todas restrições sejam atendidas, mesmo que isso cause descumprimentos de demanda. Cada desobediência à demanda implica no acréscimo de uma penalidade com valor igual a 100. Dessa maneira, as soluções entregues pelo presente método são compatíveis com as soluções obtidas pelos métodos que abastecem a NSPLib. A realização de todos os testes somou mais de 20 dias ininterruptos de processamento.

3.2. Comparação dos Procedimentos de Melhoramento

Uma comparação entre os procedimentos de melhoria é feita na Tabela 1 a partir de testes com algumas instâncias. Gerada uma solução pelo procedimento de construção da solução inicial, os procedimentos de melhoramento foram empregados isoladamente. O custo alcançado e a redução conseguida para problemas de tamanhos diferentes são apresentados. Tais resultados não envolvem a substituição de violações às restrições por desobediências à demanda. Porém, as inclusões de penalidade são equivalentes em quantidade, sendo que cada violação pode ser substituída por uma desobediência à demanda. A primeira coluna indica n, o número de enfermeiros do respectivo problema. A segunda indica d, o número de dias da escala. A terceira informa o arquivo utilizado. A quarta indica o custo da solução inicial que, muitas vezes, inclui penalidades por violações de restrições. A quinta e a sexta colunas trazem o menor custo obtido pelo PCR e a redução percentual conseguida em relação à solução inicial. A sétima e a oitava colunas mostram o custo da solução alcançada pelo PRT e a redução propiciada por ele. Nas duas últimas colunas consta, respectivamente, o custo da solução obtida pela combinação de ambos os procedimentos e a redução que tal combinação proporcionou.

Tabela 1: Comparação da redução de custo através dos procedimentos de melhoria.

Analisando a Tabela 1 é possível constatar que o PCR é capaz de obter maiores reduções de

custo que o PRT. Para algumas instâncias, o PCR conseguiu isoladamente chegar ao mesmo valor que o obtido pela combinação dos dois procedimentos. Contudo, os dados mostram que os procedimentos combinados propiciam resultados que isoladamente o PCR e o PRT nem sempre são capazes de obter.

3.3. Comparação dos Resultados

O algoritmo proposto primeiramente executa o procedimento de construção da solução inicial. Obtida tal solução, são empregados os procedimentos de melhoramento. Primeiramente o PCR percorre a escala da esquerda para a direita. Em seguida, o PRT faz o mesmo caminho. Então os dois procedimentos são aplicados novamente na mesma ordem no sentido inverso. Essas quatro passagens pela escala constituem uma iteração. Como o algoritmo proposto trabalha com uma única solução que é melhorada no decorrer da execução, o critério de parada usado é a ocorrência de 3 iterações consecutivas sem melhoria. Tal critério se justifica pelo fato de que pode haver alterações na escala sem que haja redução no custo. Isso ocorre devido às inúmeras

n d Arquivo Solução Inicial PCR Redução

PCR(%) PRT Redução PRT(%)

PCR e PRT

Redução PCR e PRT(%)

25 7 1 343 309 9,91 313 8,74 307 10,49 50 7 1 1123 580 48,35 584 47,99 580 48,35 75 7 1 939 880 6,28 882 6,07 880 6,28

100 7 1 2476 1289 47,94 1292 47,81 1289 47,94 30 28 1 3998 1583 60,40 2149 46,24 1573 60,65 60 28 1 6267 3186 49,16 3364 46,32 3184 49,19


possibilidades de alocação de turnos em tarefas fictícias e recombinações entre jornadas que podem proporcionar melhoria mesmo após algumas iterações com o custo estagnado. Além desse critério, existe um limite máximo de 20 iterações no total.

A Tabela 2 apresenta os resultados obtidos nos testes para diferentes quantidades de enfermeiros e de dias. Na terceira coluna são explicitadas as quantidades de instâncias testadas. A quarta, a quinta e a sexta colunas se referem aos melhores resultados da NSPLib empregando EM ou BD e indicam a média do custo total das soluções, o tempo médio de resolução em segundos e a média de violações de restrições, respectivamente. A sétima, a oitava e a nona colunas mostram as mesmas informações mas se referem ao Algoritmo Proposto (AP).

Tabela 2: Comparação de resultados entre AP e NSPLib.

Na Tabela 3 constam valores percentuais que comparam o desempenho do AP com os

resultados da NSPLib. Na quarta coluna, para cada tamanho de problema, consta a porcentagem de vezes em que os resultados da biblioteca foram melhores que os do AP, considerando os custos. Na quinta coluna, a porcentagem de vezes em que um mesmo custo foi encontrado. Na sexta, a porcentagem de vezes que o AP obteve um custo menor. A tabela também mostra as relações de custo, de tempo de execução e de violações de restrições entre o AP e a NSPLib. Esses valores são dados pela fórmula Gap=[(Valor AP – Valor NSPLib)/Valor NSPLib]·100. Porcentagens positivas indicam o quanto o AP ficou acima da NSPLib e porcentagens negativas indicam o quanto o desempenho do AP foi melhor que o dos trabalhos de referência.

Tabela 3: Comparação e relação de desempenho entre o AP e os dados da NSPLib.

Ao se observar as Tabelas 2 e 3 fica evidente que, conforme o tamanho da instância do

problema cresce, melhores se tornam os resultados do AP em relação à NSPLib em termos de custos. Nos problemas com menos enfermeiros e menores jornadas, os resultados do AP ficaram aquém dos resultados da biblioteca. Isso ocorreu com os problemas envolvendo 25 enfermeiros. Enquanto o custo médio das soluções da NSPLib foi de 305,11, o AP obteve um custo médio de 306,72, ou seja, 0,53% maior. Em 48,57% desses problemas a NSPLib apresentou custos menores contra apenas 5,21% do AP. Nos problemas com 50 enfermeiros os custos se aproximaram, ficando a média do AP apenas 0,17% acima da média da NSPLib. Também houve maior equilíbrio na quantidade de problemas em que cada um obteve melhor solução, sendo 31,08% dos casos favoráveis à NSPLib e 19,68% ao AP. Com 75 enfermeiros, o AP obteve um

n

d

Instâncias Testadas

NSPLib AP Custo Médio

Tempo Médio (s)

Média de Violações

Custo Médio

Tempo Médio (s)

Média de Violações

25 7 7290 305,11 1,664 0,530 306,72 2,046 0,530 50 7 7290 587,06 4,416 0,847 588,05 7,502 0,847 75 7 7290 912,86 12,468 1,503 913,11 18,142 1,503

100 7 7290 1389,23 20,000 1,664 1388,72 35,096 1,663 30 28 960 1911,19 34,000 4,019 1865,54 314,629 3,919 60 28 960 3786,04 87,676 7,019 3683,10 1441,458 6,743

n

d

Instâncias Testadas

Melhores Soluções (%) Relação AP/NSPLib (%) NSPLib Melhor

Mesmo Custo

AP Melhor

Gap Custo

Gap Tempo

Gap Violações

25 7 7290 48,57 46,21 5,21 0,53 22,96 0,00 50 7 7290 31,08 49,23 19,68 0,17 69,88 0,00 75 7 7290 19,47 40,21 40,33 0,03 45,51 0,00 100 7 7290 13,50 30,77 55,73 -0,04 75,48 -0,06 30 28 960 1,77 0,21 98,02 -2,39 825,38 -2,49 60 28 960 2,19 0,00 97,81 -2,72 1544,07 -3,93


custo médio 0,03% superior ao da NSPLib mas alcançou melhor resultado em 40,33% dos casos, contra 19,47% da biblioteca. A partir dos problemas com 100 enfermeiros o AP foi melhor. Para esse tamanho de problema o AP obteve custo menor em 55,73% das instâncias testadas enquanto a NSPLib apresentou menor custo em 13,50% das vezes. Além da redução de 0,04% do custo médio, o AP ainda obteve redução na média de restrições violadas, -0,06% que a NSPLib. Resolvendo escalas de 28 dias com 30 enfermeiros, o AP também obteve melhores soluções. Seu custo médio ficou 2,39% abaixo dos custos da NSPLib. Também foram violadas menos restrições, exatamente -2,49%. Com 60 enfermeiros seu custo médio ficou 2,72% abaixo dos valores dos trabalhos de referência e houve -3,93% de desobediências à demanda.

A Tabela 4 apresenta os custos médios das soluções das instâncias para as quais tanto a NSPLib quanto o AP obtiveram soluções factíveis. Tais custos, não envolvendo desobediência à demanda nem violações a restrições rígidas, permitem uma comparação entre o método proposto e os resultados da NSPLib sem a interferência das penalidades. Na quarta coluna dessa tabela estão as quantidades de instâncias comparáveis por apresentarem solução factível tanto pela NSPLib quanto pelo AP. Na quinta coluna estão os custos médios das soluções dessas instâncias, obtidos na biblioteca. A sexta coluna mostra quantas instâncias no total resultaram em soluções factíveis pela NSPLib. Na sétima coluna constam os custos médios das soluções das instâncias comparáveis obtidas pelo AP. A oitava coluna traz o número total de instâncias para as quais o AP obteve soluções factíveis.

Tabela 4: Comparação envolvendo soluções factíveis.

Através dos resultados da Tabela 4 é possível observar a mesma tendência constatada na

Tabela 2. Para instâncias envolvendo menos enfermeiros e menos dias o desempenho do AP fica aquém dos resultados da NSPLib. À medida que o tamanho das instâncias crescem, os custos encontrados pelo AP se tornam menores que o da biblioteca e se distanciam desta.

O tempo de execução, apesar de apresentado, é de difícil comparação pois diferentes máquinas foram utilizadas pelos diferentes métodos. As execuções que alimentaram a NSPLib foram realizadas em um Toshiba SPA10 com um processador Intel Celeron de 2,4 GHz e com 256 MB de RAM. Apesar de haver técnicas que fornecem um fator de comparação entre computadores diferentes, as mesmas não foram empregadas pois sua confiabilidade não é absoluta. Apenas a realização de testes com os diferentes algoritmos em uma mesma máquina poderia confirmar e mensurar o maior dispêndio de tempo do AP em relação aos outros métodos.

4. Conclusões

O algoritmo heurístico proposto neste trabalho se baseia em um procedimento exato de complexidade polinomial para resolver subproblemas. As soluções obtidas pelo AP mostraram, em geral, ser melhores que as soluções disponíveis na base de dados de referência do problema. Portanto, este artigo contribuiu com um novo algoritmo que supera os desafios fomentados por Maenhout, M. Vanhoucke (2007).

O AP mostrou ser capaz de resolver desde problemas pequenos até problemas de grande porte. Exatamente para estes últimos problemas o algoritmo alcançou os melhores resultados, quando comparado aos trabalhos de referência. Isto significa que o resultado alcançado foi superior para as instâncias de tamanho mais realista, justamente na classe de problemas onde se pode justificar o uso de algoritmo heurístico.

n

d

Total de

Instâncias

Instâncias

Comparadas

NSPLib AP Custo Médio

Soluções Factíveis

Custo Médio

Soluções Factíveis

25 7 7290 6435 250,55 6435 251,46 6435 50 7 7290 6563 499,94 6563 500,08 6563 75 7 7290 6466 757,92 6466 756,83 6466

100 7 7290 6597 1217,76 6597 1215,35 6600 30 28 960 660 1476,43 660 1444,98 669 60 28 960 664 3015,90 664 2950,41 675


O algoritmo pode ser considerado eficiente do ponto de vista do tempo computacional, mesmo com tempo maior que o dos trabalhos usados como referência. Devido a essa característica, o algoritmo pode ser utilizado na elaboração de escalas semanais ou mensais, mesmo que as condições de demanda e preferência sejam dinâmicas, podendo ser executado em curto espaço de tempo. Embora não seja a meta principal desta investigação, esta abordagem mostrou ser bastante útil para ser aplicada em casos reais de escalonamento de enfermeiros.

Agradecimentos: Ao apoio financeiro do Conselho Nacional de Desenvolvimento Científico e Tencológico (CNPq) e ao PIBIC/CNPq-FA-UEM.

5. Referências AICKELIN, U.; DOWSLAND, K. (2004), An indirect genetic algorithm for a nurse scheduling problem. Computers and Operations Research, 31(5), 761-778. BARD, J. ; PURNOMO, H. (2008), Preference scheduling for nurses using column generation. European Journal of Operations Research, 164(2), 510-534. BELLANTI, F., CARELLO, G., DELLA CROCE, F. e TADEI, R. (2008), A greedy-based neighborhood search approach to a nurse rostering problem. European Journal of

Operations Research, 153(1), 28-40. BURKE, E. K., CURTOIS,T., POST, G., QU, R. e VELTMAN, B. (2008), A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. European

Journal of Operations Research, 188(2), 330-341. CARPANETO G.; TOTH P. (1987), Primal-dual algorithms for the assignment problem. Discrete Applied Mathematics, 18, 137-153. FERLAND, J. A., BERRADA, I., NABLI, I., AHIOD, B., MICHELON, P., e GASCON, V. (2001), Generalized assignment problem type goal programming problem: application to nurse scheduling. Journal of Heuristics, 7(4), 391-413. KAWANAKA, H., YOSHIKAWA, T., SHINOGI, T. e TSURUOKA, S. (2003), Constraints and Search Efficiency in Nurse Scheduling Problem. IEEE International.

Symposium on Computational Intelligence in Robotics and Automation, Kobe, 1, 312-317. KUNDU, S. e ACHARYYA, S. (2008), A SAT approach for solving the nurse scheduling problem. IEEE Region 10 Conference TENCON 2008, Hyderabad, 1-6. LI, J. e AICKELIN, U. (2003), A Bayesian optimization algorithm for the nurse scheduling problem. The 2003 Congress on Evolutionary Computation. 3, 2149-2156. MAENHOUT, B. e VANHOUCKE, M. (2007), An electromagnetic meta-heuristic for the nurse scheduling problem. Journal of Heuristcs, Amsterdã, 13(4), 359-385. MAENHOUT, B. e VANHOUCKE, M. An electromagnetic meta-heuristic for the nurse scheduling problem. Working Paper, Faculteit Economie en Bedrijfskunde, Gent, 2005. MAENHOUT, B. e VANHOUCKE, M. (2006), New Computational Results for the Nurse Scheduling Problem: A Scatter Search Algorithm. Lecture Notes in Computer Science, Berlin, 3906, 159-170. OSOGAMI, T. e IMAI, H. (2000), Classification of Various Neighborhood Operations for the Nurse Scheduling Problem. Lecture Notes in Computer Science, 1969, 72-83. OHKI, M.; MORIMOTO, A. e MIYAKE, K. (2006), Nurse scheduling by using cooperative GA with efficient mutation and mountain-climbing operators. Third International IEEE

Conference Intelligent Systems, Londres, 164-169. OHKI, M.; UNEME, S. e KAWANO, H. (2008), Parallel processing of cooperative genetic algorithm fornurse scheduling. Fourth Int. IEEE Conference Intelligent Systems, Varna, 36-41. OUGHALIME, A.; ISMAIL, W. e YEUN, L. (2008), A tabu search approach to the nurse scheduling problem. Int. Symposium on Information Techonology, Kuala Lumpur, 1, 1-7. TSAI, C.; LI, S. (2009), A two-stage modeling with genetic algorithms for the nurse scheduling problem. Expert Systems with Applications, 36(5), 9506-9512.


Documents

UM ALGORITMO HEURÍSTICO PARA OTIMIZAÇÃO DO … · o algoritmo utiliza um decodificador que preenche as lacunas da escala de modo que os custos sejam mínimos. Ohki, Morimoto e