( PDF ) Alocação de recursos humanos em unidades de saúde através da técnica de problemas sujeitos a restrições: proposta de uso de restrições programáveis e análise de desempenho de heurísticas

Download PDF

ads:

UNIVERSIDADE FEDERAL DO AMAZONAS

FACULDADE DE TECNOLOGIA

PROGRAMA DE PÓS

GRADUAÇÃO EM ENGENHARIA ELÉTRICA

ALOCAÇÃO DE RECURSOS HUMANOS EM UNIDADES DE SAÚDE ATRAVÉS DA

TÉCNICA DE PROBLEMAS SUJEITOS A RESTRIÇÕES: PROPOSTA DE USO DE

RESTRIÇÕES PROGRA

MÁVEIS E ANÁLISE DE DESEMPENHO DE HEURÍSTICAS

DAYSE APARECIDA RIVERA ROCHA

MANAUS

2009

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

NIVERSIDADE FEDERAL DO AMAZONAS

FACULDADE DE TECNOLOGIA

PROGRAMA DE PÓS

GRADUAÇÃO EM ENGENHARIA ELÉTRICA

DAYSE APARECIDA RIVERA ROCHA

ALOCAÇÃO DE

RECURSOS HUMANOS EM UNIDADES DE SAÚDE ATRAVÉS DA

TÉCNICA DE PROBLEMAS SUJEITOS A RESTRIÇÕES: PROPOSTA DE USO DE

RESTRIÇÕES PROGRAMÁVEIS E ANÁLISE DE DESEMPENHO DE HEURÍSTICAS

Orientador: Profº Dr

Cícero

Ferreira Fernandes Costa Filho

ori

entadora:

Profª

Dra. Marly Guimarães Fernandes Costa

MANAUS

2009

Dissertação apresentada ao Programa de Pós-

Graduação em Engenharia Elétrica

Universidade Federal do Amazonas, como

requisito parcial para a obtenção do título de

Mestre em Engenharia Elétrica, área de

concentração

Controle e Automação de

Sistemas

ads:

Ficha Catalográfica

(Catalogação realizada pela Biblioteca Central da UFAM)

R672a

Rocha

Dayse Aparecida Rivera

Alocação de recursos humanos em unidades de saúde através da técnica

de problemas sujeitos a restrições: proposta de uso de restrições

programáveis e análise de desempenho de heurísticas / Dayse Aparecida

Rivera Rocha.

Manaus: UFAM, 2009.

f.; il. color.

tação

(Mestrado em Engenharia Elétrica

)

––

Universidade

Federal do Amazonas, 2009

Orientador: Profº Dr.

Cícero Ferreira F. Costa Filho

orientadora: Profª Dra. Marly Guimarães F. Costa

1. Serviço de informação – Saúde

Sistema Único de Saúde 3.

Cooperativas médicas

Costa Filho, Cícero Ferreira F.

II.

Costa, Marly

Guimarães F.

III. Universidade Federal do Amazonas IV. Título

CDU

614.2:004(811.3)(043.3)

Aos meus pais e irmão

AGRADECIMENTOS

Aos meus pais, que sempre me incentivaram em meus estudos e a toda a família pela

torcida.

Ao professor Cícero Costa pela imensa contribuição despendida para conclusão desse

trabalho

À professora Marly Costa

ela atenção dada s

empre que

precisei.

Aos amigos do mestrado Luciano Oliveira, Nairon Viana e Orlewilson Maia, e aos

amigos da Fucapi,

pela força e apoio

Ao Ce

ntro de P&D em Tecnologia Eletrô

nica e da Informa

çã

–

CETELI, por

seu

apoio

em infra

estrutura cedida

A todos aqueles que me ajudaram de alguma forma durante todo o mestrado, desde o

nivelamento.

Nossas dúvidas são traidoras e nos fazem

perder o bem que poderíamos

conquistar

não fosse o medo de tentar.

William Shake

speare

RESUMO

A crescente utilização dos serviços de saúde, ocasionada pelo aumento da expectativa

de vida da população, vem sendo acompanhada por baixos valores

repassados

pelo Sistema

Único de Saúde e pelos planos de saúde para a realização dos procedi

mentos

às clínicas e

hospitais

Diante desse cenário

indispensável a utilização de sistemas de informação para o

controle de custo efetivo. Nesse contexto, este

trabalho

propõe uma ferramenta para o

planejamento do uso de recursos humanos na área de saúde, aqui chamado de sistema de

alocação de recursos humanos. Muitos trabalhos foram desenvolvidos para a resolução do

problema de alocação de recursos humanos na área de saúde, mais especificamente na área de

enfermagem.

O presente trabalho trata da alocação de médicos cooperados em unidades de

saúde públicas estaduais da cidade de Manaus. Tais profissionais pertencem à cooperativas

que prestam serviços ao estado do Amazonas

Para tal, utilizou-

a abordagem PSR

associada

a heurísticas como VRM - Valores Restantes Mínimos, VP - Verificação Prévia

heurística de grau e heurística especial,

esta

última sendo

uma

prop

osta n

te trabalho.

metodologia do trabalho envolve a modelagem matemática das restrições do problema

modelagem computacional e

codificaç

ão do projeto. Nas duas ú

ltimas

etapas

utiliz

abordagem orientada a objetos. A ferramenta modelada permite a programação das restrições,

o que garante flexibilidade d

sua

utilização

. Experimentos foram realizados para avaliar o

desempenho das heurísticas acima citadas e verificar quais as mais adequadas a serem

utilizadas num problema real. Os resultados mostraram que a heur

ística e

special apresentou os

melhores tempos de convergência e a heurística VP apresentou a menor quantidade de nós

expandidos

. A utilização da VP, no entanto, mostrou-se inviável, devido ao alto consumo de

memória requerida pela mesma. Nas conclusões desse trabalho afirma-se que, para resolução

do estudo do caso real apresentado, a melhor combinação de heurísticas foi a utilização da

heurística VRM para a escolha da melhor unidade de alocação a ser atribuída, e da heurística

especial, para a escolha do melhor plantonista a ser atribuído à vaga. Essa associação

heurísticas

apresentou resultados satisfatórios, com um tempo de elaboração da escala de

46,7min.

A elaboração dessa esca

la manual é feita num tempo de

duas

semanas.

Palavras

-chave: Alocação de recursos humanos, busca retroativa, inteligência artificial,

cooperativas médicas.

ABSTRACT

The increasing use of

the

health

system, caused

the increase of population life

expectancy

, is

associated

in Brazil

with

the

low transferred

values

the

“Sistema Único de

Saú

– SUS/Brasil”

and

the

health plans for the accomplishment of the procedures to the

clinics and hospitals. In this scenario

is indispensable the use of information systems for

effective cost

control

Inserted in this context this work proposes a tool for human resource

planning in the health area,

here

called

human resources in this work by allocation

syst

em of

human resources. Many works have been developed for the resolution of the problem of

allocation of human resources in the health area, more specifically in the area of nursing. The

present work deals with the problem of allocation of cooperated do

cto

rs in State health units

Manaus

city.

For such, it was used

the

PSR

approach

associated

to heuristic rules

heuristic

MRV - M

inimum

emaing

Values

forward checking

degree

heuristic

and special

heuristic, this last one being propos

in this work. The adopted methodology consists of the

mathematical modeling of the problem restrictions, computational modeling and codification

of the project. In the two last stages it was used an object-oriented approach. The developed

tool enables the

programming

restrictions,

what assures its flexible use. Experiments ha

been carried through to evaluate the performance of the heuristics above cited to verify the

most adequate to be used in a real problem. The results have

shown

that the special heuristic

presen

ted the best convergence time and the forward checking

heuristic

presented the smaller

amount of expanded nodes. However, the use of the forward checking

tic

was

revealed

impracticable,

due to the high consumption of memory required

In this way, for the

resolution of the real problem, the heuristic M

was

used for the choice of the best vacan

to be attributed, and the special heuristic, for the choice of optimum medical to be attributed

to the vacancy

This association presented satisfactory res

ults

with a scale

elaboration

time

7 min. The manual elaboration of this scale takes about 2 weeks to be accomplished.

Keywords:

Allocation of resources, backtracking algorithm

artificial intelligence, medical

cooperatives.

LISTA DE ILUSTRAÇÕES

Figura 2.1

–

Escala dos enfermeiros

................................................................

.........................

Figura 3.1

Algoritmo que define o domínio das variáveis

................................

.....................

Figura 3.2

–

Árvore de espaço de estado para o problema de satisfação de restrições

............35

Figura 3.3

–

Fluxograma do algoritmo de busca retroativa................................

......................

Figura 3.4

–

Algoritmo de pesquisa

com

retrocesso (Adaptada de RUSSELL; NORVIG,

2004)

................................................................

................................

.........37

Figura 3.5

–

Adição heurística de grau ao fluxogram

a do algoritmo de busca

........................

Figura 3.6

–

Um exemplo de aplicação da heurística de verificação prévia

.............................

Figura 3.7

–

Adição heurí

stica de verificação prévia ao fluxograma do algoritmo de busca

...41

Figura 3.8

–

Pseudocódigo do algoritmo de pesquisa

com

-retrocesso com a heurística de

verificação prévia

................................

................................................................

......................

Figura 3.9

–

Diagrama de caso de uso do sistema com suas respectivas funcionalidades

.......44

Figura 3.10

–

Diagrama de classes

................................................................

...........................

Figura 3.11

Diagrama de objeto para caracterização da classe Vaga

................................

.....47

Figura 3.12

Diagrama de objeto para caracterização da classe Restrição Unár

..................48

Figura 3.13

Diagrama de objeto para caracterização da classe Restrição Múltipla

...............48

Figura 3.14

Diagrama de sequência d

a geração da escala

................................

......................

Figura 3.15

Tela principal do sistema

................................................................

....................

Figura 3.16

Tela de cadastro de plantonista

................................

...........55

Figura 3.17

Tela de cadastro de unidade de saúde

................................................................

Figura 3.18

Tela de cadastro de turno

................................................................

....................

Figura 3.19

–

Tela de configuração dos dados da escala

................................

..........................

Figura 3.20

–

Tela de cadastro de quantidade de vagas nos turnos das unidades

....................

Figura 3.21

–

Tela de cadastro das restrições unárias

...............................................................

Figura 3.22

–

Tela com a lista de vagas e seus respectivos domínios

................................

......58

Figura 3.23

–

Tela de cadastro de restrição múltipla

................................................................

Figura 3.24

–

Tela com lista de vagas com seu respectivo plantonista alocado após execução

da busca

................................................................

................................

.....59

Figura 4.1

–

Fluxograma de execução para definição da escala.

................................

..............69

LISTA DE TABELAS

Tabela

1.1

–

Artigos publicados

................................

...............................................................

Tabela 4.2

–

Lista de restrições unárias

................................................................

....................

Tabela 4.3

– Resultado de experimento dos testes no sist

ema com restrições unárias

.............63

Tabela 4.4

–

Resultado de experimento dos testes no sistema com restrições múltiplas

.........64

Tabela 4.5

–

Resultado de experimento dos testes no sistema com restrições unárias e

múltiplas

................................................................

................................

....66

Tabela 4.6

–

Quantidade de vagas por unidade, dia e turno

................................

.....................

Tabela 4.7

–

Escala do plantonista 1................................................................

.........................

Tabela 4.8

–

Escala do plantonista 26

................................................................

.......................

Tabela 4.9

–

Escala do pla

ntonista 128

................................................................

.....................

Tabela 4.10

–

Escala da Unidade Fundação CECON

...............................................................

Tabela 4.11

–

Escala do Pronto Socorro 28 de Agosto

................................

.............................

Tabela 4.11

–

Escala do Hospital João Lúcio

................................

...........74

SUMÁRIO

1. Introdução

................................

.............................

1.1 Objetivo Geral

................................................................

................................

.................15

1.2 Objetivos Específicos

................................

.....15

1.3 Estrutura da Dissertação

................................

................................................................

2. Revisão Bibliográfica

................................

...........17

2.1 Artigo 1: Programação de restrições par

a escalonamento de enfermeiros.

....................

2.1.1 Restrições

................................................................

................................

.................19

2.1.2 Solucionando o problema

................................................................

........................

2.1.3 Resultados do processamento................................

................................

..................23

2.2 Artigo2: Uma modelagem em duas fases com algoritmos genéticos para o problema de

escalonamento de enfermeiro.

................................

..............................

2.2.1 Desenvolvimento do modelo ................................

................................

...................23

2.2.2 Modelo do algoritmo de solução e processo

................................

............................

2.3 Artigo 3: Uma abordagem baseada em busca tabu para o problema de escalonamento de

enfermeiros

................................

................................................................

...........................

2.3.1 Restrições do problema

................................

............................

2.3.2 Programação por meta e Busca Tabu

................................

.......28

2.3.3 Solução do Problema

................................

...............................................................

2.3.4 Resultados obtidos

................................

................................................................

...30

3. METODOLOGIA

................................................................

................................

.................31

3.1. Modelo do problema

................................

......32

3.1.1. Variáveis do problema

................................................................

...........................

3.1.2. Restrições

................................................................

................................

...............33

3.2. Algoritmo de Busca

................................

.......35

3.2.1. Heurístic

................................................................

................................

..............37

3.3. Características e Modelagem do Sistema

................................

.....42

3.3.1 Projeto e Modelagem do Sistema Computacional

................................

...................42

3.4 Ferramentas da implementação ................................................................

......................

3.4.1 Java

................................

................................................................

..........................

3.4.2

Tomcat

................................

................................................................

.....................

3.4.3 MySQL

................................

................................................................

....................

3.5 Aspectos da Interface Visual

................................................................

..........................

4. RESULTADOS

................................

................................................................

....................

4.1 Resultados das Heurísticas

................................

..............................

4.1.1 Testes no sistema sem restrições

................................

.............60

1.2 Testes no sistema com restrições unárias

................................................................

4.1.3 Testes no sistema com restrições múltiplas

................................

.............................

4.1.4 Testes no sistema com

restrições unárias e múltiplas

................................

..............65

4.2 Resultados do Estudo de Caso

................................................................

........................

4.2.1 Descrição do estudo de caso

................................................................

....................

4.2.2 Descrição dos resultados do estudo de caso ................................

............................

5. Discussão, Conclusões e Trabalhos Futuros

................................

.........76

Referências Bibliográficas

................................

........80

Introdução

Os hospitais utilizam a sua experiência com o suporte de uma infra-

estrutura

dispendiosa para prestar serviços de qualidade à população. De acordo com Spyropoulos

(2000), essa infra

estrutura é composta de:

Pessoal: Médicos de várias especialidades, enfermeiras, técnicos especializados na

manutenção de equipamento

s, pessoal administrativo, etc;

Unidades de terapia intensiva, com uma infra-estrutura dispendiosa para o suporte de

pacientes que requerem tratamento intensivo;

Salas de cirurgia, com equipamentos dedicados para realização de diversos

procedimentos operatórios;

Laboratórios especializados: Raios-X, ultra-

som,

tomografia, análises clínicas,

ressonância, et

Infra

-estrutura auxiliar: ambulâncias para transferências de emergência, leitos para

estadia de pacientes, farmácia para fornecimento de drogas, restaurantes para

provimento de refeições, etc.

Vários fatores pressionam por um controle efetivo dos recursos hospitalares, d

entre

esses fatores, o mais importante são os baixos valores pagos para a realização dos

procedimentos pelo Sistema Único de Saúde e pelos planos de saúde. Registra-se ainda que o

aumento da expectativa de vida em todo o mundo e no Brasil em particular, tem implicado

demandas crescentes para o sistema de saúde, implicando em aumentos de custos tanto para o

sistema público quanto privado de prestação de serviços de saúde.

Um controle efetivo dos custos exige que o gerenciamento da inf

-estrutura hospitalar

seja feito de forma eficiente, propiciando uma redução de custos sem a diminuição da

qualidade dos serviços prestados.

O controle de custo efetivo torna indispensável a utilização de sistemas de informação,

tanto os de propósitos gerais voltados para a contabilidade e controle financeiro, como os

sistemas de gerenciamento específicos voltados para o planejamento e alocação, como os

sistemas de planejamento do uso de recursos hospitalares (O

DDI

et al., 2000), sistemas de

alocação de enfermeiros (V

ALOUXIS

et al., 2000), etc. Esses sistemas constituem uma

pequena parte do que se convenciona chamar de um Sistema de Informação em Saúde – SIS

HORTLIFE

et al

