142506 - cdsid

UM MODELO DE DESIGNAÇÃO PARA SALAS DE CIRURGIAS: O CASO DO
HOSPITAL SANTA LYDIA EM RIBEIRÃO PRETO, SP
José Francisco Ferreira Ribeiro1
e-mail [email protected]
André Lucirton Costa1
e-mail [email protected]
Alexandre Bevilacqua Leoneti1
e-mail [email protected]
Renato Mantelli Picoli1
e-mail [email protected]
Diana Costa de Santi2
e-mail [email protected]
Faculdade de Economia, Administração e Contabilidade de Ribeirão Preto
Universidade de São Paulo, Av. Bandeirantes, 3900, Monte Alegre, Ribeirão Preto, SP
1
2
Hospital Santa Lydia, Rua Tamandaré, 484, Campos Elíseos, Ribeirão Preto, SP
RESUMO
Neste artigo é apresentado um modelo matemático em variáveis binárias 0-1 para efetuar a
designação dos procedimentos cirúrgicos às salas de cirurgia num hospital. A formulação
proposta é baseada no modelo da designação generalizada, que maximiza a soma das
preferências de utilização das salas pelos médicos e efetua a designação das cirurgias
respeitando o tempo disponível em cada uma das salas. O programa correspondente foi
escrito em linguagem Visual Basic do Microsoft Excel, e testado para programação de
cirurgias no Hospital Santa Lydia em Ribeirão Preto, SP.
PALAVARAS CHAVE. Problema da Designação Generalizada, Programação de
Cirurgias, Otimização
Área principal: SA – PO na Área de Saúde
ABSTRACT
This paper presents a mathematical model in binary variables 0-1 to make the assignment
of surgical procedures to the operating rooms in a hospital. The proposed model is based on
the general assignment problem, which maximizes the sum of preferences for the use of the
operating rooms by doctors, respecting the time available in each room. The corresponding
program was written in Visual Basic of Microsoft Excel, and tested to schedule surgeries at
Santa Lydia Hospital in Ribeirão Preto, Brazil.
KEYWORDS. Generalized Assignment Problem, Scheduling of Surgeries, Optimization
Main area: SA – OR in Health
1. Introdução
O Hospital Santa Lydia, em Ribeirão Preto, SP, é um hospital municipal fundado em
1960. Inicialmente tinha o propósito de atender às crianças carentes devido ao surto de
pólio e meningite na região. Hoje é um hospital geral, atendendo à população nas mais
diferentes especialidades médicas. O centro cirúrgico está apto a realizar cirurgias de alta,
média e baixa complexidade. Para tanto, dispõe de quatro salas de cirurgia e cinco leitos de
recuperação, que são usados diariamente.
O objetivo desse trabalho é desenvolver um modelo matemático e um programa de
computador para auxiliar o corpo médico do Hospital Santa Lydia a efetuar a designação
das cirurgias programadas para o dia seguinte às salas de cirurgia disponíveis. O modelo
matemático utilizado para efetuar a programação das salas de cirurgia nesse trabalho é o
modelo da designação generalizada (Arenales et al., 2007).
Uma revisão bibliográfica sobre os modelos matemáticos e os métodos de
resolução propostos na literatura para o problema da designação generalizada está
disponível na seção 2 desse artigo. Na seção 3 é apresentado o modelo matemático
desenvolvido para a resolução do problema. Um exemplo ilustrativo do modelo matemático
proposto é fornecido na seção 4. Os resultados dos testes computacionais realizados podem
ser vistos na seção 5. O modelo proposto foi utilizado para a programação de cirurgias no
Hospital Santa Lydia em Ribeirão Preto, SP. As conclusões finais e as referências estão nas
seções 6 e 7 respectivamente.
Nos testes, foi utilizado o suplemento SOLVER do Microsoft Excel para a resolução
dos problemas, por ser um dos softwares mais populares e disseminados da história da
computação.
2. Revisão Bibliográfica
O problema da designação generalizada é NP-completo (Garey e Johnson, 1977).
Dada a complexidade algorítmica do problema não é possível resolver de maneira ótima o
problema da designação generalizada para exemplos de grande porte por meio de
algoritmos exatos. Por essa razão a proposição de algoritmos heurísticos ou aproximados
para resolvê-lo é um recurso frequentemente encontrado na literatura.
Martello e Toth (1992) fazem uma revisão dos métodos exatos e aproximados para
a resolução do problema da designação generalizada, com diferentes funções-objetivo,
transformações e limites. Cattrysse e Van Wasswnhove (1992) chamam a atenção para o
grande número de métodos desenvolvidos com base em branch-and-bound. Amini e Racer
(1994) fazem estudo para comparar o desempenho de heurísticas disponíveis para resolver
o problema. Öncan (2007) faz uma revisão bibliográfica das metaheurísticas e heurísticas.
Morales e Romeijn (2005) descrevem o estado da arte.
Algoritmos aproximados e rápidos são descritos por Fisher e Ramchandran
(1981), Mazzola e Neebe (1993), Shmoys e Tardos (1993), French e Wilson (2002), Wilson
(2005), Nutov et al. (2006) e Yagiura et al. (2006). Zhang e Ong (2007) propõem uma
heurística associada à programação multiobjetivo. Mazzola e Wilcox (2001) obtêm soluções
factíveis para mais de 99% dos exemplos testados com auxílio de um algoritmo específico.
Heurísticas greedy são utilizadas por Romeijn e Morales (2000) e Sharkey e Romeijn (2010)
com apresentação de bons resultados. Cohen et al. (2006) fazem a aproximação pelo
problema da mochila. Heurísticas baseadas em técnicas de geração de colunas são descritas
por Cattrysse et al. (1994) e Moccia et al. (2009). Métodos heurísticos de busca local são
apresentados por Racer e Amini (1994) e Yagiura et al. (1998).
A metaheurística busca tabu é utilizada pelos métodos propostos por Laguna et al.
(1995), Díaz e Fernández (2001) e Ferland et al. (2001). Lourenço e Serra (2002) propõem
uma busca local seguida de busca tabu. Yagiura et al. (2004) empregam a busca tabu e
descrevem soluções ótimas 0.16% distantes no máximo da melhor solução conhecida.
Por sua vez, Chu e Beasley (1997) e Liu et al. (2012) fazem uso dos algoritmos
genéticos para resolver o problema da designação generalizada. Fetl e Rajdl (2004)
apresentam uma comparação da heurística desenvolvia por eles com o software CPLEX, da
Microsoft, sendo que o método proposto por eles é significativamente mais rápido para
grandes instâncias.
A lógica fuzzy é utilizada por Hairi-Gaboui (2003). Avella et al. (2010) empregam
os planos de corte. Ozbakir et al. (2010) resolve o problema com o algoritmo Bee, que imita
o comportamento natural das abelhas na procura por alimento. Um modelo para localização
de facilidades por meio de designação generalizada é proposto por Ross e Soland (1977).
O método branch-and-bound, associado ou não a heurísticas, é um dos métodos
mais utilizados para a resolução do problema da designação generalizada. Ross e Soland
(1975) resolvem problemas com mais de 4.000 variáveis binárias 0-1 por meio do método
branch-and-bound. Klastorin (1979) usa o método branch-and-bound associado ao método
do subgradiente para resolver problemas com mais de 12.000 variáveis binárias. Gavish e
Pirkul (1991) e Osorio e Laguna (2003) também empregam o branch-and-bound.
Um método branch-and-bound associado à geração de colunas é proposto por
Savelsbergh (1997). Nauss (2004) utiliza o branch-and-bound com planos de corte,
relaxação lagrangeana e otimização subgradiente. Posta et al. (2012) associam relaxação
lagrangeana e programação dinâmica. Woodcock e Wilson (2010) propõem o branch-andbound combinado com a busca tabu. Farias Jr et al. (2000) resolvem o problema com o
auxílio do branch-and-cut. Barnhart et al. (1998) e Ceselli e Righini (2006) utilizam o
branch-and-price. A relaxação lagrangena ou surrogate é a base dos métodos de resolução
do problema da designação generalizada propostos por Fisher et al. (1986), Jörnsten e
Näsberg (1986), Guignard e Kim (1987), Barcia e Jörnsten (1990), Lorena e Narciso (1996),
Narciso e Lorena (1999), Nauss (2003), Fisher (2004) e Jeet e Kutanoglu (2007). Lorena e
Narciso (1996) descrevem resultados menos de 0.5% distantes do ótimo.
3. Modelo Matemático
No problema da designação generalizada tem-se m agentes (operários, máquinas,
etc) para executar n tarefas, com m < n. Neste caso, cada tarefa deve ser executada por um
único agente, e um agente pode ser designado para executar mais de uma tarefa. A execução
da tarefa j pelo agente i requer uma quantidade aij da capacidade do recurso bi com custo
cij.
Seja xij a variável binária 0-1:
xij
se a tarefa j é designada ao agente i
caso contrário
1
0
O modelo matemático do problema da designação generalizada pode ser escrito da
seguinte forma (Arenales et al., 2007):
m
n
Min f   cij xij
(1)
i 1 j 1
Sujeito a
m
x
i 1
ij
 1 ( j  1,..., n)
