CENTRO FEDERAL DE EDUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Curso de Mestrado em Modelagem
Matemática e Computacional
Uma Solução do Problema de
Programação de Equipes de
Saúde Pública Via
Metaheurísticas
Dissertação de Mestrado, submetida ao Curso de
Mestrado em Modelagem Matemática e Computacional, como parte dos requisitos para a obtenção
do título de Mestre em Modelagem Matemática e
Computacional.
Aluno: Nagibe Anderson da Silva Borba
Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET/MG)
Belo Horizonte, fevereiro de 2010.
B726s
Borba, Nagibe Anderson da Silva
Uma solução do problema de programação de equipes de
saúde pública via metaheurísticas /
Nagibe Anderson da
Silva Borba. – Belo Horizonte, 2010.
86p.
Dissertação (Mestrado) – Centro Federal de Educação
Tecnológica de Minas Gerais
Programa de Pós-Graduação em Modelagem Matemática e
Computacional
Orientador: Sérgio Ricardo de Souza
1. Otimização combinatória - Teses. 2. Modelos
matemáticos - Teses. 3. Programação heurística - Teses. 4.
Família - Saúde e higiene - Política governamental - Betim
(MG) - Teses. I. Souza, Sérgio Ricardo de. II. Centro Federal
de Educação Tecnológica de Minas Gerais.
III. Título.
CDD 512.72
Elaboração da ficha catalográfica por Biblioteca-Campus II / CEFET-MG
Dedico este trabalho a minha querida mãe, Dona Aninha, que me ensinou, em sua
luta diária, os preceitos de moral e dignidade.
Dedico também a minha pequenina, minha filha Ana Clara, que é a razão do meu
viver.
iii
“Só é útil o conhecimento que nos torna melhores.”
Sócrates, 470 a 399 a.C
iv
Agradecimentos
Primeiramente, a Deus, por ter me colocado este desafio para que eu pudesse
superá-lo e testar meus limites.
À minha querida mãe, por ter me ensinado a sempre buscar o melhor, independente das barreiras que eu encontrasse, independente das restrições que me limitassem.
À minha amada filha, para a qual devo muita atenção e carinho devido a minha
ausência para os estudos, e que apesar da sua pouca idade, entendia que eu estava
buscando uma realização pessoal e profissional.
Ao Professor Sérgio Ricardo, a quem tenho muito respeito, por ter acreditado
em meu trabalho e me aceitado como seu orientando, pela sua dedicação e atenção
com o programa e seus orientandos, pelos puxões de orelha quando eu precisava e
pela paciência.
Aos meus colegas do mestrado, os quais sempre estiveram a disposição para
tentar solucionar qualquer dúvida que eu tivesse, pelo companheirismo e carinho.
Aos meus amigos e familiares, que entenderam a minha ausência para os estudos.
Às pessoas que, de alguma forma, contribuíram para a conclusão deste trabalho.
À todos vocês, meus sinceros agradecimentos.
v
Resumo
Este trabalho propõe o desenvolvimento de um modelo de apoio à decisão para problemas de programação de equipes do Programa de Saúde da Família (PSF), do
Núcleo de Apoio à Saúde da Família (NASF) e de Unidades de Pronto Atendimento
(UPA) em regiões onde estas estruturas foram implantadas. Uma programação de
equipes exige o estudo de um volume muito grande de informações, o que torna a
tarefa complexa e sujeita à ocorrência de conflitos entre os elementos envolvidos.
Problemas de otimização combinatória do tipo scheduling possuem processos satisfatórios para alcançar soluções factíveis para este tipo de programação. Neste tipo
de problema, as restrições são divididas em dois conjuntos: restrições rígidas (hardconstraints), que nunca devem ser violadas; restrições flexíveis (Soft-constraints),
que são desejáveis, mas não essenciais. Neste trabalho, são propostos o estudo
destas metodologias e a construção de modelos de otimização combinatória para
solucionar o problema de programação de equipes de saúde, com a otimização dos
recursos humanos utilizados. Para a validação dos desenvolvimentos apresentados,
é apresentada a aplicação da metodologia proposta à uma instância real de dados,
associada ao município de Betiom, em Minas Gerais, Brasil, obtendo-se resultados
satisfatórios no tocante aos objetivos propostos.
Palavras-Chave: Problemas de Programação de Equipes; Otimização Combinatória; Modelagem Matemática; Heurísticas Computacionais; Equipes de Saúde.
vi
Abstract
This dissertation proposes to develop a decision support model for team scheduling
problems of the Family Health Program, of the Family Health Support Centers and
of the Emergency Care Units in regions where these structures have been implemented. A schedule of teams requires the study of a very large volume of information,
which makes the task complex and subject to the occurrence of conflicts between
the elements involved. Combinatorial optimization problems like scheduling ones
have satisfactory ways to achieve workable solutions to this type of programming.
In this type of problem, constraints are divided into two sets: hard-constraints, i.e,
restrictions that should never be violated; and soft-constraints, i.e., constraints that
are desirable but not essential. In this dissertation, it is proposed the study of these
methodologies and the construction of combinatorial optimization models for solving the scheduling problem of health care teams, with the optimization of human
resources used. To validate the methodology, it presents application of it to a real
instance data associated with the city of Betim, Minas Gerais, Brazil, obtaining
satisfactory results with regard to the proposed objectives.
Palavras-Chave: Team Health Scheduling Problem; Family Health Program; Combinatorial Optimization; Mathematical Modelling; Computacional Heuristics.
vii
Sumário
1 Introdução
1.1 Preliminares . . . . . . . .
1.2 Objetivo . . . . . . . . . .
1.2.1 Objetivo Geral . .
1.2.2 Objetivo Específico
1.3 Organização do Trabalho .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Revisão dos modelos de Otimização Combinatória
de Problemas de Programação de Equipes
2.1 Caracterização do Problema . . . . . . . . . . . . .
2.2 Problema de Programação de Tripulações . . . . . .
2.2.1 Revisão Bibliográfica . . . . . . . . . . . . .
2.3 Problemas de Programação de Enfermeiras . . . . .
2.3.1 Revisão Bibliográfica . . . . . . . . . . . . .
2.4 Problema de Programação de Quadro de Horários .
2.4.1 Revisão Bibliográfica . . . . . . . . . . . . .
2.5 Considerações Finais . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
2
3
3
Para Resolução
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
5
7
7
8
9
11
12
3 Definições de Estruturas Relacionadas ao Atendimento da Atenção
Básica e Pré-hospitalar
3.1 Caracterização do Programa de Saúde da Família (PSF) . . . . . . .
3.1.1 Histórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Composição das Equipes do PSF . . . . . . . . . . . . . . . .
3.1.3 Programação das Equipes no PSF . . . . . . . . . . . . . . . .
3.2 Caracterização de uma Unidade de Pronto Atendimento (UPA) . . .
3.2.1 Salas de Estabilização (SE) . . . . . . . . . . . . . . . . . . .
3.2.2 Unidades de Pronto Atendimento (UPA) . . . . . . . . . . . .
3.2.3 Composição das Equipes de uma UPA . . . . . . . . . . . . .
3.2.4 Programação de Equipes para uma UPA . . . . . . . . . . . .
3.2.5 Problema de Escala de Profissionais de uma UPA . . . . . . .
3.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
13
14
14
15
18
18
19
19
20
22
24
4 Modelagem Matemática Proposta Para a Programação de Equipes
de Saúde da Atenção Básica e Pré-Hospitalar - Estudo de Caso
4.1 Arquitetura para o PSF . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Características do Problema . . . . . . . . . . . . . . . . . . .
4.1.2 Descrição do Modelo Matemático Proposto para o PSF . . .
25
26
26
29
viii
4.2
4.3
4.1.3 Matrizes e Vetores do Modelo Matemático para o PSF
4.1.4 Parâmetros de Entrada e Variável de Decisão . . . . .
4.1.5 Descrição das Restrições . . . . . . . . . . . . . . . . .
4.1.6 Função Objetivo . . . . . . . . . . . . . . . . . . . . .
4.1.7 Modelo Matemático Completo para o PSF . . . . . . .
Arquitetura para a UPA . . . . . . . . . . . . . . . . . . . . .
4.2.1 Características do Problema . . . . . . . . . . . . . . .
4.2.2 Descrição do Modelo Matemático proposto para a UPA
4.2.3 Matrizes e Vetores do Modelo Matemático para a UPA
4.2.4 Parâmetros de Entrada e Variável de Decisão . . . . .
4.2.5 Descrição das Restrições . . . . . . . . . . . . . . . . .
4.2.6 Função Objetivo . . . . . . . . . . . . . . . . . . . . .
4.2.7 Modelo Matemático Completo para a UPA . . . . . . .
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . .
5 Revisão de Heurísticas e Metaheurísticas
5.1 Problemas de Otimização Combinatória .
5.2 Heurísticas e Metaheurísticas . . . . . . .
5.2.1 Heurísticas Construtivas . . . . . .
5.2.2 Heurísticas de Refinamento . . . .
5.3 Metaheurísticas . . . . . . . . . . . . . . .
5.3.1 Iterated Local Search (ILS) . . . . .
5.4 Considerações Finais . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
32
33
33
34
34
35
38
39
40
42
42
43
.
.
.
.
.
.
.
44
44
45
45
46
47
48
50
6 Resultados Computacionais para os Problemas de Programação de
Equipes de Saúde
6.1 Metodologia para Implementação Computacional . . . . . . . . . . .
6.2 Descrição do problema teste para o PSF . . . . . . . . . . . . . . . .
6.2.1 Inicialização dos Testes Para o Problema do PSF . . . . . . .
6.2.2 Estrutura de Vizinhança . . . . . . . . . . . . . . . . . . . . .
6.2.3 Solução via ILS para o problema do PSF . . . . . . . . . . . .
6.3 Descrição do problema teste para a UPA . . . . . . . . . . . . . . . .
6.3.1 Inicialização dos Testes Para o Problema da UPA . . . . . . .
6.3.2 Estrutura de Vizinhança . . . . . . . . . . . . . . . . . . . . .
6.3.3 Solução via ILS para o problema do PSF . . . . . . . . . . . .
6.4 Análise dos Resultados Computacionais . . . . . . . . . . . . . . . . .
6.4.1 Análise dos Resultados Computacionais Para o Problema do
PSF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4.2 Análise dos Resultados Computacionais Para o Problema da
UPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
53
53
54
55
56
58
59
60
62
64
64
66
67
7 Conclusão e Trabalhos Futuros
69
7.1 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Referências
71
ix
Lista de Tabelas
3.1
3.2
3.3
3.4
3.5
3.6
3.7
Parâmetros para implantação de SE . . . . . . . . . . . . . . .
Estruturação de equipes de UPA por parâmetros populacionais
Estrutura de profissionais, conforme parâmetros e fonte. . . . .
Períodos de trabalho . . . . . . . . . . . . . . . . . . . . . . .
Turnos de trabalho - UPA . . . . . . . . . . . . . . . . . . . .
Carga horária semanal - UPA . . . . . . . . . . . . . . . . . .
Número de profissionais por turno - UPA . . . . . . . . . . . .
4.1
4.2
4.3
4.4
Área 8 dividida em microáreas e populações correspondentes . . . .
Modelo de dados para o PSF . . . . . . . . . . . . . . . . . . . . . .
Quadro de Funcionários da Unidade de Atendimento Imediato Sete
de Setembro, em Betim - MG . . . . . . . . . . . . . . . . . . . . .
Denominação de especialidade profissionais . . . . . . . . . . . . . .
6.1
6.2
Resultados dos testes em instância do PSF . . . . . . . . . . . . . . . 65
Resultados dos testes em instância para UPA . . . . . . . . . . . . . 67
x
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
20
21
21
21
22
23
. 27
. 30
. 36
. 37
Lista de Figuras
3.1
Exemplo de um município dividido em áreas e microáreas. . . . . . . 16
4.1
4.2
4.3
4.4
4.5
4.6
4.7
Área 8 dividida em microáreas . . . . . . . . . . . . . . . . . . . .
Exemplo: Microáreas de responsabilidade de cada equipe PSF . .
Exemplo: transferência de microárea da equipe B para a equipe A
Modelo da matriz solução para o problema do PSF . . . . . . . .
Modelo da matriz solução para o problema da UPA . . . . . . . .
Modelo da matriz solução para o problema da UPA . . . . . . . .
Exemplo de aplicação da função F (i) . . . . . . . . . . . . . . . .
. . 27
. . 28
. 28
. . 29
. . 37
. . 38
. . 41
5.1
5.2
5.3
5.4
5.5
5.6
Representação de um problema de otimização. . .
Pseudocódigo da Heurística Construtiva. . . . . .
Pseudocódigo do método de descida. . . . . . . .
Pseudocódigo do Método de Descida Randômico.
Visão geral da Metaheurística ILS . . . . . . . . .
Pseudocódigo da Metaheurística ILS . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
45
46
47
47
49
50
6.1
6.2
6.3
6.4
6.5
6.6
Distribuição de tarefas para equipes do PSF . . . . . . . . . . . . . .
Pseudocódigo para busca em vizinhança variável - PSF. . . . . . . . .
Pseudocódigo para a função de avaliação - PSF. . . . . . . . . . . . .
Pseudocódigo da Descida Randômica para o PSF. . . . . . . . . . . .
Pseudocódigo da Metaheurística ILS para o PSF. . . . . . . . . . . .
Movimento proibido para o algoritmo do PSF: microáreas com mais
de uma equipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Movimento proibido para o algoritmo do PSF: microáreas inexistentes
Distribuição de tarefas para equipes de uma UPA . . . . . . . . . . .
Pseudocódigo para busca em vizinhança variável - UPA. . . . . . . .
Movimento de busca local para o algoritmo da UPA . . . . . . . . . .
Movimento proibido para o algoritmo da UPA: troca entre profissionais de mesma categoria, mas com carga horária diferentes . . . . . .
Movimento proibido para o algoritmo da UPA: troca entre profissionais de categorias diferentes . . . . . . . . . . . . . . . . . . . . . . .
Movimento penalizado para o algoritmo da UPA . . . . . . . . . . . .
Pseudocódigo para a função de avaliação - UPA. . . . . . . . . . . . .
Pseudocódigo da Descida Randômica para a UPA. . . . . . . . . . . .
Pseudocódigo da Metaheurística ILS para o PSF. . . . . . . . . . . .
Gráfico da distribuição de tarefas para equipes do PSF da área 1 . . .
Gráfico da distribuição de tarefas para equipes do PSF da área 1 . . .
54
55
55
56
57
6.7
6.8
6.9
6.10
6.11
6.12
6.13
6.14
6.15
6.16
6.17
6.18
xi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
58
59
60
61
61
62
62
63
63
64
65
66
66
6.19 Comportamento do algoritmo para o problema
ao tempo médio de execução . . . . . . . . . .
6.20 Comportamento do algoritmo para o problema
ao número de iterações . . . . . . . . . . . . .
xii
da UPA,
. . . . .
da UPA,
. . . . .
com relação
. . . . . . . . 67
com relação
. . . . . . . . 67
Capítulo 1
Introdução
1.1
Preliminares
Esta dissertação propõe o estudo e a aplicação de um modelo de otimização
combinatória para solucionar o problema de programação de equipes e distribuição
de tarefas em equipes de saúde pública, especificamente equipes da atenção préhospitalar. O planejamento de equipes de trabalho exige o estudo de um volume
muito grande de informações, o que torna a tarefa complexa e sujeita à ocorrência
de conflitos entre os elementos envolvidos. Um modelo matemático de programação
destas equipes deve promover a otimização da alocação dos recursos humanos disponíveis, visando o melhor aproveitamento da mão de obra e conseqüente redução
de custos operacionais.
Um problema de programação de equipes é, geralmente, uma tarefa que demanda
grande esforço analítico e conhecimento das diversas variáveis envolvidas na questão.
Modelos de otimização combinatória, específicos para este tipo de problema, procuram atribuir a estas variáveis o melhor ajuste possível, de forma que atendam a um
determinado objetivo e satisfaçam um conjunto de restrições impostas ao problema.
Existe, na literatura, uma série de problemas do tipo scheduling (Ernst et al.,
2004), e muitos deles são aplicados na resolução de problemas que possuem características semelhantes aos problemas para os quais estes métodos foram baseados
originalmente. Como exemplo, o Problema de Programação de Enfermeiros, além
de escalonamento de profissionais em saúde, pode ser aplicado em escalonamento
de Call Centers, devido às semelhanças de estrutura de alocação de profissionais e
quadro de horários. Em geral, estes problemas relacionam o número de profissionais,
por categoria, a serem alocados em um quadro de horários, respeitando restrições
impostas para cada situação, como preferências dos profissionais, restrições de recursos de força de trabalho e materiais, normas trabalhistas, acúmulo de tarefas e
períodos de descanso, dentre outras questões. Nota-se então que, para cada situação, deve-se ter estratégias diferentes de planejamento, uma vez que as situações se
diferem umas das outras, fato que dificulta a implementação de um modelo único
para resolução de qualquer problema, mesmo que semelhantes entre si.
A solução para estes problemas pode ser encontrada através de métodos de programação matemática, que são capazes de encontrar a solução ótima para o problema. Porém, em casos em que há um número grande de variáveis envolvidas, como
acontece em problemas reais, o esforço computacional aplicado para a determinação
1
1.2
Introdução
2
da solução ótima torna o método de programação matemática exato extremamente
impraticável e inviável, com alto custo computacional e a obtenção de resultados em
escalas de tempo muito elevadas. Como descrito na literatura, estes problemas são
classificados como do tipo NP-Difícil, uma vez que não é possível determinar a sua
solução em tempo polinomial (Beddoe, 2004) (Avella et al., 2007).
O planejamento operacional em saúde consiste em determinar, dentre outros
ítens, uma equipe multiprofissional para assistir a população de uma determinada
região (Brasil, 2004). Este planejamento deve focar a cobertura de toda a população
em questão. Em grande parte dos casos, a demanda de trabalho é o fator ponderador
desta programação e a oferta operacional deve ser suficientemente adequada para
atender a esta demanda. Diante disto, o método proposto objetiva a eliminação de
inviabilidades, como a sobreposição de tarefas, excesso do tempo de trabalho, alto
custo operacional e utilização inadequada da mão-de-obra.
Diante do exposto, o objetivo principal deste trabalho é realizar um estudo dos
principais modelos de otimização combinatória, aplicáveis em programação de equipes, e adequá-los às características do problema de programação de equipes de saúde
pública, especificamente de equipes da atenção pré-hospitalar. As estruturas dos
problemas propostos têm algumas características de problemas do tipo scheduling
discutidos neste trabalho, no que tange ao escalonamento, equipes multiprofissionais, quadro de horários e distribuição de tarefas, assim como as restrições impostas. Porém, algumas características particulares destas equipes foram observadas,
como profissionais da mesma categoria com cargas horárias diferenciadas, questões
de balanceamento de distribuição de tarefas e programação das equipes baseada
na população a ser atendida, independente diretamente da demanda de atendimentos. Estas características serão abordadas na modelagem matemática dos problemas
tratados.
Os modelos matemáticos aqui propostos devem identificar as restrições impostas
para os problemas, sejam elas rígidas ou flexíveis. Para a resolução computacional, serão testados e propostos algoritmos heurísticos para a obtenção e exploração
de soluções factíveis, com movimentos de busca aleatória local em vizinhança, objetivando encontrar boas soluções para o problema. A utilização de metodologias
heurísticas para a determinação de soluções para problemas desta classe é grande
importância, pois, apesar de não retornar necessariamente uma solução ótima ou
não apresentar garantias quanto a otimalidade da solução encontrada, permite a
determinação de soluções de boa qualidade, aliado ao fato destas técnicas aceitarem
restrições operacionais com certa facilidade.
1.2
1.2.1
Objetivo
Objetivo Geral
Este trabalho tem, como objetivo geral, o estudo do planejamento de equipes de
saúde para o Programa de Saúde da Família (PSF) e para as Unidade de Pronto
Atendimento (UPA), através da aplicação de técnicas de pesquisa operacional.
1.3
Introdução
1.2.2
3
Objetivo Específico
Como objetivos específicos, pretende-se:
• Propor modelos matemáticos, na forma de problemas de otimização combinatória, que proporcionem apropriada representação dos problemas tratados;
• Incluir, nos modelos propostos, situações cotidianas do mundo real, como sobreposição de tarefas, janelas de tempo, jornadas duplas, dentre outras, e
apresentá-las como inviabilidades ou restrições que dificultam a resolução do
problema proposto;
• Desenvolver um pacote computacional para a resolução dos problemas propostos, utilizando, para tal, algoritmos metaheurísticos como Iterated Local
Search (ILS) e Variable Neighborhood Search (VNS), para realizar buscas de
melhores soluções em estruturas de vizinhanças e para o refinamento destas
soluções;
• Aplicar os modelos propostos para a resolução, via o pacote computacional
desenvolvido, em instâncias fictícias e reais de dados para o planejamento de
equipes de saúde;
• Avaliar e criticar o modelo proposto e as soluções computacionais encontradas.
1.3
Organização do Trabalho
Esta dissertação está organizada da seguinte maneira: no capítulo 2, são revisados os principais métodos de resolução de problemas de otimização combinatória
relacionados à programação de equipes e tarefas: Problemas de Programação de Tripulações, Problemas de Programação de Enfermeiras e Problemas de Programação
de Quadro de Horários. O capítulo 3 apresenta os principais conceitos que abrangem o sistema de atenção básica à saúde e assistência pré-hospitalar no âmbito da
saúde pública, incluindo as estruturas do PSF e da UPA. A seguir, no capitulo 4,
são apresentados os modelos de dados a serem explorados pelos algoritmos de otimização para programação de equipes do PSF e UPA, como também os modelos
exatos de formulação matemática para cada programação. O capítulo 5 faz uma
breve revisão sobre métodos heurísticos, apresentando definições de heurísticas de
construção, heurísticas de refinamento e metaheurísticas. O capítulo 6 apresenta as
soluções computacionais propostas, as metodologias e os movimentos para busca de
soluções factíveis. Os resultados alcançados para os problemas de programação de
equipes de saúde pública, assim como suas interpretações, são mostrados no capítulo
6.4 e, por fim, as conclusões deste trabalho e as propostas para trabalhos futuros
estão expostas no capítulo 7.
Capítulo 2
Revisão dos modelos de Otimização
Combinatória Para Resolução de
Problemas de Programação de
Equipes
Este capítulo faz uma revisão dos problemas mais comuns de otimização combinatória para programação de equipes, suas aplicações e traz um estudo bibliográfico
para estes tipos de problemas. Na seção 2.1, é dada uma introdução sobre os modelos
de programação de equipes e suas características gerais. Na seção 2.2, é apresentado
o modelo do problema de programação de tripulações e discutida sua importância
em transportes urbanos e viários; a seção 2.3 apresenta o problema de programação
de enfermeiras, suas categorias e revisão bibliográfica; e, por fim, na seção 2.4 é
descrito o problema de programação de quadro de horários, os tipos mais comuns e
sua aplicação.
2.1
Caracterização do Problema
Elaborar um modelo de programação de equipes de trabalho não é uma tarefa
trivial. Este trabalho exige o estudo de um volume muito grande de informações,
o que torna o torna de difícil resolução e sujeito à ocorrência de uma variedade de
conflitos entre os diversos elementos envolvidos. Deve-se ter um conhecimento prévio
de escalas de trabalho, mão-de-obra disponível, variações das equipes entre os turnos,
períodos de trabalho, preferências dos funcionários, enfim, todo um conjunto de
variáveis complexas, mas necessárias para o mecanismo de trabalho e que demandam
um conhecimento indispensável.
Este é um tipo de trabalho em que, dependendo da dimensão do problema, é
praticamente impossível alcançar uma solução ideal pela sua resolução de forma
manual ou através de um método exato em tempo hábil.
Em várias empresas, públicas e privadas, este tipo de trabalho tem ganhado
muito importância. Uma vez que se queira obter melhores margens de lucros, redução de custos operacionais e melhor aproveitamento dos recursos disponíveis, estudos envolvendo modelagem de programação de equipes, com recursos matemáticos
4
2.2
Revisão dos modelos de Otimização Combinatória para PPE
5
e computacionais, têm fornecido bons resultados para estas empresas.
Existem, na literatura, vários trabalhos relacionados à programação de equipes.
Ernst et al. (2004) identificaram 28 categorias de métodos que têm sido usados
em problemas de programação de pessoas, dentre 700 trabalhos disponíveis na literatura desde 1950. Uma das razões para esse número expressivo de categorias é
devido ao fato de que não é possível a construção de um modelo matemático único
que se adeque a qualquer problema. Cada problema possui características específicas, que devem ser levadas em consideração no momento de elaboração do modelo
matemático. Programação de empregados envolve cobertura de pessoal, orçamento
e programação de tarefas a curto prazo. Embora esses campos tenham horizontes
variáveis, eles são fortemente interrelacionados (Burke et al., 2004b).
Dentre os modelos estudados por Ernst et al. (2004), pode-se destacar os modelos
de problemas do tipo scheduling: programação de tripulações (crew scheduling),
programação de escalas de enfermeiras (nurse rostering) e programação de quadro
de horários (timetabling).
O problema de Programação de Tripulações (Crew Scheduling) tem sido amplamente aplicado na programação de tripulação de vôos e de transporte público. O
problema de Programação de Escalas de Enfermeiras (nurse rostering), além de aplicação do modelo para programação de escalas de enfermeiras, também tem grande
aplicação na programação de atendentes de call centers e equipes multiprofissionais. O Problema de Programação de Horários (timetabling) tem larga utilização
em alocação de professores no quadro de horários de escolas(school timetabling),
programação de horário de cursos (course timetabling) e programação de horário de
exames (exame timetabling).
A maioria dos problemas de programação de equipes e tarefas tem três classes
de variáveis independentes, que são chamadas de dimensões, segundo Causmaecker
et al. (2004): Pessoal (P), tempo (T) e tarefas ou deveres (D). A dimensão Pessoal
consiste em todos os empregados envolvidos no problema, divididos em grupos, de
acordo com a capacidade de cada um. A dimensão Tempo pode ser subdividida em
períodos de tempo a serem programados. Estes períodos podem ser diferenciados
para horários noturnos ou feriados. Estas três variáveis (P, T e D) definem um espaço
de dimensão tridimensional. Neste espaço, a maioria das posições é infactível devido
às restrições dos problemas tratados, que podem ser rígidas ou flexíveis, dependendo
do problema tratado.
Em alguns casos, como problemas de quadro de horário escolar, que envolve grupos diferentes de estudantes, salas de aula, professores e divisão de tempo em horas,
há uma quarta dimensão, chamada de Local (L). Os grupos de estudantes correspondem às tarefas, os professores são os funcionários e as salas de aula são os locais.
No caso de problemas de transporte, a tarefa e o local são semelhantes, portanto,
não há necessidade de criar uma quarta dimensão. Cada tarefa é caracterizada por
espaços de tempo, local de inicio e local de término.
2.2
Problema de Programação de Tripulações
Os Problemas de Programação de Tripulações (PPT) têm sido objeto permanente de estudo, pois os sistemas públicos de transporte de passageiros têm sofrido
2.2
Revisão dos modelos de Otimização Combinatória para PPE
6
transformações de forma contínua e crescente nos últimos 30 anos, fato que exige,
cada vez mais, a elaboração de estratégias para melhor aproveitamento dos recursos
disponíveis. Em programação de tripulações para transporte público, sejam linhas
aéreas ou transporte terrestre, este tipo de planejamento inclui muitas variáveis,
interdependentes e desafiadoras: tripulações, rotas, manutenção de equipamentos,
inventário, janelas de tempo de trabalho, enfim, fatores que tornam esta tarefa complexa e extremamente inviável para a resolução manual.
Em geral, o objetivo deste tipo de programação é determinar o conjunto de
tarefas ou rotas que as tripulações devem cumprir, de forma que, considerando as
restrições existentes, como trocas, janelas de tempo e períodos de descanso, gerem
o menor custo possível, mas que garantam que as tripulações cumpram todas as
tarefas existentes.
São características destes tipo de problema, segundo Rishnan e Johnson (2005):
• As tripulações são programadas segundo os pontos de embarque inicial e chegada final, podendo ocorrer troca dessas tripulações entre um embarque e
outro. Essas trocas dependem da existência de pontos de troca de tripulações
coincidentes com os horários de troca e distância da rota. A programação deve
minimizar o custo gerado por essas trocas, respeitando as restrições impostas
e legislação trabalhista e observando rotas e o volume de trocas necessário;
• Quanto aos horários de saída de veículos para uma determinada rota: deve
existir um quadro de horários que apresente todos os veículos com horários
de saída e rotas a serem cumpridas. Este quadro deve prever os períodos
necessários para a manutenção do veículo, tempo percorrido por cada rota e
horários de chegada. O quadro é baseado em demandas de mercado. Esta
estrutura pode ser aplicada em transporte terrestre ou aéreo;
• Alocação dos veículos: os veículos são alocados segundo o custo e lucro da
rota a ser percorrida. Leva-se em conta a demanda requerida e o tamanho
do veículo, objetivando-se a realização de todas as tarefas, respeitando-se as
restrições impostas e maximizando a margem de lucro;
• Normalmente, as programações de rotas e tripulações são geradas mensalmente, observando-se as restrições do problema e períodos de folgas, férias,
horários de menor demanda, dentre outros fatores que influenciam no custo.
O numero de tripulações tende a ser muito grande, quando mal programada.
O mesmo acontece com o número de veículos. Além disso, muitas regras de
trabalho complexas e regulamentos de segurança têm que ser satisfeitos.
O primeiro e o último ítens são o foco principal de uma programação de tripulações. Esta programação começa com o problema de otimização diária das trocas de
tripulações, para então serem feitos os ajustes necessários para a semana, prevendose horários de menor demanda e fins de semana. Então, planeja-se como serão
as trocas durante o mês, prevendo-se férias, feriados, períodos de descanso, entre
outros.
As restrições para este tipo de problema podem aparecer na forma da legislação
trabalhista, preferência dos funcionários, horários de entrada e saída de funcionários,
posto de trocas e outras relativas ao problema tratado especificamente.
2.3
Revisão dos modelos de Otimização Combinatória para PPE
7
Um modelo matemático para este tipo de problema deve considerar todas as
possíveis soluções, cujo número tende a crescer numa razão exponencial em relação
à dimensão do problema. Nesta linha, vários autores têm desenvolvido modelos
capazes de gerar escalas de tripulações que satisfaçam às restrições impostas, com
menor custo possível.
2.2.1
Revisão Bibliográfica
Uma proposta inicial de automação para programação de Problemas de Programação de Tripulações (PPT) foi descrita por Elias (1964), com o uso de heurísticas,
porém sem a garantia de otimização do resultado. Esta possibilidade veio a acontecer com a iniciativa de Manington e Wren (1975). Com o advento de metaheurísticas
capazes de fugir de ótimos locais, como os Algoritmos Genéticos, Simulated Annealing e Busca Tabu, a resolução do PPT expandiu-se para novos horizontes, pois,
mesmo que não garanta encontrar o ótimo global, pode-se incluir com facilidade
qualquer tipo de restrição.
Ambil et al. (1992) estudaram a seqüência de vôos que começam e terminam
em uma base de troca de tripulações. O objetivo do trabalho foi a minimização
de custos, considerando que um membro da tripulação trabalha em 4 ou 5 equipes,
por semana. Os autores relatam que o Método Branch and Bound não produziu
bons resultados na resolução do problema proposto. A resolução foi realizada por
programação linear, usando uma coluna para cada grupo de funcionários.
Pezzella e Faggioli (1997) propuseram um método computacional efetivo para
produzir soluções boas para problemas com mil restrições e em torno de um milhão de variáveis. A resolução é baseada em relaxação lagrangeana e otimização de
sub gradiente. Depois de reduzir o número de linhas e colunas com testes lógicos,
usou-se algoritmos heurísticos gulosos para construir limites inferiores e superiores
objetivando a produção de soluções de boa qualidade.
Kohl e Larisch (2004) fizeram uma descrição mais inclusiva de linhas aéreas
do mundo real, os tipos de problemas do tipo rostering, modelagem e otimização.
Descrevem como os modelos matemáticos capturam as varias restrições e objetivos
na indústria de linhas aéreas.
2.3
Problemas de Programação de Enfermeiras
Programação de enfermeiros é um problema complexo de escala de funcionários
que afeta o funcionamento de hospitais no mundo inteiro. Porém, os termos nurse
rostering e nurse scheduling têm sido utilizados durante anos como modelos de
resolução para problemas de vários tipos de programação de escala de pessoas (Burke
et al., 2004a).
A necessidade de modelos de otimização satisfatórios e soluções de software associadas é devida a uma série de razões. É muito importante a construção de modelos
que representem o mundo real, que sejam flexíveis e que atendam às restrições impostas, como satisfazer desejos e preferências pessoais dos trabalhadores envolvidos,
exigências dos sócios, legislação trabalhista e equilíbrio da carga de trabalho uni-
2.3
Revisão dos modelos de Otimização Combinatória para PPE
8
forme entre as pessoas. Comparado às muitas situações industriais, onde existem
horários regulados de pessoal e consistem de ciclos estáveis de manhã-dia-noite, instituições de saúde freqüentemente requerem mais flexibilidade em termos de horas
e tipos de troca.
Burke et al. (2004b) classificaram os problemas de programação de enfermeiros
(nurse scheduling) nas seguintes categorias:
• Programação de pessoas para Hospital (Hospital Staffing): modelo que envolve
a determinação do número de pessoas necessárias para determinadas especialidades, de acordo com a demanda de trabalho. Fatores que podem tornar esta
tarefa complexa são a estrutura e normas da organização, formas de recrutamento de pessoal, habilidades, preferência dos trabalhadores, necessidade dos
pacientes e outras circunstâncias inerentes à instituição.
• Programação centralizada (centralized scheduling): enfermeiras chefe ou gerentes de unidade são responsáveis por gerar as escalas e horários localmente.
A vantagem é que as enfermeiras recebem uma atenção mais personalizada.
Por outro lado, este tipo de programação pode gerar tratamento preferencial
para alguns funcionários.
• Programação manual (Self-Scheduling): trata-se do processo manual de programação de escalas e horários. Esta técnica consome mais tempo que uma
programação automática, mas tem a vantagem de ter uma cooperação maior
dos profissionais. Programação manual é tão comum que automatização completa não é recomendável.
• Programação cíclica (Cyclical Scheduling): cada pessoa trabalha em ciclos de
um número de semanas. Elas conhecem o seu horário por um longo tempo
e os mesmos padrões de horário são usados inúmeras vezes. Existem benefícios significativos, mas horários cíclicos infelizmente geram um numero muito
grande de falhas, como a impossibilidade de indicar, sem mudanças importantes, muitas das características do problema e preferências pessoais, que fazem
parte dos problemas modernos.
2.3.1
Revisão Bibliográfica
Berrad et al. (1996) desenvolveram uma modelo de programação multi-objetivo
para representar um problema do mundo real, contendo restrições rígidas e flexíveis
em um hospital canadense. O modelo proposto produziu encontros padronizados
por enfermeiras chefes. Foi utilizado Método de Busca Tabu para a solução.
Em 2000, Hofe (2000) apresentou uma proposta de análise de um solução do
problema real de nurse rostering utilizando lógica fuzzy para o tratamento das restrições. A técnica de Branch and bound e iterações de melhoria foram usadas para
rápida produção de bons resultados.
Outra investigação com dados reais, com exploração de soluções por aproximação com algoritmos genéticos, é apresentada em Aickelin e Dowsland (2000). Nesta
2.4
Revisão dos modelos de Otimização Combinatória para PPE
9
referência, mostrou-se a geração de soluções de qualidade para problemas específicos. Embora o método seja para uma instância de problemas em particular, os
conceitos da metodologia proposta poderiam ser aplicados em outros problemas de
programação de enfermeiros.
Em uma revisão de automação de programação de enfermeiros (Burke et al.,
2004a), mostrou-se que, embora existam muitas pesquisas na área, surpreendentemente poucos destes métodos foram testados em instâncias reais de dados. Das
técnicas que têm sido aplicadas em problemas do mundo real, há certa dominância
dos métodos heurísticos. Uma aproximação que tem sido aplicada em vários hospitais é a Busca Tabu com hibridização (Burke et al., 1999). A Técnica de Busca
Tabu foi integrada com técnicas que usualmente são observadas em aproximações de
programação manual. O algoritmo tem sido utilizado para criar escalas de enfermeiros em hospitais com vários tipos de troca, regulamentos de trabalho e categorias
de especialidades. Em Burke et al. (2001) foi proposto um algoritmo híbrido entre
a Técnica de Busca Tabu e uma aproximação evolucionária, com uso de algoritmos meméticos, para produzir uma metodologia que pudesse gerar soluções de alta
qualidade, mas com elevação de tempo computacional.
Bellanti et al. (2004) trataram um problema com restrições rígidas e objetivas,
usando várias técnicas de busca local. Os autores apresentaram bons resultados
para Busca Tabu e Iterated Local Search(ILS) com o uso de vizinhança definida por
mudanças de tarefas nas trocas noturnas.
Burke et al. (2004b) salientam que programação de empregados envolve tarefas,
orçamentos em curto prazo e problemas de alocação. Embora estes campos tenham
vários horizontes, eles estão fortemente inter-relacionados. Os autores consideraram
várias categorias diferentes de enfermeiros em um hospital da Bélgica.
Burke et al. (2005) fizeram uma programação de enfermeiros com heurísticas
híbridas, Variable Neighborhood Search (VNS) e algoritmos genéticos, com busca
de vizinhança variável. Os autores mostraram que a pesquisa pode ser estendida e
a qualidade de solução pode ser melhorada por uma combinação cuidadosa e uso
repetido de heurística ordenada e busca de vizinhança variável.
Em 2007, Burke et al. (2007) estudaram uma variedade de operações de vizinhança, que tem sido utilizada em buscas com Iterated Local Search (ILS), e aproximações metaheurísticas para resolver problemas de programação de enfermeiros.
Os autores testaram e analisaram a eficiência dessas vizinhanças em problemas com
referências em cenários reais. Eles mostraram que os melhores resultados derivam
da combinação de heurísticas para uso: PG (Critério de ganho positivo) com TR
(heurística com restrição de tempo) e WD (seleção de movimentos em dias que tem
violações e que ocorrem depois do ultimo movimento).
2.4
Problema de Programação de Quadro de Horários
Problema de programação de quadro de horários é um tipo especial de problema
do tipo scheduling. Trata-se de um problema em que se busca construir quadros
de horários para uma série de atividades, atendendo a um determinado conjunto de
restrições. Na maioria dos casos, a confecção de um quadro de horários baseia-se
2.4
Revisão dos modelos de Otimização Combinatória para PPE
10
em encontrar uma solução boa e viável dentro de um conjunto de soluções factíveis,
respeitando-se as restrições do problema. Este método foi proposto inicialmente
para resolver problemas de alocação de professores em salas de aula, com o objetivo
de promover a eliminação de inviabilidades como a sobreposição de tarefas e janelas
de tempo.
Em instituições de ensino, programação de quadro de horários é uma das principais atividades administrativa, pois determina o próprio funcionamento da instituição durante o período de sua utilização. Existem várias formulações, tanto para
os professores e estudantes, como também para cursos e exames. Os problemas de
quadro de horários podem ser divididos em três categorias principais: quadro de
horários escolar (Scholar Timetabling), quadro de horários de curso (Course Timetabling) e quadro de horários de exames (Exame Timetabling).
Estes problemas estão sujeitos a muitas restriçõe,s que são divididas em duas
categorias: rígidas e flexíveis. Restrições rígidas são obrigatoriamente atendidas;
restrições flexíveis são desejáveis que sejam atendidas, mas não são essenciais. Em
situações do mundo real, é normalmente impossível satisfazer a todas as restrições
flexíveis. Exemplos de restrições flexíveis são a designação do horário do exame, os
eventos espalhados no tempo, a coerência na formulação do quadro, além da própria
preferência dos profissionais envolvidos.
Um grande número de eventos para serem programados e uma vasta variedade
de restrições impostas no quadro de horários fornecem o material necessário para
construção do conjunto de todas as soluções possíveis. Problemas de quadro de
horários têm chamado a atenção de varias comunidades científicas por em torno de
50 anos, e na última década houve um crescimento de interesse neste campo.
Uma série de aproximações para problemas de quadro de horários tem sido descrita na literatura e testada com dados reais. Estas aproximações podem ser de
quatro tipos:
• métodos seqüenciais, os quais ordenam os eventos usando domínio heurístico
e em um determinado período de tempo, não entrando em conflito uns com os
outros;
• método aglomerado, no qual o conjunto de eventos é dividido em grupos que
satisfazem as restrições rígidas e, então, os grupos são designados para períodos
de tempo para cumprir as restrições flexíveis;
• aproximação baseada em restrições. Neste método, um problema de quadro
de horários é modelado como um conjunto de variáveis tal que valores devem
ser assumidos para satisfazer um número de restrições;
• métodos meta-heurísticos. Nas últimas duas décadas, uma variedade de aproximações metaheurísticas como simulated annealing, busca tabu, algoritmos
genéticos e aproximações híbridas foram investigadas para resolver problemas
de quadro de horários. Os métodos meta-heurísticos começam com uma ou
mais soluções iniciais e empregam estratégias que tentam evitar um ótimo
local. Todos estes algoritmos de busca podem produzir soluções de alta qualidade, mas a um custo computacional considerável.
2.4
Revisão dos modelos de Otimização Combinatória para PPE
2.4.1
11
Revisão Bibliográfica
Colorni et al. (1991) propuseram um algoritmo genético direto que usa uma
matriz para representar o quadro de horários. Cada elemento da matriz é um gene.
Um alfabeto de caracteres é usado para representar os atributos dos eventos. Uma
vantagem deste método é o uso de filtros de algoritmos para gerar soluções factíveis.
Erben e Keppler (1995) recomendaram um método direto para problemas de
quadro de horários de curso semanal. A proposta é usar a técnica clássica de codificação de genes, que representam cromossomos como uma string de bits. Nessa
aproximação, o quadro de horários é definido como o mapeamento de vetor de cinco
elementos: classe, professor, lição, sala e período, em um conjunto binário.
Burke et al. (1995) propuseram um algoritmo genético em que um cromossomo
é representado como uma seqüência ordenada de exames. Um operador crossover
híbrido foi introduzido, onde apenas exames agendados em ambos os pais são escolhidos para a próxima fase.
Inteligência artificial baseada em aproximações com o uso de metaheurísticas
foram consideradas para busca de boas soluções: simulated annealing, busca tabu
e algoritmos genéticos. Abramson et al. (1999) propuseram um algoritmo usando
Simulated Annealing com algoritmos seqüenciais e paralelos. Porém, este algoritmo
é incapaz de escapar de um mínimo local, desde que a temperatura se torne também
baixa.
Schaerf (1999) propôs um algoritmo busca tabu com um método randomizado
não ascendente (RNA). Este método porém trouxe desvantagens quanto ao tempo
computacional, pois busca tabu e RNA são algoritmos interativos e requerem mais
tempo de processamento.
Schaerf e Gaspero (2001) exploraram as técnicas básicas de busca local com
Simulated Annealing e Busca Tabu, e aplicou estas técnicas para resolver variações
específicas de problemas de quadro de horários, tais como quadro de horários escolar,
quadro de horários de curso e quadro de horários de exames.
Um algoritmo genético direto foi proposto por Wilke et al. (2002), sendo os genes
organizados em um modelo de ninho. Este método aplica mecanismos heurísticos e
operadores híbridos para evitar a exploração de todo o espaço de busca e promover a
qualificação dos indivíduos. O algoritmo genético padrão continua até que o número
de gerações sem prover um valor significativo alcance um valor pré-definido.
Chand (2002) propôs uma aproximação heurística para resolver o problema de
quadro de horários com uma vantagem em descartar gerações previas de alocações
geradas. Porem, neste método, algumas restrições flexíveis se tornaram rígidas e
isto dificultou a obtenção de performance nos algoritmos heurísticos.
Souza et al. (2003) usaram busca tabu com uma solução inicial determinada por
uma estratégia gulosa. Este procedimento produz soluções por considerar resultados
factíveis.
Sigl et al. (2003) usaram um cubo 3D correspondente às salas, dias e janelas
de tempo para modelar o quadro de horários escolar. Neste método, cada gene é
um individuo que representa uma classe e cada individuo representa uma solução.
O algoritmo começa com uma solução infactível, e tenta encontrar uma solução
factível. Os autores implementaram a performance do algoritmo usando eliminação
por torneio, permitindo o crescimento do tamanho da população sem reduzir o
2.5
Revisão dos modelos de Otimização Combinatória para PPE
12
algoritmo.
Asmus et al. (2005) criaram um sistema de inferência fuzzy baseado em três das
cinco heurísticas básicas.
Kazarlis et al. (2005) propuseram um algoritmo genético com gene indireto baseado em eventos prioritários. Este método também usa um numero de operadores de
busca local, incluindo operador combinatorial Micro-GA hill-climbing, para evitar
um ótimo local, resolvendo restrições e descobrindo ótimas soluções com eficiência.
Rahoual e Saad (2006) indicaram um método híbrido que combina algoritmo
genético e Busca Tabu. Este último com o objetivo de fugir de ótimos locais.
2.5
Considerações Finais
A revisão dos principais modelos de otimização combinatória para programação de equipes, presentes na literatura, fornece informações sobre as estruturas de
construção de modelos matemáticos propostos para este tipo de problema. Porém,
percebe-se que cada modelo matemático, dentro de uma mesma metodologia, referese a uma instância de dados específica, o que inviabiliza a aplicação de um modelo
específico em outras instâncias de dados. Isto é justificável, pois cada instância de
dados apresenta características específicas a ela, e que não são aplicáveis a outras
instâncias. Ernst et al. (2004) identificaram 28 categorias de métodos que tem sido
usados em problemas de programação de pessoas. Alguns destes métodos são semelhantes, ou seja, foram desenvolvidos para resolver o mesmo tipo de problema.
Embora os modelos matemáticos diferenciem um do outro, em uma mesmo tipo de
problema, a base metodológica é mantida na maioria dos casos.
Quanto a aplicação de heurísticas para resolução destes problemas, a pesquisa
realizada mostrou que heurísticas de busca local, como VNS e ILS, juntamente
com o Busca Tabu, têm sido mais usadas do que heurísticas evolutivas, como os
algoritmos genéticos. Isto pode ocorrer devido ao fato das instâncias de dados para
estes tipos de problemas terem dimensões muito grandes, na maioria dos casos de
instâncias reais, e um elevado volume de variáveis. Ainda, segundo Lourenço et al.
(2002), o método ILS tem sido usado, com sucesso, em problemas do tipo scheduling.
Embora existam muitos trabalhos publicados nessa área, poucos foram aplicados em
instâncias reais, como cita Burke et al. (2004a) para o problema de programação de
enfermeiros.
Outro ponto importante, quando se resolve adotar uma metodologia para um
problema de modelagem qualquer, é o desenvolvimento de um modelo de dados
para o problema a ser tratado. Este modelo de dados deve ser fiel representação dos
fatos que serão estudados. Além disto, o modelo matemático, representando os parâmetros de entrada e variáveis de decisão, deve estar condizente com a metodologia
adotada. Pode ser necessária a adoção de parâmetros de entrada, em detrimento
a de outros que são nativos da metodologia, mas que não devem alterar a base
conceitual de sua estrutura.
Capítulo 3
Definições de Estruturas
Relacionadas ao Atendimento da
Atenção Básica e Pré-hospitalar
Neste capítulo, serão apresentados os principais conceitos que abrangem o sistema de atenção básica à saúde e assistência pré-hospitalar. Entende-se por Atenção
Básica como sendo a assistência médica básica para a população, geo-referenciada,
e que deve ter mecanismos para promover a assistência e o acesso ao sistema de
saúde a todas as pessoas da região pela qual a unidade de saúde de referência é
responsável, educando, prevenindo e garantindo condições mínimas de saúde para a
população. Quanto ao atendimento pré-hospitalar considerado neste trabalho, tratase de unidades de atendimento de urgência/emergência, anterior à hospitalização,
que prestam atendimento especializado a enfermos com necessidade de atendimento
imediato.
O principal objetivo deste capítulo é, assim, fornecer conhecimento sobre a composição e programação de equipes e tarefas para estas estruturas, de modo a fornecer
subsídios para, no Capítulo 4, a apresentação de uma proposta de modelo matemático, que identifique os parâmetros de entrada, juntamente com suas restrições, as
variáveis de decisão e a função objetivo, buscando soluções que apresentem uma melhora na cobertura de atendimento médico para toda a população e promova uma
melhor distribuição das tarefas para as equipes.
O capítulo está organizado da seguinte forma: a seção 3.1 faz uma apresentação
da estrutura proposta para a atenção básica no Brasil, o Programa de Saúde da Família (PSF) e o Núcleo de Apoio à Saúde da Família (NASF), descrevendo um breve
histórico, a composição e programação de suas equipes; as Unidades de Pronto Atendimento (UPA), referentes ao atendimento pré-hospitalar de urgência/emergência,
são apresentadas na seção 3.2.
3.1
Caracterização do Programa de Saúde da Família (PSF)
O Programa Saúde da Família (PSF) apresenta-se como um modelo de atenção
em saúde, baseado na prevenção e na vigilância, que busca articular uma ação
13
3.1
Estruturas da Atenção Básica e Pré-Hospitalar
14
programática com as políticas públicas setoriais e transitórias, segundo definido
na “Avaliação Normativa do Programa Saúde da Família no Brasil” publicada pela
Ministério da Saúde em 2004 (Brasil, 2004). Uma equipe do PSF deve prestar
assistência integral, efetiva, contínua e com qualidade, considerando a perspectiva
da família, por meio da abordagem interdisciplinar, do planejamento de ações do
trabalho e do compartilhamento de decisões.
A Medicina de Família, especialidade reconhecida em vários países, é realizada,
no Brasil, através do PSF. Uma das estratégias implica em atender às necessidades
da população e, ao mesmo tempo, instalar-se nas universidades, seja como disciplina
em cursos de graduação na area médica, seja em programas de pós-graduação.
3.1.1
Histórico
Data de 1973 a primeira tentativa de introdução dessa proposta no Brasil, segundo Campos e Belisário (2001), por uma iniciativa coordenada pela Organização
Mundial de Saúde (OMS) e a Associação Brasileira de Ensino Médico (ABEM), que
promoveram um seminário na Faculdade de Medicina de Petrópolis, intitulado “A
Formação do Médico de Família”. Vem a seguir, como marco inicial desse processo
na América Latina, um seminário realizado em 1978 em Campinas (SP), sobre a
formação do médico generalista. Colocou-se, naquele momento, a preocupação de se
discutir as diferenças existentes entre os diversos projetos em curso: saúde comunitária, medicina social, sanitarismo, preventivismo, dentre outros, e os programas do
médico de família, no intuito de equilibrar a sua formação. Esta proposta ganhou
adeptos, estabeleceu alianças, mas também conviveu com opositores. Um balanço
geral confirma que foi um movimento muito débil: em duas décadas de existência,
as residências de medicina geral da família não formaram mais que poucas centenas
de profissionais e ficaram circunscritas a poucas unidades federadas. Houve enfrentamentos com outras correntes institucionalizadas e resistências à expressão “médico
de família”. A resistência se deu pelo rechaço à idéia de que se segmentasse a assistência, sendo os cidadãos de primeira assistidos pelo especialistas e os pobres pelos
médicos de família, como acontecia em vários países.
A estratégia do PSF foi iniciada no Brasil, de forma mais consistente, em junho de
1991, com a implantação do Programa de Agentes Comunitários de Saúde (PACS).
Em janeiro de 1994, foram formadas as primeiras equipes de Saúde da Família,
incorporando e ampliando a atuação dos agentes comunitários.
As unidades de saúde da atenção básica do programa são capazes de resolver
grande parte dos problemas de saúde em sua comunidade, prestando um atendimento
de bom nível, prevenindo doenças, evitando internações desnecessárias e promovendo
melhoria na qualidade de vida da população.
3.1.2
Composição das Equipes do PSF
As equipes do PSF no Brasil são normalmente compostas por (Brasil, 2004):
• Médico: atende a todos os integrantes de cada família, independente de sexo e
idade, desenvolvendo, com os demais integrantes da equipe, ações preventivas
e de promoção da qualidade de vida da população.
3.1
Estruturas da Atenção Básica e Pré-Hospitalar
15
• Enfermeiro: supervisiona o trabalho do Agente Comunitário de Saúde (ACS)
e do Auxiliar de Enfermagem, realizando consultas na unidade de saúde, bem
como assistindo as pessoas que necessitam de cuidados de enfermagem no
domicílio.
• Auxiliar ou técnico de enfermagem: realiza procedimentos de enfermagem na
unidade básica de saúde e no domicílio, além de executar ações de orientação
sanitária.
• Agente Comunitário de Saúde (ACS): faz a ligação entre as famílias e o serviço
de saúde, visitando cada domicílio pelo menos uma vez por mês; realiza o mapeamento de cada área, o cadastramento das famílias e estimula a comunidade
a aderir ao Programa.
3.1.3
Programação das Equipes no PSF
A programação das equipes no PSF é uma tarefa rotineira, feita no âmbito das
secretarias municipais de saúde. Esta atividade envolve, basicamente, o escalonamento de profissionais para as equipes de saúde da família, normalmente compostas
por um médico, um enfermeiro, um técnico de enfermagem ou auxiliar de enfermagem, juntamente com os agentes comunitários de saúde. Estas equipes devem
atender a uma determinada demanda de usuários, calculada, por via de regra, na
faixa de 2.400 a 4.000 habitantes para cada equipe, dependendo da região assistida
(Brasil, 2004). Há a preocupação de organizações governamentais em prestar assistência em saúde a toda a população, de forma a evitar que os usuários fiquem sem
assistência ou migrem para outras áreas em busca de atendimento. Cada região de
um dado município tem uma ou mais unidades PSF de referência, as quais alocam
as equipes de saúde. Esta região é dividida em áreas e microáreas, e cada microárea
possui uma equipe de saúde responsável por ela. A Figura 3.1 mostra o exemplo de
um município dividido em áreas, e uma das áreas dividida em microáreas.
Algumas características devem ser levadas em conta ao se tratar da programação
de equipes do PSF:
• As equipes são compostas, no mínimo, por um médico de família, um enfermeiro, um auxiliar ou técnico de enfermagem e seis agentes comunitários de
saúde (ACS);
• A equipe pode ser ampliada, tendo, neste caso, a presença de um dentista, um
auxiliar de consultório dentário e um técnico em higiene dental;
• A equipe multiprofissional é responsável por, no máximo, 4.000 habitantes e,
no mínimo, 2.400 habitantes, sendo a média recomendada de 3.000 habitantes,
com jornada de trabalho de 40 horas semanais para todos os seus integrantes;
• O número de ACS deve ser suficiente para cobrir a totalidade da população
cadastrada, com um máximo de 750 pessoas por ACS e de 12 ACS por equipe
de Saúde da Família. No mínimo, devem existir 6 ACS por equipe;
3.1
Estruturas da Atenção Básica e Pré-Hospitalar
16
Município dividido em regiões: áreas e microáreas
Área: 5
População: 6.659 hab.
Área: 7
População: 9.743 hab.
3
10
1
Área: 6
População: 3.734 hab.
12
16
2
4
6
7
5
17
21
20
8
Microáreas
11
9
Área: 8
População: 12.252 hab.
13
19
14
18
15
Figura 3.1: Exemplo de um município dividido em áreas e microáreas.
• O número máximo de equipes por município é determinado pela relação:
N.Equipe_MAX =
População do município
2400
• O número máximo de ACS é determinado pela relação:
N.ACS_MAX =
População do município
400
• Para a região Norte do país, o número máximo de ACS é dado por:
N.ACS_MAX_norte =
População do município População rural do município
+
400
280
• Existe, ainda, a possibilidade de complementar uma equipe do PSF com um
dentista, um auxiliar de consultório dentário e um técnico de higiene dentária.
A esta equipe complementar dá-se o nome de Equipe Estendida. Contudo, o
número de equipes estendidas deve ser, no máximo, igual ao número de equipes
do PSF;
• Existência de um enfermeiro supervisor para cada 30 ACSs.
Uma outra possibilidade é a implantação de uma equipe de profissionais especializados, denominado Núcleo de Apoio à Saúde da Família (NASF), uma vez que a
equipe básica do PSF é constituída por profissionais generalistas. O NASF pode ter
duas composições:
• NASF 1, que deve ser composto, no mínimo, por cinco profissionais distintos
de nível superior, podendo ser: assistente social, professor de educação física,
farmacêutico, fisioterapeuta, fonoaudiólogo, médico acunpunturista, médico
3.1
Estruturas da Atenção Básica e Pré-Hospitalar
17
ginecologista, médico homeopata, médico pediatra, médico psiquiatra, nutricionista, psicólogo e terapeuta ocupacional. Esta equipe do NASF deve esta
vinculada a, no mínimo, oito equipes do PSF, e a, no máximo, vinte equipes.
• NASF 2, que deve ser composto, no mínimo, por três profissionais distintos de nível superior, podendo ser: assistente social, professor de educação
física, farmacêutico, fisioterapeuta, fonoaudiólogo, nutricionaista, psicólogo e
terapeuta ocupacional. Esta equipe do NASF deve esta vinculada a, no mínimo, três equipes do PSF, e é recomendada para municípios com densidade
populacional abaixo de dez habitantes por quilômetro quadrado.
Um grande problema existente hoje é que as microáreas estão em constante
redimensionamento, gerando, em curtos espaços de tempo, novas programações das
equipes de saúde. Outro grande problema no redimensionamento destas equipes é
que normalmente ele é feito manualmente, sem a precisão necessária, com grandes
possibilidades de falhas, principalmente se ocorre contratação demasiada de equipes,
acarretando um custo altamente inviável ou a má distribuição destas equipes.
A programação de equipes de saúde no âmbito do PSF e do NASF pode ser
relacionado a dois problemas clássicos de otimização combinatória: Problema de
Programação de Enfermeiros (Nurse Rostering Problem) e Problema de Programação de Tripulações (Crew Scheduling Problem). Embora estes dois problemas
apresentem questões comuns a serem tratadas pelos algoritmos de solução, como
janelas de tempo, sobreposição de tarefas e preferências de funcionários, cada um
deles, no entanto, tem suas características específicas, como já discutido nas seções
2.2 e 2.3.
O Problema de Programação de Enfermeiros é um modelo combinatorial que
trata do número de enfermeiros em escalas de horários. Algumas variáveis deste
tipo de problema foram observadas para este projeto: escalas de tempo e especialidades dos enfermeiros. O Problema de Programação de Tripulações trata de equipes
multiprofissionais, que devem cumprir um determinado número de tarefas durante o
dia. Uma programação para ambos os modelos é feita anteriormente, normalmente
para um mês.
O tratamento proposto para o Problema de Programação de Equipes do PSF e
NASF é a melhor distribuição de pessoas e/ou famílias a serem atendidas por cada
equipe. Para isto, deve-se considerar as seguintes observações:
• a região, na qual se tem implantado o PSF, é subdividida em “áreas”, as quais
são divididas em “microáreas” e estas em “segmentos”;
• cada microárea deve ser assistida por apenas uma equipe do PSF;
• uma equipe do PSF pode atender a mais de uma microárea, dentro da mesma
área;
• uma equipe não pode atender a mais de uma área;
• não é necessário manter uma sequência de microáreas que será atendida por
uma equipe. É uma restrição flexível, uma vez que deve-se priorizar a melhor
distribuição de pessoas a serem atendidas por equipe.
3.2
Estruturas da Atenção Básica e Pré-Hospitalar
18
• a programação de equipes no PSF não trata de escalas de tempo e, sim, de
escalas de atendimento.
• uma equipe do NASF deve respeitar, conforme sua composição, os parâmetros
mínimo e máximo de vinculação com as equipes do PSF.
Neste trabalho, o território delimitado para a área de uma equipe do PSF é o
mesmo território da área de abrangência, conforme sugerido por Pereira e Barcellos
(2006). As áreas de abrangência são divisões de uma região do município em regiões
estratégicas para atenção básica em saúde, levando-se em consideração o fácil acesso
dos usuários, o perfil epidemiológico e o caráter administrativo, gerencial, econômico
ou político. Uma área de abrangência deve conter uma população o mais homogênea
possível, do ponto de vista socioeconômico e epidemiológico, caracterizando as “áreas
homogêneas de risco”. Além disso, cada área deve conter uma Unidade Básica de
Saúde (UBS), que será a sede da Equipe de Saúde da Família e local de atendimento
da população assistida.
3.2
Caracterização de uma Unidade de Pronto Atendimento (UPA)
Com vista ao atendimento de urgência/emergência pré-hospitalar,o modelo de
Atenção à Saúde propõe tipos de estruturas físicas de assistência e cria mecanismos
para implantação do componente pré-hospitalar fixo, conforme descrito em Brasil
(2009):
• Unidades de Pronto Atendimento (UPA);
• Salas de Estabilização (SE).
A seguir, serão descritas as estruturas de cada componente.
3.2.1
Salas de Estabilização (SE)
As SE são estruturas implantadas em locais apropriados ou unidades de saúde
estratégicos em relação à rede de suporte ao SAMU (Serviço de Atendimento Móvel
de Urgência), e que devem se configurar como pontos de apoio ao atendimento,
transporte e/ou transferência de pacientes críticos e graves nas localidades onde o
SAMU tem caráter regional. Sua implantação é necessária também em locais com
grande extensão territorial de característica rural ou com isolamento geográfico de
comunidades e em regiões com cobertura populacional menor que 50.000 habitantes.
Tabela 3.1: Parâmetros para implantação de SE
Serviço/
Unidade
SE
População da Região
de cobertura
Menor que 50.000 hab.
No de atendimentos
médicos em 24 horas
Demanda
Número mínimo
médicos/plantão
1 médico generalista
habilitado em urgências
3.2
Estruturas da Atenção Básica e Pré-Hospitalar
19
As SE devem prestar atendimento de urgência e estabilização a pacientes que
necessitem de um atendimento imediato, até a sua locomoção para uma unidade de
urgência de maior porte. O seu horário de funcionamento é de vinte e quatro (24)
horas/dia, durante sete (7) dias por semana, e é aceitável a presença de apenas um
médico previamente treinado e habilitado para o atendimento das urgências mais
frequentemente observadas em cada localidade. Segundo o Ministério da Saúde, a
SE deve ser implantada observando os parâmetros da Tabela 3.1.
3.2.2
Unidades de Pronto Atendimento (UPA)
Uma UPA é um estabelecimento de saúde de complexidade intermediária entre
as Unidades Básicas de Saúde ou Saúde da Família e a rede hospitalar, e compõe,
juntamente com estas, uma rede organizada de atenção às urgências. Segundo Brasil
(2009), a UPA deve “articular-se com a Estratégia de Saúde da Família, Atenção
Básica, SAMU, unidades hospitalares, unidades de apoio diagnóstico e terapêutico
e com outros serviços de atenção à saúde do sistema locorregional, construindo fluxos coerentes e efetivos de referência e contrarreferência e ordenando os fluxos de
referência através das Centrais de Regulação Médica de Urgências e complexos reguladores instalados.”
Uma UPA presta atendimento de urgência/emergência para uma demanda populacional regionalizada, agregando assim um serviço assistencial de saúde, no que
tange ao atendimento pré-hospitalar. Existem diretrizes estabelecidas por órgãos
públicos - Ministério da Saúde (Brasil) - e organizações governamentais - Organização Mundial de Saúde (OMS) e Organização PanAmericana de Saúde (OPAS), para
composição de equipes das UPA’s, tendo como parâmetro o critério populacional.
Este é o critério considerado neste trabalho.
3.2.3
Composição das Equipes de uma UPA
Segundo orientações do Ministério da Saúde do Brasil, o dimensionamento e a
organização assistencial dessas unidades devem, no mínimo, ter uma equipe de saúde
composta por médico e enfermeiro nas vinte e quatro (24) horas para atendimento
contínuo de clínica médica e clínica pediátrica. Nos casos em que a região exigir,
considerando-se características epidemiológicas, os indicadores de saúde como morbidade e mortalidade e as características da rede assistencial, poderá ser ampliada a
equipe de saúde, contemplando as áreas de clínica cirúrgica, ortopedia e odontologia
de urgência. Para este trabalho, foram pesquisadas estruturas de organização de
UPA’s em diversas regiões do Brasil, como também os parâmetros recomendados
pela OMS e pela OPAS.
De acordo com Brasil (2009), a estruturação de equipes de trabalho de uma UPA,
por parâmetros populacionais, deve ser preconizado conforme a Tabela 3.2.
Os recursos humanos e a capacidade diária de realizar atendimentos médicos
também são definidos conforme a Tabela 3.2. A Tabela 3.2 ainda mostra que as
UPA são classificadas em três (3) diferentes portes: UPA I, UPA II e UPA III, de
acordo com a população da região a ser coberta.
A pesquisa de quadros de recursos humanos em UPAs já instaladas forneceu um
quadro de profissionais padrão, que é composto por:
3.2
Estruturas da Atenção Básica e Pré-Hospitalar
20
Tabela 3.2: Estruturação de equipes de UPA por parâmetros populacionais
UPA
População da
região de cobertura
50.000 a 100.000
habitantes
Número de atendimentos
médicos em 24 horas
50 a 150
pacientes
Porte II
100.001 a 200.000
habitantes
151 a 300
pacientes
Porte III
200.001 a 300.000
habitantes
301 a 450
pacientes
Porte I
Número mínimo de
médicos por plantão
2 médicos, sendo
um pediatra e
um clínico geral
4 médicos, distribuídos
entre pediatras
e clínicos gerais
6 médicos, distribuídos
entre pediatras
e clínicos gerais
• Médico Clínico Geral;
• Médico Traumato-Ortopedista;
• Médico Pediatra;
• Dentista (UPA porte III);
• Assistente social;
• Enfermeiro;
• Técnico de Enfermagem;
• Técnico de Patologia;
• Técnico de Radiologia;
• Farmacêutico;
• Cirurgião Geral;
• Enfermeiro Chefe.
A carga horária de cada especialidade, assim como o número de profissionais,
deve ser suficiente para atender a população assistida. O Quadro 3.3 apresenta uma
estrutura básica do quadro de categorias profissionais para uma UPA, assim como
a fonte dos parâmetros:
3.2.4
Programação de Equipes para uma UPA
A programação de equipes de uma UPA deve considerar uma série de parâmetros
de entrada, o que torna a tarefa dispendiosa e de elevado nível de complexidade. A
seguir, são apresentados alguns destes parâmetros:
3.2
Estruturas da Atenção Básica e Pré-Hospitalar
21
Tabela 3.3: Estrutura de profissionais, conforme parâmetros e fonte.
Categoria
Médico Clínico
Médico Traumatoortopedista
Médico Pediatra
Assistente Social
Enfermeiro
Téc. Enfermagem
Téc. Patologia Clínica
Téc. Radiologia
Farmacêutico
Cirurgião Geral
Enfermeiro Chefe
Dentista
Carga horária Número de profissionais
diária
no horário
(plantão ou diário)
24 hs
(parâmetro MS)
24 hs
1
Recomendação
24 h
24 h
24 h
24 h
24 h
24 h
8h
24 h
24 h
8h
MS
Pesquisa
OMS
Pesquisa
Pesquisa
Pesquisa
Pesquisa
Pesquisa
Pesquisa
OPS/MPAS
(parâmetro MS)
1
2 para cada 1000 hab.
4 para cada 1000 hab.
2
1
1
1
1
1 para cada 5000 hab.
MS
Pesquisa
Tipos de períodos
Existem quatro tipos de períodos de entrada de profissionais que trabalham vinte e
quatro (24) horas, durante uma semana: manhã, dia, tarde e noite. Estes períodos
são referências com relação ao momento de entrada do profissional na UPA, que pode
ser diferente entre as categorias ou até mesmo na mesma categoria. As Tabelas 3.4
e 3.5 demonstram a divisão de períodos e turnos em uma determinada situação.
Tabela 3.4: Períodos de trabalho
Período
Manha
Dia
Tarde
Noite
Início
07:00
13:00
19:00
01:00
Fim
13:00
19:00
01:00
07:00
Tabela 3.5: Turnos de trabalho - UPA
Turno
Início
Diário
07:00
Noturno 19:00
Fim
19:00
07:00
Tipos de turnos
Quanto aos turnos, o profissional pode assumir suas funções dentre os dois turnos
da Tabela 3.5.
3.2
Estruturas da Atenção Básica e Pré-Hospitalar
22
A carga horária de cada profissional é predefinida pela instituição a qual ele é
vinculado. Em um caso específico, a carga horária semanal de cada profissional é a
apresentada na Tabela 3.6, de acordo com sua categoria.
Tabela 3.6: Carga horária semanal - UPA
Categoria
Carga horária semanal
Médico Clínico
20 hs
Médico Traumato-ortopedista
20 hs
Médico Pediatra
20 hs
Assistente Social
20 hs
Enfermeiro
20 hs
Téc. Enfermagem
30 hs
Téc. Patologia Clínica
30 hs
Téc. Radiologia
24 hs
Farmacêutico
20 hs
Cirurgião Geral
20 hs
Enfermeiro Chefe
20 hs
Dentista
20 hs
Como o período de atendimento de uma UPA deve ser de vinte e quatro (24)
horas, o número de profissionais por turno deve ser respeitado. Porém, entre uma
mesma categoria profissional podem existir diferenças de carga horárias diárias. A
categoria de técnico de enfermagem, por exemplo, pode ter profissionais que trabalham 6 horas diárias, como também profissionais que trabalham em plantões de
12 horas. Situação semelhante pode acontecer com os profissionais médicos, enfermeiros e assistentes sociais que podem ter carga diária de 4 horas, ou plantões de
12 horas, e os outros técnicos com carga horária semelhante ao do técnico de enfermagem. Os farmacêuticos e dentistas têm, obrigatoriamente, carga horária de 4
horas diárias cada um, a serem cumpridas durante o período da manha ou da tarde.
Internamente, os profissionais costumam combinar entre si uma escala de plantão
de 8 horas em alguns dias da semana, mas sempre respeitando a sua carga horária
semanal.
3.2.5
Problema de Escala de Profissionais de uma UPA
Problemas deste porte estão relacionados na literatura como problemas NPdifíceis, e existem métodos de otimização combinatorial que visam melhorar os resultados de uma função objetivo proposta, seja a redução de custos operacionais,
a eliminação de janelas de tempo, a minimização de preferência dos profissionais,
dentre outras questões passíveis de tratamento.
Para que se possa alcançar bons resultados neste tipo de problema, é necessário
atender a um conjunto de restrições, comuns a estes modelos de programação de
equipes, e que devem ser respeitadas. Estas restrições podem ser classificadas como
restrições rígidas (hard constraints) ou restrições flexíveis (soft constraints). A classificação de restrições rígidas e flexíveis depende da função objetivo que se queira
minimizar ou maximizar.
3.2
Estruturas da Atenção Básica e Pré-Hospitalar
23
No caso deste problema, o objetivo é encontrar soluções factíveis que respeitem as restrições de recursos humanos, preferências dos profissionais e legislação
vigente, minimizando a insatisfação de profissionais e maximizando a cobertura de
assistência.
Quanto às restrições, podem-se destacar as seguintes:
• A demanda deve ser atendida em sua totalidade (ou seja, deve haver profissionais em todos os períodos de atendimento);
• O profissional não deve trabalhar por dois turnos seguidos;
• Garantir que o profissional seja escalado para trabalhar em apenas um turno
por dia;
• Um profissional não pode dar assistência a mais de uma população (ou unidade
de saúde) ao mesmo tempo;
• Um plantão não pode ter mais de um profissional da mesma especialidade,
quando este não for permitido;
• Cada profissional tem que cumprir sua carga horária semanal;
• Um profissional não pode estar em dois plantões ao mesmo tempo;
• É preciso respeitar o número mínimo de profissionais necessários para um
bom funcionamento do período/ turno, garantindo também que um número
máximo de funcionários por período/ turno não seja ultrapassado;
• É necessário verificar a indisponibilidade do profissional em trabalhar em determinado período/ turno, a mesma pode ocorrer devido a fatores como férias,
licença maternidade, entre outras.
Tabela 3.7: Número de profissionais por turno - UPA
PERIODO
Médico Clínico
Médico Traumato-ortopedista
Médico Pediatra
Assistente Social
Enfermeiro
Téc. Enfermagem
Téc. Patologia Clínica
Téc. Radiologia
Farmacêutico
Cirurgião Geral
Enfermeiro Chefe
Dentista
Manha
3
1
3
1
2
4
1
1
1
1
1
1
Tarde
3
1
3
1
2
4
1
1
1
1
1
1
Noite
3
1
3
1
2
4
1
1
0
1
1
0
Madrugada
1
1
1
1
2
2
1
1
0
1
1
0
Um ponto importante a ser destacado é a restrição que trata do número de
profissionais por turno, o que deve ser planejado antes do escalonamento. Esta
3.3
Estruturas da Atenção Básica e Pré-Hospitalar
24
programação envolve as questões dos parâmetros anteriormente tratados e apresentará o quantitativo de profissionais, por período, a ser demandado. A Tabela 3.7
exemplifica esta situação.
3.3
Considerações Finais
O propósito do estudo das estruturas de quadro de funcionários de PSF e UPA é a
criação de modelos matemáticos que venham a auxiliar no planejamento das equipes
para estes programas. É comum a falta ou quadro deficitário de profissionais em
instituições de saúde, principalmente nas regidas pelo poder público. Uma dessas
causas é um mal planejamento dessas equipes, que normalmente é realizada de
forma manual e sem parâmetros de referência. Uma UPA, por exemplo, possui uma
estrutura de restrições que podem ser trabalhadas com um modelo de programação
de equipes do tipo scheduling (horários diferenciados, trocas de turnos, períodos manha, dia, tarde e noite).
Um fato importante na modelagem matemática para o PSF e UPA é que o
planejamento das equipes para estes programas tem, como parâmetro principal de
modelagem, a população da região a ser estudada, diferentemente dos modelos para
programação de equipes encontrados na literatura, que tem como parâmetros de
modelagem o volume de atendimentos.
Capítulo 4
Modelagem Matemática Proposta
Para a Programação de Equipes de
Saúde da Atenção Básica e
Pré-Hospitalar - Estudo de Caso
Neste capítulo, são apresentados os modelos de formulação matemática para
programação de equipes do Programa de Saúde da Família (PSF) e das Unidades de Pronto Atendimento (UPA). Estas estruturas de atendimento à saúde foram
apresentadas no Capítulo 3. Os algoritmos propostos devem otimizar o volume de
atendimento feito pelos profissionais de saúde, considerando suas disponibilidades,
volume de tarefas, horários e outras restrições características de problemas de programação de equipes.
A idéia de se criar modelos matemáticos para programação de equipes de saúde
do PSF e UPA partiu da dificuldade que os profissionais de recursos humanos de
uma unidade de saúde possuem para organizar seu quadro de funcionários, seja de
Atenção Básica ou de Urgência/Emergencia, ocasionando em falta de profissionais
de saúde, escalas mal programadas, falta de estratégias para solucionar problemas
de recursos humanos, como férias, licença maternidade, dentre outros. Outro fato
ponderador é a assistência médica à população, que, na maioria dos casos, tem se
mostrado deficiente e insuficiente. Conforme discutido no capítulo 3, estes modelos
devem retratar fielmente as restrições impostas pelos problemas, assim como suas
variáveis de decisão e funções objetivo.
A construção dos modelos de dados para os problemas de programação de equipes
e tarefas do PSF e da UPA demandou adoção de estratégias para a busca de vizinhos
factíveis, objetivando, com a aplicação de métodos heurísticos, encontrar a melhor
solução possível. Em ambos os problemas, os modelos de dados foram desenvolvidos
de forma generalizada, ou seja, houve a preocupação de se desenvolver modelos que
podem ser aplicados em qualquer instância de dados do PSF ou da UPA, ou de
qualquer outro problema com características semelhantes aos problemas tratados.
Em alguns casos, a particularização se dá devido ao porte do município e capacidade
física instalada, mas a estrutura base dos modelos será mantida.
O capítulo está organizado da seguinte forma: na seção 4.1, é apresentada uma
proposta para programação de equipes do PSF, com o objetivo de reduzir a diferença,
25
4.1
Modelagem Matemática
26
entre as equipes, do número de tarefas distribuídas, e proporcionar uma melhor
distribuição das mesmas. Um outro objetivo é tratar da programação do número de
equipes suficiente para cumprir as tarefas propostas. Na seção 4.2, é apresentada
uma proposta de programação de equipes das UPA’s, com o objetivo de otimizar o
quadro de funcionários e o volume de atendimentos, eliminando janelas de tempo
e promovendo a presença de profissionais em todos os horários para os quais existe
demanda.
Para ambos os casos, é apresentado um modelo de organização dos dados para
processamento do algoritmo, assim como é feita a apresentação e a descrição das variáveis de cada problema, o modelo matemático de programação inteira que descreva
o problema em questão, suas restrições e a função objetivo a ser otimizada.
4.1
Arquitetura para o PSF
Nesta seção, será apresentado um modelo em variáveis inteiras de organização
dos dados para programação de equipes do PSF . Como exposto no seção 3.1, a
organização do modelo de saúde da família é o geo-referenciamento da população
por áreas, e estas são divididas internamente por microáreas, as quais são assistidas
por equipes de saúde da família.
4.1.1
Características do Problema
Para geo-referenciamento da população, o município coberto pelo PSF é dividido em áreas, e estas em microáreas. Uma equipe do PSF se responsabiliza pelo
acompanhamento de cerca de 3 mil a 4 mil pessoas de uma determinada área, ou
seja, a equipe se responsabiliza por um certo número de microáreas cuja soma de
suas populações está entre 3 mil e 4 mil pessoas.
As equipes são compostas, no mínimo, por um médico de família, um enfermeiro,
um auxiliar de enfermagem e 6 agentes comunitários de saúde. Quando ampliada,
conta ainda com um dentista, um auxiliar de consultório dentário e um técnico
em higiene dental. Esta composição visa fornecer assistência em saúde básica, e é
constante para todas as equipes do PSF.
Porém, as áreas estão sempre sofrendo modificações na sua subdivisão, devido ao
aumento das populações de suas microáreas. Normalmente, nesta situação, os planejadores redividem a área, renumeram as microáreas e, consequentemente, transferem
algumas familias de uma microárea para outra, como também de uma equipe pra
outra.
A Figura 4.1 exemplifica uma determinada área, subdividida por microáreas de
cobertura de equipes do PSF, conforme Tabela 4.1. No caso, uma equipe A está
responsável pela assistência de 3015 pessoas, correspondentes às microáreas 1, 2, 3,
16 e 19. Uma outra equipe B está responsável por 4658 pessoas, correspondentes às
microáreas 4, 5, 6, 7, 8, 9, 10 e 11, extrapolando assim o limite permitido do total
de pessoas assistidas.
Uma solução para este problema seria a transferência de assistência de algumas
famílias atendidas pela equipe B, georeferenciadas por uma ou mais microáreas, para
serem atendidas pela equipe A, conforme demonstram as Figuras 4.2 e 4.3. Nesta
4.1
Modelagem Matemática
27
Área: 8
População: 12.252 hab.
microáreas
Figura 4.1: Área 8 dividida em microáreas
Tabela 4.1: Área 8 dividida em microáreas e populações correspondentes
Microárea
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
População total
População
502
570
676
457
704
708
562
614
544
528
541
590
412
747
734
532
455
629
735
442
570
12252
simulação, houve a transferência de responsabilidade pela microárea 6 da equipe B
para a equipe A. Logo, a equipe A fica responsável por 3.723 pessoas, enquanto a
4.1
Modelagem Matemática
28
equipe B fica responsável por 3.950 pessoas. Após a transferência das famílias, as
equipes estão responsáveis pelo número de pessoas permitido, não extrapolando os
limites impostos.
Área: 8
População: 12.252 hab.
Pessoas atendidas:
Equipe A
3015
Equipe B
4658
Legenda:
Equipe A
Equipe B
Figura 4.2: Exemplo: Microáreas de responsabilidade de cada equipe PSF
Área: 8
População: 12.252 hab.
Pessoas atendidas:
Equipe A
3723
Equipe B
3950
Microárea transferida
para a equipe A
Legenda:
Equipe A
Equipe B
Figura 4.3: Exemplo: transferência de microárea da equipe B para a equipe A
Uma observação importante neste problema é que as unidades de atendimento
do PSF são fixas, localizadas em um ponto estratégico da área, de forma a facilitar
o acesso a toda a sua população. Estas unidades de atendimento abrigam todas
as equipes responsáveis pela área, porém, os profissionais de cada equipe só podem
atender pessoas residentes nas microáreas de sua responsabilidade. Estas microáreas
não precisam, necessariamente, serem contíguas, ou seja, não precisam ter limites
territoriais comuns. Logo, uma equipe pode, por exemplo, ser responsável pelas
microáreas 1, 2, 6, 15,... até completar o seu limite de pessoas atendidas.
O algoritmo proposto tem como objetivo encontrar a melhor combinação possível,
de forma que todas as equipes responsáveis pela área atendam um número de pessoas
4.1
Modelagem Matemática
29
entre os limites mínimo e máximo, promovendo assim um equilíbrio da distribuição
de tarefas entre elas.
Esta programação de equipes para o PSF envolve algumas características que
devem ser consideradas na elaboração de um modelo matemático, como descrito na
seção 3.1: composição e ampliação das equipes; limites mínimo e máximo de pessoas
atendidas; carga horária semanal; número máximo de equipes de um município,
calculado de acordo com a sua população; números mínimo e máximo de ACS que
podem ser contratados; e outras características que se traduzem em restrições para
a distribuição das tarefas, conforme o modelo matemático proposto.
4.1.2
Descrição do Modelo Matemático Proposto para o PSF
Para resolução do problema de distribuição de tarefas entre as equipes do PSF
de uma mesma área, é proposto um modelo de dados que possa representar a distribuição de familias, por área e microárea, para programação inteira, como mostra
a Tabela 4.2.
A distribuição das variáveis nesta representação dos dados, em uma matriz inteira, é a seguinte: as colunas representam as áreas aj , e as linhas representam as
microáreas mi de cada área. Cada pij representa a população daquela área, para
cada microárea. As áreas têm número de microáreas diferentes, logo existem pij = 0
que representam as áreas que não contém a microárea correspondente.
A representação de uma solução para este problema é em forma de matriz binária,
que mostra a alocação das equipes nas microáreas pelas quais são responsáveis,
em suas respectivas áreas. A Figura 4.4 mostra um exemplo de solução para este
problema. A solução sij = 1 se a equipe j presta assistência para a microárea i, e
solução sij = 0, caso contrário.
area1
area2
microarea
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
5
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
area3
equipes
8
9
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
area4
10
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
11
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
area5
13
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
14
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
15
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Figura 4.4: Modelo da matriz solução para o problema do PSF
16
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4.1
AREA2
538
616
711
532
474
557
703
673
483
560
696
732
451
548
0
0
0
0
0
0
0
0
0
0
0
AREA3
518
746
474
573
462
629
509
740
450
576
714
517
682
664
697
723
735
588
0
0
0
0
0
0
0
AREA4
510
449
414
724
562
630
643
728
642
618
447
497
488
672
517
506
704
645
419
422
681
690
549
459
710
AREA5
426
745
729
401
708
469
638
605
451
744
743
0
0
0
0
0
0
0
0
0
0
0
0
0
0
AREA6
407
506
634
445
419
693
630
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
AREA7
746
507
548
561
452
426
429
629
746
716
568
513
648
500
626
455
673
0
0
0
0
0
0
0
0
AREA8
502
570
676
457
704
708
562
614
544
528
541
590
412
747
734
532
455
629
735
442
570
0
0
0
0
AREA9
716
668
466
479
508
725
554
583
742
448
724
469
629
690
606
577
596
729
527
428
676
442
612
493
0
AREA10
450
424
550
468
489
542
647
517
575
479
507
479
719
605
528
478
0
0
0
0
0
0
0
0
0
Modelagem Matemática
AREA1
477
710
439
723
415
668
560
620
677
740
549
635
513
488
550
723
551
446
404
451
508
577
0
0
0
Tabela 4.2: Modelo de dados para o PSF
30
Para este modelo de dados, a estrutura do problema de alocação de equipes se
torna semelhante ao do problema de programação de enfermeiras, apresentado no
capítulo 2.
MICRO01
MICRO02
MICRO03
MICRO04
MICRO05
MICRO06
MICRO07
MICRO08
MICRO09
MICRO10
MICRO11
MICRO12
MICRO13
MICRO14
MICRO15
MICRO16
MICRO17
MICRO18
MICRO19
MICRO20
MICRO21
MICRO22
MICRO23
MICRO24
MICRO25
4.1
Modelagem Matemática
4.1.3
31
Matrizes e Vetores do Modelo Matemático para o PSF
Esta seção apresenta as matrizes e os vetores presentes na modelagem matemática do problema de distribuição de tarefas para equipes do PSF. Como apresentado
na subseção 4.1.2, a matriz solução é uma matriz binária, e representa se uma equipe
j presta assistência para a microárea i. Além da matriz solução, os parâmetros organizacionais e de preferências profissionais foram apresentados em forma de matrizes
e vetores, apresentados a seguir:
• Vetor de Áreas: este vetor representa as áreas geográficas de atendimento do
PSF, e é classificado numericamente.
• Matriz de Microáreas: informa a qual área j pertence a microárea i.
• Matriz equipes do PSF: informa a qual área j pertence a equipe k.
• Matriz população por microárea: informa população da microárea i da área j.
• Vetor mínimo de pessoas atendidas: este vetor representa o limite mínimo de
pessoas que podem ser assistidas pela equipe k.
• Vetor máximo de pessoas atendidas: este vetor representa o limite máximo de
pessoas que podem ser assistidas pela equipe k.
• Vetor mínimo de microáreas atendidas: este vetor representa o limite mínimo
de microáreas que podem ser assumidas pela equipe k.
• Vetor máximo de microáreas atendidas: este vetor representa o limite máximo
de microáreas que podem ser assumidas pela equipe k.
• Matriz de disponibilidades: esta matriz é binária e representa a disponibilidade
de cada equipe k para assumir cada microárea i da área j .
• Vetor meta de atendimento: informa a meta de atendimento que deve ser
atingida por cada equipe k.
4.1.4
Parâmetros de Entrada e Variável de Decisão
Para construção do modelo matemático, deve-se considerar os seguintes parâmetros de entrada e variável de decisão do problema:
aj : área, coluna da matriz de dados, para j = 1, . . . , m;
wi : microárea, linha de cada área, para i = 1, . . . , n;
ejk : equipe de saúde k na área j, para k = 1, . . . , q, j = 1, . . . , m;
pij : população da microárea i da área j;
bjk : número máximo de pessoas assistidas pela equipe k da área j, k = 1, . . . , q;
4.1
Modelagem Matemática
32
rjk : número mínimo de pessoas assistidas pela equipe k da área j, k = 1, . . . , q;
ljk : número mínimo de microáreas da área j atendidas pela equipe k, k = 1, . . . , q;
hjk : número máximo de microáreas da área j atendidas pela equipe k, k = 1, . . . , q;
dijk : disponibilidade da equipe k para atuar na microárea i da área j. dijk = 1 se
a equipe k está disponível pra atuar na microárea i da área j; dijk = 0, caso
contrário.
fjk : meta de atendimento na área j pela equipe k, k = 1, . . . , q;
xijk : variável de decisão. xijk = 1 se a população da microárea i da área j é
assistida pela equipe k; xijk = 0, caso contrário.
4.1.5
Descrição das Restrições
Nesta seção serão apresentados as restrições impostas ao problema, conforme
modelo de organização do PSF, discutido na seção 3.1.3. O problema proposto tem
uma série de restrições, seja por modelo operacional, por regras institucionais ou
preferências dos profissionais. Para o desenvolvimento deste projeto, foram consideradas as seguintes restrições:
i) O número máximo de pessoas assistidas pela equipe k da área j deve ser
respeitado:
n
X
xijk pij ≤ bjk , (j = 1, . . . , m; k = 1, . . . , q)
(4.1)
i=1
ii) O número mínimo de pessoas assistidas pela equipe k, na área j, deve ser
cumprido:
n
X
pij xijk ≥ rij , (j = 1, . . . , m; k = 1, . . . , q)
(4.2)
i=1
iii) O número mínimo de microáreas da área j, atendidas pela equipe k, deve ser
cumprido:
n
X
xijk ≥ ljk , (j = 1, . . . , m; k = 1, . . . , q)
(4.3)
i=1
iv) O número máximo de microáreas da área j, atendidas pela equipe k, deve ser
respeitado:
n
X
xijk ≤ hjk , (j = 1, . . . , m; k = 1, . . . , q)
(4.4)
i=1
v) Cada microárea i da área j deve ser atendida por uma única equipe k:
q
X
k=1
xijk ≤ dijk , (i = 1, . . . , n; j = 1, . . . , m; k = 1, . . . , q)
(4.5)
4.1
Modelagem Matemática
33
vi) A meta de atendimento na área j pela equipe k deve ser cumprida:
n
X
xijk pij ≥ fjk , (j = 1, . . . , m; k = 1, . . . , q)
(4.6)
i=1
As tarefas a serem executadas, ou seja, o número de pessoas a serem assistidas,
devem ser distribuídas de forma equilibrada, permitindo que o número de tarefas,
entre as equipes, seja menos diferenciado. Diante disto, deve-se diminuir a diferença,
em quantidade, de tarefas entre as equipes. A função objetivo, neste caso, busca
minimizar o número de tarefas para cada equipe, enquanto a restrição (4.6) procura
maximizar o volume de tarefas para cada equipe. Esta estratégia visa encontrar um
ponto de equilíbrio, no que tange ao volume de tarefas, entre as equipes. Outro
objetivo a ser minimizado é o número de equipes por área.
4.1.6
Função Objetivo
A função objetivo para o problema proposto deve retratar, em um modelo matemático inteiro, o número de microáreas atendidas por cada equipe, levando-se em
consideração os limites mínimo e máximo de tarefas ou pessoas que podem ser atendidas pela equipe, objetivando reduzir a diferença, em módulo, do número de tarefas
entre elas. De acordo com a modelagem das restrições, a avaliação das soluções será
dada pela função:
f=
q
n
X
X
xijk pij
(4.7)
k=1 i=1
Esta função representa a função objetivo a ser minimizada para solução do problema, respeitando as restrições impostas ao mesmo.
4.1.7
Modelo Matemático Completo para o PSF
O modelo completo para otimizar a distribuição de tarefas para as equipes do
PSF é apresentado da seguinte forma:
min
q
n
X
X
xijk pij
(4.8)
k=1 i=1
Sujeito à:
n
X
xijk pij ≤ bjk , (j = 1, . . . , m; k = 1, . . . , q)
(4.9)
pij xijk ≥ rij , (j = 1, . . . , m; k = 1, . . . , q)
(4.10)
i=1
n
X
i=1
n
X
i=1
xijk ≥ ljk , (j = 1, . . . , m; k = 1, . . . , q)
(4.11)
4.2
Modelagem Matemática
n
X
34
xijk ≤ hjk , (j = 1, . . . , m; k = 1, . . . , q; k = 1, . . . , q)
(4.12)
xijk ≤ dijk , (i = 1, . . . , n; j = 1, . . . , m; k = 1, . . . , q)
(4.13)
i=1
q
X
k=1
n
X
xijk pij ≥ fjk , (j = 1, . . . , m; k = 1, . . . , q)
(4.14)
i=1
xijk ∈ {0, 1}, ∀i, j, k
4.2
(4.15)
Arquitetura para a UPA
Nesta seção, será apresentado o modelo matemático estruturado para a resolução
do problema de alocação de profissionais em uma Unidade de Pronto Atendimento
(UPA). O algoritmo proposto deve minimizar o número de profissionais, por especialidade, em cada horário, mas respeitando as restrições impostas e garantindo um
quadro de profissionais suficiente para a demanda nos horários. O algoritmo deverá,
também, restringir as jornadas duplas, excesso de horas extras, respeitando os números mínimo e máximo de profissionais para cada horário, os horários de entrada
e saída para cada profissional e suas disponibilidades.
4.2.1
Características do Problema
A seguir, serão apresentadas as características associadas ao problema em questão e que devem ser consideradas no desenvolvimento de um modelo matemático:
• Existem horários diferenciados de entrada. Cada profissional, dependendo de
sua carga horária semanal e diária, tem seu próprio horário de entrada e saída.
Por exemplo, existem médicos clínicos com carga horária de 4 horas por dia e
outros com carga horária de 12 horas por dia, com entrada inicial às 08:00 horas
e 07:00 horas, respectivamente. O mesmo acontece no caso de profissionais do
nível médio, com carga horária de 6 horas e 12 horas, e entrada inicial de 08:00
horas e 07:00 horas, respectivamente;
• Existe uma demanda de profissionais por horário. Em determinados horários
e dias, é necessário que se tenha um numero de profissionais, das diversas especialidades, que seja suficiente para atender a demanda de atendimentos. No
período de 00:00 até 06:00, horas há uma demanda reduzida de atendimento,
logo necessita-se de menor número de profissionais nestes horários. É preciso
também observar o número mínimo de profissionais necessários para um bom
funcionamento do período/turno, garantindo também que um número máximo
de funcionários por período/turno não seja ultrapassado;
4.2
Modelagem Matemática
35
• Pode ocorrer carga horária diferenciada para a mesma categoria profissional.
Profissionais da mesma categoria têm cargas horárias diárias diferenciadas,
mas com a mesma carga horária semanal. Um médico clínico, por exemplo,
assim como a maioria dos profissionais de uma UPA com funcionamento 24
horas, pode assumir cargas horárias diferenciadas. No caso do médico clínico,
pode ser carga diária de 4 horas ou de 12 horas, mas cumprindo, pelo menos, 20
horas semanais; um técnico em enfermagem pode assumir carga horária diária
de 6 horas ou de 12 horas, mas cumprindo, pelo menos, 30 horas semanais; um
técnico em radiologia pode assumir carga horária de 4 horas diárias, cumprindo
carga horária de 24 horas semanais. Porém, uma vez que o profissional assumiu
uma determinada carga horária, de acordo com suas preferências e necessidades
da instituição, deverá cumpri-la por durante todo o mês e não poderá assumir
outra carga horária, a não ser que esteja previsto na legislação vigente. Podem
existir mais de um profissional de saúde da mesma categoria no mesmo horário,
mas não deve ultrapassar o máximo permitido para aquele horário;
• De acordo com a legislação, as diferentes categorias profissionais têm, para
cada uma delas, cargas horárias mínimas e máximas. O profissional, então,
deve cumprir a carga horária para a qual foi contratado, mas, caso haja necessidade, ele poderá cumprir horas extras até um número de horas permitido,
de acordo com sua disponibilidade e necessidade da instituição;
• Jornadas duplas: um profissional não poderá assumir dois turnos seguidos
de trabalho, ou seja, realizar uma jornada dupla. Salvo os casos em que
a legislação permitir, como, por exemplo, enfermeiros que trabalham 4 horas,
podem cumprir outro plantão de 4 horas, totalizando uma carga horária diária
de 8 horas, mas sempre respeitando os limites de horas semanais;
• Turnos de trabalho: preferencialmente, um profissional deve ser escalado de
forma a trabalhar em apenas um turno por dia, seja turno de 12 horas, 06
horas ou 4 horas;
• Indisponibilidade do profissional em trabalhar em determinado período/turno,
devido a preferências pessoais. A mesma pode ocorrer devido a fatores como
férias, licença maternidade, entre outras;
• Existe a necessidade de atender a demanda em sua totalidade (ou seja, deve
haver profissionais em todos os períodos de atendimento).
Para modelar estes fatores, são propostos os vetores e matrizes descritos no item
4.2.3 para, então, no item 4.2.4, estas estruturas se tornem parâmetros de modelagem
matemática para resolução do problema.
4.2.2
Descrição do Modelo Matemático proposto para a UPA
A alocação de profissionais em uma UPA deve obedecer aos parâmetros definidos
pela legislação específica, preferências profissionais e regras organizacionais, de modo
a suprir a demanda de atendimento da população de uma determinada região. Para
que as soluções encontradas para o problema sejam factíveis e atendam às condições
4.2
Modelagem Matemática
36
impostas a ele, é necessário que estes parâmetros sejam apresentados em forma de
matrizes e vetores, que irão interagir com a solução inicial na busca de uma solução
ótima global.
A construção de um modelo de dados para alocação de profissionais em uma
UPA foi baseada na estrutura de dados de um Problema de Programação de Enfermeiros. Algumas características próprias do problema de alocação de profissionais
nas UPA’s, como definidas por Brasil (2009) e apresentadas na seção 3.2, foram
consideradas, levando-se à estruturação de um modelo de dados que condiz com a
realidade do problema.
O objetivo principal deste algoritmo é alocar os profissionais de saúde existentes
de modo a minimizar o excesso de profissionais, por especialidade, em cada horário, e
eliminação das janelas de tempo, respeitando as restrições impostas para o problema.
Neste entendimento, as janelas de tempo são horários que não possuem alocados as
especialidades necessárias para o cumprimento da demanda naquele horário.
Como estudo de caso, serão apresentados os dados do quadro de funcionários da
Unidade de Atendimento Imediato Sete de Setembro, do município de Betim, no
Estado de Minas Gerais. Os dados são referentes ao mês de dezembro de 2008.
A equipe da unidade é composta pelos profissionais e pela quantidade apresentada na Tabela 4.3.
Tabela 4.3: Quadro de Funcionários da Unidade de Atendimento Imediato Sete de
Setembro, em Betim - MG
ESPECIALIDADE
MEDICO CIRURGIAO GERAL
MEDICO CLINICO GERAL
MEDICO EM RADIOLOGIA
MEDICO PEDIATRA
FARMACEUTICO BOTICARIO
FARMACEUTICO BIOQUIMICO
ENFERMEIRO
ENFERMEIRO OBSTETRICO
ASSISTENTE SOCIAL
TECNICO DE ENFERMAGEM
AUXILIAR DE ENFERMAGEM
TECNICO EM RADIOLOGIA
TECNICO EM PATOLOGIA CLINICA
AUXILIAR TECNICO EM PATOLOGIA
TOTAL DE PROFISSIONAIS
NÚMERO DE
PROFISSIONAIS
5
7
1
10
2
1
6
1
3
14
35
5
5
3
98
Para efeitos de implementação do algoritmo e descrição do modelo, as especialidades profissionais receberam as denominações de variáveis nos termos apresentados
na Tabela 4.4.
O número de profissionais por equipe é definido de acordo com a legislação vigente, que tem, como parâmetro, a população da região assistida. Sendo assim, a
equipe multiprofissional de cada UPA deve ser dimensionada de acordo com o exposto no Capítulo 3.2. O modelo de UPA aqui considerado equivale a uma UPA III.
4.2
Modelagem Matemática
37
Tabela 4.4: Denominação de especialidade profissionais
ESPECIALIDADE
MEDICO CIRURGIAO GERAL
MEDICO CLINICO GERAL
MEDICO EM RADIOLOGIA
MEDICO PEDIATRA
FARMACEUTICO BOTICARIO
FARMACEUTICO BIOQUIMICO
ENFERMEIRO
ENFERMEIRO OBSTETRICO
ASSISTENTE SOCIAL
TECNICO DE ENFERMAGEM
AUXILIAR DE ENFERMAGEM
TECNICO EM RADIOLOGIA
TECNICO EM PATOLOGIA CLINICA
AUXILIAR TECNICO EM PATOLOGIA
VARIÁVEL
MCIRUR
MCLIN
MRADIO
MPEDI
FARMBOT
FARBIO
ENF
ENFOB
ASSISTSO
TECENF
AUXENF
TECRADIO
TECPATOL
AUXPATOL
A modelo de dados proposto para a matriz solução é uma matriz binária, tendo
cada elemento xij na forma:
i = profissional;
j = horário de trabalho.
Logo, na matriz, o termo em xij = 1 indica que existe um profissional de uma
especialidade alocado naquele horário, e xij = 0, caso contrário.
A representação da matriz de dados é em forma de matriz binária, conforme
apresentado pela Figura 4.5 e representa uma possível solução. As linhas representam os profissionais disponíveis na instituição, agrupados por especialidade, e são
representados por pi . As colunas representam os horários de trabalho, definidos,
devido à complexidade do problema, de hora em hora, e são representadas por hj .
Cada elemento xij da matriz de dados representa a alocação do profissional i no
horário j. Caso o profissional i esteja alocado no horário j, então xij = 1, e xij = 0,
caso contrário.
HORÁRIO j
SEGUNDA
PROFISSIONAL i
MCIRUR1
MCIRUR2
MCIRUR3
MCIRUR4
MCIRUR5
MCLIN1
MCLIN2
MCLIN3
MCLIN4
MCLIN5
MCLIN6
MCLIN7
...
0
1
2
3
4
5
6
7
8
9
10
11
HOR1 HOR2 HOR3 HOR4 HOR5 HOR6 HOR7 HOR8 HOR9 HOR10 HOR11 HOR12 ...
0
1
2
3
4
5
6
7
8
9
10
11 ...
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Figura 4.5: Modelo da matriz solução para o problema da UPA
4.2
Modelagem Matemática
38
Antes de realizar a alocação dos profissionais, é necessário estabelecer o número
de profissionais, por especialidade, que será alocado em cada horário, respeitando as
restrições de disponibilidade, de horários e de parâmetros institucionais impostas.
A Figura 4.6 representa uma possível solução para a programação de médicos cirurgiões e médicos clínicos. A representação tem a seguinte estrutura: as categorias
profissionais, com diferentes cargas horárias diárias, são representados pelos vetorescoluna da matriz de dados. A categoria MCIRUR4, por exemplo, é representada
pelo j, que informa quantos médicos-cirurgiões, com carga horária diária de 4 horas,
estão presentes no horário i. A categoria MCIRUR12, representada pelo vetor j + 1,
informa quantos médicos cirurgiões, com carga horária diária de 12 horas, estão
presentes no horário i. Logo, para saber quantos médicos cirurgiões estão presentes
no horário i, faz-se a soma do vetor j com o vetor j + 1.
Figura 4.6: Modelo da matriz solução para o problema da UPA
O modelo matemático proposto neste trabalho para a programação de profissionais de uma UPA tem, como base, a matriz representada pela Figura 4.6 e o
modelo de otimização do Problema de Programação de Enfermeiros como referência
metodológica. As subseções seguintes descrevem o modelo matemático com esses
parâmetros para o seu desenvolvimento.
4.2.3
Matrizes e Vetores do Modelo Matemático para a UPA
A Figura 4.5 mostra a matriz solução, e representa os profissionais disponíveis
para a instituição e os horários nos quais serão alocados. Os parâmetros organizacionais e de preferências profissionais são apresentados em forma de matrizes e
vetores, apresentados a seguir:
• Matriz de horários de entrada: esta matriz é binária, e representa os diferentes
horários de entrada para as diversas categorias profissionais. Profissionais de
4.2
Modelagem Matemática
39
uma mesma categoria podem ter horários diferenciados de entrada, assim como
profissionais de categorias diferentes podem ter os mesmos horários de entrada;
• Matriz de disponibilidades: esta matriz é binária e representa a disponibilidade
de cada profissional para cada horário;
• Matriz de número mínimo de profissionais, por categoria: esta matriz representa o número mínimo de profissionais, por categoria, que devem ser alocados
em um determinado horário. O tamanho desta matriz é definido pelo número
de categorias profissionais e pelo total de horários da matriz solução;
• Matriz de número máximo de profissionais, por categoria: esta matriz representa o número máximo de profissionais, por categoria, que podem ser alocados
em um determinado horário. O tamanho desta matriz é definido pelo número
de categorias profissionais e pelo total de horários da matriz solução;
• Vetor com o número mínimo de horas semanais trabalhadas a serem cumpridas,
por profissional: este vetor tem o tamanho i, e representa o número de horas
trabalhadas que devem ser cumpridas por cada profissional da instituição;
• Vetor com o número máximo de horas semanais trabalhadas permitidas, por
profissional: este vetor representa o número máximo de horas trabalhadas que
podem ser cumpridas por cada profissional da instituição;
• Matriz de custos: representa o custo financeiro de manter profissional j no
horário i.
• Vetor de categorias profissionais: este vetor representa o número de categorias
profissionais que são tratadas na matriz solução.
4.2.4
Parâmetros de Entrada e Variável de Decisão
Consideram-se os seguintes parâmetros de entrada e variáveis de decisão do problema, para a construção de um modelo matemático:
Índices
• i = 1, . . . , n horários de trabalho;
• j = 1...m perfis de categorias profissionais (entende-se por cada perfil como
sendo uma categoria de profissional com sua carga horária diária);
• k = 1, . . . , l categorias profissionais;
• t = 1, . . . , w diferentes cargas horárias diárias para uma categoria profissional.
4.2
Modelagem Matemática
40
Parâmetros de Entrada e Variável de Decisão
hi : horário i, corresponde à linha da matriz de dados, para i = 1, . . . , n;
pj : perfil de categoria profissional j, corresponde à coluna da matriz de dados, para
j = 1, . . . , m;
cij : custo do profissionalj para trabalhar no horário i, para i = 1, . . . , n e j =
1, . . . , m ;
eij : entrada do profissional i para trabalhar no horário j, de modo que eij = 1 se
o profissional i pode entrar no horário j; e eeij = 0, caso contrário;
dij : disponibilidade do profissional i para trabalhar no horárioj, de modo que
dij = 1 se o profissional i está disponível para o horário j; e dij = 0, caso
contrário;
ut = tipo de carga horária de uma categoria profissional, para t = 1, . . . , w;
qjk : número mínimo de profissionais da categoria k no horárioj, para j = 1, . . . , m
e k = 1, . . . , l;
sjk : número máximo de profissionais da categoria k no horário j, para j = 1, . . . , m
e k = 1, . . . , l;
F (i): somatório do total de profissionais da categoria, para i = 1, . . . , n;
zj : vetor com o índice de mudança de categoria. Indica, na matriz de dados,
a mudança de uma categoria profissional para outra, para j = 1, . . . , m e
t = 1, . . . , w;
xij : variável de decisão do problema, de modo que xij = 1 se o profissional i esta
atendendo no horário j; e xij = 0, caso contrário.
Seja u o conjunto de cargas horárias que podem ser assumidas por uma categoria
profissional j, u = 1, . . . , w. A função F (i) determina o total de profissionais de uma
mesma categoria j, com cargas horárias diferentes, alocados em um mesmo horário
i, e pode ser descrita como:
F (i) =
w
X
xuj , ∀j ∈ {z}
(4.16)
u=1
A Figura 4.7 mostra um exemplo da aplicação da função F (i).
4.2.5
Descrição das Restrições
Para o desenvolvimento deste modelo, consideraram-se as seguintes restrições:
4.2
Modelagem Matemática
41
Categoria u :
Médico Cirurgião j com
carga horária de 4
horas/dia
Horário i
SEGUNDA
DIA DA SEMANA
HORÁRIO MCIRUR4
MCIRUR12
HOR7
0
HOR8
1
HOR9
1
HOR10
1
HOR11
1
HOR12
1
HOR13
1
HOR14
1
HOR15
1
HOR16
1
HOR17
1
HOR18
1
HOR19
1
HOR20
1
HOR21
1
HOR22
1
HOR23
1
HOR24
0
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
Categoria u :
Médico Cirurgião j
com carga horária
de 12 horas/dia
F(i) = 3
Figura 4.7: Exemplo de aplicação da função F (i)
Restrições
O número mínimo de profissionais por categoria, no horário, deve ser cumprido:
n
X
xij ≥ qjk , (j = 1, . . . , m; k = 1, . . . , l)
(4.17)
i=1
O número máximo de profissionais por categoria, no horário, deve ser respeitado:
n
X
xij ≤ sjk , (j = 1, . . . , m; k = 1, . . . , l)
(4.18)
i=1
O profissional não deve ser alocado em mais de um horário do mesmo dia:
n
X
xij ≤ 1, (j = 1, . . . , m)
(4.19)
i=1
O profissional deve respeitar o seu horário i de entrada:
m
X
xij ≤ eij , (i = 1, . . . , n)
j=1
O profissional i deve estar disponível para o horário i :
(4.20)
4.3
Modelagem Matemática
m
X
42
xij ≤ dij , (i = 1, . . . , n; (j = 1, . . . , m)
(4.21)
j=1
4.2.6
Função Objetivo
A função objetivo representa o custo total, por categoria, do profissional j alocado no horário i. Esta é a função a ser minimizada, e sua representação matemática
é dada por:
f=
n
m
X
X
cij xij
(4.22)
i=1 j=F (i)
4.2.7
Modelo Matemático Completo para a UPA
O modelo completo para otimizar a distribuição de tarefas para as equipes do PSF
é apresentado da seguinte forma:
min
n
m
X
X
cij xij
(4.23)
i=1 j=F (i)
sujeito a:
n
X
xij ≥ qjk , (j = 1, . . . , m; k = 1, . . . , l)
(4.24)
xij ≤ sjk , (j = 1, . . . , m; k = 1, . . . , l)
(4.25)
i=1
n
X
i=1
n
X
xij ≤ 1, (j = 1, . . . , m)
(4.26)
xij ≤ eij , (i = 1, . . . , n)
(4.27)
xij ≤ dij , (i = 1, . . . , n)
(4.28)
i=1
m
X
j=1
m
X
j=1
4.3
Modelagem Matemática
4.3
43
Considerações Finais
A proposta de elaboração de modelos de otimização para solucionar problemas
de programação de equipes em saúde, especificamente em saúde pública, auxilia na
melhoria da qualidade da prestação de serviços em saúde pública, tanto do ponto
de vista dos usuários quanto dos profissionais de saúde. A falta de métodos e
ferramentas de planejamento traz uma série de transtornos para a gestão destes
serviços, como contratação demasiada, insatisfação dos profissionais e pacientes,
falta de profissionais de saúde nos horários que tem demanda de atendimento, dentre
outros problemas causados pelo fato de não existirem métodos eficazes que produzam
soluções em tempo hábil. Normalmente, essas programações são feitas manualmente,
são mensais e devem prever uma série de restrições. Os modelos propostos procuram
englobar as restrições básicas do problema, e algumas que foram percebidas.
As dificuldades encontradas para elaboração dos modelos foram:
• a determinação dos modelos de dados, que foi pensada com a preocupação de
que estes fossem projetados de forma genérica, aplicáveis em todas as situações
que envolvam os problemas em questão;
• a definição da função objetivo a ser tratada em cada problema de programação,
seus parâmetros e variáveis de decisão.
A pesquisa literária apresentou poucos trabalhos relacionados a este tipo específico de problema. Os trabalhos que mais se identificaram com este problema foram
os que trataram do problema de programação de enfermeiros, sendo a maioria deles apresentados por Edmund K. Burke ((Burke et al., 1999), (Burke et al., 2001),
(Burke et al., 2004b), (Burke et al., 2004a), (Burke et al., 2005), (Burke et al.,
2007)), para resolução de programação de equipes de enfermeiros para hospitais e
alguns envolvendo equipes para atendimento homecare. Ainda assim, os parâmetros
para a programação apresentada nesses trabalhos levam em conta o volume de atendimentos por horário, diferentemente dos parâmetros utilizados neste trabalho, que
considera a população residente na região, conforme regras institucionais.
Capítulo 5
Revisão de Heurísticas e
Metaheurísticas
Este capitulo faz uma breve introdução de otimização combinatória, os problemas mais comuns e o uso de heurísticas computacionais como ferramentas para
a resolução de problemas dessa classe. O objetivo deste capítulo é fornecer um
embasamento teórico sobre os métodos combinatórios e estratégias computacionais
adotados por este trabalho.
A seção 5.1 apresenta uma rápida explanação sobre Problemas de Otimização
Combinatória. Na seção 5.2 são abordados os conceitos de Heurísticas e Metaheurísticas, assim como os tipos estudados. A seção 5.3 faz um estudo mais abrangente
sobre Metaheurísticas e sobre a Metaheurística Iterated Local Search (ILS) e suas
especificações. Finalizando, a seção CRevHeur faz algumas considerações a respeito
do presente capítulo.
5.1
Problemas de Otimização Combinatória
Otimização Combinatória é uma estratégia para resolução de problemas discretos, aplicados em tomada de decisões. Muitos destes problemas podem ser encontrados em diversas áreas, tais como problemas de planejamento e programação (scheduling) de produção e pessoas, problemas de corte e empacotamento, roteamento de
veículos, redes de comunicação, problemas de localização, dentre outros.
Problemas desta classe podem ter a seguinte modelagem (Souza, 2007): seja S
um conjunto de variáveis discretas s (soluções), e uma função objetivo f , tal que
f : S → ℜ, que associa um valor real f (s) a cada solução s ∈ S. Deve-se encontrar
uma solução que seja ótima, para s ∈ S, de modo que ou f (·) atinja seu maior valor
(problema de maximização) ou seu menor valor (problema de minimização).
Um problema de otimização pode ser representado pela Figura 5.1, na qual são
mostrados um ótimo local e o ótimo global para o caso de um problema de otimização
contínua. No caso do exemplo apresentado, deseja-se minimizar a função f (s). O
ótimo global é o menor valor assumido pela função objetivo, e um ótimo local é uma
solução de mínimo local em uma região do espaço de busca de soluções.
44
5.2
Revisão de Heurísticas e Metaheurísticas
45
Figura 5.1: Representação de um problema de otimização.
5.2
Heurísticas e Metaheurísticas
Souza (2007) cita que uma heurística pode ser definida como uma técnica que
procura boas soluções, que sejam próximas da otimalidade, a um custo computacional razoável, mas que não garante encontrar a solução ótima. Diversas pesquisas
sobre métodos heurísticos foram realizadas para solução de problemas do tipo scheduling, como os que são abordados neste trabalho.
Heurísticas foram desenvolvidas para resolver classes particulares de problemas.
Somente na década de 1980 que começaram a ser propostos métodos heurísticos com
caráter generalizado e que podem ser aplicados a uma gama maior de problemas.
Esses procedimentos heurísticos foram chamados de metaheurísticas, sendo que sua
característica básica é uma menor rigidez, quando comparadas aos métodos clássicos de resolução de problemas de otimização, e sua capacidade de fugir de ótimos
locais. Blum e Roli (2003) fizeram uma revisão sobre metaheurísticas e problemas
de aplicação.
As heurísticas e metaheurísticas são algoritmos baseados em algoritmos de construção e de otimização. As heurísticas construtivas produzem soluções viáveis para
um problema dado, construindo a solução elemento por elemento. As heurísticas
de refinamento, ou técnicas de Busca Local, são métodos que tentam melhorar uma
solução. Essas heurísticas são baseadas na noção de vizinhança.
5.2.1
Heurísticas Construtivas
As heurísticas construtivas são responsáveis pela construção de uma solução viável para um dado problema. Essas heurísticas constroem a solução elemento por
elemento, de acordo com a função de avaliação escolhida, que, por sua vez, depende
do problema em questão. O pseudocódigo apresentado na Figura 5.2 descreve o
procedimento geral das heurísticas construtivas.
Nas heurísticas clássicas, geralmente os elementos da solução são ordenados por
uma função gulosa, que avalia a melhora trazida por cada elemento. Assim, a cada
iteração, o melhor elemento é escolhido. O tipo mais simples de construção é quando
os elementos são escolhidos de forma aleatória.
As construções gulosas geralmente apresentam resultados muito melhores quando
5.2
Revisão de Heurísticas e Metaheurísticas
46
procedimento HeuristicaConstrutiva(f (·), N (·), s, iterMax)
1 s ← ∅;
2 Inicialize o conjunto C de elementos candidatos
3 enquanto (C 6= ∅) faça
4
e ← escolha um elemento do conjunto C
5
s ← s ∪ e;
6
Atualize o conjunto C de elementos candidatos
7 fim-enquanto;
8 Retorne s;
fim HeuristicaConstrutiva();
Figura 5.2: Pseudocódigo da Heurística Construtiva.
comparadas à construção aleatória. No entanto, assim como na construção aleatória, apresentam a desvantagem de que uma decisão tomada, na inserção de um
elemento, não pode ser alterada. Se a decisão for ruim, não existe a possibilidade
de corrigi-la. As soluções finais, geradas por esses tipos de heurísticas, apresentam
uma diversidade muito pequena, mesmo que sejam utilizadas regras para conduzir
a procura. A utilização de uma componente aleatória na construção pode reduzir
essas desvantagens.
Em problemas NP-difíceis, geralmente as heurísticas construtivas, sejam gulosas
ou aleatórias, não resultam em soluções de boa qualidade e podem conduzir a um
ótimo local, necessitando, assim, de métodos heurísticos de refinamento.
5.2.2
Heurísticas de Refinamento
As heurísticas de refinamento, ou técnicas de Busca Local, são métodos que
tentam melhorar uma solução. Essas heurísticas são baseadas na noção de vizinhança. Uma estrutura de vizinhança é uma função N : S → 2S , que define, para
todo s ∈ S, um conjunto de vizinhos N (s) ⊆ S. O conjunto N (s) é chamado de
vizinhança de s.
Uma solução s′ faz parte da vizinhança da solução s se e somente se s′ é resultado de uma modificação em s, causada por um determinado movimento m, de tal
maneira que continue a fazer parte do conjunto de soluções possíveis.
Portanto, a vizinhança resulta da maneira escolhida para a geração de soluções
viáveis. Tal escolha não possui regras definidas a serem aplicadas em todos os
problemas. Para isso, ela utiliza o conceito de estrutura de vizinhança para explorar
o espaço de soluções do problema de otimização na busca de melhores soluções.
Dois métodos clássicos de busca local são o Método da Descida e o Método de
Descida Randômico. O Método da Descida parte de uma solução inicial s qualquer e,
a cada passo, analisa todos os seus possíveis vizinhos (considerando uma vizinhança
N (s) qualquer), movendo-se somente para aquele que apresentar uma melhora no
valor atual da função de avaliação. Assim, o método para quando um ótimo local é
encontrado. A Fig. 5.3 mostra o pseudocódigo do algoritmo.
O Método de Descida Randômico é uma variação do Método de Descida. Este
5.3
Revisão de Heurísticas e Metaheurísticas
47
procedimento Descida(f (·), N (·), s)
1 V = {s′ ∈ N (s) | f (s′ ) < f (s)};
2 enquanto (|V| > 0) faca
3
Selecione s′ ∈ V, sendo s′ = arg min{f (s′) | s′ ∈ V};
4
s ← s′ ;
5
V = {s′ ∈ N (s) | f (s′ ) < f (s)};
6 fim-enquanto;
7 Retorne s;
fim Descida;
Figura 5.3: Pseudocódigo do método de descida.
método parte de uma solução inicial qualquer e, a cada iteração, escolhe aleatoriamente uma estrutura de vizinhança, que é aplicada à solução corrente. Em seguida,
analisa um vizinho qualquer, movendo-se somente para o vizinho que representar
uma melhora estrita no valor atual da função de avaliação. O método é interrompido após um número fixo de iterações sem melhora no valor da melhor solução
obtida até então.
A Figura 5.4 apresenta o pseudocódigo do método de descida randômico.
procedimento DescidaRandomica(f (·), N (·), s, iterMax)
1 iter = 0; contador de iterações sem melhora
2 enquanto (iter < iterMax) faça
3
iter = iter + 1;
4
selecione aleatoriamente s′ ∈ N (s);
5
Se (f (s′ ) < f (s)) faça
6
iter = 0;
7
s ← s′ ;
8
fim-se;
9 fim-enquanto;
10 Retorne s;
fim DescidaRandomica();
Figura 5.4: Pseudocódigo do Método de Descida Randômico.
5.3
Metaheurísticas
As heurísticas de construção e de refinamento, em geral, não conseguem fugir de
um ótimo local. As metaheurísticas, por outro lado, têm a capacidade de escapar
de ótimos locais, através de estratégias que permitem uma melhor exploração do
espaço de busca.
As metaheurísticas são definidas, de acordo com Osman e Laporte (1996), como
um processo de geração iterativo, que guia uma heurística subordinada, combinando
5.3
Revisão de Heurísticas e Metaheurísticas
48
inteligentemente diferentes conceitos para explorar o espaço de busca. As metaheurísticas podem ser classificadas, segundo o princípio que utilizam para explorar o
espaço de busca, em metaheurísticas baseadas em busca local e metaheurísticas
baseadas em busca populacional.
Nas metaheurísticas baseadas em busca local, a exploração é realizada através
da aplicação de movimentos à solução corrente, que levam o algoritmo a uma solução promissora de sua vizinhança (Souza, 2007). Pertencem a essa categoria as
metaheurísticas Simulated Annealing (SA), Busca Tabu, GRASP e Iterated Local
Search.
As metaheurísticas baseadas em busca populacional se inspiram nos mecanismos
encontrados na natureza. Consistem em manter um conjunto de boas soluções e
combiná-las, de forma a tentar produzir soluções ainda melhores. Se enquadram
nessa categoria as metaheurísticas Algoritmos Genéticos (AG), Algoritmos Meméticos (AM), Particle Swarm Optimization (PSO) e Ant Colony System (ACS). Ainda,
pode-se construir um modelo heurístico híbrido para explorar, com mais objetividade, o espaço de busca das soluções. Em (Burke et al., 2005), o autor mostrou que
a utilização de um modelo híbrido, para resolução do problema de escala de enfermeiros, apresentou melhores resultados em comparação a um modelo de algoritmo
genético, para o mesmo problema.
5.3.1
Iterated Local Search (ILS)
O método Iterated Local Search (ILS) possui muitas das características de uma
metaheurística: simples, robusta, de fácil implementação e de grande efetividade.
O método tem como foco a busca de soluções em um pequeno subespaço de busca,
definida pela solução ótima local, para um dado problema de otimização. O procedimento de busca local pode ser melhorado, gerando-se novas soluções de partida,
alcançadas através de perturbações na solução ótima local. Para retornar resultados de qualidade, o método depende principalmente da escolha do local de busca,
da pertubação e da aceitação de critérios. Segundo (Souza, 2007), o mecanismo de
perturbação deve ser forte o suficiente para permitir escapar do ótimo local corrente
e permitir explorar diferentes regiões. Ao mesmo tempo, a modificação precisa ser
fraca o suficiente para guardar características do ótimo local corrente.
Existem dois critérios que devem ser levados em consideração, em relação ao
nível de perturbação e a aceitação de uma solução corrente: a diversificação e a
intensificação. Estes critérios estão diretamente relacionados com o método de perturbação. Se a perturbação for pequena, a diversificação da busca de soluções fica
próxima à solução corrente; se a perturbação for intensa, a busca será mais expandida, aceitando-se qualquer solução s pertencente ao espaço de soluções.
Embora tenha uma conceituação de simplicidade, o ILS tem se tornado um algoritmo competitivo. A essência do ILS pode ser dada como uma construção interativa
de uma sequência de soluções geradas por outro método heurístico, aceitando soluções de piora, conduzindo a soluções melhores distantes do ótimo local.
Um pseudocódigo geral para o procedimento ILS é apresentado pela Figura 5.6.
A seguir são discutidos os principais elementos desse pseudocódigo:
• Solução Inicial: O ILS inicia em uma solução inicial s0 , de um conjunto S
Revisão de Heurísticas e Metaheurísticas
49
Perturbação
Custo
5.3
Espaço de soluções S
Figura 5.5: Visão geral da Metaheurística ILS
de soluções factíveis. Uma solução inicial de boa qualidade pode ser importante para que o ILS possa encontrar soluções mais rapidamente, e melhores
possíveis. Geralmente, se escolhe um método heurístico guloso para encontrar
soluções iniciais. Estes métodos, quando combinados com o ILS, podem trazer algumas vantagens sobre os métodos randômicos (Lourenço et al., 2002):
quando combinados com ILS, soluções iniciais gulosas oferecem soluções de
melhor qualidade, levando, em geral, a menor número de passos, e, portanto,
menor esforço computacional.
Segundo Lourenço et al. (2002), não existem respostas claras sobre a melhor
escolha para gerar uma solução inicial, mas soluções iniciais gulosas parecem
ser recomendadas quando se quer soluções rapidamente, a um baixo curso.
Para muitos, uma solução inicial pode parecer pouco relevante, então escolhese o método de mais fácil implementação. Se for uma aplicação que não sofre
influência persistente da solução inicial por muito tempo, provavelmente o ILS
terá dificuldades de explorar o conjunto S, então outra perturbação ou critério
de aceitação pode ser aceito.
• Busca Local: Conforme demonstra a Figura 5.5, o ILS começa com uma
busca local de soluções factíveis, normalmente uma descida randômica, mas
nada impede de se usar um outro método heurístico. Como não tem possibilidade do algoritmo da descida randômica fugir do ótimo local, ou seja, aceitar
soluções de piora, é aplicada, então, uma pertubação na solução ótima local
s∗, fazendo com que se encontre soluções factíveis s′ , mesmo que de piora. Ao
encontrar s′ , aplica-se novamente a heurística inicial, no caso a descida randômica, para se encontrar melhores soluções. Se após a aplicação da descida
randômica em s′ encontrar s melhor que s∗, então s∗ recebe s.
• Perturbação: Quando se aplica uma descida local, o algoritmo considera
5.4
Revisão de Heurísticas e Metaheurísticas
50
procedimento IteratedLocalSearch(s, Min, Max, Itermax)
1 s0 = sc; solução inicial recebe solução corrente
2 s = Busca local(s0); DescidaRandomica em (s0)
3 Iter = 0;
4 enquanto (iter < Iter Max) faça
5
iter = iter + 1;
6
s’ = Perturbação(s); mudança de linhas em s
s’’ = BuscaLocal(s’); DescidaRandomica em (s’)
Se (f(s’’ ) < f(s)) faça
s ← s’’ ;
fim-se;
7 fim-enquanto;
8 Retorne s;
fim IteratedLocalSearch();
Figura 5.6: Pseudocódigo da Metaheurística ILS
como sendo um ótimo global, pois não tem condições de fugir daquele ótimo
local. O ILS escapa deste ótimo local aplicando perturbações no mínimo local.
Uma questão a ser considerada é o quão forte deve ser a pertubação. Se
a perturbação for muito forte, o ILS pode se comportar como uma iniciação
randômica, então é baixa a probabilidade de se encontrar as melhores soluções.
Por outro lado, se a perturbação for muito fraca, a procura local se concentrará
próximo ao ótimo local e a diversificação do espaço de busca estará muito
limitada.
• Critério de Aceitação: O procedimento “critérios de aceitação” determina
se uma solução s é aceita ou não como uma nova solução corrente. Este
procedimento tem uma forte influência na busca de soluções em S. Ele pode
ser usado para controlar o balanço entre a intensificação e a diversificação da
busca. Lourenço et al. (2002) descreve este critério como o sendo o Critério
de Aceitação de Markovian.
5.4
Considerações Finais
Problemas com grande volume de restrições e variáveis, com grau de complexidade exponencial, tendem a ser resolvidos por métodos heurísticos, pois estes métodos trazem uma boa solução a um custo computacional baixo e em tempo hábil,
se comparado aos métodos de resolução exata. Porém, para que o método adotado
seja eficiente, deve-se ter um modelo matemático que represente bem o problema a
ser otimizado.
Em um trabalho de otimização, deve-se testar várias heurísticas para se obter a
melhor solução possível, se não a solução ótima. Em métodos heurísticos, é relevante
a obtenção de uma solução inicial de boa qualidade. Uma boa solução inicial pode
5.4
Revisão de Heurísticas e Metaheurísticas
51
ser obtida por heurísticas de refinamento, como busca local randômica. Também
pode-se utilizar metaheurísticas como o ILS ou Busca Tabu para encontrar soluções
iniciais, e outro método para refinar a melhor solução encontrada.
Capítulo 6
Resultados Computacionais para os
Problemas de Programação de
Equipes de Saúde
Este capítulo apresenta a descrição, a metodologia e a modelagem computacional
dos problemas tratados. O objetivo é apresentar a aplicação de métodos heurísticos nos modelos de dados desenvolvidos e descritos no capítulo 4 e os resultados
alcançados pela solução computacional.
A busca por soluções de qualidade demanda a aplicação de métodos heurísticos
para a busca de soluções factíveis devido à complexidade dos problemas. Por se
tratar de problemas NP-difíceis e não haver estudos anteriores a respeito dos mesmos,
a aplicação de métodos exatos não é viável, pois não retornam boas soluções em
tempo computacional satisfatório. Neste trabalho, a aplicação da metaheurística
Iterated Local Search (ILS), associada com busca local, apresentou bons resultados
com baixo custo computacional e em tempo hábil. O algoritmo ILS foi implementado
em linguagem C++, utilizando a plataforma DEV-C++ versão 4.9.9.2, e executado
em um computador com processador Intel Celeron, com 1 GB de memória RAM, e
sistema operacional Windows XP. Foram utilizadas as instâncias-teste comentadas
no capítulo 4.
Para ambos os casos, a solução inicial foi gerada aleatoreamente, porém, observando as restrições rígidas inerentes a cada um dos problemas, as quais foram
rigorosamente obedecidas. Houve o relaxamento das restrições flexíveis, para que os
algoritmos explorassem melhor o espaço de soluções candidatas e determinassem a
melhor solução inicial para as heurísticas aplicadas.
As seções 6.2 e 6.3 descrevem os problemas-teste para o PSF e para a UPA, respectivamente, assim como a descrição das instâncias e das estruturas de vizinhança
para busca de vizinhos no espaço de soluções factíveis. Nestas seções, particular
atenção foi dada a descrição dos movimentos proibidos na busca de vizinhança variável.
A seção 6.4 apresenta a análise dos resultados alcançados pelas implementações
computacionais e as soluções encontradas, como também a interpretação destes
resultados. Por fim, a seção 6.5 faz algumas considerações quanto aos resultados
encontradas pelo método heurístico.
52
6.2
6.1
Solução Computacional Para os PPE de Saúde
53
Metodologia para Implementação Computacional
Para desenvolver um método eficaz de programação de equipes de saúde pública,
com a elaboração de uma arquitetura capaz de ser adaptável às diversas regiões
e perfis das diferentes populações, fez-se necessária a realização de uma revisão
bibliográfica, com foco na modelagem matemática de problemas para otimização
de programação de equipes e métodos de busca de soluções satisfatórias. Neste
sentido, os principais métodos de análise combinatória propostos para a resolução de
problemas de equipes e tarefas forneceram embasamento científico e técnicas para o
desenvolvimento dos modelos de dados, como propostos no capítulo 4. Estes modelos
de dados, compostos por vetores e matrizes, foram implementados em uma solução
computacional para que pudessem ser manipulados pelos métodos heurísticos, com
o escopo de encontrar as soluções desejadas.
Após a construção computacional das estruturas propostas, foi realizada a implementação de parâmetros para as estruturas de vizinhança variável. A identificação
do espaço de busca de soluções factíveis se fez necessária para que o algoritmo encontre vizinhos candidatos a solução viável. A implementação de movimentos proibidos
e penalizados pelo algoritmo tem a função de delineamento do espaço de busca e a
identificação de soluções infactíveis.
Uma revisão da literatura permitiu a identificação dos principais métodos heurísticos aplicados a problemas do tipo scheduling, o que possibilitou a modelagem dos
algoritmos propostos neste trabalho. O método Iterated Local Search (ILS) tem boa
aplicação neste tipo de problema, como descreve Lourenço et al. (2002), e, associado
ao Método de busca local randômica, foram os métodos heurísticos utilizados neste
trabalho.
Após a modelagem computacional dos problemas tratados, o algoritmo será aplicado em instâncias de dados fictícias e reais do PSF e da UPA, com o objetivo de
analisar o funcionamento adequado da solução computacional, assim como a flexibilidade do método heurístico para fugir de ótimos locais. A análise dos resultados
obtidos nos testes computacionais permitirá a avaliação de desempenho dos algoritmos e sua possível validação.
6.2
Descrição do problema teste para o PSF
Para a solução do problema de programação de equipes do Programa de Saúde da
Família (PSF), foi desenvolvido um algoritmo utilizando a metaheurística Iterated
Local Search (ILS) com busca local gulosa. Nesta implementação, o objetivo é o
equilíbrio da distribuição de tarefas entre as equipes que atendem a uma mesma
área. O modelo de dados utilizado é o de uma instância teste, apresentado na
Tabela 4.2 do capítulo 4.1. A função objetivo representa, em módulo, a diferença do
volume de tarefas atribuídas entre uma equipe e as outras. A Figura 6.1 apresenta
o volume de tarefas atribuídas a cada equipe da Area1. Pela Figura, observa-se a
diferença de tarefas entre uma equipe e outra. O propósito do algoritmo é promover
o equilíbrio de tarefas atribuídas às equipes.
6.2
Solução Computacional Para os PPE de Saúde
6.2.1
54
Inicialização dos Testes Para o Problema do PSF
O problema-teste adotado neste trabalho representa uma instância de dados
gerada aleatoriamente, observando-se todos os aspectos críticos de legislação e organização do PSF. A instância de dados, representada pela Tabela 4.2, contém os
dados referentes à distribuição de população por área e microárea e é composta por
10 áreas e 175 microáreas, e inclui, também, a população residente em cada microárea. Embora seja uma instância reduzida, representa, de maneira fiel, o modelo de
organização da população para assistência do PSF, inclusive a simulação de problemas inerentes à programação de equipes para este programa de saúde, como a má
distribuição de tarefas entre as equipes.
Para geração de solução inicial, foi criando um algoritmo com a finalidade de
distribuir as populações da área por equipes. O algoritmo faz uma contagem da
população da área aj e, a cada soma menor ou igual a 4.000 pessoas, é gerada uma
equipe do PSF para assistir a esta população. A partir daí, o algoritmo estabelece
um parâmetro de distribuição de tarefas e, no caso em estudo, o parâmetro adotado
foi a média de pessoas assistidas por equipe.
Para exemplificar, considera-se as populações da Área1 para a instância teste em
estudo, como apresentado na Figura 6.1. A média de tarefas, ou seja, a população
assistida por equipe, foi de 3.106 pessoas.
População assistida por Equipe do PSF - Area 1 - Instância teste
4500
4000
3992
3734
3613
3500
3000
2500
Pop. Assistida
2000
1500
1085
1000
500
0
equipe1
equipe2
equipe3
equipe4
Figura 6.1: Distribuição de tarefas para equipes do PSF
A soma das diferenças entre as populações atendidas por equipe, em relação ao
parâmetro, foi de 4.042 pessoas, para a solução inicial.
A função objetivo para o problema proposto deve retratar o número de equipes
em cada área e a diferença, em módulo, do número de tarefas entre elas. De acordo
com a modelagem das restrições, a avaliação das soluções será dada pela função 6.1.
Esta função também representa a função objetivo a ser minimizada para solução do
problema, respeitando as restrições impostas.
f=
q
n
X
X
k=1 i=1
xijk pij
(6.1)
6.2
Solução Computacional Para os PPE de Saúde
6.2.2
55
Estrutura de Vizinhança
Gerada a solução inicial, foi iniciado, então, o algoritmo heurístico para busca
de soluções factíveis na vizinhança. O movimento de busca local é feito através do
Método de Descida Local gulosa, buscando a melhor solução para a função objetivo
do que a da solução inicial. Este procedimento se deu pela troca de microáreas
assistidas entre as equipes, dentro da mesma área, e suas respectivas populações.
O primeiro movimento a ser realizado é encontrar uma solução factível s′ vizinha
de s, como apresentado pelo pseudocódigo da figura 6.2.
procedimento slinhaP SF (s)
1 s0 = s; Solução inicial recebe solução
2 para área j ← 1 até total_area faça
3
selecione aleatoriamente uma área j;
4
selecione aleatoriamente uma microárea i que admite população;
5
selecione aleatoriamente outra microárea i que admite população;
6
permute a alocação das equipes nestas microáreas;
7
j + 1;
8 fim-para;
fim slinhaP SF ();
Figura 6.2: Pseudocódigo para busca em vizinhança variável - PSF.
A solução s′ encontrada é então avaliada pela função de avaliação, para que
possa ser validada como solução factível. O pseudocódigo da figura 6.3 apresenta o
algoritmo utilizado para implementação desta função de avaliação.
procedimento avaliaP SF (s, metaArea)
1 saval = s; Solução avaliação recebe solução
2 avalSol = 0;
3 para área j ← 1 até total_area faça
4
parametroArea = metaArea;
5
avalArea = 0;
6
para microárea i ← 1 até total_microarea faça
7
avalArea = avalArea + |parametroArea/nrEquipes − popMicro|;
8
fim-para;
9
avalSol = avalSol + avalArea;
10 fim-para;
11 Retorne avalSol;
fim avaliaP SF ();
Figura 6.3: Pseudocódigo para a função de avaliação - PSF.
6.2
Solução Computacional Para os PPE de Saúde
6.2.3
56
Solução via ILS para o problema do PSF
Os movimentos de troca da heurística devem promover a minimização das diferenças
do número de tarefas entre as equipes, aproximando os valores de número de pessoas
assistidas ao parâmetro estabelecido, promovendo assim uma melhor distribuição das
tarefas.
A figura 6.4 apresenta o pseudocódigo para o método da descida randômica
aplicada ao problema do PSF. A função f (·) representa a função de avaliação da
solução, sendo que: N (·) representa o conjunto de soluções no espaço de busca;
IterMax é o número máximo de iterações; F Os e F Os′′ são variáveis que recebem
os valores da função de avaliação das soluções s e s′ , respectivamente.
procedimento DescidaRandomicaP SF (f (·), N (·), s, iterMax)
1 iter = 0; contador de iterações sem melhora
2 FOs;
3 FOs’;
4 enquanto (iter < iterMax) faça
5
iter = iter + 1;
6
selecione aleatoriamente s′ ∈ N (s);
7
F Os = f (s); recebe o valor da função de avaliação f(s)
8
F Os′ = f (s′ ); recebe o valor da função de avaliação em s’
9
Se (F Os < F Os′) faça
10
iter = 0;
11
s ← s′ ;
12
fim-se;
13 fim-enquanto;
14 Retorne s;
fim DescidaRandomicaP SF ();
Figura 6.4: Pseudocódigo da Descida Randômica para o PSF.
A partir da primeira solução de melhora, foi realizado o procedimento de perturbação do ILS, em que, a partir da solução da busca local, foi realizada trocas duplas
entre as equipes, tentando, assim, escapar do ótimo local. O nível de perturbação
para este algoritmo foi de nível 2.
O pseudocódigo para o procedimento ILS é apresentado pela figura 6.5. Neste
pseudocódigo, pode-se identificar: f (·), função de avaliação; N (·), conjunto de soluções no espaço de busca; s0 , que recebe a solução corrente, s, solução que recebe
descida randômica em s0 ; s′ , que recebe recebe perturbação em s, onde duas equipes
trocam de microareas entre si, dentro de uma mesma área; s′′ , solução que recebe o
valor da descida randômica em s′ ; F Os e F Os′′ , que são variáveis que recebem os
valores da função de avaliação das soluções s e s′′ , respectivamente.
Alguns movimentos de busca local foram considerados como proibidos, pela possibilidade de geração de soluções infactíveis. A Figura 6.6 apresenta um movimento
proibido, em que há uma troca de bits entre as linhas e colunas. Este movimento
6.3
Solução Computacional Para os PPE de Saúde
57
procedimento ILSP SF (f (·), N (·), s, iterMax)
1 s0 = sa ; Solução inicial recebe solução atual
2 s = DescidaRandPSF(s0 );
3 iter = 0;
4 enquanto (iter < iterMax) faça
5
iter = iter + 1;
6
s′ = perturbação (s);
7
s′′ = DescidaRandPSF(s′ );
8
F Os = f (s);
9
F Os′ = f (s′′ );
10
Se (F Os′′ < F Os) faça
11
s ← s′ ;
12
Senão
13
s′ = perturbação (perturbação (s));
14
s′′ = DescidaRandPSFs′ ;
15
F Os = f (s);
16
F Os′ = f (s′′ );
17
Se (F Os′′ < f F Os) faça
18
s ← s′ ;
19
fim-se;
20
fim-se;
21
fim-se;
22 fim-enquanto;
23 Retorne s;
fim ILSP SF ();
Figura 6.5: Pseudocódigo da Metaheurística ILS para o PSF.
pode provocar a alocação de mais de uma equipe para a mesma microárea, como
demonstra a Figura. No exemplo, a microárea 6 estaria sendo assistida por duas
equipes, a equipe 1 e a equipe 3, caso este movimento fosse permitido.
Um outro movimento proibido é a troca de bits entre uma microárea que possui
uma equipe alocada e uma microárea inexistente, como está exemplificado na Figura
6.7. Como a dimensão da matriz solução é baseada na área com o maior número
de microáreas, podem existir janelas de uma coluna referenciando uma microárea
inexistente, como exemplifica a Figura 6.7, na qual a área 1 é composta por 22
microáreas.
6.3
Solução Computacional Para os PPE de Saúde
microarea
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
area1
equipes
2
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
58
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
Figura 6.6: Movimento proibido para o algoritmo do PSF: microáreas com mais de
uma equipe
6.3
Descrição do problema teste para a UPA
No caso deste problema, o objetivo é encontrar soluções factíveis que respeitem as restrições de recursos humanos, preferências dos profissionais e legislação
vigente, minimizando o custo de contratação de profissionais e eliminação de janelas
de tempo, ou seja, horários sem a presença de categorias profissionais exigidas para
aquele horário.
O problema de programação de profissionais de uma UPA envolve uma série de
parâmetros de entrada:
• horários de trabalho;
• categoria profissional;
• custo do profissional ;
• número mínimo de horas semanais trabalhadas a serem cumpridas pelo profissional;
• número máximo de horas semanais trabalhadas a serem cumpridas pelo profissional;
• horário de entrada do profissional;
• disponibilidade do profissional para trabalhar no horário;
• tipo de carga horária de uma categoria do profissional;
• número mínimo de profissionais da categoria no horário;
• número máximo de profissionais da categoria no horário.
6.3
Solução Computacional Para os PPE de Saúde
microarea
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
area1
equipes
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
59
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
Figura 6.7: Movimento proibido para o algoritmo do PSF: microáreas inexistentes
Cada parâmetro deve ser considerado para cada categoria profissional. Profissionais, de uma mesma categoria, por exemplo, podem ter cargas horárias diferenciadas,
mas devem ser tratados com os mesmos critérios de restrição impostos ao problema.
6.3.1
Inicialização dos Testes Para o Problema da UPA
Para resolução do problema, foi construído um modelo de dados que representasse, de forma fidedigna, as características do problema em questão, como descrito
no capítulo 4.
A metodologia base de Otimização Combinatória, para este problema, é o de
Programação de Enfermeiras. Foram consideradas as seguintes características do
problema:
• foram tratadas 6 categorias de profissionais (médico cirurgião, médico clínico,
médico radiologista, médico pediatra, técnico de enfermagem e técnico em
patologia;
• existem três tipos de horário de entrada do profissional na unidade (por exemplo, 08:00-12:00-16:00, 08:00-14:00,07:00-19:00);
• existem dois tipos de carga horária semanal (20 horas e 30 horas);
• existem três tipos de carga horária diária (4 horas, 6 horas e 12 horas).
Nesta implementação, a função objetivo é a descrita na subseção 4.2.6, do capítulo 4, e representa o custo total, por categoria, do profissional j alocado no horário
i, e que deve ser minimizado.
Uma mesma categoria profissional pode ter diferentes cargas horárias diária e
horários de entrada. Por exemplo, um médico clínico, com carga horária diária de
4 horas, tem entrada inicial às 08:00 horas. Um outro médico, com carga horária
diária de 12 horas, tem entrada inicial às 07:00 horas. O somatório do número de
6.3
Solução Computacional Para os PPE de Saúde
60
profissionais em um determinado horário não deve ultrapassar os limites mínimo
e máximo permitidos para aquele horário. Como exemplo, a Figura 6.8 mostra o
modelo de dados parcial para este problema.
DIA DA SEMANA
SEGUNDA
HORÁRIO MPEDI4
HOR7
0
HOR8
1
HOR9
1
HOR10
1
HOR11
1
HOR12
1
HOR13
1
HOR14
1
HOR15
1
HOR16
1
HOR17
1
HOR18
1
HOR19
1
HOR20
1
HOR21
1
HOR22
1
HOR23
1
HOR24
0
MPEDI12 TECENF6 TECENF12
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
4
2
1
4
2
1
4
2
1
4
2
1
4
2
1
4
2
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
Figura 6.8: Distribuição de tarefas para equipes de uma UPA
A instância é composta por 168 horários, que representam o total de horas de
uma semana, e seis diferentes categorias profissionais, com diferentes cargas horárias
semanais e diárias, como também diferentes horários de entrada. Para esta abordagem, o algoritmo ILS foi implementado com busca local randômica. Foi utilizada a
instância-teste comentada na seção 4.2 e representada pela Figura 6.8
Para geração de solução inicial, foi criado um algoritmo com a finalidade de
criar uma distribuição de profissionais, de acordo com os parâmetros de entrada
mostrados anteriormente, nesta seção. A medida que vão se preenchendo os horários,
o algoritmo calcula quantos profissionais tem naquele horário, quais horários estão
com número de profissionais excedente ou insuficiente, e se existem janelas de tempo,
ou seja, sem profissional para atendimento.
6.3.2
Estrutura de Vizinhança
Gerada a solução inicial, foi iniciado, então, o algoritmo heurístico para busca
de soluções factíveis na vizinhança. O movimento de busca local foi feito através
de descida randômica, buscando melhor solução para função objetivo do que a da
solução inicial. Este procedimento se deu pela de alocação de profissionais de um
horário para outro, dentro da mesma categoria. A figura 6.9 apresenta o pseudocódigo do algoritmos para o movimento de busca de vizinhos factíveis. Para execução
do algoritmo, são descritas as seguintes variáveis: s, solução corrente; s0 , solução inicial do algoritmo; horaEntrada, matriz de dados com horas de entrada permitidas;
cargaHoraria, vetor com dados de carga horária de cada categoria profissional;
minP ro, matriz com o número mínimo de profissionais permitidos por horário e
categoria profissional; maxP ro, matriz com o número mínimo de profissionais permitidos por horário e categoria profissional.
6.3
Solução Computacional Para os PPE de Saúde
61
procedimento slinhaUP A(s, horaEntrada, cargaHoraria, minP ro, maxP ro)
1 s0 = s; Solução inicial recebe solução
2 enquanto (horaEntrada for diferente de 1) faça
3
selecione aleatoriamente uma categoria profissional j em horaEntrada;
4
Se (horaEntrada = 1) faça
5
enquanto (horaEntrada for diferente de 1) faça
6
selecione aleatoriamente outro horário de entrada;
7
fim-enquanto;
8
fim-se;
9 permute o número de profissionais entre os dois horários em s;
10 fim-enquanto;
11 Retorne s;
fim slinhaUP A();
Figura 6.9: Pseudocódigo para busca em vizinhança variável - UPA.
A Figura 6.10 exemplifica um movimento permitido realizado pela busca local,
e mostra a alocação de um profissional que inicialmente entraria às 19:00 horas, e
que após o movimento, ele passou a entrar às 08:00 horas.
Figura 6.10: Movimento de busca local para o algoritmo da UPA
Para garantir a factibilidade das soluções encontradas na busca local, foram
determinados alguns movimentos proibidos, como mostram as Figuras 6.11 e 6.12.
Em 6.11, o movimento realizado é proibido pois, mesmo que seja entre profissionais
da mesma categoria, as cargas horárias são diferentes. No movimento apresentado
pela Figura 6.12 ocorre a troca entre profissionais de categorias diferentes. Logo, os
movimentos de troca, nesta estrutura, estão proibidos quando forem de uma coluna
para outra.
Foi considerado também um movimento penalizado, onde ocorre o movimento
de um profissional alocado em um determinado horário para outro horário em que
não há demanda para aquele profissional, ou há extrapolação dos limites mínimo ou
máximo do número de profissionais para aquele horário. A Figura 6.13 representa
este movimento penalizado.
A figura 6.14 apresenta o algoritmo utilizado para implementação da função de
6.3
Solução Computacional Para os PPE de Saúde
SEGUNDA
DIA DA SEMANA
HORÁRIO MCIRUR4
MCIRUR12
HOR7
0
HOR8
1
HOR9
1
HOR10
1
HOR11
1
HOR12
1
HOR13
1
HOR14
1
HOR15
1
HOR16
1
HOR17
1
HOR18
1
HOR19
1
HOR20
1
HOR21
1
HOR22
1
HOR23
1
HOR24
0
62
MCLIN4
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
0
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
0
0
MCLIN12
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Figura 6.11: Movimento proibido para o algoritmo da UPA: troca entre profissionais
de mesma categoria, mas com carga horária diferentes
SEGUNDA
DIA DA SEMANA
HORÁRIO
HOR7
HOR8
HOR9
HOR10
HOR11
HOR12
HOR13
HOR14
HOR15
HOR16
HOR17
HOR18
HOR19
HOR20
HOR21
HOR22
HOR23
HOR24
MCIRUR4
MCLIN4
MCIRUR12
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
0
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
0
0
MCLIN12
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Figura 6.12: Movimento proibido para o algoritmo da UPA: troca entre profissionais
de categorias diferentes
avaliação para a solução s do problema do PSF. São descritas as seguintes variáveis:
s, solução corrente; saval , solução inicial do algoritmo; horaEntrada, matriz de
dados com horas de entrada permitidas; minP ro, matriz com o número mínimo de
profissionais permitidos por horário e categoria profissional; maxP ro, matriz com o
número mínimo de profissionais permitidos por horário e categoria profissional; total,
que recebe a penalização para as restrições de mínimo e máximo de profissionais e
hora de entrada; contaJanelas, que recebe a penalização quanto ao número de
janelas vagas, ou seja, horários sem profissionais; taxaP enal1 e taxaP enal2, que
são as taxas de penalização aplicadas; penalT otal, que representa a penalização
total da solução avaliada.
6.3.3
Solução via ILS para o problema do PSF
A partir da primeira solução de melhora, foi realizado o procedimento de perturbação do ILS, em que, a partir da solução da busca local, foi realizada trocas
duplas entre as categorias profissionais, tentando escapar do ótimo local. O nível de
perturbação para este algoritmo foi de nível 2.
O método da descida randômica, utilizado na implementação do ILS para o pro-
6.3
Solução Computacional Para os PPE de Saúde
63
Figura 6.13: Movimento penalizado para o algoritmo da UPA
procedimento avaliaUP A(s, maxP ro, minP ro, horaEntrada)
1 saval = s; Solução avaliação recebe solução corrente
2 total = 0;
3 penalT otal = 0;
4 contaJanelas = 0;
5 Se ((numP ro > maxP roounumP ro < minP ro)ehoraEntrada = −1) faça
6
total = total + 1 ∗ taxaP enal1;
7
fim-se;
8 Se (numP ro for diferente de 0 e horaEntrada for diferente de −1) faça
9
contaJanelas = contaJanelas + 1 ∗ taxaP enal2;
10 fim-se;
11 penalT otal = (total + contaJanelas);
12 Retorne penalT otal;
fim avaliaUP A();
Figura 6.14: Pseudocódigo para a função de avaliação - UPA.
blema da UPA, é apresentado pelo pseudocódigo da figura 6.15. Neste pseudocódigo,
identificam-se: função f (·), que representa a função de avaliação da solução; N (·)
que representa o conjunto de soluções no espaço de busca; iter, que é o contador
de iterações sem melhora; IterMax é o número máximo de iterações; F Os e F Os′
são variáveis que recebem os valores da função de avaliação das soluções s e s′ ,
respectivamente.
O algoritmo do método ILS para o problema da UPA é apresentado pelo pseudocódigo da figura 6.16, e possui as seguintes variáveis: função f (·), como a função
de avaliação da solução; N (·) como o conjunto de soluções no espaço de busca;
horaEntrada, matriz de dados com horas de entrada permitidas; minP ro, matriz
com o número mínimo de profissionais permitidos por horário e categoria profissional; maxP ro, matriz com o número mínimo de profissionais permitidos por horário
e categoria profissional; iter, que é o contador de iterações sem melhora; IterMax é
o número máximo de iterações; s0 que recebe a solução corrente sc ; s, que recebe a
descida randômica em s0 ; s′ , recebe perturbação em s, onde dois horários trocam o
6.4
Solução Computacional e Análise dos Resultados
64
procedimento DescidaRandUP A(f (·), N (·), s, iterMax, horEntrada)
1 iter = 0; contador de iterações sem melhora
2 FOs; recebe o valor da função de avaliação em s
3 FOs’; recebe o valor da função de avaliação em s’
4 enquanto (iter < iterMax) faça
5
iter = iter + 1;
6
FOs = 0;
7
FOs’ = 0;
8
selecione aleatoriamente s′ ∈ N (s);
9
F Os ← f (s);
10
F Os′ ← f (s′ );
11
Se (F Os < f F Os′) faça
12
iter = 0;
13
s ← s′ ;
14
fim-se;
15 fim-enquanto;
16 Retorne s;
fim DescidaRandUP A();
Figura 6.15: Pseudocódigo da Descida Randômica para a UPA.
número de funcionários entre si, dentro de uma mesma categoria profissional; F Os
e F Os′′ , variáveis que recebem os valores da função de avaliação das soluções s e s′′ ,
respectivamente.
6.4
Análise dos Resultados Computacionais
Esta seção apresenta os resultados das soluções computacionais implementadas
para os problemas de programação de equipes de saúde propostos, assim como a
interpretação destes resultados. Na seção 6.4.1 são mostrados os resultados para
o problema do PSF e uma interpretação gráfica destes resultados. A seção 6.4.2
apresenta os resultados encontrados para o problema da UPA e também os gráficos
interpretativos da solução computacional.
6.4.1
Análise dos Resultados Computacionais Para o Problema do PSF
Após a execução dos testes computacionais para o problema do PSF, obtevese o comportamento médio da execução do algoritmo, como mostra a Tabela 6.1.
Nesta Tabela, as colunas Area1, Area2,..., Area10 representam as diferenças de
distribuição de tarefas entres as equipes daquela área; a coluna FO representa os
valores da função objetivo de cada execução do ILS, sendo que o valor do teste 1
representa o valor da solução inicial. Foram realizados cinco testes para a instância
6.4
Solução Computacional e Análise dos Resultados
65
procedimento ILSUP A(f (·), N (·), s, iterMax, horaEntrada, cargaHoraria, minP ro, maxP ro)
1 s0 = sc ; Solução inicial recebe solução corrente
2 s = DescidaRandUPA(s0 ); solução recebe o valor da descida randômica em s0
3 iter = 0;
4 enquanto (iter < iterMax) faça
5
iter = iter + 1;
6
s′ = perturbação (s);
7
s′′ = DescidaRandUPA(s′ );
8
F Os = f (s);
9
F Os′′ = f (s′′ );
9
Se (F Os′′ < f F Os) faça
11
s ← s′ ;
11
Senão
11
s′ = perturbação (perturbação (s));
7
s′′ = DescidaRandUPA(s′ );
8
F Os = f (s);
9
F Os′′ = f (s′′ );
9
Se (F Os′′ < f F Os) faça
11
s ← s′ ;
12
fim-se;
12
fim-se;
13 fim-enquanto;
14 Retorne s;
fim ILSUP A();
Figura 6.16: Pseudocódigo da Metaheurística ILS para o PSF.
de dados. A Tabela mostra o valor da função objetivo para cada uma das áreas
e o valor global, observando-se uma melhora em torno de 18% do valor da função
objetivo para a solução inicial.
Deve-se ressaltar que, nos testes realizados, considerou-se que o número de equipes é fixo para cada área, e não se considerou as indisponibilidades das equipes.
Não é possível realizar comparação com resultados existentes na literatura para esta
classe de problema teste, pois a instância foi criada com métodos aleatórios e existem
poucos trabalhos com aplicação reais de modelos de otimização para programação
de equipes de saúde da família.
Testes com a instância
Teste 1
Teste 2
Teste 3
Teste 4
Teste 5
Area1
4042
3578
3396
3924
3378
Area2
3518
2998
2862
3188
2820
Area3
517
314
201
337
311
Area4
1308
1282
1402
912
1104
Area5
297
91
87
137
469
Area6
0
0
0
0
0
Area7
1987
1775
1639
1343
1505
Area8
2702
2636
2923
2595
2329
Area9
691
841
1087
1023
450
Tabela 6.1: Resultados dos testes em instância do PSF
Area10
3626
3834
3776
3352
3116
FO
18688
17349
17373
16811
15482
6.4
Solução Computacional e Análise dos Resultados
66
Uma representação gráfica dos resultados é dada pelos gráficos das Figuras 6.17
e 6.18. A Figura 6.17 apresenta a distribuição de tarefas para as equipes da área 1,
da instância teste.
População assistida por Equipe do PSF - Area 1 - Instância teste
4500
4000
3992
3734
886
3500
3613
628
507
Meta: 3106
3000
2500
Pop. Assistida
2021
2000
1500
1085
1000
500
0
equipe1
equipe2
equipe3
equipe4
Gap total: 4042
Figura 6.17: Gráfico da distribuição de tarefas para equipes do PSF da área 1
A Figura 6.18 mostra um melhor equilíbrio na distribuição de tarefas após a execução do ILS, reduzindo assim o GAP da diferença do número de pessoas atendidas
entre as equipes, com relação à meta proposta.
População assistida por Equipe do PSF - Após ILS
4500
4000
3901
3877
795
3500
3229
771
123
Meta: 3106
3000
2500
1689
2000
Pop. Assistida
1417
1500
1000
500
0
eqp1
eqp2
eqp3
eqp4
Gap total: 3378
Figura 6.18: Gráfico da distribuição de tarefas para equipes do PSF da área 1
6.4.2
Análise dos Resultados Computacionais Para o Problema da UPA
A partir da solução inicial encontrada para o problema da UPA, foi aplicado
o algoritmo ILS, conforme descrito na subseção 6.3.2, na busca de soluções que
minimizem o custo total da alocação de profissionais nos horários estipulados. Foram testados vários valores de pesos para a função de penalização. Os resultados
encontrados estão apresentados na Tabela 6.2.
6.5
Solução Computacional e Análise dos Resultados
Teste
1
2
3
4
Valor da função de
Penalização para s
1002000
5970000
59700
5970
Numero máximo
de iterações ILS
10
100
50
50
67
Valor da função de
Penalização para s
987900
5551200
58200
5840
% de melhora
1,41%
7,02%
2,51%
2,18%
Tabela 6.2: Resultados dos testes em instância para UPA
A seguir, os gráficos das Figuras 6.19 e 6.20 mostram o comportamento do algoritmo em relação ao tempo médio de processamento e ao número de iterações. O
gráfico da Figura 6.19 mostra que o índice de melhora da qualidade do resultado
aumenta de acordo com o tempo médio de processamento do algoritmo. Uma outra
avaliação foi quanto às iterações, mostrando que o resultado melhora na medida em
que se aumenta o número de iterações, conforme mostra o gráfico da Figura 6.20.
8,00%
180
7,02%
160
7,00%
6,00%
140
160
120
5,00%
100
4,00%
2,51%
3,00%
80
2,18%
2,00%
% Melhora
Tempo médio (minutos)
60
40
12 1,41%
1,00%
30
30
3
4
0,00%
20
0
1
2
Figura 6.19: Comportamento do algoritmo para o problema da UPA, com relação
ao tempo médio de execução
120
8,00%
7,02%
100
7,00%
100
6,00%
80
5,00%
60
50
2,51%
40
50
2,18%
4,00%
Número máximo de
iterações ILS
% Melhora
3,00%
2,00%
20
1,41%
1,00%
10
0
0,00%
1
2
3
4
Figura 6.20: Comportamento do algoritmo para o problema da UPA, com relação
ao número de iterações
6.5
Considerações Finais
Para este trabalho foram produzidos resultados computacionais com índices de
melhora expressivos e de relevante importância, pois são os primeiros resultados
6.5
Solução Computacional e Análise dos Resultados
68
encontrados via metaheurísticas para este tipo de problema. Foi implementado um
algoritmo ILS (Interated Local Search), com busca local randômica, em C++, para
resolução do problema de programação de equipes da UPA e do PSF. Os resultados
apresentam melhoras na solução inicial de mais de 7% para UPA e de 18% para
PSF.
Em relação ao equilíbrio de tarefas para o PSF, os resultados indicam que houve
uma melhor distribuição de tarefas entre as equipes, ou seja, melhor equalização de
tarefas de modo que as equipes tendam a ter um número de microáreas assistidas
mais próximo da meta estipulada. Além disso, evita-se a contratação de equipes
para assistir a uma microárea que, a princípio, estaria desassistida em detrimento à
sobrecarga de tarefas para uma outra equipe, devido à má distribuição das microáreas.
Quanto aos resultados para a UPA, uma melhor programação de equipes gera
tanto a satisfação dos funcionários, uma vez que suas preferências sejam satisfeitas,
quanto a satisfação dos pacientes, que terão uma cobertura maior de profissionais
nos horários que geram maior demanda de atendimentos. Assim, como no problema
do PSF, evita-se também a contratação desnecessária de profissionais em detrimento
aos horários que alocam um número de profissionais em excesso.
Em suma, estes resultados se traduzem, diretamente, em redução de custo operacional e melhoria na satisfação dos funcionários, uma vez que foi realizada uma
melhor distribuição de tarefas e otimização dos recursos de força de trabalho.
Os algoritmos propostos necessitam de ajustes em seus códigos, pois ainda apresentam dificuldades de sair de um ótimo local. É necessário testá-los com outros
parâmetros e instâncias, além de outros critérios de penalização. Existe, portanto,
grande possibilidade de melhora dos resultados, seja com melhorias na aplicação do
método heurístico adotado, seja com a implementação de outros métodos heurísticos, como o busca tabu e algoritmos evolutivos, como já testado por outros autores
para este tipo de problema, conforme apresentado no capítulo 2.
Diante do exposto, o objetivo é dar continuidade às implementações de métodos
heurísticas, de forma a construir algoritmos mais eficazes na busca de soluções factíveis de boa qualidade, como também testar os modelos propostos em instâncias
de dados maiores.
Capítulo 7
Conclusão e Trabalhos Futuros
Este capítulo trata do fechamento deste trabalho, expressando as conclusões do
autor quanto a pesquisa e desenvolvimento realizados, e apresenta propostas para
busca de melhores soluções para os problemas aqui trabalhados.
7.1
Conclusão
Quando se trata de construção de modelos matemáticos, exige-se um esforço e
dedicação muito grande para desenvolver um modelo que retrate, com fidelidade, o
problema que está sendo estudado. Em se tratando de programação de equipes, o
número de variáveis é elevado, e durante o estudo do problema, uma ou outra pode
passar despercebido, mas que podem alterar bastante a solução final. A modelagem
matemática proposta por este trabalho é relacionada a problemas NP-Difíceis, logo
o grau de complexidade aumenta exponencialmente com o número de variáveis do
problema.
A deficiência no planejamento do quadro de profissionais de saúde incide diretamente sobre a saúde da população, acarretando em custos operacionais, inclusive
custos para o sistema relacionados à falhas na assistência preventiva. A elaboração
de modelos de otimização, para solucionar problemas de programação de equipes em
saúde, não foi por acaso. É grande o volume de informações e variáveis, o que tornou
o trabalho interessante do ponto de vista acadêmico. Não foi encontrada na literatura referências de problemas relacionados a programação de equipes para a saúde
pública, aqui estudados, como também problemas deste tipo tendo como parâmetro
de entrada a população de uma região e, por consequência, a não existência de instâncias de dados para comparações de resultados computacionais. Abre-se, então,
uma margem de pesquisa operacional no que trata de programação de equipes multiprofissionais, envolvendo as restrições apresentadas neste trabalho e parâmetros de
entrada diferenciados .
A literatura estudada forneceu informações sobre várias metodologias para o planejamento de equipes de trabalho, porém com aplicação diretamente relacionada às
características dos problemas tratados pelos autores. Forneceu também informações
sobre as estruturas de construção de modelos matemáticos propostos para problemas semelhantes. O modelo de análise combinatória que mais se assemelhou aos
problemas aqui tratado foi o Problema de Programação de Enfermeiros(PPE). Durante o desenvolvimento do modelo, foram testados também os modelos de Problema
69
7.2
Trabalhos futuros
70
de Programação de Tripulações(PPT) e o Problema de Programação de Quadro de
Horários(PQH).
Outro produto deste trabalho foi o desenvolvimento dos modelos de dados para
representação dos problemas em questão. Os modelos criados procuram representar,
de forma fiel e generalizada, os dados que serão estudados e otimizados. A generalização dos modelos foi fator de grande relevância e abrange as características básicas
existentes em outras instâncias do PSF e UPA.
Os resultados alcançados por este trabalho apresentam melhoras na solução inicial de mais de 7% para UPA e de 18% para PSF, obedecendo todas as restrições
impostas e preferências dos profissionais. Estes são os primeiros resultados encontrados, via metaheurísticas, para os problemas propostos. Espera-se que, após este
trabalho, haja continuidade na implementação de métodos heurísticos para melhorar
a qualidade dos resultados na busca de busca de soluções.
Um dos objetivos deste trabalho é incentivar futuros pesquisadores a investir em
pesquisa operacional, propondo modelos de otimização diferenciados, na busca de
soluções para problemas do nosso cotidiano e voltados para a população em geral,
principalmente no que trata de serviços públicos, como telefonia, saúde, transporte
urbano, entre outros. Espera-se, portanto, que este trabalho seja um ponto de
referência para outros trabalhos futuros.
7.2
Trabalhos futuros
Para desenvolvimento em trabalhos futuros, pretende-se a aplicação de métodos heurísticos na busca de soluções factíveis para o problema de programação de
equipes de saúde. Pretende-se usar métodos de busca local, como o ILS e VNS,
algoritmos evolucionários como o GA (Algoritmos Genéticos) e o DPSO (Otimização por Troca de Partículas, para problemas discretos), e o hibridismo entre eles. É
proposto também a comparação entre os métodos testados, assim como a publicação
e apresentação de resultados computacionais.
Referências Bibliográficas
Abramson, D.; Dang, H. e Krisnamoorthy, M. (1999). Simulated annealing cooling
schedules for the school timetabling problem. Asia Pacific Journal of Operational
Research, v. 16, p. 1–22.
Aickelin, U. e Dowsland, K. A. (2000). Exploiting problem structure in a genetic
algorithmapproach to a nurse rostering problem. Journal of Scheduling, v. 3, n. 3,
p. 139–153.
Ambil, R.; Tanga, R. e Johnson, R. L. (1992). A global approach to crew-pairing
optimization. IBM Systems Journal, v. 31, n. 1.
Asmus, H.; Burke, E.K. e Garibaldi, J.M. (2005). Fuzzy multiple heuristic ordering
for course timetabling. 5th United Kingdom Workshop on Computational Intelligence, p. 302–309, London, UK.
Avella, Pasquale; D’Auria, Bernardo; Salermo, Saverio e Vasel’Ev, Igor. (2007). A
computational study of local search algorithms for italian high-school timetabling.
Journal of Heuristics, v. 13, p. 543–556.
Beddoe, Gareth Richard. Case-Based Reasoning in Personnel Rostering. PhD thesis,
University of Nottingham, Grã-Bretanha, (2004).
Bellanti, F.; Carello, G.; Croce, F. Della e Tadei, R. (2004). A greedy-based neighborhood search approach to a nurse rostering problem. European Journal of Operational Research, v. 153, p. 28–40.
Berrad, I.; Ferland, J. e Michelon, P. (1996). A multi-objective approach to nurse
scheduling with both hard and soft constraints. Socio-Economic Planning Science,
v. 30, n. 3, p. 183–193.
Blum, C. e Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview
and conceptual comparison. ACM Computing Surveys, v. 35, n. 3, p. 268–308.
Brasil, Ministério Saúde. (2004). Avaliação Normativa do Programa Saúde da Família no Brasil. MINISTÉRIO DA SAÚDE, Brasília, Brasil.
Brasil, Ministério Saúde. (2009). Portaria No 1.020, de 13 de Maio de 2009 Estabelece diretrizes para a implantação do componente pré-hospitalar fixo para a
organização de redes locorregionais de atenção integral às urgências. MINISTÉRIO
DA SAÚDE, Brasília, Brasil.
71
Referências Bibliográficas
72
Burke, Edmund K.; Berghe, Greet Vanden e Landeghem, Hendrik Van. (2004)a.
The state of the art of nurse rostering. Journal of Scheduling, v. 7, p. 441–499.
Burke, Edmund K.; Curtois, Timothy; Post, Gerhard; Qu, Rong e Veltman, Bart.
(2005). A hybrid heuristic ordering and variable neighbourhood search for the nurse
rostering problem. Computer Science Technical Report, v. NOTTCS-TR-2005-9.
Burke, Edmund K.; Curtois, Timothy; Qu, Rong e Berghe, Greet Vanden. (2007).
A time pre-defined variable depth search for nurse rostering. Computer Science
Technical Report, v. NOTTCS-TR-2007-6.
Burke, Edmund K.; deCausmaecher, Patrick e Berghe, Greet Vanden. (2004)b. Novel
Meta-heuristic Approaches to Nurse Rostering Problems in Belgian Hospitals. Handbook of Scheduling: Algorithms,Models and Performance Analysis, Nottingham.
Burke, Edmund K.; deCausmaecker, Patrick e Berghe, Greet Vanden. (1999). A
hybrid tabu search algorithm for the nurse rostering problem. Simulated Evolution
and learning, 1998, Lecture Notes in Artificial Intelligence, v. 1585, p. 187–194.
Burke, Edmund K.; deCausmaecker, Patrick e Berghe, Greet Vanden. (2001). A
memetic approach to the nurse rostering problem. Applied Intelligence, v. 15, n. 3,
p. 199–214.
Burke, Edmund K.; Elliman, D.G. e Weare, R.F. (1995). A hybrid genetic algorithm
for highly constrained timetabling problems. 6th Int. Conf. on Genetic Algorithms,
v. , p. 605–610.
Campos, Francisco Eduardo e Belisário, Soraya Almeida. (2001). O programa de
saúde da família e os desafios para a formação profissional e a educação continuada.
Comunicação, Saúde, Educação - Departamento de Medicina Preventiva e Social,
v. 5, p. 133–142.
Causmaecker, Patrick De; Demeester, Peter; Berghe, Greet Vanden e Verbeke, Bart.
(2004). Analysis of real-world personnel scheduling problems. PATAT04: Proceedings of the 5th International Conference on Practice and Theory of Automated
Timetabling, p. 183–197, Pittsburgh, USA.
Chand, A. (2002). A heuristic approach to constraint optimization in timetabling.
South Pacific Journal of Natural Science, v. 20, p. 64–67.
Colorni, A.; Dorigo, M. e Maniezzo, V. (1991). A genetic algorithm to solve the
timetable problem. Technical Report, v. 90-060.
Elias, S. E. G. (1964). The use of digital computers in the economic scheduling for
both man and machine in public transport. Technical Report, v. 49.
Erben, W. e Keppler, J. (1995). A genetic algorithm solving a weekly coursetimetabling problem. First International Conference on Practice and Theory of
Automated Timetabling, p. 283–295, Edinburgh, U.K.
Referências Bibliográficas
73
Ernst, A. T.; Jiang, H. Krishnamoorthy M.; Owens, B. e Sier, D. (2004). Annotated
bibliography of personnel scheduling and rostering. Annals of Operations Research,
v. 127, p. 21–144.
Hofe, H. Meyer Auf’m. (2000). Solving rostering tasks as constraint optimization.
E.K. Burke, W. Erben (Eds.): Practice and Theory of Automated Timetabling,
Third International Conference, Konstanz, Springer, v. , p. 191–212.
Kazarlis, S.; Petridis, V. e Fragkou, P. (2005). Solving university timetabling problems using advanced genetic algorithms. 5th International Conference on Technology and Automation, p. 131–136, Thessaloniki, Greece.
Kohl, Niklas e Larisch, Stefan E. (2004). Airline crew rostering: Problem types,
modeling, and optimization. Annals of Operations Research, v. 127, p. 223–257.
Lourenço, H. R.; Martin, O. e Stutzle, T. (2002). Iterated local search. Glover, F. e
Kochenberger, G., editors, Handbook of Metaheuristics, volume 57 of International
Series in Operations Research & Management Science, p. 321–353. Kluwer Academic
Publishers, Norwell, MA, EUA.
Manington, B. e Wren, A. (1975). A general computer method for bus crew scheduling. Workshop on Automated Techniques for Scheduling of Vehicle operators for
Urban Public Transportation Services, Chicago.
Osman, I.H. e Laporte, G. (1996). Metaheuristics: A bibliography. Annals of
Operations Research, v. 63, p. 511–623.
Pereira, Martha Priscila Bezerra e Barcellos, Christovam. (2006). O território no
programa de saúde da família. Revista Brasileira de Geografia Médica e da Saúde,
v. 2, p. 47–55.
Pezzella, Ferdinando e Faggioli, Eurico. (1997). Solving large set covering problems
for crew scheduling. Sociedad de Estadística e Investigación Operativa. lnstituto di
Informatica, Università di Ancona, v. 5, n. 1, p. 41–59.
Rahoual, M. e Saad, R. (2006). Solving timetabling problems by hybridizing genetic
algorithms and tabu search. 6th Int. Conf. on the Practice and Theory of Automated
Timetabling, p. 467–472, Brno, Czech Republic.
Rishnan, Balaji Gopalak e Johnson, Ellis L. (2005). Airline crew scheduling: Stateof-the-art. Annals of Operations Research, v. 140, p. 305–337.
Schaerf, A. (1999). A survey of automatic timetabling. Artificial Intelligence Review,
Springer Netherlands, v. 13, n. 2, p. 87–127.
Schaerf, A. e Gaspero, L.D. (2001). Local search techniques for educational timetabling problems. 6th International Symposium on Operations Research in Slovenia,
v. , p. 13–23.
Sigl, B.; Golub, M. e Mornar, V. (2003). Solving timetable scheduling problem by
using genetic algorithms. 25th IEEE Int. Conf. on Information Technology Interfaces, p. 519–524, Cavtat/Dubrovnik, Croatia.
Referências Bibliográficas
74
Souza, M. J. F. (2007). Inteligência Computacional para Otimização. Departamento
de Computação - UFOP, Ouro Preto, Brasil.
Souza, M.J.F.; Maculan, N. e Ochi, L.S. (2003). A grasp- tabu search algorithm
for solving school timetabling problems. Metaheuristics: computer decision-making,
Kluwer Academic Publishers, v. , p. 659–672.
Wilke, P.; Gröbner, M. e Oster, N. (2002). A hybrid genetic algorithm for school
timetabling. 15th Australian Joint Conference on Artificial Intelligence: Advances
in Artificial Intelligence, p. 455–464, Canberra, Australia.