142506 - cdsid
Transcrição
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.