., 2001

Estes

diferem substancialmente de outros si

stemas de i

nformação,

especi

almente quando se consideram as situações de emergência dos pacientes e a

imprevisibilidade das situações.

Nessa dissertação de mestrado estamos preocupados com essa pequena parte de um SIS

que trata do planejamento do uso de recursos humanos na área de saúde. Doravante referir-

nos

emos a esses sistemas por sistemas de alocação de recursos humanos.

Na literatura, conforme será visto na revisão bibliográfica, a área da saúde que mais

utiliza sistemas de alocação de recursos humanos é a de Enfermagem.

Ela

tem características

peculiares que sugerem e demandam de forma veemente o uso sistemas de informação para

alocação de recursos humanos:

Trabalha com um grande número de atores que, sem distinção, podem exercer o

mesmo papel dentro de uma estrutura hospitalar. Ao nos referirmos ao termo sem

distinção queremos dizer que na Enfermagem não existem, como na M

edicina,

especialidades;

O trabalho de enfermagem exige um grande número de profissionais;

Regulamentando a jornada do enfermeiro existem diversas normas trabalhistas que

criam diversas restrições para a alocação dos períodos d

seu

trabalho.

Ao considerarmos o número de médicos por especialidade em uma unidade hospitalar

de porte médio, veremos que esse número é consideravelmente menor do que o

enfermeir

os. Esse fato torna a alocação dos médicos uma tarefa mais simples de se realizar.

Nessa dissertação, no entanto, estamos preocupados em resolver uma situação particular

existente na cidade de Manaus, capital do Estado do Amazonas, que passaremos a expor em

breves linhas. A prestação dos serviços médicos às Unidades Hospitalares da rede pública

estadual da cidade de Manaus é realizada, predominantemente, através de cooperativas

médicas. Atualmente, dois mil médicos prestam serviço ao estado do Amazonas através das

cooperativas médicas, como cooperativa dos pediatras, dos anestesistas, dos neurocirurgiões,

etc.

Essas cooperativas apresentam um número de profissionais que se situa numa faixa

entre 50 e 200, que prestam serviços a aproximadamente 20 unidades hospitalares ligadas à

rede pública estadual, que incluem maternidades, unidades de emergência, etc.

A forma de prestação de serviços é através de plantões, que são expedientes de trabalho

que se estendem por 6h, 8h ou 12h, período esse que depende da co

operativa envolvida.

O trabalho desenvolvido nessa dissertação visou a proposta, o projeto e o

desenvolvimento de uma ferramenta computacional inteligente que, considerando o rol de

restrições características das cooperativas médicas, permitisse a alocação mensal desses

profissionais nas unidades de saúde estaduais públicas do estado do Amazonas.

Na literatura, muitos trabalhos abordam a alocação e o planejamento de recursos na área

de saúde. Em Valouxis et. al. (2003) apresenta-se uma solução para o problema de alocação

de enfermeiras utilizando programação linear inteira. Em Oddi (2000) os autores encaram o

desafio de solucionar o problema de alocação de recursos médicos frente à necessidade de um

gerenciamento dinâmico e incerto, onde as restrições mudam repentinamente devido a

necessidades médicas. A solução encontrada pelos autores foi propiciar uma alocação

interativa de recursos, onde o profissional interage com o sistema na busca de uma melhor

solução.

Problemas de alocação de recursos humanos podem

ser encarados como

uma questão

satisfação de restrições (R

USSEL

L, 2004). Uma alternativa para resolução desses problemas

é utilizar-se o algoritmo de busca retroativa. Outra opção é fazer uso de métodos de busca

locais, como, por exemplo, o método de conflitos mínimos. Uma desvantagem deste último,

no entanto, é que o mesmo pode trabalhar indefinidamente em busca de uma solução, mesmo

que não seja possível obtê-la. Já o método de busca retroativa, na medida em que explora de

forma exaustiva o espaço de estados, tem a capacidade de concluir sobre a existência ou não

de uma solução. Quando uma solução existe, no entanto, o algoritmo de conflitos mínimos

encontra

-a num tempo muito rápido quando comparado ao tempo obtido com o método de

busca retroativa puro. Para alguns problemas clássicos de inteligência artificial, mostrou-

que a utilização do algoritmo de busca retroativa associado a heurísticas apropriadas apresenta

um desempenho semelhante ao algoritmo de conflitos mínimos (

RUSSEL

, 2004).

Nesse trabalho estamos interessados em pesquisar a utilização do algoritmo de busca

ret

roativa

para a solução do problema de alocação de recursos humanos na área de saúde

anteriormente citado. Procuramos caracterizar o uso de diversas heurísticas clássicas já

propost

as na literatura, bem como propor outras heurísticas que denominamos de especiais.

Afora isso, ocupamo-nos também da modelagem matemática das restrições inerentes ao

contexto do problema. A modelagem lógica do sistema foi realizada através da linguagem

UML

. A implementação do sistema através de uma linguagem voltada para a

WEB

foi outra

preocupação do trabalho. Por fim, o desempenho de diversas heurísticas foi avaliado e a

melhor configuração de heurísticas foi util

izada para simulação de um caso

real.

1.1 O

bjetivo Geral

Modelagem e caracterização do uso algoritmo de busca retroativa para solução de

problemas de alocação de recursos humanos na área de saúde com restrições (PSRs),

comparando o desempenho do método de força bruta com as heurísticas: de V

alores Restantes

Mínimos

- VRM, Verificação Prévia e a combinação de ambas, na solução do problema de

alocação de recursos humanos em unidades de saúde.

1.2 O

bjetivos

specíficos

Propor uma heurística especial para uso com o algoritmo de busca retroativa na

alocação de recursos humanos na área de saúde;

Comparar o desempenho do algoritmo de busca retroativa puro com outros algoritmos

que utilizam a busca retroativa associada às heurísticas de grau, de verificação prévia e

valores restantes mínimos e com a

heurística especial proposta;

Modelar matematicamente um conjunto de restrições para as demandas específicas da

atividade de alocação de recursos humanos em unidades de saúde, permitindo o

estabelecimento de prioridades para esse conjunto de restrições;

Modelar logicamente um aplicativo com interface amigável que

permita

trabalhar com

restrições programáveis, garantindo uma grande flexibilidade ao sistema de alocação de

recursos humanos proposto;

Modelar uma base de dados para armazenamento dos dados necessários ao estudo

proposto;

Adaptar o algoritmo de busca ret

roativa

, permitindo ao mesmo trabalhar com

restrições priorizadas;

Implementar um sistema para alocação de recursos humanos que permita verificar a

aplicação dos conceitos e propostas dessa dis

sertação em um caso real.

1.3 Estrutura da Dissertação

Esta dissertação está organizada em cinco capítulos, dentre os quais este é o primeiro.

O Capítulo 2

refere

à revisão bibliográfica. Nesse, apresentamos em uma tabela o

resumo das características de trabalhos revisados na literatura, onde sumariamos a técnica

empregada pelos autores para a alocação, a aplicação pretendida, o tipo de

modelagem/linguagem utilizada no desenvolvimento e se a ferramenta desenvolvida admite

ou não a programação das restrições. Além disso, escolhemos, para uma abordagem mais

aprofundada, três dos trabalhos apresentados nessa tabela. Estes trabalhos escolhidos tratam

da alocação automática

de recursos humanos da área de saúde

apítulo

3 refere

metodologia da di

ssertação;

onde

apresenta

mos

a modelagem

matemática do problema, a modelagem computacional do sistema e detalha

mos

funcionamento das heurísticas utilizadas neste projeto

A modelagem matemática,

anteriormente citada, refere-se à modelagem das restrições de um

problema

de alocação de

recursos humanos na área de saúde. Na modelagem computacional; apresenta

mos

diagramas

de UML do aplicativo implementado para validação da proposta metodológica dessa

dissertação. As heurísticas apresentadas correspondem a heurísticas clássicas já publicadas na

literatura e a uma heurística especial proposta como contribuição dessa dissertação de

mestrado.

O Capítulo 4 apresenta os experimentos realizados para caracterização do uso das

heurísticas, apresenta um estudo de caso da

aplicação da ferramenta desenvolvida na alocação

de profissionais de cooperativas médicas do estado do Amazonas. Nesse capítulo também é

feita a discussão dos resultados

Finalmente, o Capítulo 5 apresenta as conclusões, discute as contribuições do trabal

desenvolvido e apresenta sugestões de trabalhos futuros.

evisão

ibliográfica

Solucionar problemas de alocação de recursos humanos de forma manual exige

frequentemente um tempo considerável. Devido a isso, muitas pesquisas vêm sendo rea

lizadas

nas últimas décadas para propiciar ferramentas computacionais que permitam a realização

dessa tarefa de forma automática.

Existe uma grande variedade de domínios de problemas de alocação de recursos.

Através de uma avaliação dos artigos publicados

na última conferência PATAT (

Practice and

Theory of Automated Timetabling) realizada no período de 18 a 22 de agosto de 2008, na

cidade de Montreal, os domínios desses problemas se estendem às seguintes áreas: geração de

horários de ligas de esportes, de empregados, de transporte, acadêmico, na alocação de

recursos humanos na área de saúde, etc. Na tabela 1 faz-se uma apreciação de alguns artigos

publicados ao longo dos anos no período que se estende de 1995 a 2008, considerando as

seguintes variáveis de comparação: Ano de publicação, autores, método proposto, se admite

ou não a configuração das restrições e a aplicação pretendida para a ferramenta desenvolvida.

Como pode ser visto, as técnicas de alocação são bem variadas, utilizando desde algoritmo

genéti

co até programação linear. Por outro lado, pode ser verificado que nem todos os

trabalhos permitem a programação das restrições. Dentre os que permitem, está o trabalho

proposto nessa dissertação de mestrado. Neste capítulo analisaremos algumas abordagens

utilizadas para solucionar problemas de alocação de recursos humanos publicadas na literatura

e apresentados nessa tabela. Procuramos selecionar artigos que tratam do tema de alocação de

recursos humanos na área pertinente a essa dissertação: A área de saúde. Os artigos

examinados foram: Programação de restrições para escalonamento de enfermeiras (W

EIL

., 1995); uma modelagem em duas fases com algoritmos genéticos para o problema de

escalonamento de enfermeiro (T

SAI

et al., 2009) e uma abordagem baseada em busca tabu

para o problema de escalonamento de enfermeiros (O

UGHALIME

et al

., 2008).

Tabel

1.1

–

Artigos publicados

Ano de

publicação

Autores

Título

Técnica

de Alocação

Admite

configuraçao

das restrições

Tipo de modelagem/

Linguagem

Aplicação

1995

Georges Weil, Kame Heus,

Patrice Francois and Marc

Poujode

Constraint Programming for

Nurse Scheduling

Programação de Restrição

Não

Técnica de programação

orientada a Objeto/

Le-Lisp e C ++

Employee Timetabling

2008

Ahmed Oughalime, Wan

Ismail, Liong Yeun

A tabu search approach to

the nurse scheduling problem

Busca Tabu

Sim

Employee Timetabling

2009

Chang-Chun Tsai,

Sherman Li

A two-stage modeling with

genetic algorithms for the

nurse scheduling problem

Algoritmos Genéticos

Parcialmente

Análise de sistemas UML/-

Employee Timetabling

2003

A. Anagnostopoulos,

L. Michel,

P. Van Hentenryck,

and Y. Vergados

A Simulated Annealing

Approach to the Traveling

Tournament Problem

Algoritmo Simulated

Annealing

Não

Local Search - Simulated

Annealing Algorithm/-

Escalonamento de

Torneios Esportivos

2008

Soolmaz Massoodian,

Afsaneh Esteki

A Hybrid Genetic Algorithm

for Curriculum Based Course

Timetabling

Algoritmos Genéticos

e Busca Local

Não

Geração de horários

de cursos

2008

Michael Clark, Martin Henz,

and Bruce Love

QuikFix - A Repair-based

Timetable Solver

Solução baseada em SAT

Sim

Técnica de programação

orientada a Objeto/-

Geração de horários

em escolas

2004

Hadrien Cambazard,

Fabien Demazeau,

Narendra Jussien

and Philippe David

Interactively solving school

timetabling problems using

extensions of constraint

programming

Programação de Restrição

Sim

Técnica de programação

orientada a Objeto/Java

Geração de horários

em escolas

2006

Fadi Aloul, Bashar Al-

Rawi*, Anas Al-Farra,

Basel Al-Roh

Solving Employee Timetabling

Problems Using Boolean

Satisfiability

Programação Inteira Linear

Sim

-/Visual Basic

Employee Timetabling

1998

Kathryn Dowsland

Nurse scheduling with tabu

search and strategic oscillation

Busca Tabu e Solução

Estratégica

Não

Employee Timetabling

2009

Dayse Rocha,

Cícero Costa,

Marly Costa

Alocação de recursos humanos

em unidades de saúde através da

técnica de Problemas Sujeito a

Restrições: Proposta de uso de

restrições programáveis e Análise

de desempenho de heurísticas.

Problema de Satisfação

de Restrição

Sim

Modelagem orientada

a objeto/Java

Geração de escala de

plantonistas

em unidades de saúde

2.1 Artigo 1: Programação de restrições para escalonamento de enfermeiros

O serviço de escalonamento de enfermeiros consiste em distribuir os recursos

humanos da equipe de enfermagem sobre um dado período, respeitando certo número

de regulamentações trabalhistas, políticas do hospital, preferências pessoais e o bom

senso. Uma escala num período fixo (2, 4, ou 6 semanas) que especificam dias e turnos

de trabalho e dias de folga é associada a cada membro da equipe de enfermeiros na

modelagem do problema do artigo.

Um hospital é composto por vários departamentos. Cada

possui uma ou mais

equipes de enfermeiros chamadas de unidades médica

s funcionais.

Geralmente, uma unidade opera 24 horas por dia, sete dias na semana, com cada

dia divi

do em três períodos: manhã (D) de 8 horas, tarde (E) de 8 horas e noite (N) de

10 horas.

2.1.1

Restrições

As restrições que interferem na geração do escalonamento são definidas como

compulsórias ou opcionais.

As regulamentações trabalhistas e as políticas do hospital são consideradas como

restrições compulsórias. A lista a seguir apresenta alguns exemplos de restrições desse

tipo:

- Um enfermeiro não pode trabalhar mais de sete dias consecutivos. Se algum

enfermeir

o trabalhar sete dias consecutivos

ele deve ter, pelo menos, dois dias de folga.

- Um enfermeiro não deve trabalhar mais de quatro noites consecutivas. Caso isto

ocorra, e

ste deve folgar por pelo

menos dois

dias.

- Se um enfermeiro trabalhar à noite, ele não deve trabalhar nem no turno da

manhã, nem no turno da tarde do dia seguinte.

As restrições opcionais se baseiam, na maioria das vezes, em preferências

pessoais, e, estas podem ser violadas. A l

ista a seguir apresenta alguns exemplos:

Um en

fermeiro não deveria trabalhar dois

finais de semana consecutivos.

- Um enfermeiro não pode ter um dia de folga isolado, por exemplo, (1 0 1), onde

1 = trabalhando, e 0 = de folga.

Um enfermeiro não pode te

r um dia de trabalho isolado, por exemplo

(0 1 0).

A programação de restrição está situada na intersecção da inteligência artificial com a

pesquisa operacional. Essa última área do conhecimento soluciona problemas

combinacionais complexos, como escalonamento, planejamento, alocação de recursos,

problema de sequ

enciamento de carro, etc.

Mais formalmente, a programação de restrição consiste em resolver uma classe de

problemas chamada de problema de satisfação de restrições (PSR); que é definida pela

tupla (X

, D, C), onde:

X = {x

, ..., x

} um conj

unto de n variáveis do problema;

D = {d

, ..., d

} um conjunto de n domínios; cada variável x

recebe um valor

pertencente a d

;

C = {c1, ..., c

} um conjunto de m restrições onde c

é uma restrição que assume

valo

res entre (x

, ..., x

Resolver um PSR significa encontrar uma instância (ou todas as instâncias), V,

para cada variável de X de forma que:

))

(

),...,