n
a x
j 1
ij ij
 b j (i  1,..., m)
xij  0 / 1
(2)
(3)
(4)
A função-objetivo (1) minimiza o custo total da designação dos agentes às tarefas. A
restrição (2) garante que cada tarefa será executada por um único agente, e a restrição (3)
não permite que a capacidade do recurso bi seja ultrapassada. A restrição (4) estabelece o
tipo das variáveis como binárias.
4. Exemplo ilustrativo
Para ilustrar o modelo matemático proposto, suponha que cinco médicos têm sete
cirurgias para serem programadas para o dia seguinte em 2 salas, com tempo igual a 10
horas disponíveis em cada uma das salas (600 minutos no total).
Uma modificação na função-objetivo do modelo da designação generalizada foi
introduzida para levar em conta as preferências (pij) dos médicos pelas salas, estabelecidas
em 3 níveis: maior preferência, indiferença e indesejável, conforme dado abaixo:
pij
10
5
0
se sala j for preferível para o médico i
se sala j for indiferente para o médico i
se sala j for indesejável para o médico i
A Tabela 1 apresenta a preferência de cada um dos médicos. A Tabela 2 fornece o
tempo em minutos (aij) que os médicos necessitam, em média, para efetuar cada uma das
cirurgias. A nova função-objetivo (5) é apresentada abaixo. Ressalta-se que, neste caso, a
formulação utilizada realizará a maximização do critério.
m
n
Max f   pij xij
(5)
i 1 j 1
Tabela 1 – Preferências pelas salas de cirurgia
Médico
Médico 1
Médico 2
Médico 3
Médico 4
Médico 5
Sala 1
10
10
0
5
10
Sala 2
5
10
10
10
5
Tabela 2 – Médicos e tempo de cirurgia (minutos)
Cirurgia
Cirurgia 1
Cirurgia 2
Cirurgia 3
Cirurgia 4
Cirurgia 5
Cirurgia 6
Cirurgia 7
Médico
Médico 1
Médico 2
Médico 3
Médico 4
Médico 5
Médico 3
Médico 1
Tempo de cirurgia (minutos)
300
180
120
60
240
90
150
Finalmente, o modelo matemático correspondente pode ser dado por:
Max
10x11 + 5x12 + 10x21 + 10x22 + 0x31 + 10x32 + 5x41 + 10x42 +
10x51 + 5x52 + 0x61 + 10x62 + 10x71 + 5x72
Sujeito a
x11 + x12 = 1
x21 + x22 = 1
x31 + x32 = 1
x41 + x42 = 1
x51 + x52 = 1
x61 + x62 = 1
x71 + x72 = 1
300x11 + 180x21 + 120x31 + 60x41 + 240x51 + 90x61 + 150x71 ≤ 600
300x12 + 180x22 + 120x32 + 60x42 + 240x52 + 90x62 + 150x72 ≤ 600
300x13 + 180x23 + 120x33 + 60x43 + 240x53 + 90x63 + 150x73 ≤ 600
xij = 0/1
O resultado obtido pelo SOLVER do Microsoft Excel é: x12 = 1, x21 = 1, x32 = 1, x42 = 1,
x51 = 1, x62 = 1, x72 = 1 e as demais variáveis valem zero. Assim, as cirurgias 2 e 5 serão
designadas à sala 1, e as cirurgias 1, 3, 4, 6 e 7 à sala 2. A soma das preferências da
designação obtida é igual a (10 + 10) + (5 + 10 + 10 + 10 + 5) = 60, que corresponde ao
máximo de atendimento possível das preferências de cada médico.
5. Testes computacionais
Testes computacionais foram realizados para a programação das salas de cirurgia
do Hospital Santa Lydia, em Ribeirão Preto, SP. No teste computacional aqui apresentado, o
objetivo foi programar 13 cirurgias em quatro salas disponíveis para um dia específico do
mês de abril do ano corrente (2015). O modelo matemático para a resolução do problema
da designação tem 13 x 4 = 52 variáveis binárias 0-1 para determinar o valor. Para
preservar o sigilo dos dados não são apresentados os nomes das cirurgias, bem como os
nomes dos médicos.
A Tabela 3 apresenta, para cada um dos sete médicos escalados para o dia em
planejamento, as respectivas preferências pelas salas. De acordo com entrevistas com a
equipe responsável pela programação das salas de cirurgias, essas preferências estão
principalmente relacionadas a aspectos operacionais e de disposição de instrumental nas
salas. Ressalta-se que um médico, tendo preferência por mais de uma sala, poderá ser
alocado em qualquer uma daquelas que lhe são preferíveis.
Tabela 3 – Preferências pelas salas de cirurgia
Médico
Médico 1
Médico 2
Médico 3
Médico 4
Médico 5
Médico 6
Médico 7
Sala 1
10
0
5
5
5
10
10
Sala 2
0
10
5
5
5
0
10
Sala 3
5
0
10
5
10
0
10
Sala 4
0
0
5
10
5
0
10
Para cada uma das 13 cirurgias, de diferentes graus de complexidade, a equipe
responsável pelo planejamento apresentou os dados da Tabela 4, que foram estimados com
base no tempo médio em minutos para a realização de cada uma delas. Além disto, a equipe
também apresentou quais seriam os médicos responsáveis por cada uma delas.
Tabela 4 – Médicos e tempo de cirurgia (minutos)
Cirurgia
Cirurgia 1
Cirurgia 2
Cirurgia 3
Cirurgia 4
Cirurgia 5
Cirurgia 6
Cirurgia 7
Cirurgia 8
Cirurgia 9
Cirurgia 10
Cirurgia 11
Cirurgia 12
Cirurgia 13
Médico
Médico 3
Médico 4
Médico 4
Médico 4
Médico 3
Médico 3
Médico 7
Médico 5
Médico 2
Médico 6
Médico 4
Médico 1
Médico 3
Tempo de cirurgia (minutos)
60
40
150
120
60
60
120
60
60
180
60
180
60
Os dados foram inseridos em uma planilha Excel por meio da programação, em
linguagem Visual Basic, de um algoritmo que permite que cada cirurgia seja associada a um
médico e a um tempo de cirurgia (em minutos). A planilha alerta quando a soma total de
minutos disponíveis nas quatro salas é ultrapassada, o que não ocorreu no presente caso,
considerando-se a disponibilidade de sete horas por cada sala para o dia planejado. Os
dados dos médicos, cirurgias e preferências por salas devem ser previamente cadastrados,
respectivamente, nas planilhas “Médicos”, “Cirurgias” e “Prioridade”. A Figura 1 apresenta a
tela principal (interface) do modelo de designação generalizada para as salas de cirurgia.
Figura 1 – Tela principal para inclusão dos dados
O resultado obtido pelo SOLVER do Microsoft Excel para o dia em planejamento foi:
x101 = 1, x121 = 1, x72 = 1, x92 = 1, x13 = 1, x53 = 1, x63 = 1, x83 = 1, x133 = 1, x24 = 1, x34 = 1, x44 = 1
e x114 = 1 e as demais variáveis valem zero. Assim, as cirurgias 10 e 12 serão designadas à
sala 1, as cirurgias 7 e 9 à sala 2, as cirurgias 1, 5, 6, 8 e 13 à sala 3, e as cirurgias 2, 3, 4 e 11
à sala 4. A soma das preferências da designação obtida foi igual a 130, que corresponde ao
máximo de atendimento das preferências de cada médico. Considerando que o tempo
disponível em cada sala era de 420 minutos (7 horas), houve uma ociosidade média de 110
minutos por sala, sendo os seguintes tempos 360, 180, 300 e 370 os respectivamente
designados para as salas de 1 a 4. O tempo computacional para obtenção do resultado foi
inferior a 1 segundo em um computador com processador Intel Core 2 Duo e com 4 GB de
memória RAM.
O resultado obtido foi apresentado à equipe de planejamento da utilização das salas
de cirurgia do Hospital Santa Lydia para análise do desempenho do programa e da
qualidade da solução. A equipe julgou o planejamento proposto adequado, tendo
observado que todas as restrições do problema foram respeitadas. A equipe de
planejamento também chamou a atenção para a necessidade de realizar o sequenciamento
das atividades programadas, uma vez que algumas cirurgias têm prioridade de horário
sobre as outras.
6. Conclusões
Nesse artigo é proposto um modelo matemático em variáveis binárias para efetuar
a designação das cirurgias às salas de cirurgia de um hospital. A função-objetivo maximiza a
soma das preferências dos médicos pelas salas de cirurgia. A primeira restrição garante que
cada cirurgia será executada em apenas uma das salas disponíveis. A segunda restrição não
permite que o tempo disponível para cirurgias em cada uma das salas seja ultrapassado. A
formulação proposta é baseada o modelo da designação generalizada.
O modelo matemático proposto foi testado sobre o problema de programação das
salas de cirurgia do Hospital Santa Lydia, em Ribeirão Preto, SP. O Hospital pode realizar
cirurgias de alta, média e baixa complexidade nas mais diversas especialidades médicas.
Para tanto, dispõe de quatro salas de cirurgia. O problema foi resolvido com auxílio do
modelo matemático proposto e resolvido pelo software Solver-Excel da Microsoft. Os
resultados obtidos foram considerados excelentes e animadores pelos responsáveis pela
tomada de decisão, os quais ensejam a continuidade do trabalho.
Referências
Amini, M. M., Racer, M. A rigorous computational comparison of alternative solution methods for the
generalized assignment problem, Management Science, 40, 7, p. 868-890, 1994.
Arenales, M., Armentano, V., Morabito, R., Yanasse, H., Pesquisa Operacional, Elsevier, 2007.
Avella, P., Boccia, M., Vasilyev, I. A computational study of exact knapsack separation for the generalized
assignment problem, Computational Optimization and Applications, 45, 3, p. 543-555, 2010.
Barcia, P., Jörnsten, K. Improved lagrangean decomposition: an application to the generalized assignment
problem, European Journal of Operational Research, 46, 1, p. 84-92, 1990.
Barnhart, C., Johnson, E. L. Nemhauser, G. L., Savelsbergh, M. W. P., Vance, P. Branch-and-price:
column generation for solving huge integer programs, 46, 3, p. 316-329, 1998.
Cattrysse, D. G., Van Wassenhove, L. N. A survey of algorithms for the generalized assignment problem,
European Journal of Operational Research, 60, 3, p. 260-272, 1992.
Cattrysse, D. G., Salomon, M., Van Wassenhove, L. N. A set partitioning heuristic for the generalized
assignment problem, European Journal of Operational Research, 72, 1, p. 167-174, 1994.
Ceselli, A., Righini, G. A Branch-and-price algorithm for the multilevel generalized assignment problem,
Operations Research, 54, 6, p. 1172-1184, 2006.
Chu, P. C., Beasley, J. E. A genetic algorithm for the generalised assignment problem, 24, 1, Computers &
Operations Research, 24, 1, p. 17-23, 1997.
Cohen, R., Katzir, L., Raz, D. An efficient approximation for the generalized assignment problem,
Information Processing Letters, 100, 4, p. 162-166, 2006.
Díaz, J. A., Fernández, E. A Tabu search heuristic for the generalized assignment problem, European
Journal of Operational Research, 132, 1, p. 22-38, 2001.
Farias Jr, I. R., Johnson, E. L., Nem hauser, G. L. A generalized assignment problem with special ordered
sets: a polyhedral approach, Mathematical Programming, 89, 1, p. 187-203, 2000.
Ferland, J. A., Berrada, I., Nabli, I., Ahiod, B., Michelon, P., Gascon, V., Gagné, E. Generalized
assignment type goal programming problem: application to nurse scheduling, Journal of Heuristics, 7,
4, p. 391-413, 2001.
Fetl, H., Rajdl, G. R. An improved hybrid genetic algorithm for the generalized assignment problem, SAC
'04 Proceedings of the 2004 ACM symposium on Applied Computing, p. 990-995, 2004.
Fisher, M. L., Ramchandran, J. A generalized assignment heuristic for vehicle routing, Networks, 11, p.
109-124, 1981.
Fisher, M. L. The lagrangian relaxation method for solving integer programming problems, Management
Science, 50, 12, p. 1861-1871, 2004.
Fisher, M. L., Jaikumar, Van Wassenhove, L. N. A multiplier adjustment method for the generalized
assignment problem, Management Science, 32, 9, p. 1095-1103, 1986.
French, A. P., Wilson, J. M. Heuristic solution methods for the multilevel generalized assignment problem,
Journal of Heuristics, 8, 2, p. 143-153, 2002.
Garey, M. R., Johnson, D. S. Computers and intractability: a guide to the theory of NP-completeness,
Freeman, 1977.
Gavish, B., Pirkul, H. Algorithms for the multi-resource generalized assignment problem, Management
Science, 37, 6, p. 695-713, 1991.
Guignard, M., Kim, S. Lagrangean decomposition: a model yielding stronger lagrangean bounds,
Mathematical Programming, 39, 2, p. 215-228, 1987.
Hairi-Gaboui, S. A fuzzy genetic multiobjective optimization algorithm for a multilevel generalized
assignment problem, Systems, Man, and Cybernetics, 33, 2, p. 214-224, 2003.
Jeet, V., Kutanoglu, E. Lagrangian relaxation guided problem space search heuristics for generalized
assignment problems, European Journal of Operational Research, 182, 3, p. 1039-1056, 2007.
Jörnsten, K., Näsberg, M. A new lagrangian relaxation approach to the generalized assignment problem,
European Journal of Operational Research, 27,3, 1986.
Klastorin, T. D. An effective subgradient algorithm for the generalized assignment problem, Computers &
Operations Research, 6, 3, p. 155-164, 1979.
Laguna, M., Kelly, J. P., Gonzáles-Velarde, J. L., Glover, F., Tabu search for the multilevel generalized
assignment problem, European Journal of Operational Research, 82, 1, p. 176-189, 1995.
Liu, L., Mu, Haibo, Song, Y., Luo, H., Li, X., Wu, F. The equilibrium generalized assignment problem and
genetic algorithm, Applied Mathematics and Computation, 218, 11, p. 6526-6535, 2012.
Lorena, L. A. N., Narciso, M. G. Relaxation heuristics for a generalized assignment problem, 91,3, p. 600610, 1996.
Lourenço, H. R., Serra, D. Adaptive search heuristics for the generalized assignment problem: Mathware &
Soft Computing, 9,3, p. 209-234, 2002.
Martello, S., Toth, P. Generalized assignment problems, Lecture Notes in Computer Science 650, p. 351369, 1992.
Mazzola, J. B., Neebe, A. W. An algorithm for the bottleneck generalized assignment problem, Computers
& Operations Research, 20, 4, p. 355-362, 1993.
Mazzola, J. B., Wilcox, S. P. Heuristics for the multi-resource generalized assignment problem, Naval
Research Logistics, 48, 6, p. 468-483, 2001.
Moccia, L., Cordeau, J. F., Monaco, M. F., Sammarra, M. A column generation heuristic for a dynamic
generalized assignment problem, Computers & Operations Research, 36, 9, p. 2670-2681, 2009.
Morales, D. R., Romeijn, H. E. The generalized assignment problem and extensions, Handbook of
Combinatorial Optimization, p. 259-311, 2005.
Narciso, M. G., Lorena, L. A. N. Lagrangean/surrogate relaxation for generalized assignment problems,
European Journal of Operational Research, 114,1, p. 165-177, 1999.
Nauss, R. M., Solving the generalized assignment problem: an optimizing and heuristic approach,
INFORMS Journal on Computing, 15, 3, p. 249-266, 2003.
Nauss, R. M. The elastic generalized assignment problem, Journal of the Operational Research Society, 55,
p. 1333–1341, 2004.
Nutov, Z., Beniaminy, I., Yuster, R. A (1–1/e)-approximation algorithm for the generalized assignment
problem, Operations Research Letters, 34, 3, p. 283-288, 2006.
Öncan, T. A survey of the generalized assignment problem and its applications, INFOR: Information
Systems and Operational Research, 45, 3, p. 123-141, 2007.
Osorio, M. A., Laguna, M. Logic cuts for multilevel generalized assignment problems, European Journal of
Operational Research, 151, 1, p. 238-246, 2003.
Ozbakir, L., Baykasoglu, A., Tapkan, P. Bees algorithm for generalized assignment problem, Applied
Mathematics and Computation, 215, 11, p. 3782-3795, 2010.
Posta, M., Ferland, J. A., Michelon, P. An exact method with variable fixing for solving the generalized
assignment problem, Computational Optimization and Applications, 52, 3, p. 629-644, 2012.
Racer, M., Amini, M. M., A robust heuristic for the generalized assignment problem, Annals of Operations
Research, 50, 1, p. 487-503, 1994.
Romeijn, H. E., Morales, D. R. A class of greedy algorithms for the generalized assignment problem,
Discrete Applied Mathematics, 103, 1-3, p. 209-235, 2000.
Ross, G. T., Soland, R. M. A branch and bound algorithm for the generalized assignment problem,
Mathematical Programming, 8, 1, p. 91-103, 1975.
Ross, G. T., Soland, R. M. Modeling facility location problems as generalized assignment problems,
Management Science, 24, 3, p. 345-357, 1977.
Savelsbergh, M. A branch-and-price algorithm for the generalized assignment problem, Operations
Research, 6, p. 831-841, 1997.
Sharkey, T. C., Romeijn, H. E. Greedy approaches for a class of nonlinear generalized assignment
problems, Discrete Applied Mathematics, 158, 5, p. 559–572, 2010.
Wilson, J. M. An Algorithm for the generalized assignment problem with special ordered sets, Journal of
Heuristics, 11, 4, p. 337-350, 2005.
Woodcock, A. J., Wilson, J. M. A hybrid tabu search/branch & bound approach to solving the generalized
assignment problem, European Journal of Operational Research, 207, 2, p. 566-578, 2010.
Yagiura, M., Yamaguchi, T., Ibaraki, T. A variable depth search algorithm with branching search for the
generalized assignment problem, Optimization Methods and Software, 10, 2, p. 419-441, 1998.
Yagiura, M., Ibaraki, T., Glover, F. An ejection chain approach for the generalized assignment problem,
INFORMS Journal on Computing, 16, 2, p. 133-151, 2004.
Yagiura, M., Ibaraki, T., Glover, F. A path relinking approach with ejection chains for the generalized
assignment problem, European Journal of Operational Research, 169, 2, p. 548-569, 2006.
Zhang, C. W., Ong, H. L. An efficient solution to biobjective generalized assignment problem, Advances
in Engineering Software, 38, 1, p. 50-58, 2007.