((;

)(;

iii

xVxVcCc

dxVXx

é satisfeito.

Este método permite a dissociação da modelagem do problema (variáveis e

res

trições) do algoritmo usado para solucionar o problema.

Ao se tratar de PSR com domínios finitos, várias técnicas podem ser combinadas

para encontrar uma solução para o problema. As técnicas geralmente usadas são: gerar e

testar, retrocesso puro,

forward c

hecking

, e

looking ahead

2.1.2

Solucionando o problema

Na implementação do problema foi utilizada a biblioteca, do

Lisp

e C++, Ilog-

Solver

. A principal função dessa ferramenta é integrar a programação de restrição com

um ambiente de programação completo que inclui uma linguagem orientada a objeto,

programação funcional e estruturada, programação não determinística (como Prolog), e

bibliotecas gráficas.

Ilog

Solver

fornece uma classe de objetos chamada “ct-var”, que representam

as variáveis com restrição. Estas variáveis podem receber valores de qualquer tipo:

cadeia de caracteres, inteiros, números racionais, números reais, datas e outra

estruturas de dados arbitrário

Além disso, no

Ilog

Solver

, um objeto pode ser usado como uma variável restrita,

e que uma restrição pode ser definida ao nível de classe, onde todas as instâncias da

classe compartilham a mesma restrição.

Para a modelagem do problema, houve a combinação da programação a objetos e

a técnica de programação de restrição.

Foram definidas as classes “enfermeiro”, que possui os seguintes atributos:

informações sobre a identidade do enfermeiro (nome, título, etc.); e as variáveis restritas

usadas para gerar a escala.

Definir a escala num período de 14 dias significa preencher o quadro a segui

especificando para cada enfermeiro os dias de trabalho e turno, e dias de folga (figura

1).

seg1

ter1

qua1

qui1

sex1

sab1

dom1

seg2

ter2

qua2

qui2

sex2

sab2

dom2

N-1

1 1 1 1 0 0 0

N-2

2 2 2 2 2 2 2

N-3

3 3 3 3 0 0 0

N-N

1 1 0 0 1 1 1

…………

Figura

2.1

–

Escala

dos enfermeiros

Um quadrado da figura pode ter um dos seguintes valores: 0 (folga), 1 (turno da

manhã), 2 (turno da tarde) e 3 (turno da noite).

Uma linha

da figura

contem

14 quadrados

que

corresponde a cada dia.

Logo, na classe “enfermeiro” são introduzidas 14 variáreis restritas, cada uma

correspondendo a cada dia na escala, o domínio dessas variáveis é (0 1 2 3). O código a

seguir define essas variáveis.

(defctclass nurse

name

surname

(mon

I (ct

var I 2 3 0) constrained)

(tue

I (ct

var 1 2 3 0) constrained)

(sat

(ct

var 1 2 3 0) constrained)

(sun

2 (ct

var I 2 3 0) constrained))

As restrições relativas aos enfermeiros são chamadas de classes de restrições, e

são consideradas no nível de classe, “enfermeiro”, definida acima.

Como exemplo será

analisa

da a seguinte

restrição

: “um enfermeiro não pode

trabalhar mais de sete dias consecutivos. Se algum enfermeiro trabalhar

sete

dias

consecutivos, ele deve ter, pelo menos, dois dias de folga” .

Essa restrição é considerada

em cada série de

nove

dias. Se na atribuição dos

primeiros sete só existir valores 1 ou 2,

então, os últimos dois dias serão iguais a zero (0). Este teste é feito todas as vezes que

os primeiros sete dias recebem valores. Este passo é possível no Ilog-Solver definindo-

se uma nova restrição, cuja regra d

e propagação é descrita como:

(defctconstraint seven

days

sucs

(day

I day

...

day

(when (day

a) (day

...

(day

test

( if a, b, c, d, e , j g

I or 2

)

assert (day

0) (day

)).

O algoritmo usado para buscar uma solução para

o problema é:

Begin

While remaining variables not

assigned to any value

choose the variable which has the smallest domain (v*)

choose a value (d*) in the domain

assign v* to d*

propagate the predifined constraints

if there is a fail (the do

main

any variable becomes empty) then

Backtrack

endif

endwhile

end

Como pode ser visto nesse código, a heurística de valores restantes mínimos,

VRM

, é utilizada durante a escolha da variável a ser atribuída, uma vez que a variável

com o menor domínio é selecionada. Mais adiante, no capítulo de metodologia, essa

heurística será definida com mais propriedade.

A busca por uma solução para o problema pode ser feita de várias maneiras:

solução manual, solução automática, solução semi-automática, e solução nos casos da

ocorrência de ausência. O sistema pode também indicar a não existência de soluções e o

usuário pode, então, relaxar algumas restrições ou modificar alguns valores.

2.1.3

Resultados do processamento

Segundo os autores, a implementação dessa modelagem para a solução do

problema de escalonamento de enfermeiros apresentou resultados satisfatórios.

2.2

Artigo2: Uma modelagem em duas fases com algoritmos genéticos para o

problema de escalonamento de enfermeiro.

Nesse artigo o problema de escalonamento de enfermeiros é solucionado

utilizando a abordagem de algoritmos genéticos.

Algoritmos genéticos podem resolver problemas de otimização com múltiplas

variáveis (Mitchell, 1998), além de poder executar processamento paralelo, que pode,

efetiva

mente, economizar tempo de processamento. O artigo em questão trata do

desenvolvimento de uma abordagem diferente por integrar a abordagem de

programação matemática com algoritmos genéticos para solucionar o problema de

escalonamento de enfermeiros.

2.2.1

Desenvolvimento do modelo

No artigo, foram consideradas as políticas do hospital, direitos trabalhistas e

preferências dos enfermeiros num modelo matemático de duas fases. Na primeira fase

os dias de trabalho e folga do enfermeiro são organizados em um mod

elo que possibilita

a utilização do algoritmo genético para organização da escala com a verificação

simultânea da violação de alguma restrição. Na segunda fase, são definidos os turnos

dos dias em que o enfermeiro trabalhará, sendo o algoritmo genético usado na busca da

melhor escala.

No modelo proposto para as folgas dos enfermeiros procura-se minimizar a

seguinte função de aptidão:

Min G = b

Y + b

(1)

Na equação (1) b

e b

são parâmetros ajustáveis. O sistema pode configurar os

valores de b

e b

de acordo com as características de cada caso. As variáveis Y e Z são

definidas através das seguintes expressões:

ORY

Ni Tt

itit

(2)

NRNRZ

Ni Tt

(3)

A equação (2) é a razão da incompatibilidade entre a escala definida pelo sistema

e a escala desejada pela equipe. Quando a escala do sistema não equivale a escala

definida pela equipe então,

itit

= 1, do contrário

itit

= 0. Onde, N é o

número total de enfermeiros e T é o total de dias do período da es

cala. As variáveis R

são definidas da seguinte forma:

No modelo proposto procura-se distribuir as folgas nos domingos e feriados

nacionais da forma mais equânime possível. Esse objetivo é alcançado através do termo

Z da

equação

(1), explicitado na equação (3). A equação (3) expressa a variância dos

dias em que os enfermeiros têm folga aos domingos e feriados na escala definida pelo

sistema. Nessa equação a variável T1 é o conjunto formado por domingos e feriados

nacionais

do período da escala.

A equação (4) a seguir apresenta um exemplo de restrição da primeira fase, que

representa que o número total de enfermeiros de folga por dia não pode exceder o

número que é permitido pelas regras do hospital (P

TtPR

;

(4)

caso contrário

0: caso contrário

1: se o i

ési

mo plantonista está escalado para ter o t

ésimo dia de folga na

escala do sistema

1: se o i

ésimo plantonista está escalado para ter o t

ésimo dia de

folga na escala da equipe.

No modelo proposto para as folgas dos enfermeiros procura-se minimizar a

seguinte função de aptidão:

Min G = b

X + b

V + b

(5)

Na equação (1) b

e b

são parâmetros ajustáveis. As variáveis X, V e W são

definidas através das seguintes expre

ssões:

NDNDX

Ni Tt

(6)

NNNNV

Ni Tt

(7)

NMDEME

Ni Tt

itititititit

(8)

As equações (6) e (7) são variâncias do número de turnos diurnos e noturnos

atribuídos à equipe. Elas são adicionadas à função de aptidão para melhorar a

unif

ormidade dos turnos diurnos e noturnos para cada enfermeiro na escala gerada pelo

sistema.

, na equação (6) indica se o i-ésimo enfermeiro está trabalhado no turno diurno

do t-ésimo dia (1, se estiver trabalhando e, 0 caso contrário). N

indica se o i-

ésimo

enfermeiro está trabalhado no turno noturno do t-ésimo dia (1, se estiver trabalhando e,

0 caso contrário).

A equação (8) representa a razão da inconsistência entre a escala definida pelo

sistema e a escala desejada pela equipe. Nessa equação E

indica se o i-

ésimo

enfermeiro está trabalhando no turno diurno na escala definida pelo enfermeiro no t-

ésimo dia (1), se estiver trabalhando e, (0) caso contrário. M

indica se o i-

ésimo

enfermeiro está trabalhando no turno noturno na escala definida pelo enfermeiro no t-

ésimo dia (1, se estiver trabalhando e, 0 caso contrário). Quando a inconsistência ocorre

entre a escala definida pelo sistema e a escala definida pela equipe, resulta em |E

– D

= 1 e, também, |M

| = 1. Portanto, o valor resulta

nte deve ser dividido por 2.

A equação (9) a seguir, apresenta um exemplo de restrição da segunda fase, que

representa que o número de enfermeiros alocados para o turno diurno deve exceder o

número mínimo requerido pelo hospital. Onde Dt indica o número mínimo de

enfermeiros no turno diurno no t-ésimo dia, e T é o número total de dias do período da

escala.

TtDD

;

(9)

2.2.2 Modelo do algoritmo de solução e processo

O estudo do artigo divide a operação de alocação de enfermeiros em dois

mod

elos: escala de dias de trabalho e folga e os turnos dos dias de trabalho do

enfermeiro. As seções a seguir tratam dos algoritmos de solução e processo desses dois

modelos.

Os processos de resolução para o modelo de escala de folga são listados a seguir:

(1) Codificação: na operação de escala de trabalho e folga, os enfermeiros

organizam primeiramente suas escalas de folga. Essa escala é armazenada em uma

string

para representar os cromossomos, um dos elementos necessários na execução de

algoritmos genéticos. Os genes em todos os cromossomos são divididos em cinco tipos:

“A

-J” que representa a prioridade para os dias de folga desejados pelos enfermeiros (A,

mais alta prioridade e B, mais baixa prioridade), “1” representa turno diurno, “2” turno

noturno, “3”

representa folga especial, “5” representa dias sem atribuição.

(2) Função de aptidão: a função de aptidão dessa fase é definida pela equação (1).

(3) Processo de escalonamento: o processo para escalonamento de dias de

trabalho e folga começa com a carga das escalas definidas pelos enfermeiros dos

arquivos e a criação da população inicial. Então, o sistema verificará se a população

inicial viola alguma das restrições. Se violar, o processo de modificação será executado.

Se não violar, a função de aptidão será calculada e será comparada com as condições de

finalização. O sistema continuará a evoluir a população através de processos como

mutação, modificação e verificação das restrições para avaliar se as condições de

término foram atingidas. E, finalmente a decodificação dos cromossomos será

processada para criar uma escala satisfatória.

Após solucionar o modelo de escala dos dias de trabalho e folga, o próximo passo

será o processo de solução para o modelo dos turnos da escala dos enfermeiros. Este

consiste do

s seguintes passos:

(1) Codificação: nesta etapa, é adotado o mesmo método de codificação usado na

primeira fase. A única diferença é que, o sistema lida com genes cujas

strings

são

formadas por “1” (turno diurno) ou “2” (turno noturno).

(2) Função de apti

dão: a equação (5) é a função de aptidão desse modelo.

(3) Procedimentos de processamento: nesta etapa, os procedimentos de

processamento consistem dos seguintes passos:

crossover

, seleção, verificação da

consistência dos resultados e, caso estes não sejam consistentes, a realização de

modificação é necessária.

O sistema computacional foi desenvolvido de acordo com o método de análise

UML. Este consiste de três casos de uso: (1) cadastro de escala definido pelos

enfermeiros, (2) otimização da escala e (3) c

onsulta de escala e modificação.

Após a adição dos componentes de banco de dados ao sistema, este pôde ser

dividido em três módulos: (1) interface com o usuário, (2) módulo de otimização do

algoritmo genético e, (3) banco de dados do sistema de escala.

Est

e artigo apresenta uma solução para o problema de escalonamento de

enfermeiros que permite a configuração de algumas restrições, que se restringem as

preferências pessoais dos enfermeiros, entretanto, as restrições originadas da política do

hospital e das leis trabalhistas, ficam definidas de maneira estática no código, ou seja,

não há uma rotina que possibilite

usuário

alter

ação

sas restrições, ficando esta

atividade a cargo da equipe responsável pela manutenção do software

2.3

Artigo 3: Uma abordagem baseada em busca tabu para o problema de

escalonamento de enfermeiros

Essa abordagem tenta desenvolver um sistema computadorizado que utilize,

efetivamente, o pessoal da equipe de enfermagem. O sistema também trata da equidade

na organização dos horários e considera as preferências da equipe para maximizar a

satisfação de

les

com a alocação realizada.

O problema consiste na escala de n enfermeiros por um período de duas semanas.

Um dia de trabalho possui três turnos, manhã, tarde e noite. O turno da man

hã

inicia

às 7:00 e vai até às 14:00, o turno da tarde

inicia às 14:00 e vai até às 21:00 e o turno

da noite

inicia às 21:00 e vai até às 07:00.

2.3.1 Restrições do problema

O problema tratado no artigo contém um total de 12 restrições. Não é e

sperado

que todas as restrições sejam satisfeitas. Devido a isso, estas são divididas em restrições

obrigatórias,

e restrições opcionais, que podem ser violadas.

As restrições obrigatórias são representadas pelas regras do hospital. E

las

devem

ser satisfei

tas, caso contrário, a escala será considerada inaceitável.

São exemplos de restrições obrigatórias:

- assegurar que o numero mínimo de enfermeiros de plantão por turno seja

atendido;

- deve-se alocar cada enfermeiro somente a um turno por dia, e, caso este trabalhe

no turno noturno, assegurar que e

não trabalhe no turno da manhã nem da tarde do dia

seguinte;

- atribuir aos enfermeiros 3 turnos noturnos seguidos por dois dias de folga.

As restrições opcionais representam as preferências dos enfermeiros, e, caso estas

não sejam satisfeitas, ainda assim, a escala é considerada uma escala aceitável.

São exemplos de restrições opcionais:

- tentar evitar que seja atribuído um turno vespertino a um enfermeiro seguido de

um turno matutino ou noturno no dia s

eguin

te;

- assegurar que cada enfermeira tenha, pelo menos, 1 dia de folga nos finais de

semana.

2.3.2

Programação por

meta

para encontrar uma solução harmoniosa se dá por meio da conversão de cada

restrição opcional num objetivo flexível em que a restrição correspondente pode ser

violada, se necessário.

No caso do problema em questão, os objetivos flexíveis são os seguintes:

G1: Minimizar a violação da primeira restrição opcional;

G2: Minimizar a violação da segunda restrição opcional;

...

GN: Minimizar a violação da n

ésima restrição opcional.

Técnicas heurísticas são bastante usadas na resolução de problemas de alocação

porque elas tendem a ser rápidas. Muitas abordagens heurísticas, entretanto, são

incapazes de produzir escalas facilmente quando um grande número de restrições está

presente. Dentre estas heurísticas, a busca tabu tem se mostrado ser muito efetiva numa

variedade de problemas.

2.3.3

Solução do Problema

O problema é formulado de forma a encontrar uma combinação de padrões de

turnos factíveis que não somente satisfaça às restrições obrigatórias, mas também

minimize a função objetivo. No trabalho do artigo, um algoritmo guloso, cuja

principal

característica é selecionar a cada passo o maior valor possível sem refazer as suas

decisões

é aplicado para obter u

ma boa solução inicial, e, então, um algoritmo de busca

tabu gera sucessivas soluções para encontrar a melhor solução para o problema.

Para começar a busca tabu, uma solução inicial deve ser preparada utilizando-se o

método guloso baseado nos quatro passos

a seguir:

Passo 1 – atribuir os turnos da noite a cada enfermeiro de modo que os requis

itos

pessoais sejam satisfeitos;

Passo 2 – atribuir os turnos da tarde a cada enfermeiro, tentando satisfazer todas

as restrições opcionais;

Passo 3

–

tentar agrupar os

turnos

vespertinos de cada enfermeiro;

Passo 4 – atribuir todos os turnos da manhã, tentado satisfazer as restrições

opcionais.

O algoritmo de busca tabu explora o espaço de soluções utilizando uma

combinação de três tipos de vizinhança. A primeira vizinhança N(S) é baseada em

padrões de atribuição dos turnos da noite, e, um movimento factível é definido como

qualquer mudança na atribuição desses padrões aos enfermeiros. A segunda vizinhança

N(A) é baseada no turno da tarde. O tamanho desta vizinhança é reduzido para

direcionar a busca tabu numa região promissora do espaço de solução. Essas duas

vizinhanças são combinadas para gerar uma solução parcial. A terceira vizinhança N(M)

envolve

a mudança de escala a escala por meio da alteração dos padrões de turn

matutino de um único enfermeiro ou mais de um enfermeiro por um único turno ou

mais.

O algoritmo de busca tabu inicia com a geração de uma nova solução; este gera

uma solução parcial e uma solução completa. Cada vez que o algoritmo gera uma

solução a intensificação é realizada. A estimação da solução será realizada somente

após a intensificação para evitar teste de soluções não promissoras.

O algoritmo de busca tabu explora a vizinhança da manhã da solução corrente,

primeiramente; se após p interações nenhuma melhora na solução é obtida uma

diversificação usando a vizinhança da tarde é realizada. A diversificação gera uma nova

solução parcial que é usada para explorar sub-domínios na vizinhança da manhã que

não pode ser obtida de outra maneira. Após a realização da diversificação baseada no

turno da tarde, o algoritmo explora a vizinhança da manhã da nova solução corrente. Se

após q diversificações na vizinhança da tarde não houver nenhuma melhora na solução,

uma diversificação usando os padrões atribuição dos turnos da noite é aplicada. Após a

diversificação baseada nos padrões de atribuição dos turnos da noite, o algoritmo

reinicia do ponto inicial. Se após r diversificações nos padrões de atribuição dos turnos

noturno

não houver nenhuma melhora, o algor

itmo é parado.

Há três listas-tabu associadas aos três tipos de vizinhanças. A primeira lista-

tabu

(S) mantém na memória as combinações dos padrões de atribuição dos turnos da noite.

A segunda lista mantém na memória as combinações de turno da tarde visita

das.

E, a

terce

ira lista (W) mantém na memória

as soluções visitadas.

O critério de aspiração permite à busca sobrescrever o

status

tabu da solução e,

também, proporcionar retrocesso de soluções recentes conforme estas caminhem por um

novo caminho em dire

ção a uma melhor solução.

Para a busca tabu, dois critérios de parada são considerados. Se após r

diversificações na vizinhança do padrão de atribuição dos turnos noturnos não houver

nenhuma melhora o algoritmo pára. E, o algoritmo é finalizado se este alcançar o

número máximo de interações definidas pelo usuário.

A qualidade da escala pode ser medida pelo número de violações para cada

objetivo. Uma escala ótima é aquela com nenhuma violação.

2.3.4 Resultados obtidos

De acordo com os resultados apresentados pelo artigo, o algoritmo obteve boas

soluções para o problema da geração da escala, e, o tempo de execução ficou em menos

de um minuto.

METODOLOGIA

O problema de alocação de recursos humanos em unidades de saúde consiste em

distribuir plantonistas nas vagas disponíveis das unidades de tal maneira que esta

distribuição obedeça a um conjunto de restrições definidas previamente pelo

profissional responsável por esta tarefa.

Nessa dissertação procuramos resolver esse problema formulando o mesmo como

um problema de satisfação de restrições (

RUSSEL

L, 2004). Para a solução utilizou-se o

algoritmo de busca retroativa associado a heurísticas.

A formulação de um problema de satisfação de restrições pressupõe a existência

de um modelo onde são definidas as variáveis do problema, seus domínios associados e

as restrições que se pretende definir sobre essas

variáveis. Inicialmente, nesse capítulo

de metodologia, pretende-se apresentar essas definições dentro de um formalismo

matemático original.

Em seguida é apresentado o algoritmo de busca retroativo e as heurísticas

associadas com a aplicação do mesmo. No rol das heurísticas utilizadas nesse trabalho,

ao lado de heurísticas já consagradas, propôs-se a utilização de uma heurística especial,

que, como será visto no capítulo de resultados, apresentou o melhor desempenho em

termos da complexidade no tempo.

Em termos práticos essa dissertação envolveu o projeto, modelagem e

implementação de um sistema computacional flexível para a alocação de recursos

humanos na área de saúde, que embutisse na sua concepção a formulação matemática

desenvolvida para as restrições e que propiciasse a utilização do algoritmo de busca

retroativa

associado às heurísticas que apresentaram os melhores resultados em termos

de complexidade no tempo. A principal característica do sistema computacional

desenvolvido

é possibilitar ao usuário uma programação das restrições a serem

utilizadas em um problema de agendamento. Essa característica permite que o sistema

computacional seja moldado para aplicações distintas. Na

sequ

ência

do capítulo, serão

apresentados os pressupostos sobre os quais foi projetado esse sistema computacional,

a modelagem através da orientação a objetos, ressaltando a apresentação de diagramas

de casos de uso, diagrama de classes, diagrama de objetos e diagrama de sequência, e

por fim, aspectos da interface visual apresentada ao usuário.

1. Modelo do problema

O modelo de um problema de satisfação de restrições é constituído por um

conjunto de variáveis do problema, pelo domínio dessas variáveis e pela caracterização

das restrições utilizadas.

1.1. Variáveis do problema

Para a definição das variáveis de um problema de alocação de recursos humanos

em uma unidade de saúde é necessário que seja entendido o contexto da aplicação. Em

um sistema de saúde, o trabalho é normalmente dividido em plantões, distribuídos em

turnos de 8, 12 ou 24 horas, ao longo de um mês. Além disso, existem várias unidades

de serviço, cada uma com necessidades especiais em termos de vagas de plantonistas

por turno. Antes de iniciar a solução de um problema de alocação de recursos humanos

na área da saúde é necessário então que estejam bem definidas: a duração de um turno,

as unidades envolvidas na alocação e o número de vagas de plantonistas necessárias em

cada unidade. Além disso, é mister que se defina o conjunto de plantonistas disponíveis

para esse problema de alocação.

Assim sendo, definem-se como o conjunto das variáveis do problema as

dimensões de uma matriz, M(d,t,h,v), denominada de matriz de alocação. As quatro

dimensões da matriz M são: o dia do mês (d), o turno (t), a unidade de serviço (h) e a

vaga de plantão (v). Dessa maneira, as dimensões da matriz, também denominadas de

variáveis do problema, são representadas pela quádrupla (d, t, h, v). Os elementos dessa

quádrupla podem assumir os seguintes valores:

–

dia do mês.

}

,...,

3,2,1{

nDd

, onde

= 31.

–

turno,

,...,

21 n

tttTt

, onde

corresponde ao primeiro turno da unidade e

ao último turno.

– unidade de serviço,

,...,

21 n

hhhHh , onde n

representa o número de

unidades de serviço.

– vaga de plantão,

,...,

21 n

vvvVv , onde n

representa o número de

plantões por unidade de serviço.

Cada elemento M(d

, t

, h

, v

) da matriz de alocação é denominado de unidade de

alocação. O conjunto de plantonistas disponíveis para alocação em cada unidade de

aloc

ação é denominado de domínio dessa unidade de alocação. Assim, o domínio de

uma unidade de alocação é definido como:

,...,

21 n

pppP

, onde

representa o número total de plantonistas.

A atribuição de um valor a todos os elementos da matriz de alocação M,

representada por M(d

) = p

, é definida como um estado do problema.

1.2. Restrições

As restrições definidas neste trabalho podem ser agrupadas nas seguintes

categorias:

Restrições unárias;

Restrições múltiplas.

1.2.1

Restriçõ

es Unárias

As restrições unárias impõem limites ao domínio das variáveis do problema.

Assim, para cada tripla (d

), ou conjunto das mesmas, é especificado um

subconjunto de plantonistas P

que pode ser atribuído ao domínio das mesmas. Um

subconjunt

o de triplas é definido através da especificação de subconjuntos para os

elementos

t e h. dessa forma, as restrições unárias são expressas através do seguinte

enunciado:

Para

D,,...,

,dDd

1211 x

HhhhHh

,...,,

211

, tem

que

, onde

,...,

211

PpppP

Quando mais de uma restrição unária limitar o domínio de uma tripla, o domínio

resultante é obtido através de uma operação de intersecção. Por exemplo, se C

e C

limitam o domínio da tripla (d

, t

, h

), em R

e R

, respectivamente, o domínio final é

dado por

RR .

A definição do domínio das variáveis é mostrada através do pseudocódigo na

figura

3.1

. Essa etapa ocorre antes do início da execução do algoritmo de busca.

função

DEFINIR

DOMÍNIO

VAGAS (escala)

para cada vaga em

SELECIONAR

VAGAS(escala)

faça

para cada plantonista em SELECIONAR

PLANTONISTA(escala)

faça

se plantonista é consistente com vaga de acordo

com

RESTRIÇõES-

UNÁRIAS[escala]

então

adicionar plantonista ao domínio da

aga

Figura

3.1 -

Algoritmo que define o domínio das variáveis

No estudo de caso de alocação de recursos humanos em unidades de saúde

apresen

ado

no capítulo de Resultados, encontr

amos

restrições unárias do tipo:

- Plantonistas veteranos são alocados em unidades menos complexas (

menos

críticas) e em dias úteis;

- Plantonistas novatos são alocados em unidades complexas (mais críticas) e nos

finais de semana.

1.2.2 Restrições Múltiplas

As restrições múltiplas relacionam valores atribuídos a duas ou mais t

riplas,

limitando o espectro de valores que pode ser atribuído. Enquanto as restrições unárias

atuam nos domínios das variáveis, ou seja, nos possíveis valores que podem ser

atribuídos aos elementos da matriz M, as restrições múltiplas atuam no momento da

atribuição, verificando possíveis conflitos que possam existir entre a atribuição de valor

a uma nova tripla e os valores já atribuídos a outras triplas. Enquanto a verificação das

restrições unárias precede a execução do algoritmo de busca retroativa, a v

erificação das

restrições múltiplas ocorre durante a execução desse algoritmo.

As restrições múltiplas são expressas a seguir:

“Para n subconjuntos de triplas: (d

), (d

),..., (d

), onde:

nnnnnn

HhHhHhTtTtTtDdDdDd ,...,,;,...,,;,...,,

221122112211

, com

PpPpPp ,...,,

2211

, tem

se que

PPP ...

No estudo de caso de alocação de recursos humanos em unidades de sa

úde

apresentado no capítulo de R

esultados, encontr

amos

restrições múltiplas do tipo:

Um plantonista não pode ser alocado p

ara duas vagas no mesmo horário.

Um plantonista não pode dar três plantões seguidos.

2. Algoritmo de Busca

Para facilitar a busca por soluções, os problemas de alocação de recursos humanos

podem ser organizados como um espaço de estados em uma árvore [

Deris

et al, 2000],

como mostrado na figura

3.2

. Os níveis da árvore correspondem às vagas, e cada nível j

tem

m filhos que correspondem a m possíveis atribuições à v

, 1

n. A solução do

problema passa a ser dada por um vetor solução [v

, v

, ..., v

] representando o caminho

do nó raiz aos nós das folhas. Como todo nó, a princípio, tem o mesmo número de

filhos em todos os níveis, o total do espaço de possíveis soluções é m

. Para um mesmo

problema de alocação existem várias soluções e métodos distintos para encontrar essas

soluções. Nesse trabalho opt

amos

pela utilização do algoritmo de busca retroativa. A

escolha do mesmo deveu

se as seguintes razões: É um algoritmo de fácil implementação

computacional; permite trabalhar com diversas heurísticas que aceleram o seu

desempenho e permite que sejam introduzidas restrições que controlam as atribuições

de valores às variáveis da matriz de alocação. Essa última característica possibilita a

adaptação do algoritmo a qualquer problema de alocação para o qual se busca uma

solução.

Figura

3.2

–

Árvore de espaço de estado para o problema de satisfação de restrições

Na figura

3 apresenta

mos

um fluxograma do algoritmo de busca

(RUSSEL

200

4). O algoritmo detalhado, em pseudocódigo, é mostrado na figura 3

. As

principais características do algoritmo de busca retroativa são: 1) Utiliza uma

sequ

ência

crescente de atribuições parciais até chegar a uma atribuição completa; 2) Utiliza uma

função recursiva que possibilita o retrocesso quando uma atribuição parcial fal

ha.

Figura

3 –

Fluxograma do algoritmo de busca retroativa

função

PESQUISA

COM

RETROCESSO(escala)

retorna

uma solução ou

falha

retornar

RETROCESSO

RECURSIVO({}, escala)

função

RETROCESSO

-RECURSIVO(atribuição, escala)

retorna

uma

solução ou falha

atribuição é completa

então

retornar

atribuição

vaga <-

SELECIONAR

VAGA

NÃO

ATRIBUÍDA(VARIÁVEIS[escala],atribuição,escala)

para cada plantonista em VALORES-

ORDEM

DOMÍNIO(vaga,

atribuição, escala) faça

se plantonista é consistente com atribuição de acordo

com RESTRIÇõES[escala]

então

adicionar {vaga = plantonista}

a atribuição

resultado <-

RETROCESSO

RECURSIVO(atribuição,escala)

se resultado

falha

então

retornar

resultado

remover {vaga = plantonista} de atribuição

retornar

falha

Figura 3.4

–

Algoritmo de pesquisa

com

retrocesso (Adaptada de RUSSELL; NORVIG, 200

O algoritmo de pesquisa com retrocesso executa uma busca em profundidade q

escolhe valores (plantonistas) para uma variável (vaga) de cada vez e efetua o retrocesso

quando uma variável não tem valores válidos restantes a serem atribuídos.

O procedimento

RETROCESSO

RECURSIVO

chama

SELECIONAR

VAGA

NÃO

ATRIBUÍDA,

para selecionar a vaga a ser atribuída e

VALORES

ORDEM

DOMÍNIO

para obter valores (plantonistas) para a vaga selecionada. Após a escolha do

plantonista a ser atribuído, é verificado se tal atribuição é consistente, ou seja, se não

violará nenhuma das restrições múlt

iplas definidas para o problema. Se alguma restrição

for violada, o algoritmo retrocede para a variável instanciada mais recentemente que

ainda possuir valores a serem “testados”.

2.1. Heurísticas

Apesar do algoritmo de busca retroativa reduzir, consideravelmente, o espaço de

busca, ainda assim é necessário que o procedimento de busca com retrocesso seja

aprimorado por meio da incorporação de heurísticas. Nesse trabalho utilizamos as

seguintes heurísticas: Valores Restantes Mínimos (VRM) (KUMAR, 1992), he

urística

de grau (BAPTISTE, 200), verificação prévia (VP) (T

SANG

, 1993) e heurística

especial. Essa última é uma proposta desse trabalho de dissertação. A seguir essas

heurísticas são descritas.

2.1.1 Valores Restantes Mínimos (VRM)

A heurística VRM é usada para melhorar a busca por uma solução num PSR,

ordenando as variáveis a serem atribuídas. Como o próprio nome sugere, em cada passo

o algoritmo seleciona a variável mais restrita, ou seja, a com menor domínio. A lógica é

a de que essa variável é a que tem a maior probabilidade de em breve provocar falha,

podando assim a árvore de busca.

Por exemplo, se houver uma variável X com zero valor restante, a heurística

VRM selecionará esta variável na próxima atribuição, e a falha será detectada

imediatamente,

evitando buscas inúteis em outras variáveis.

Essa heurística foi aplicada neste projeto no momento da seleção da vaga a ser

atribuída, ou seja, no passo “Selecionar vaga não atribuída”, onde a vaga com menor

número de plantonistas no seu domínio é selecio

nada.

Uma desvantagem da aplicação dessa heurística consiste em decidir qual variável

selecionar como um ponto de partida num estado, quando todas as variáveis possuem o

mesmo número de valores em seu domínio. Esse problema foi

resolvido

neste projeto

por

meio da utilização das restrições unárias na definição dos domínios das variáveis e,

também, com a utilização da heurística de

grau, que será descrita na seç

ão a seguir.

2.1.2 Heurística de grau

A heurística de grau é responsável por selecionar a variável que está envolvida no

maior número de restrições múltiplas. No problema de alocação de recursos humanos

essa heurística foi aplicada na etapa “Classificar vagas” (figura

5), onde cada vaga

classificada

de acordo com a quantidade de restrições múltiplas em que esta está

envolvida. A vaga que contemplar o maior número de restrições múltiplas será

selecionada primeiro, reduzindo, dessa maneira, o fator de ramificação.

Utilizar

restri

ões

rias

defini

ão

dos

dom

ínios

das

vari

áveis

Selecionar

vaga

não

atribuí

Classificar

vagas

Figura

3.5

–

Adição heurística de grau ao fluxograma

do algoritmo de busca

A heurística VRM é, geralmente, um guia mais poderoso na etapa de seleção da

vaga a ser atribuída, mas a heurística de grau é muito útil como um critério de

desempate.

2.1.3 Verificação Prévia

A heurística de verificação prévia otimiza a utilização das restrições múltiplas

durante a busca. Quando um plantonista é atribuído a uma vaga X, o processo de

verificação prévia examina cada vaga não-atribuída Y que está conectada por uma

restrição múltipla a X e exclui do domínio de Y qualquer valor que esteja inconsistente

com o valor escolhido para X.

No problema de alocação de recursos humanos as restrições múltiplas que

conectam as variáveis são do tipo “diferentes”, um exemplo de aplicação dessa

heurística é apresentado na figura

6, ilustra

ndo

a resolução do problema de alocação

de recursos humanos. O problema mostrado consiste de quatro vagas. Cada vaga possui

três plantonistas em seu domínio. As restrições definidas para este problema foram: o

plantonista que ocupar a vaga 1 deve ser diferente dos plantonistas que o ocuparem as

vagas 2 e 4. Como pode ser observado, as atribuições parciais {v

= p

, v

= p

} e {v

, v

= p

, v

= p

, v

= p

}, que são atribuições inválidas não ocorrerão durante a

execução da busca, pois no momento em que é atribuído p

à v

, este valor é removido

dos domínios de v

e v

. Uma possível solução para o problema seria a atribuição {v

, v

= p

, v

= p

, v

= p

Vaga

v1 = p1 v1 = p2

v1 = p3

Vaga

v2 = p1 v2 = p2

v2 = p3 v2 = p1

v2 = p2

v2 = p3

v1 <> v2

v3 = p1 v3 = p2

v3 = p3

Vaga

v3 = p1 v3 = p2

v3 = p3

v4 = p1 v4 = p2

v4 = p3

Vaga

v1 <> v4

Figura

3.6

–

Um exemplo de aplicação da heurística de

verificação prévia

As figuras

7 e

8 apresentam as etapas onde a heurística de verificação prévia é

inserida no fluxograma e no pseudocódigo do algoritmo de busca retroativa

respectivamente.

Selecionar plantonista

Há plantonistas

dom

ínio

vaga

Atribuiç

ão

consistente?

Atribuir plantonista à

vaga

Todas

as vagas

estão

preenchidas

Sim

Retroceder

para

vaga

Não

Sim

Não

Sim

Não

Há

vaga

anterior?

Aplicar

heur

ística

verificaç

ão

évia

Restaurar

dom

ínio

vaga

Figura

3.7

–

Adição heurística de verificação prévia ao fluxograma do algoritmo de busca

função

PESQUISA

COM

RETROCESSO(escala)

retorna

uma solução ou

falha

retornar

RETROCESSO

RECURSIVO({}, escala)

função

RETROCESSO

-RECURSIVO(atribuição, escala)

retorna

uma

solução ou falha

atribuição é completa

então

retornar

atribuição

vaga <-

SELECION

VAGA

NÃO

ATRIBUÍDA(VARIÁVEIS[escala],atribuição,escala)

para cada plantonista em VALORES-

ORDEM

DOMÍNIO(vaga,

atribuição, escala) faça

se plantonista é consistente com atribuição de acordo

com RESTRIÇõES[escala]

então

adicionar {vaga = plantonista}

a atribuição

APLICAR

HEURÍSTICA

VERIFICAÇÃO

PRÉVIA(vaga,

plantonista, escala)

resultado <-

RETROCESSO

RECURSIVO(atribuição,escala)

se resultado

falha então

retornar

resultado

remover {vaga = plantonista} de atribuição

RESTAURAR

DOMÍNIO

VAGA(vaga, escal

retornar

falha

Figura

3.8

–

Pseudocódigo do algorit

mo de pesquisa

com

retrocesso com a heurística de verificação

prévia

2.1.4 Heurística Especial

A Heurística Especial proposta neste trabalho se baseia na premissa de que certos

tipos de restrições ocorrem com frequência em problemas reais e podem ser

tratados

empregando

-se algoritmos de propósito específicos, sendo estes mais eficientes que os

métodos de uso geral acima descrito.

A heurística proposta consiste na seguinte ação: Durante a etapa de seleção do

plantonista, dá-se preferência ao menos presente nos domínios das vagas e com menor

número de plantões atribuídos. Essa iniciativa reduz a probabilidade das atribuições de

todas as vagas de um determinado plantonista ser realizadas apenas no final, quando as

possibi

dades de conflito são maiores.

3. Características e Modelagem do Sistema

Para mostrar a viabilidade da aplicação do PSR e suas heurísticas na resolução do

problema de alocação de recursos humanos em unidades de saúde, foi desenvolvido um

protótipo que consiste de uma aplicação na

Web

desenvolvido na plataforma J2EE.

As subseções a seguir são dedicadas a apresentar os artefatos de modelagem, o

ambiente de desenvolvimento do projeto (ferramentas utilizadas na implementação) e

uma visão geral do sistema.

3.3.1

Projeto e Modelagem do Sistema Computacional

O projeto do sistema computacional desenvolvido foi realizado tendo em mente

os seguintes pressupostos:

As classes e os objetos do sistema devem possibilitar a programação das

restrições unárias e múltiplas obedecendo a modelagem matem

ática

desenvolvida para as mesmas em seções anteriores desse capítulo;

A utilização do sistema deve permitir ao usuário a possibilidade de programar as

restrições a serem utilizadas em uma aplicação específica;

A utilização do algoritmo de busca retroativa deve privilegiar a utilização da

heurística que apresentou o melhor resultado em termos da complexidade no

tempo;

O projeto da interface com o usuário deve primar pela simplicidade e

inteligibilidade, exteriorizando a elegância da modelagem mate

mática

des

envolvida;

As ferramentas utilizadas para a implementação do sistema computacional

devem possibilitar a portabilidade do mesmo para diversas plataformas, uma

independência em relação a arquitetura e

possuir

custo zero.

A modelagem da ferramenta computacional foi efetuada utilizando a linguagem

UML (Unified Modeling Language), uma linguagem visual para modelar sistemas

computacionais por meio do paradigma de orientação a objetos [Martins, 2005]. F

criado o diagrama de casos de uso, que ilustra as funcionalidades essenciais para a

realização da alocação de recursos humanos, o diagrama de classes, que descreve os

tipos de objetos presentes no sistema, e o diagrama de objetos, que espelha os vários

tipos de relacionamentos estáticos existente entre as classes

3.1.1 Diagrama de caso de uso

O diagrama de casos de uso apresentado na figura

9 mostra as funcionalidades

do sistema, identificadas durante o estudo do problema, e, também, como este interage

com o seu ambiente. Como pode ser visto, esse diagrama expressa um dos pressupostos

do projeto, qual seja o de possibilitar a programação das restrições unárias e múltiplas,

através dos casos de uso “Cadastrar Restrições Unárias” e “Cadastrar Restrições

Múltiplas”. Como será mostrado no diagrama de sequência, o último caso de uso

acessado pelo usuário é o “Gerar escala”. Somente quando todos os cadastros forem

efetuados no sistema (plantonistas, unidades, turnos, restrições e dados da escala) é que

esse caso de uso é acessado. A seguir detalharemos a função realizada por alguns casos

de uso:

Cadastrar Turno: Através desse caso de uso o usuário cadastra os turnos de

trabalho das unidades de saúde, onde somente o parâmetro descrição do turno

é definido;

Cadastrar Plantonista: Através desse caso de uso o usuário cadastra os

plantonistas associados à cooperativa. Os parâmetros definidos são: nome do

plantonista e o número de plantões máxim

os em que este deve ser alocado;

Cadastrar Unidade: Através desse caso de uso o usuário cadastra as unidades

às quais a cooperativa presta serviço. Somente o parâmetro nome da unidade é

definido nesse caso;

Definir Dados da Escala: Nesse caso de uso, define

-se quais turnos, unidades e

plantonistas, previamente cadastrados, farão parte de uma escala. Além disso,

define

-se nesse caso de uso, a quantidade de vagas necessárias para cada turno

de cada unidade

;

Cadastrar Restrições Unárias: Através desse caso de uso o usuário cadastra as

restrições unárias do problema;

Cadastrar Restrições Múltiplas: O

nde

usuário cadastra as restrições múlt

iplas

do problema.

Figura

3.9

–

Diagrama de caso de uso

do sistema com suas respectivas funcionalidades

O papel de

Usuário

é exercido por um plantonista responsável por organizar a

escala de toda equipe.

3.1.1 Diagrama de classes

Através do diagrama de classes, da figura

10, visualizam-se as classes que

compõem o sistema com seus respectivos atributos e métodos, bem como os seus

relacionamentos. Esse diagrama apresenta uma visão estática de como as classes estão

organizadas, preocupando

se em defini

r a estrutura lógica das mesmas.

Figura

–

Diagrama de classes

A seguir, cada classe apresentada na figura

10 é descrita.

Vaga: refere-se à unidade de alocação do problema. Esta classe possui como

atributos a data da vaga e o atributo preenchida que indica se a vaga está

disponível ou ocupada. Além disso, essa classe possui relacionamento com as

classes Unidade e Turno, que indicam à qual unidade e à qual turno tal vaga

pertence, respectivamente. Esta classe relaciona-se, também, com a classe

Plant

onista por meio das classes de associação DomínioVaga e

Escal

aPlantonista, abaixo explanadas;

MatrizAlocacao: é uma coleção de todas

as vagas envolvidas no problema;

Plantonista: refere-se aos recursos humanos a serem alocados nas vagas. Esta

classe possui os atributos nomePlantonista e numeroMaximoPlantoes, que

armazenam o nome do plantonista e o número máximo de plantões permitidos

à ca

da plantonista, respectivamente;

EscalaPlantonista: estabelece uma relação entre as classes Vaga e Plantonista e

indica q

ue um determinado plantonista está

alocado à uma determinada vaga;

DominioVaga: estabelece, à semelhança da classe EscalaPlantonista, uma

relação entre as classes Vaga e Plantonista, entretanto, esta classe indica que

um sub-conjunto de plantonistas pertence ao domínio de uma das vagas do

problema;

Unidade: corresponde

aos dados das unidades de saúde;

Turno: corresponde aos dados de turno do problema. Esta classe possui

tipoTurno como um dos seus atributos, que define como o campo turno deverá

ser tratado. A função deste campo ficará mais clara na apresentação do

diagrama, o diagrama de objetos;

Heurística: corresponde aos da

dos das heurísticas do problema;

PSR: Essa classe não possui atributos, porém é no método definirEscala desta

classe que é

exec

utado o algoritmo de busca;

RestricãoUnária: modela as restrições unárias do problema. Essa classe

apresenta associações semelhantes à classe Vaga, devido ao fato dessa classe

ser a responsável por apresentar as características que as vagas devem ate

nder

para definir seus domínios;

SubRestricãoMultipla: modela as sub-restrições múltiplas do problema, ou

seja, define as características dos o

peradores da restrição múltipla;

RestricõesMúltiplas: Essa classe não possui atributos, porém é a classe que

interliga

as sub restrições múltiplas de determinada restrição múltipla e, é

responsável também, por verificar se a escala de determinado plantonista

atende às restrições múltiplas do problema, isso é feito através do método

escalaConsistente

definido nesta classe.

3.1.2 Diagrama de objetos

O diagrama de objetos, chamado também de diagrama de instâncias, é muito útil

para explorar exemplos de objetos do mundo real e a relação entre eles. Embora os

diagramas de classes sejam muito bons na descrição de muitas informações, algumas

vezes eles podem se tornar muito complexos e, o diagrama de objetos pode ser uma boa

opção na explicação de relações complexas entre as classes. Este diagrama mostra uma

fotografia de um sistema em execução.

A figura

11 apresenta o diagra

ma de objetos de uma vaga do sistema. Esta vaga,

como pode ser observado na figura

11, é uma vaga do dia 03/06/2009 que ocorre no

primeiro turno na unidade João Lúcio, e que ainda não está preenchida.

Figura

Diagrama de objeto para caracterizaç

ão da classe Vaga

Um exemplo de uma restrição unária é apresentado no diagrama de objetos da

figura

12. Essa restrição pode ser interpretada como: Os plantonistas Maria José, João

Batista e José Roberto não podem dar plantão dia 12 no segundo turno, na unidade 28

de Agosto.

Figura

Diagrama de objeto para caracterização da classe Restrição Unária

A figura

13 apresenta o diagrama de objetos da classe restrição múltipla. Essa

restrição pode ser interpretada como: os Plantonistas que trabalharem dia 5, na unidade

28 de Agosto, no segundo turno não podem trabalhar nesta mesma unidade dia 6 no

primeiro turno.

Figura

Diagrama de objeto para caracterização da classe Restrição Múltipla

3.1.3 Diagrama de sequ

ência

O diagrama de sequência procura determinar a sequência de eventos que ocorrem

em um determinado processo, ou seja, quais condições devem ser satisfeitas e quais

métodos devem ser disparados entre os objetos envolvidos e em que ordem durante um

processo específico. Dessa maneira, determinar a ordem em que os eventos ocorrem, as

mensagens que são enviadas, os métodos que são chamados e como os objetos

interagem entre si dentro de um determinado processo é o objetivo principal de

ste

diagrama. O diagrama de sequência da figura

14 mostra o diagrama de sequência da

geração da escala do sistema

Figura

Diagrama de sequ

ência da geração da escala

3.4

Ferramentas da implementação

Nesta seção são apresentadas as decisões relacionadas a implementação do

protótipo do sistema computacional, como a linguagem de programação escolhida, o

servidor de aplicação e o SGBD utilizados. A seguir, cada um desses itens

é discutido

4.1 Java

A tecnologia Java é tanto uma linguagem de programação quanto uma plataforma.

Essa tecnologia foi desenvolvida pela companhia Sun Microsystems (D

EITEL

, 2005).

Na linguagem de programação Java, todo o código fonte é o primeiro escrito em

arquivos de texto simples que terminam com a extensão Java. Esses arquivos fonte são

compilados em seguida para arquivos.classe através do compilador javac. Um arquivo

.classe não contém código que é nativo para o seu processador, em vez disso este

contém

bytecodes -

a linguagem da máquina virtual Java (Java VM).

A linguagem de programação Java apresenta as seguintes caracte

rísticas:

É considerada uma linguagem simples, pois permite o desenvolvimento de

sistemas em diferentes sistemas operacionais e arquitetura de hardware, sem que o

programador tenha que se preocupar com detalhes de infra

estrutura. Dessa forma,

o programador consegue desempenhar seu trabalho de uma forma mais produtiva

e eficiente;

É uma linguagem orientada a objeto, pois foi criada seguindo este paradigma

e, devido a isso, traz de forma nativa a possibilidade de o programador usar os

conceitos de herança

, p

olimorfismo e encapsulamento;

A plataforma Java permite a criação de programas que implementam o

conceito

multithread

, incluindo sofisticados mecanismos de sincronização entre

processos. O

multithreading

é uma técnica de programação concorrente, que

permit

e projetar e implementar aplicaçõ

es paralelas de forma eficiente;

É uma linguagem interpretada, ou seja, após a compilação é gerado um

arquivo intermediário (nem texto nem executável) no formato

bytecode

, que

poderá ser executado em qualquer arquitetura (Windows, Linux, Mac e Unix) que

tenha uma máquina virtual Java instalada. A

linkedição

do programa no formato

bytecode

é realizada no momento de sua execução de forma simples e totalmente

gerenciada

pela JVM (Java Virtual Machine);

É independente de arquitetura, está projetada para dar suporte a sistemas que

serão implementados em plataformas heterogêneas (hardware e software), como

ambiente Unix, Linux e Mainframe. Nesses ambientes, o sistema deve ser capaz

de ser executado em diferentes

hardwares

;

É uma linguagem portável. O que garante a portabilidade dos programas

desenvolvidos em Java é a Máquina Virtual Java.

Devido às características acima descritas, que satisfazem os pressupostos do

projeto, a linguagem Java foi escolhida como a linguagem de progra

mação.

3.4.2

Tomcat

foi o servidosr escolhido para o desenvolvimento deste projeto. O

projeto Jakarta Tomcat tem suas origens nos primórdios da tecnologia

servlet

Java. Os

servlets

são embutidos em servidores da

web

especiais, chamado

servlet

con

tainers

(originalmente chamada de servlet engines). A

Sun

criou o primeiro

servlet

container

chamado de Java Web Server, que introduziu essa tecnologia, mas não era muito

robusta. Enquanto isso, a empresa ASF criou o JServ, que foi um servlet engine que s

integrava com o servidor

web

Apache

RITTAIN

, 2003

)

Em 1999, a

Sun

doou seu código para o

servlet

container

ASF, e os dois projetos

foram fundidos para criar o servidor Tomcat. Hoje, o Tomcat serve como

implementação de referência oficial da

Sun

(RI), que

significa que a primeira prioridade do Tomcat é ser totalmente compatível com as

especificações

servlet

e JSP publicado pela

Sun

. As páginas JSP são simplesmente uma

alternativa, semelhante à forma do HTML, de se escrever

servlets

4.3 MySQL

O MySQL é um completo sistema de gerenciamento de banco de dados

relacional, de código-fonte aberto, gratuito, que apresenta características como

estabilidade e agilidade. Utiliza a linguagem padrão SQL e apresenta alta escalabilidade

sendo capaz de lidar com um grande volume de dados, sem que haja comprometimento

da integridade, nem do desempenho para a manipulação dos dados.

Atualmente é um dos SGBDs mais utilizados na Internet e várias linguagens de

programação têm interface com ele. Uma outra vantagem desse SGBD é a sua

portabilidade. Existem versões disponíveis deste SGBD para os sistemas operacionais

Linux, FreeBSD, OpenBSD, NetBSD, Solaris, Windows, AIX, etc. por sua facilidade

de aquisição e de administração, o MySQL foi o SGBD utilizado para a criação do

protótipo

EITOSA

, 2006)

5 Aspectos da Interface Visual

Os pressupostos apresentados para o projeto nortearam a implementação da

interface visual do sistema. Nessa seção apresenta-se os principais itens dessa interface.

A figura

15 ilustra a tela principal do sistema. E, em seguida, cada opção dessa tela é

explanada em detalhes.

Figura

Tela principal do sistema

Cadastro de Plantonista: nessa opção da aplicação o plantonista responsável

pela escala realiza o cadastro dos dados dos plantonistas que fazem parte da

cooperativa, como nome e o número máximo de plantões em que o plantonista

pode trabalhar (figura

16).

Figura

Tela de cadastro de plantonista

Cadastro de Unidade: consiste na funcionalidade que permite ao usuário

cadastrar as unidades de saúde que possuem vagas disponíveis, ou seja, que

precisam de plantonistas alocados a estas. Nesse cadastro é preciso informar

somente o nome da unidade. Uma vez cadastrada uma unidade, essa informação

fica disponível no momento da definição dos dados da escala. A figura

mostra o cadastro de uma unidade de saúde.

Figura

Tela de cadastro de unidade de saúde

Cadastro de turno: consiste na funcionalidade que permite cadastrar os turnos

de trabalho das unidades de saúde. Nesse cadastro é preciso informar somente a

descrição do turno. Uma vez cadastrado um turno, essa informação fica disponível

no momento da definição dos dados da escala. A figura

18 mostra o cadastro do

turno das unidades de saúde.

Figura

Tel

a de cadastro de turno

Nova Escala: Essa opção consiste na definição dos dados da escala, onde se

escolhe a heurística a ser utilizada na pesquisa, os plantonistas disponíveis para a

escala, as unidades de saúde para as quais serão realizadas a alocação,

quantidade de turnos dessas unidades, um descrição para identificação da escala e

as datas de início e fim que compreendem o período da escala (figura

19). Após

salvar esses dados, o usuário define a quantidade de vagas disponíveis em cada

unidade e tu

rno (figura

20). Com base nesses dados, o sistema gerar a matriz de

alocação. Após a geração da matriz de alocação, o usuário define as restrições

unárias da escala, e isso é feito por meio da caracterização das vagas, onde se

define o dia e/ou a unidade e/ou o turno, sob as quais tais restrições vigorarão, e

da escolha dos plantonistas que poderão ou não ser alocados a estas vagas (figura

21). Com as restrições unárias cadastradas pelo o usuário, o sistema define o

domínio de cada vaga e apresenta essa listagem ao usuário (figura

22). O

cadastro das restrições múltiplas ocorre após a definição dos domínios das vagas

(figura 3.24). Para cada restrição múltipla cadastra-se as sub-restrições que

equivalem a operadores de uma função, que se relacionarão entre si por meio do

operador diferença. Esses operadores nada mais são que caracterização de vagas

que são verificadas sempre que, durante a execução do algoritmo de busca, é

atribuído um plantonista às vagas. Após a conclusão da definição das restrições

múltiplas, executa-se a definição da escala, e, ao término desta, o resultado é

apresentado ao usuário (figura

Figura

–

Tela de configuração dos dados da escala

Figura

–

Tela de cadastro de quantidade de vagas nos turnos das unida

des

Figura

–

Tela de cadastro das restrições unárias

Figura

–

Tela com a lista de vagas e seus respectivos domínios

Figura

3.23

–

Tela de cadastro de restrição múltipla

Figura

24 –

Tela com lista de vagas com seu respectivo planton

ista alocado após execução da busca

4. RESULTADOS

Neste capítulo são apresentados e analisados os experimentos realizados para

avaliar o desempenho das heurísticas apresentadas no capítulo anterior e, em seguida, é

realizado

um estudo de caso cujos parâmetros de entrada são baseados numa

cooperativa que presta serviços às unidades de saúde de Manaus. Os experimentos

foram realizados num computador pessoal HP com processador Intel Core Duo, CPU de

1,6 GB, memória de 1536 MB

e sistema operacional

Windows Vista.

Os vários cenários simulados serão analisados considerando o número de vagas

selecionadas para atribuição, denominada nas tabelas de “resultados de nós

”.

exemplo: se no problema houver 70 vagas a serem preenchidas, e houve 24 retrocessos

durante a busca, o número de nós contabilizados será 94. Além disso, o tempo de

execução

também

é avaliado

4.1 Resultados das Heurísticas

As seções a seguir são dedicadas à apresentação dos resultados de testes

realizados no sistema desenvolvido para avaliação do desempenho das heurísticas

VRM, VP e Heurística Especial. Para cada resultado foram realizadas 5 simulações e

apresentado o melhor resultado obtido para a complexidade no tempo.

4.1.1 Testes no sistema sem restrições

Para a realização dos testes no sistema sem restrições cadastradas, foram

considerados 3

cenário

s distintos. A diferença entre esses

cenário

s está no número de

unidades de prestação de serviços. No primeiro

cenário

foram utilizadas 5 unidades de

serviço. No segundo, 10 unidades de serviço e no terceiro

cenário

, 15 unidades de

serviço. O objetivo de variar o número de unidades foi de verificar como varia o

desempenho do algoritmo em função do número de unidades de alocação a serem

definidas.

Para todos esses

cenário

s definiu

se os s

eguintes parâmetros para simulação:

A escala foi definida para uma semana;

Cada unidade trabalha com dois turnos;

Há uma vaga para cada turno em cada unidade;

Há 35 plantonistas cadastrados.

No primeiro

cenário

, com 5 unidades de prestação serviço, considerando esses

parâmetros, tem-se um total de 70 vagas por semana. Para o total de 35 plantonistas,

exige

-se de cada um 2 plantões por semana; Para o segundo

cenário

, com 10 unidades

de prestação de serviço, tem-se um total de 140 vagas por semana. Para o total de 35

plantonistas, exige-se de cada um 4 plantões por semana. Para o segundo

cenário

, com

15 unidades de prestação de serviço, tem-se um total de 210 vagas por semana. Para o

total de 35 plantonistas, exige

se de cada um 6 plantões por semana.

A tabela

1 apresenta os resultados obtidos do experimento realizado ao utilizar-

se o sistema para simular cada um dos

cenário

s acima descritos. Nessa tabela são

mostrados primeiramente resultados para a complexidade no tempo e para a

complexidade no espaço para 4 situações distintas: resultados sem heurística, com as

heurísticas VRM, Especial, VP, isoladamente e com todas ao mesmo tempo. A

complexidade no espaço é medida em termos de número de nós expandidos pelo

algoritmo. A complexidade no tempo é medida em termos do tempo de execução em

milisegundos (ms).

Tabela 4.1

–

Resultado de experimento dos testes no sistema sem restrições

Heurística

Num. Unidades

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

1º

6199

10676

108

10870

81204

83165

2º

140

18161

3596

2078123

140

17069

140 376643

140

426092

3º

233

33901

213

33357

210

29584

223 988635

210

1222750

O tempo é medido em milisegundos

Cenário

Todas

Retrocesso

VRM

Especial

A partir da tabela

1 pode-se observar que para o primeiro

cenário

, onde o

número de vagas é igual a 70, o retrocesso puro foi mais efetivo, tanto com relação ao

número de nós expandidos quanto

como

ao tempo de execução. Entretanto, com o

aumento do número de vagas a heurística especial foi mais efetiva na busca da solução.

Acredita

-se que a explicação para esse resultado pode ser buscado em parte no fato

sa heurística, diferentemente das demais heurísticas, não depender da

verificaçã

restrições

unárias

e/ou restrições múltiplas, o que acaba simplificando o uso da mesma.

A heurística VRM, por exemplo, seleciona a variável com menor domínio a ser

atribuído

sendo

as restrições unárias responsáveis em definir tal propriedade. A

heurí

stica VP, por outro lado, após a realização de cada atribuição de valor às variáveis

verifica se há alguma vaga “

ligada

” a esta através de uma restrição múltipla. Se houver,

o domínio dess

variável

é reduzido. E, tal redução, acaba por onerar o tempo de

processamento da busca por uma solução, como pode ser visto nos tempos obtidos

quando essa heurística é utilizada

4.1.2 Testes

no sistema com restrições unárias

Com o objetivo de analisar o comportamento do sistema em relação às restrições

unárias, defini

se os seguintes parâmetros para simulação:

A escala foi definida para uma semana;

O número de unidades

de serviço a ser utilizada é 10;

Cada

nidade de serviço trabalha com dois turnos

;

- Há uma vaga para cada turno em cada unidade, ou seja, n

essa

simulação há 140

vagas a serem preenchidas

;

Há 35 plantonistas cadastrados

. Para cada um

exig

4 plantões semana

A tabela

2 apresenta as restrições unárias

aplicadas

nesta e na próxima

simulação

. Essas restrições

restringem o domínio de algumas

vagas/variáveis

Tabela

4.2

–

Lista de r

estrições

nárias

RESTRIÇÃO

UNÁRIA

DESCRIÇÃO DA RESTRIÇÃO

O plantonista 1 só pode dar plantão no primeiro turno

Os plantonistas 2 e 3 não podem dar plantão no sábado no segundo turno

Os plantonistas 4 e 5 não podem dar plantão dia 22 na unidade 1

Os plantonistas 6 e 7 não podem dar plantão segunda-feira

Os plantonistas 8, 9 e 10 não podem dar plantão dia 24 na unidade 3 no

primeiro turno

Os plantonistas 11 e 12 não podem dar plantão dia 25 na Unidade 4

Os plantonistas 13 e 14 não podem dar plantão dia 26 na Unidade 9 no

primeiro turno

O plantonista 15 não pode dar plantão dia 27 na Unidade 5

Os plantonistas 16, 17 e 18 não podem dar plantão dia 28 na Unidade 6

no segundo turno

Os plantonistas 19 e 20 não podem dar plantão dia 22 na Unidade 7

Os plantonistas 21, 22 e 23 não podem dar plantão dia 23 na Unidade 8

no primeiro turno

Os plantonistas 24 e 25 não podem dar plantão dia 24 na Unidade 9

Os plantonistas 26, 27 e 28 não podem dar plantão dia 25 na Unidade 10

no primeiro turno

Os plantonistas 29 e 30 não podem dar plantão dia 26 na unidade 1

Os plantonistas 31 e 32 não podem dar plantão dia 27 na unidade 2 no

segundo turno

Os plantonistas 33, 34 e 35 não podem dar plantão dia 28 na unidade 3

tabela

3 apresenta os resultados obtidos com os

experimen

s realizados ao

executar o sistema para cada

conjunto

6 cenários. A diferença entre esses

cenários está no número de restrições unárias envolvidas. A definição desses cenários

objetivou verificar o comportamento do algoritmo com um crescente aumento da

complexidade das restrições unárias. A definição desses cenários envolve as restrições

mostradas na tabela x2 e são as seguintes: Cenário 1: Utiliza as restrições de 1 a 5;

Cenário 2: Utiliza as restrições de 1 a 8; Cenário 3: Utiliza as restrições de 1 a 10;

Cenário 3: Utiliza as restrições de 1 a 12; Cenário 4: Utiliza as restrições de 1 a 14;

Cenário

5: Utiliza as restrições de 1 a 16. Esses cenários foram analisados nas seguintes

condições:

Primeiramente sem heurística. Em seguida, com as heurísticas VRM,

Especial, VP, isoladamente

. Posteriorm

nte

com todas

as he

ísticas

ao mesmo tempo.

Tabela

3 –

Resultado de experimento dos testes no sistema

com

restrições

unárias

Heurística

ID Restrição

Unárias

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

1º

1 a 5

140

16940

140

16780

140

17154

140

378627

140

433080

2º

1 a 8

140

17187

170

21184

140

16957

143

382194

140

454229

3º

1 a 10

150

19020

140

16353

140

16685

140

379947

140

431314

4º

1 a 12

140

17931

150

18134

140

16768

140

394369

140

432005

5º

1 a 14

140

17747

140

20688

140

17134

144

389620

140

433938

6º

1 a 16

140

19808

140

16390

146

18998

140

380045

140

439709

O tempo é medido em milisegundos

O número de nós corresponde ao número de folhas expandidas na árvore de busca

Cenário

Todas

Retrocesso

VRM

Especial

Dos resultados obtidos, pode

se observar que

com a presença de restrições unárias

as simulações realizadas com a heurística

special apresent

aram

melhor desempenho

termos da complexidade no tempo nos cenários 2, 3, 4 e 5. A heurística VRM

apresentou o melhor resultado em termos da complexidade no tempo nos cenários 1 e 6.

A associação de todas as heurísticas não apresenta um bom resultado. Provavelmente

isso deve-se a complexidade no processamento envolvido para o teste de todas elas.

Observa-se nessa tabela que não existe um comportamento monotônico da

mplexidade no tempo em relação à complexidade do cenário. Esse comportamento

não monotônico deve-se a aleatoriedade do algoritmo

utilizado.

Outro dado que merece

atenção

é a repetição do comportamento da heurística VP, que, devido ao mesmo fator

explicitado na apresentação dos cenários anteriores, apresentou os maiores tempo de

execução.

4.1.3 Testes no sistema com restrições múl

tiplas

Para a realização dos testes no sistema

com restrições

múltiplas

, foram

considerados 3

cenário

s distintos. A diferença entre esses

cenário

consiste

no número

restrições múltiplas utilizadas em cada teste. No primeiro

cenário

configurou

-se o

sist

ema com a restrição múltipla definida como: Nenhum plantonista pode dar três

plantões seguidos. No segundo

cenário

, utilizou-se a restrição do primeiro

cenário

associada

outra

restrição múltipla definida como: quem dá plantão no domingo não

pode dar plantão no sábado”

E, no terceiro

cenário

, consideraram-se as duas restrições

utilizadas no segundo

cenário

associadas a restrição múltipla definida como: q

uem

trabalha na terça-feira no primeiro turno não pode trabalhar quinta-

feira

no segundo

turno.

O objetivo de variar o número de restrições múltiplas

foi

de verificar como

varia o desempenho do algoritmo em função do número de restrições múltiplas

presentes no

contexto do

problema

Para todos esses

cenário

s definiu

se os seguintes parâmetros

simulação

A escala foi definida para uma semana;

O número de unidades de serviço a ser utilizada é 10;

Cada unidade de serviço trabalha com dois turnos;

- Há uma vaga para cada turno em cada unidade, ou seja, nessa simulação há 140

vagas a serem preenchidas;

Há 35 plantonistas cadastrados, exigindo destes 4 plantões semanais.

A tabela

4 apresenta os resultados obtidos do experimento realizado ao utilizar-

se o sistema para simular cada um dos

cenário

Esses cenários foram analisados nas

seguintes condições: Primeiramente sem heurística. Em seguida, com as heurísticas

VRM, Especial, VP, isoladamente. Posteriormente com todas as heurísticas ao mesmo

tempo.

Tabela

4 –

Resultado de experimento dos testes no sistema

com restrições múltiplas

Heurística

Cenário

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

1º

154

27915

142

24154

140

24348

140 948806 140

1133535

2º

140

25705

9301

3969629

815

416133

213

1044116

140

1322134

3º

242

67479

141

29826

175

50310

211

1081455

140

1454760

O tempo é medido em milisegundos

O número de nós corresponde ao número de folhas expandidas na árvore de busca

Todas

Retrocesso

VRM

Especial

A partir dos resultados presentes na tabela

4 pode-se observar que com a

presença de restrições múltiplas o comportamento não monotônico da complexidade do

tempo em relação à complexidade do cenário é mais proeminente quando se trabalha

com as heurísticas aplicadas individualmente. Com a aplicação de todas as heurísticas

simultaneamente, no entanto, observa-se um comportamento monotônico. Nesse caso, o

desempenho da heurística VRM foi superior nos cenários 1 e 2, enquanto que

retrocesso puro foi superior no cenário 2.

4.1.4 Testes no sistema com restrições unárias e múltiplas

Para a realização dos testes no sistema com restrições unárias e

múltiplas

simultaneamente

, foram considerados 3

cenário

s distintos. A diferença entre esses

cenário

s consiste

também

no número de restrições múltiplas utilizadas em cada teste.

restrições unárias utilizadas foram as restrições da tabela x3 e, as restrições múltiplas

foram as mesmas da simulação anterior.

Para todos esses

cenário

s definiu

se os seguintes parâmetros para simulação:

A escala foi definida para uma semana;

O número de unidades de serviço a ser utilizada é 10;

Cad

a unidade de serviço trabalha com dois turnos;

- Há uma vaga para cada turno em cada unidade, ou seja, nessa simulação há 140

vagas a serem preenchidas;

Há 35 plantonistas cadastrados, exigindo destes 4 plantões semanais.

A tabela

5 apresenta os resultados obtidos do experimento realizado ao utilizar-

se o sistema para simular cada um dos

cenário

Esses cenários foram analisados nas

seguintes condições: Primeiramente sem heurística. Em seguida, com as heurísticas

VRM, Especial, VP, isoladamente. Posteriormente com todas as heurísticas ao mesmo

tempo.

Tabela

5 –

Resultado de experimento dos testes no sistema com restrições

unárias e

múltiplas

Heurística

Restrição

Unárias

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

Nós

Tempo

1º

142

25310

140

24098

144

26016

2612

2666228

140

1168094

2º

247

76551

167

39282

140

1279160

3º

178

45733

140

1388813

- Não convergiu

O tempo é medido em milisegundos

O número de nós corresponde ao número de folhas expandidas na árvore de busca

Todas

1 a 16

Cenário

Retrocesso

VRM

Especial

A partir dos resultados presentes na tabela

5 pode-se observar que com a

presença de restrições unárias e múltiplas a aplicação da heurística

especial

isoladamente foi a única que convergiu em todos

cenário

. E, em comparação com os

valores obtidos quando da aplicação de todas as heurísticas, esta última foi ótima com

relação ao número de nós expandidos, entretanto, com relação ao tempo de execução, a

aplicação da heurística especial apresentou melhores resultados, ou seja, as demais

heurísticas acaba

m onerando o tempo de execução da heurística especial.

4.2 Resultados do Estudo de Caso

As subseções a seguir são dedicadas a descrever o cenário do estudo de caso e os

resultados obtidos

com a aloca

ção realizada utilizando a ferramenta desenvolvida

4.2.1

Descrição do estudo de caso

estudo de caso desta pesquisa foi baseado numa cooperativa localizada na

cidade de Manaus que presta serviços à Secretaria Estadual de Saúde. Esta cooperativa

deve

dist

ribui

mensalmente

seus 128 plantonistas

20 unidades de saúde. A tabela

6 apresenta o quantitativo de plantonistas requeridos por unidade, dia e turno.

Tabela

4.6

–

Quantidade de vagas por unidade, dia e turno

Seg

Ter

Qua

Qui

Sex

Sab

Dom

1°

4 4 4 4 4 1 1

2°

0 1 1 1 0 1 1

1°

4 4 4 4 4 4 4

2°

3 3 3 3 3 3 3

1°

5 5 5 5 5 1 1

2°

1 1 1 1 1 1 1

1°

3 3 5 3 3 0 0

2°

0 0 0 0 0 0 0

1°

3 3 3 3 3 3 3

2°

2 2 2 2 2 2 2

1°

4 4 4 4 4 4 4

2°

4 4 4 4 4 4 4

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

2 2 2 2 2 1 1

2°

1 1 1 1 1 1 1

1°

2 2 2 2 2 1 1

2°

1 1 1 1 1 1 1

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

2 2 2 2 2 2 2

2°

2 2 2 2 2 2 2

1°

5 5 5 5 5 0 0

2°

0 0 0 0 0 0 0

1°

2 2 2 2 2 2 2

2°

2 2 1 2 2 2 2

1°

0 1 0 1 0 0 0

2°

0 0 0 0 0 0 0

1°

1 1 1 1 1 0 0

2°

0 0 0 0 0 0 0

1°

2 2 2 2 2 2 1

2°

1 1 1 1 1 1 1

Central de Regulação

HEMOAM

Ambulatório de dor crônica

Adraino Jorge

Dr. Moura Tapajós

Centro de Atendimento Materno-Infantil da Alvorada

Alzira da Silva Marreiro

Pronto Socorro da Criança Zona Sul

Pronto Socorro da Zona Oeste

Dr. Fajardo

Pronto Socorro Infantil da Zona Leste

Nazira Daou

Instituto da Criança

28 de agosto

Balbina Mestrinho

Franscica Mendes

Ana Braga

DIA DA SEMANA

Fundação CECON

Joao Lúcio

Getúlio Vargas

UNIDADE

TURNO

Para o estudo de caso a escala foi realizada para o período do mês de agosto de

2009

, o que totalizou

2329 vagas a serem preenchidas.

Os 128 plantonistas do problema foram divididos nas seguintes categorias;

- 25 plantonistas novatos, cujo número máximo de plantões é de 10 plantões ao

mês;

- 10 plantonistas antigos, cujo número máximo de plantões é de 16 plantões ao

mês;

- 93 plantonistas nem antigos nem novatos, cujo numero máximo de plantões é de

16 plantões ao mês.

As restrições unárias estabelecidas

para o

estudo de caso foram:

- Os 25 plantonistas novatos devem trabalhar somente nos finais de semana em

unidade complexas, como: João Lúcio, 28 de agosto, Pronto Socorro Infantil da Zona

Leste, Pronto Socorro da Criança Zona Sul, Pronto Socorro da Zona Oeste e Centro de

Atendimento Materno

Infantil da Alvorada.

- Os 10 plantonistas antigos devem trabalhar somente durante a semana em

unidades não complexas, como: Instituto da Criança, Dr. Fajardo, Alzira da Silva

Marreiro, HEMOAM e Ambulatório de dor crônica.

Além disso, para distribuir os plantonistas de maneira que o número de plantões

trabalhados nos finais de semana seja igual para todos os plantonistas que não são nem

antigo

nem novato

, a

seguinte

restriç

ões

unária

ram

estabelecida

- 47 plantonistas dos

plantonistas

que não são

antigo

s nem novatos podem dar

plantão somente

nos

dias 1, 2, 8, 9 e 15 de agosto;

- 46 plantonistas dos 93 plantonistas que não são antigos nem novatos podem dar

plantão somente nos dias 16

, 22, 23, 29

de agosto.

A única

restriç

ão

múltipla estabelecida para o estudo de caso foi: nenhum

plantonista pode dar

três

plantões seguidos.

4.2.

Descrição do

s resultados do

estudo de ca

Para definição da escala

desse

estudo de caso foram utilizadas as heurísticas de

grau, VRM e a heurística especial, como pode ser visto no fluxograma da figura 4.1. A

heurística de grau foi utilizada para classificar, antes do início da busca, cada vaga

relação ao número de restrições múltiplas em que estas estão envolvidas. A heurística

VRM auxilia no processo de escolha da melhor vaga a ser atribuída, ou seja, seleciona a

vaga que possuir menor número de plantonistas em seu domínio. Por fim, a heurí

stica

especial auxilia na escolha do melhor plantonista a ser atribuído. Tentativas de

utilização da heurística VP foram realizadas. No entanto

devido ao grande número de

variáveis (vagas) envolvidas no problema, sua utilização tornou-se inviável. A

invia

bilidade de seu uso deveu-

ao grande consumo de memória necessária para a

execução da propagação de restrições, o que impossibili

tou

o prosseguimento da

busca

por constante falta de memória.

Utilizar restriç

ões un

árias

na defini

ão dos dom

nios

das variá

veis

Selecionar vaga

não atribu

VRM

cio

Criar matriz de alocaç

ão

M(d,h,t,v)

Selecionar plantonista

Especial

Há

plantonistas

no dom

nio da vaga?

Atribui

ão

consistente?

Atribuir plantonista

vaga

Todas as vagas

estão preenchidas?

Fim

Sim

Retroceder para

vaga anterior

Não

Sim

Não

Sim

Não h

solu

ão

Sim

Não

Há

vaga

anterior?

Aplicar Heur

stica

de Grau

Figura 4.1

–

Fluxograma de execução para definição da escala.

Os resultados obtidos para o estudo de caso utilizando o fluxo acima descrito

foram:

Resultado de nós

: 2329;

Tempo (milisegundos): 2802581

, o que equivale a 46,7

minutos.

Como pode ser visto, quanto ao número de nós o resultado

foi

ótimo, pois não

houve a necessidade de retrocesso durante a execução da simulação do estudo de caso

Por outro lado julgamos que o tempo obtido para alocação foi satisfatório,

principalmente quando

considera

que a mesma escala, quando definida

manualmente, demora 2 semanas para ser elaborada.

As tabelas

4.7, 4.

8 e

9 apresentam as escalas obtidas pela ferramenta para

pla

ntonista 1 (novato), 26 (antigo) e 128 (nem novato nem antigo) no mês de agosto,

respectivamente.

Tabela

4.7

–

Escala do plantonista 1

Dia

Turno

Unidade

8 - Sábado

primeiro

Centro de Atendimento Materno-Infantil da Alvorada

9 - Domingo

primeiro

28 de agosto

15 - Sábado

primeiro

Joao Lúcio

16 - Domingo

segundo

28 de agosto

16 - Domingo

primeiro

Pronto Socorro da Criança Zona Sul

22 - Sábado

primeiro

Joao Lúcio

23 - Domingo

primeiro

Joao Lúcio

23 - Domingo

segundo

28 de agosto

29 - Sábado

primeiro

Joao Lúcio

30 - Domingo

primeiro

28 de agosto

Tabela 4.8

–

Escala do plantonista 26

Dia

Turno

Unidade

4 - Terça-feira

primeiro

Dr. Fajardo

5 - Quarta-feira

primeiro

Instituto da Criança

5 - Quarta-feira

segundo

Dr. Fajardo

10 - Segunda-feira

primeiro

Alzira da Silva Marreiro

10 - Segunda-feira

segundo

Instituto da Criança

13 - Quinta-feira segundo

Dr. Fajardo

14 - Sexta-feira

segundo

Alzira da Silva Marreiro

18 - Terça-feira

primeiro

Dr. Fajardo

19 - Quarta-feira

primeiro

Dr. Fajardo

20 - Quinta-feira

primeiro

Instituto da Criança

21 - Sexta-feira

primeiro

Instituto da Criança

24 - Segunda-feira

segundo

Alzira da Silva Marreiro

28 - Sexta-feira

primeiro

Instituto da Criança

28 - Sexta-feira

segundo

Instituto da Criança

31 - Segunda-feira

primeiro

Alzira da Silva Marreiro

Tabela 4.9

–

Escala do plantonista 128

Dia

Turno

Unidade

3 - Segunda-feira

segundo

Nazira Daou

5 - Quarta-feira

primeiro

Pronto Socorro da Criança Zona Sul

6 - Quinta-feira

primeiro

Adriano Jorge

7 - Sexta-feira

primeiro

Franscica Mendes

10 - Segunda-feira

segundo

Pronto Socorro Infantil da Zona Leste

11 - Terça-feira

primeiro

28 de agosto

12 - Quarta-feira

primeiro

Adriano Jorge

16 - Domingo

primeiro

Nazira Daou

17 - Segunda-feira

segundo

Pronto Socorro da Criança Zona Sul

18 - Terça-feira

primeiro

Balbina Mestrinho

20 - Quinta-feira

primeiro

Ana Braga

21 - Sexta-feira

segundo

Dr. Moura Tapajós

22 - Sábado

segundo

Alzira da Silva Marreiro

25 - Terça-feira

primeiro

Dr. Moura Tapajós

26 - Quarta-feira

primeiro

Getúlio Vargas

26 - Quarta-feira

segundo

Pronto Socorro da Criança Zona Sul

28 - Sexta-feira

primeiro

Dr. Moura Tapajós

28 - Sexta-feira

segundo

Ana Braga

29 - Sábado

segundo

Instituto da Criança

30 - Domingo

primeiro

Balbina Mestrinho

As tabelas 4.10, 4.11 e 4.12 apresentam a escala obtida pela ferramenta para

primeira

semana

do mês de agosto das unidades

ndação

CECON, 28 de Agosto e

Joã

o Lúcio, respectivamente.

Tabela 4.10

–

Escala da Unidade

Fundação

CECON

Dia

Turno

Plantonista

1 - Sábado

primeiro

Plantonista 70

1 - Sábado

segundo

Plantonista 44

2 - Domingo

primeiro

Plantonista 61

2 - Domingo

segundo

Plantonista 37

3 - Segunda-feira

primeiro

Plantonista 115

3 - Segunda-feira

primeiro

Plantonista 95

3 - Segunda-feira

primeiro

Plantonista 46

3 - Segunda-feira

primeiro

Plantonista 114

4 - Terça-feira

primeiro

Plantonista 61

4 - Terça-feira

primeiro

Plantonista 105

4 - Terça-feira

primeiro

Plantonista 57

4 - Terça-feira

primeiro

Plantonista 104

4 - Terça-feira

segundo

Plantonista 46

5 - Quarta-feira

primeiro

Plantonista 106

5 - Quarta-feira

primeiro

Plantonista 81

5 - Quarta-feira

primeiro

Plantonista 119

5 - Quarta-feira

primeiro

Plantonista 117

5 - Quarta-feira

segundo

Plantonista 121

6 - Quinta-feira

primeiro

Plantonista 37

6 - Quinta-feira

primeiro

Plantonista 82

6 - Quinta-feira

primeiro

Plantonista 46

6 - Quinta-feira

primeiro

Plantonista 127

6 - Quinta-feira

segundo

Plantonista 80

7 - Sexta-feira

primeiro

Plantonista 52

7 - Sexta-feira

primeiro

Plantonista 107

7 - Sexta-feira

primeiro

Plantonista 58

7 - Sexta-feira

primeiro

Plantonista 105

Tabela 4.11

–

Escala do Pronto

Socorro

28 de Agosto

Dia

Turno

Plantonista

1 - Sábado

primeiro

Plantonista 18

1 - Sábado

primeiro

Plantonista 7

1 - Sábado

primeiro

Plantonista 13

1 - Sábado

primeiro

Plantonista 8

1 - Sábado

segundo

Plantonista 50

1 - Sábado

segundo

Plantonista 40

1 - Sábado

segundo

Plantonista 5

2 - Domingo

primeiro

Plantonista 68

2 - Domingo

primeiro

Plantonista 43

2 - Domingo

primeiro

Plantonista 15

2 - Domingo

primeiro

Plantonista 16

2 - Domingo

segundo

Plantonista 66

2 - Domingo

segundo

Plantonista 4

2 - Domingo

segundo

Plantonista 81

3 - Segunda-feira

primeiro

Plantonista 124

3 - Segunda-feira

primeiro

Plantonista 86

3 - Segunda-feira

primeiro

Plantonista 117

3 - Segunda-feira

primeiro

Plantonista 58

3 - Segunda-feira

segundo

Plantonista 87

3 - Segunda-feira

segundo

Plantonista 71

3 - Segunda-feira

segundo

Plantonista 41

4 - Terça-feira

primeiro

Plantonista 81

4 - Terça-feira

primeiro

Plantonista 43

4 - Terça-feira

primeiro

Plantonista 94

4 - Terça-feira

primeiro

Plantonista 50

4 - Terça-feira

segundo

Plantonista 42

4 - Terça-feira

segundo

Plantonista 65

4 - Terça-feira

segundo

Plantonista 93

5 - Quarta-feira

primeiro

Plantonista 49

5 - Quarta-feira

primeiro

Plantonista 104

5 - Quarta-feira

primeiro

Plantonista 127

5 - Quarta-feira

primeiro

Plantonista 59

5 - Quarta-feira

segundo

Plantonista 119

5 - Quarta-feira

segundo

Plantonista 44

5 - Quarta-feira

segundo

Plantonista 71

6 - Quinta-feira

primeiro

Plantonista 42

6 - Quinta-feira

primeiro

Plantonista 91

6 - Quinta-feira

primeiro

Plantonista 84

6 - Quinta-feira

primeiro

Plantonista 97

6 - Quinta-feira

segundo

Plantonista 90

6 - Quinta-feira

segundo

Plantonista 127

6 - Quinta-feira

segundo

Plantonista 55

7 - Sexta-feira

primeiro

Plantonista 125

7 - Sexta-feira

primeiro

Plantonista 101

7 - Sexta-feira

primeiro

Plantonista 126

7 - Sexta-feira

primeiro

Plantonista 102

7 - Sexta-feira

segundo

Plantonista 41

7 - Sexta-feira

segundo

Plantonista 107

7 - Sexta-feira

segundo

Plantonista 108

Tabela 4.11

–

Escala

o Hospital

João Lúcio

Dia

Turno

Plantonista

1 - Sábado

primeiro

Plantonista 16

1 - Sábado

primeiro

Plantonista 23

1 - Sábado

primeiro

Plantonista 9

1 - Sábado

primeiro

Plantonista 6

1 - Sábado

segundo

Plantonista 78

1 - Sábado

segundo

Plantonista 71

1 - Sábado

segundo

Plantonista 15

1 - Sábado

segundo

Plantonista 14

2 - Domingo

primeiro

Plantonista 48

2 - Domingo

primeiro

Plantonista 58

2 - Domingo

primeiro

Plantonista 2

2 - Domingo

primeiro

Plantonista 49

2 - Domingo

segundo

Plantonista 3

2 - Domingo

segundo

Plantonista 52

2 - Domingo

segundo

Plantonista 25

2 - Domingo

segundo

Plantonista 21

3 - Segunda-feira

primeiro

Plantonista 36

3 - Segunda-feira

primeiro

Plantonista 110

3 - Segunda-feira

primeiro

Plantonista 101

3 - Segunda-feira

primeiro

Plantonista 73

3 - Segunda-feira

segundo

Plantonista 68

3 - Segunda-feira

segundo

Plantonista 38

3 - Segunda-feira

segundo

Plantonista 81

3 - Segunda-feira

segundo

Plantonista 72

4 - Terça-feira

primeiro

Plantonista 87

4 - Terça-feira

primeiro

Plantonista 41

4 - Terça-feira

primeiro

Plantonista 123

4 - Terça-feira

primeiro

Plantonista 102

4 - Terça-feira

segundo

Plantonista 63

4 - Terça-feira

segundo

Plantonista 67

4 - Terça-feira

segundo

Plantonista 122

4 - Terça-feira

segundo

Plantonista 57

5 - Quarta-feira

primeiro

Plantonista 123

5 - Quarta-feira

primeiro

Plantonista 100

5 - Quarta-feira

primeiro

Plantonista 89

5 - Quarta-feira

primeiro

Plantonista 77

5 - Quarta-feira

segundo

Plantonista 110

5 - Quarta-feira

segundo

Plantonista 116

5 - Quarta-feira

segundo

Plantonista 49

5 - Quarta-feira

segundo

Plantonista 73

6 - Quinta-feira

primeiro

Plantonista 57

6 - Quinta-feira

primeiro

Plantonista 56

6 - Quinta-feira

primeiro

Plantonista 64

6 - Quinta-feira

primeiro

Plantonista 89

6 - Quinta-feira

segundo

Plantonista 87

6 - Quinta-feira

segundo

Plantonista 116

6 - Quinta-feira

segundo

Plantonista 106

6 - Quinta-feira

segundo

Plantonista 105

7 - Sexta-feira

primeiro

Plantonista 50

7 - Sexta-feira

primeiro

Plantonista 60

7 - Sexta-feira

primeiro

Plantonista 93

7 - Sexta-feira

primeiro

Plantonista 44

7 - Sexta-feira

segundo

Plantonista 91

7 - Sexta-feira

segundo

Plantonista 38

A distribuição dos plantonistas que não são antigos nem novatos nos finais de

semana

ficou:

27 plantonistas com 3 plantões, 36 plantonistas com 4 plantões e 30

plantonistas com 5 plantões.

iscussão

onclusões

rabalhos

uturos

A motivação para o desenvolvimento dessa dissertação de mestrado, conforme

exposta na introdução, é bastante atual, qual seja a necessidade premente dos sistemas

que trabalham com a área de saúde têm de alocação de grandes contingentes de recursos

humanos em hospitais.

A principal contribuição dessa dissertação do ponto de vista da pesquisa foi a

caracterização

do desempenho do algoritmo PSR de forma isolada e com a utilização de

heurísticas, bem como o de propor uma heurística especial para a resolução do problema

de alocação na área de saúde.

O problema de alocação de recursos humanos na área de enfermagem, analisado

na revisão bibliográfica, intitulado “Programação de restrições para escalonamento de

enfermeiros

” também utilizou PSR em sua solução, entretanto, há muitas diferenças

entre a abordagem do artigo e a deste trabalho, como a modelagem do problema,

escopo de aplicação da solução, a busca pela solução e as ferramentas utilizadas na

implementação

Com relação à modelagem, a principal diferença encontra-se nas variáve

problema que no artigo citado são consideradas como sendo a tupla (dia, enfermeiro) e

o domínio destas variáveis são os valores 0 – enfermeiro sem plantão nesse dia, 1 –

enfermeira trabalhando no turno da manhã, 2

–

enfermeiro trabalhando no turno

da tarde

– enfermeiro trabalhando no turno noturno. N

est

a dissertação, as variáveis são

representadas pela tupla (dia, turno, unidade, vaga) e, seus domínios são os plantonis

tas

que podem trabalhar nestas vagas. Devido

essas diferenças, as restrições

fora

modeladas de maneira distintas, cada uma obedec

endo

ao seu respectivo

modelo.

Entretanto, a

s restrições

do artigo são classificadas

compulsórias ou opcionais

enquanto

que neste trabalho não há

tal

distinção entre as restrições

Quanto ao escopo

aplicação, o problema do artigo foi aplicado

a uma úni

ca unidade de saúde e

problema

dessa dissertação foi aplicado na escala de plantonistas pertencentes a uma cooperativa

que presta serviços a várias unidades de saúde.

Para a busca da solução

para

o problema do artigo foi utilizado o algoritmo de

retroces

so juntamente com as heurísticas VRM e consistência de arco, enquanto que

neste trabalho foram utilizadas as heurísticas VRM, VP, especial e heurística de grau

junto

com o algoritmo de retrocesso, entretanto, essa diferença se deu devido ao caráter

das pes

quisas

que, no caso do artigo foi voltada para solucionar um cenário específico e

neste trabalho buscou-se comparar o desempenho das heurísticas, para depois

aplicá

a um estudo de caso

A ferramenta utilizada para a implementação da modelagem do problema do

artigo foi a biblioteca Ilog-Solver que é uma biblioteca ligada ao Le-

Lisp

e ao C++

projetada para solucionar problemas de satisfação de restrições e neste trabalho utilizou

se ferramentas de propósito geral, como Java, MySQL e Tomcat. Isso ocorreu devido a

modelagem das restrições, que foram elaboradas para permitir que o sistema seja

flexível o suficiente para que novas restrições possam ser adicionadas ou removidas

pelo plantonista responsável pela escala e não pelo programador do sistema, o que não

ocorre no sistema do artigo, onde as restrições são definidas previamente de forma

estática no código

A modelagem e a implementação de sistemas de informação com esse objetivo

pressupõem um conhecimento pormenorizado da aplicação que se tem em vista. O f

oco

escolhido nesse trabalho foi a alocação de recursos humanos exigida pelas cooperativas

médicas que trabalham com o sistema público de saúde do Amazonas. Nesse sentido,

escolheu

-se para validação da ferramenta um estudo de caso de uma cooperativa

médica

. A aplicação da ferramenta, no entanto, é bem mais ampla. Com pequenas

alterações, a mesma pode ser utilizada dentro de um escopo mais amplo que envolve a

aloc

ação de enfermeiros, de disciplinas, etc.

As restrições previstas na modelagem foram de três tipos: unárias, restrições

múltiplas, numéricas e implícitas. As restrições numéricas limitaram-se apenas à

especificação do número de plantões por plantonista. As restrições implícitas limitaram-

se apenas a especificação de que um mesmo plantonista não pode dar dois plantões ao

mesmo tempo. Os dois primeiros tipos de restrições formam a parte mais rica desse

universo, tendo sido alvo de um trabalho de modelagem matemática que possibilitou o

desenvolvim

nto de uma interface clara e inteligível para o usuário.

As principais características da ferramenta de alocação desenvolvida podem ser

umidas nos seguintes itens:

Permite a programação das restrições. Essa característica torna amplo o

espectro de aplicações, na medida em que as características do sistema

podem ser moldadas para a aplicação que se tenha em mãos. As restrições

programáveis a que nos referimos são as unárias e múltiplas;

Permite a programação de parâmetros variados, como número de plantões

por plantonista, número de unidades de alocação, número de plantonistas,

duração dos plantões e número de plantonistas por unidade. Juntamente

com a característica anterior, essa característica aumenta mais ainda a

flexibilidade do sistema;

Utiliza o algoritmo PSR como motor da aplicação;

Otimiza o desempenho do algoritmo PSR através da utilização de

heurísticas;

Oferece uma interface inteligível para o usuário.

No desenvolvimento do trabalho experimentos com alguns cenários

(configurações

fictícias

) foram efetuados com o PSR puro, com as heurísticas VRM,

VP,

Especial (proposta dessa pesquisa) e com a junção de todas elas. O objetivo

dessas

simulações, conforme já citado,

foi

o de avaliar o desempenho destas e, por

conseguinte, selecionar as que apresentaram melhor resultado para serem aplicados na

resolução d

e um caso real. Os resultados indicaram que

heurística

Especial apresentou

melhor resultado quanto ao tempo de execução na maioria dos cenários e,

principalmente, nos mais complexos, onde estavam presentes as restrições unárias e

múltiplas.

Apesar da heurística VP ter apresentado bons resultados quando considerado

o número de nós expandido, sua aplicação ao estudo de caso se tornou inviável devido

ao alto consumo de memória

utilizado

durante o seu processamento. Logo, para o

estudo de caso foram utilizadas as heurísticas VRM, para guiar a busca quanto a melhor

vaga a ser selecionada, e a heurística Especial, na seleção do melhor plantonista para a

vaga selecio

nada.

resultados obtidos na solução do estudo de caso foram

considerados

satisfatórios

tanto

uando

considera o tempo de execução que foi de

46,7 minutos, quando se considera a quantidade de nós expandidos, que foi pequena

pois, como citado na seção de resultados, não houve retrocesso durante a execução da

busca, o que indicou a efetividade das

heurísticas

A estratégia utilizada na tentativa de distribuir de forma igual os plantões nos

finais de semana entre os plantonistas que não são novatos nem veteranos, não alcançou

o êxito necessário.

As principais conclusões desse trabalho podem ser resumidas então nos seguinte

itens:

A utilização do PSR para a alocação de recursos humanos na área de saúde

é possível, partindo de uma modelagem adequada das restrições aplicáveis

a solução do pr

blema;

associação de heurísticas ao algoritmo PSR é de fun

damental

importância para a diminuição do tempo de alocação dos recursos;

A heurística especial proposta nessa dissertação foi a que, em média,

apresentou o melhor desempenho, quando associada ao algoritmo PSR;

5.1 Trabalhos Futuros

Como trabalhos futuros

podem

propõe

se:

- Adicionar novas restrições numéricas, que permitam estabelecer um

determinado número de plantões a um grupo de plantonistas em um grupo de unidades

de alocação;

- Adotar a orientação observada em alguns artigos publicados na literatura, que

priorizam ou classificam as restrições em obrigatórias e prioritárias, possibilitando a

flexibilização das mesmas em situações de difícil convergência do algoritmo de

alocação;

- Utilizar o sistema como uma ferramenta de auxílio

para

estimativa d

recursos

humanos

mínimos

para

atender

as demandas de um hospital ou de uma unidade de

serviço de saúde

;

Adotar o sistema para novas aplicações, introduzindo restrições que viabilizem o

uso do sistema para alocação de horários escolares e para a alocação da escala de

enfermagem.

eferências

ibliográficas

BAPTISTE, Philippe. Constraint-based Scheduling: Applying Constraint Programming

to Scheduling Problems. Compiègne: Kluwer Academic Publishers, 2001. 198 p.

BRITTAIN, Jason; DARWIN, Ian. Tomcat – The Definitive Guide. O’Reilly Editora.

2003.

DEITEL, Harvey; DEITEL, Paul. Java - Como Programar: 6. ed. São Paulo: Pearson

Prentice Hall, 2005.

DERIS, Safaai; OMATU, Sigeru; OHTA, Hiroshi. Timetabling planning using the

constraint

based reaso

ning.

Computers and Operations Research 2000; 27:819

–

40.

FEITOSA, Vanessa Maria Mota. Uma Proposta para Organização e Uso do Conteúdo

Digital.

2006. 66 f.

Dissertação

(

Mestrado

em Informática) – Programa de Pós-

graduação em Informática, Universidade Feder

l do Amazonas, Manaus

KUMAR, Vipin. Algorithms for Constraint – Satisfaction Problems: A Survey.

Magazine, p. 32

44, 1992.

MARTINS, Jose Carlos Cordeiro. Gerenciando projetos de desenvolvimento de

software com PMI, RUP e UML. 2 ed. São Paulo: Brasport Livros e Multimídia Ltda,

2005.

356 p.

MITCHELL,

Melanie.

An Introduction to Genetic Algorithms. Cambridge: The MIT

Press, 1998. 221 p.

DDI

, A., C

ESTA

, A. “Toward interactive scheduling systems for managing medical

resources”, Artificial Intel

ligen

ce in Medicine, vol. 20, p.

113

138.

2000.

OUGHALIME, Ahmed; ISMAIL, Wan; YEUN, Liong. A tabu search approach to the

nurse scheduling problem. International Symposium on Information Technology,

volume 1, p. 1-

7, 2008.

RUSSEL

, S. & NORVIG, P. Inteligênci

a Artificial.

2ª. Ed. São Paulo: Campus, 2004.

HORTLIFE

, E. H., P

ERREAULT

, L. E., W

IEDERHOLD

, G., F

AGAN

, L.M. Medical

Informatics,

2001,

Springer.

PYROPOULOS

, C. D.

“AI Planning and scheduling in the medical hospital

environment”, Artificial Intel

lig

ence in Medicine, vol. 20, p.

101

111.

2000.

TSAI, Chang

Chun; LI, Sherman. A two

-stage modeling with genetic algorithms for the

nurse scheduling problem. Expert Systems with Applications: An International Journal

p. 9506

9512, 2009.

TSANG, Edward.

Foun

dations of Constraint Satisfaction. London: Academic Press,

1993. 420 p.

ALOUXIS

, C., H

OUSOS

, E. “Hybrid optimization techniques for the workshift and

rest assignment of nursing personnel”, Artificial Intelligence in Medicine, vol. 20, p.

155

175.

2003.

WEIL, Georges; HEUS, Kamel; FRANÇOIS Patrice; POUJADE, Marc.

Constraint

Programming for Nurse Scheduling

IEEE Engineering in Medicine and Biology,

417

–

422,

1995

This document was created with Win2PDF available at http://www.win2pdf.com.

The unregistered version of Win2PDF is for evaluation or non-commercial use only.

This page will not be added after purchasing Win2PDF.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 