Orientadores: Ruben Augusto Romero Lazaro, Andre Luiz Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T00:23:55Z (GMT). No. of bitstreams: 1 Oliveira_SergioAzevedode_D.pdf: 11876459 bytes, checksum: 5fe45b6ab623e895fe15f36e44d5bd24 (MD5) Previous issue date: 2004 / Resumo: Neste trabalho foram desenvolvidas diversas metaheuristicas combinatorias para a resolução do problema do planejamento da expansão da transmissão dos sistemas de energia eletrica analisado do ponto de vista estatico e a longo prazo, dentre as quais uma versão paralela da metodologia ¿simulated annealing¿ e diversas versões paralelas de algoritmos geneticos; alem de um time assincrono cujos agentes são variantes destas metaheuristicas. Todas estas versões são inicializadas por um time assincrono de algoritmos heuristicos construtivos e executadas em um ambiente de processamento distribuido composto por uma rede heterogenea de estações SUN, sistema operacional SunOS, com biblioteca para processamento paralelo PVM. Foram feitos diversos testes para os sistemas: Garver (6 barras/15 ramos), Sul brasileiro (46 barras/79 ramos), Norte-Nordeste brasileiro (87 barras/179 ramos) e sistema colombiano (93 barras/155 ramos), e os resultados comprovam a eficacia das metodologias propostas quando comparados com os resultados das versões seriais de cada metaheuristica isoladamente, bem como mostram uma redução significativa nos tempos de processamento / Abstract: In this work, several combinatorial metaheuristics are developed for solving the transmission expansion planning problem of electric power systems that is analysed considering the static and long-term approach, e.g. a parallel version of the simulated annealing methodology and several parallel versions of a genetic algorithms, besides an asynchronous team which agents are variants of these metaheuristics. All of these versions are initialized by an asynchronous team of constructive heuristic algorithms, executed in a distributed processing environment, composed of a heterogeneous network of SUN workstations, SunOS, with PVM parallel processing library. Several tests are effectuated for the systems: Garver (6 busses/15 branches); brazilian South (46 busses/79 branches), brazilian North/Northeast (87 busses/179 branches) and the colombian system (93 busses/155 branches). The results show the efficiency of the proposed methodologies when compared to the serial versions of each metaheuristic isolatedely, as well as a significative reduction on the processing times / Doutorado / Engenharia Eletrica / Doutor em Engenharia Elétrica

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T13:52:34Z (GMT). No. of bitstreams: 1 Tao_WelfaneKemil_M.pdf: 5537070 bytes, checksum: daa47ae9abdc3c330e9d2f1c0deea02e (MD5) Previous issue date: 1999 / Resumo: Esse trabalho trata o problema da minimização das perdas em sistemas de distribuição de energia elétrica. Considerando a restrição da operação radial da rede de distribuição, o problema pode ser formulado como uma generalização da árvore recobridora de custo mínimo. A solução de mínimas perdas é obtida em duas etapas. A restrição de radialidade é relaxada na primeira etapa, obtendo-se uma solução otimista para o problema. Na segunda etapa, utiliza-se uma estratégia de busca para encontrar a solução ótima global factível do problema, guiada pelas informações da solução otimista. A solução otimista é obtida através de técnicas de otimização de fluxos não lineares em redes. A estratégia de busca usa procedimentos da área de inteligência artificial. Técnicas de processamento paralelo auxiliam a obtenção mais rápida da solução ótima / Abstract: This thesis addresses the problem of loss minimization for electric energy distribution system. As distribution networks operates radially, the problem can be formulated as a generalization of minimum spanning tree problem. The minimum loss solution is obtained in two steps. The constraint of radial operation is relaxes in the first step, leading to an optimistic solution. Information from optimistic solution is used to guide search strategies for obtain the optimal feasible solution. Non-linear network flow methods are adopted to find the optimistic solution. The search strategies is based on concepts from the field of artificial intelligence. Parallel processing speeds the search of optimal solution / Mestrado / Mestre em Engenharia Elétrica

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T19:24:38Z (GMT). No. of bitstreams: 1 Costa_MarcosFabioNobregada_M.pdf: 5953099 bytes, checksum: 8ffa825d7b121106adf6cb5400d1ac28 (MD5) Previous issue date: 1999 / Resumo: Este trabalho adota uma abordagem de computação evolutiva para encontrarmos a configuração de mínimas perdas de uma rede de distribuição de energia elétrica radial. O principal elemento da busca é um Algoritmo Genético, meta-heurística que imita os processos evolutivos naturais. A partir de população de indivíduos gerada aleatoriamente, a adequação média das gerações subseqüentes de indivíduos é melhorada através de mecanismos de Seleção, Cruzamento e Mutação. Uma importante característica dos Algoritmos Genéticos é a forte atração para ótimos locais com a perda da diversidade. Para escapar destas soluções, foram implementadas estratégia de diversificação inspiradas em Busca Tabu e Cruzamentos Baseados em Comportamento. A incorporação de busca local heurística explora conhecimento específico sobre o problema, sendo utilizada juntamente com procedimento de diversificação para preservação de níveis mínimos de diversidade. Resultados sobre redes reais de médio e grande porte são apresentados / Abstract: The present work adopts an evolutionary computation approach to reach the minimum loss configuration of a radial power distribution network. The main element of the search is a Genetic Algorithm, meta-heuristic that imitates the natural evolutive process. Starting with a random-generated population, the mean fitness of successive generations is increased through Selection, Crossover and Mutation mechanisms. One important feature of Genetic Algorithms is the strong attraction to local optimal solutions. To escape from these solutions, we implemented a diversification strategy inspired in Tabu Search and Behavior-Based Crossovers. The incorporation of heuristic local search, that explores specific knowledge of the problem domain, is added to the diversification procedure to preserve a minimum level of diversity. Results for real, medium, and large distribution networks are discussed. / Mestrado / Mestre em Engenharia Elétrica

Orientadores: Carlos Magnus Carlson Filho, Raul Vinhas Ribeiro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T03:52:18Z (GMT). No. of bitstreams: 1 Banov_JoanaTeixeiraMachado_D.pdf: 682129 bytes, checksum: a4be8d02743c3241ac088f06534d5b78 (MD5) Previous issue date: 2005 / Resumo: Após a privatização, o setor de telecomunicações vem sofrendo grandes transformações tecnológicas. Do ponto de vista do usuário, isso significa a disponibilidade de serviços mais modernos. Para as empresas operadoras, a privatização significa concorrência. Para ganhar mercado é preciso um planejamento otimizado por parte das operadoras, de modo a maximizar receitas e evitar gastos excessivos com investimentos, operações e gerenciamAento das redes. Este estudo tem como objetivo auxiliar os planejadores na expansão de longo prazo da rede de acesso aos serviços de telecomunicações. O trabalho apresenta os modelos matemáticos correspondentes e propõe um método de resolução evolutivo capaz de lidar com a complexidade intrínseca do problema de Programação Linear Inteiro Misto (PLIM). O Algoritmo Híbrido Evolutivo (AHE) decompõe o problema em duas partes, uma inteira e outra real. A parte evolutiva assume a determinação das variáveis de decisão inteiras e é baseada em algoritmos genéticos ¿ método heurístico que imita a evolução das espécies para gerar soluções candidatas ao problema. A avaliação dessas soluções ¿ função de adequação ¿ acontece com a resolução do problema restante, de fluxo em redes, por meio de métodos clássicos de otimização linear. O algoritmo genético é ainda incrementado por regras anti-violação para evitar a geração de soluções candidatas infactíveis. As comparações de performance com o solver CPLEX ® comprovam que o AHE cumpre com louvor sua meta de fornecer resultados de boa qualidade para o problema em um tempo computacional de execução aceitável / Abstract: After privatization, the telecommunication area has been experienced big technological changes. From the user point of view, this means access to more modern services. For the service providers, the privatization means competition. The service providers need an optimized business plan to increase their market share, so that they can maximize their revenue and avoid excessive costs with investments, operation and management of the network. This research has the goal to assist the planners in their long-term project to expand the access network to the telecommunications services. This study presents corresponding mathematical models and proposes an evolutive resolution method capable to deal with the intrinsic complexity of the Mixed Integer Linear Programming problem (PLIM). The Hybrid Evolutive Algorithm (AHE) disassembles the problem in two parts. The evolutionary part assumes the evaluation of integer decision variables and it is based in genetic algorithms ¿ heuristic method that imitates the evolution of species to generate possible solutions for the problems. The evaluation of these solutions ¿ fitness function ¿ is achieved by solving the remaining network flow problem via classic linear optimization methods. The genetic algorithm is also enhanced by anti-violation rules to avoid generation of non-feasible solutions. The performance comparisons with the solver CPLEX ® confirms that the AHE does accomplish its goal of providing good quality results for the problem in an acceptable computer time / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador : Christiano Lyra Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T14:47:49Z (GMT). No. of bitstreams: 1 Fernandes_CristianeMariaAlvesPissarra_D.pdf: 2291495 bytes, checksum: 7e7d174ac6ac2ef1df43ec1404ef9a73 (MD5) Previous issue date: 2003 / Doutorado

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T19:18:58Z (GMT). No. of bitstreams: 1 Crepaldi_BrunoEspinosa_M.pdf: 13275684 bytes, checksum: aa236e6a56dd7ed5507276017c51b8fb (MD5) Previous issue date: 2014 / Resumo: Considerado uma variação do problema da galeria de arte, o problema do posicionamento de antenas trata do posicionamento do menor número de antenas requerido para determinar se uma pessoa está dentro ou fora da galeria. Uma antena propaga uma chave única dentro de um ângulo específico de transmissão, de modo que o conjunto de chaves recebidas em um dado ponto do plano seja suficiente para decidir se ele pertence ou não ao polígono que representa a galeria. Para verificar esta propriedade de localização, uma fórmula Booleana deve ser produzida junto com o posicionamento de antenas. Dizemos que as antenas estão em posição natural se elas estão localizadas nos vértices ou nas arestas do polígono e transmitindo sinal no ângulo formado pelos lados deste último no ponto onde a antena está posicionada. O problema do posicionamento natural de antenas é NP-difícil. Nesta dissertação, apresentamos um algoritmo exato para resolvê-lo. Para tanto, propomos um modelo inicial de programação linear inteira para o problema que, ao ser computado por um resolvedor comercial, se mostrou capaz de encontrar soluções ótimas de instâncias correspondentes a polígonos com algumas dezenas de vértices. Em seguida, através de estudos de propriedades geométricas, são introduzidas várias melhorias no modelo matemático e também na forma de computá-lo. Como consequência desta pesquisa, desenvolvemos um algoritmo iterativo baseado em programação linear inteira com o qual conseguimos solucionar o problema para instâncias consideravelmente maiores. A eficiência do nosso algoritmo é certificada por resultados experimentais que compreendem as soluções ótimas de 720 instâncias de até 1000 vértices, incluindo polígono com buracos, as quais foram calculadas em menos de seis minutos em um computador desktop padrão / Abstract: Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to determine if someone is inside or outside the gallery. Each antenna propagates a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon that represents the gallery. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. We say that the antennas are in natural position if they are located at the vertices or the edges of the polygon and transmitting their signals in the angle formed by the sides of the polygon at the point where the antenna is positioned. The natural wireless localization problem is NP-hard. In this dissertation, we present an exact algorithm to solve it. To this end, we propose an initial integer linear programming model for the problem that, after being computed by a commercial solver, proved to be capable of finding optimal solutions for instances corresponding to polygons with tens of vertices. Then, through studies of geometric properties, several improvements are introduced in the mathematical model and also in the way of computing it. As a result of this research, we develop an iterative algorithm based on integer linear programming with which we can solve the problem for considerably larger instances. The efficiency of our algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes with up to 1000 vertices, in less than six minutes on a standard desktop computer / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T19:27:17Z (GMT). No. of bitstreams: 1 Brandt_AlexFernando_M.pdf: 1939918 bytes, checksum: c6d9d34f314830d07dc1e49ad43ab514 (MD5) Previous issue date: 2014 / Resumo: Seja P um conjunto de pontos no plano. O grafo geométrico de P, G(P) = (P, E), é o grafo ponderado completo cujos vértices correspondem aos pontos de P e no qual o custo de uma aresta {i, j} é dado pela distância Euclidiana entre os pontos i e j. Inicialmente, considere um problema genérico em que se quer construir uma rede com boa qualidade de conexão ligando um conjunto de locais representados por pontos no plano. Em muitas aplicações deste tipo, o problema pode ser modelado com o auxílio de um grafo geométrico. Isso ocorre quando, por exemplo, para um par de pontos, a medida de qualidade é definida como a razão entre o comprimento do menor caminho que os conecta na rede projetada e a respectiva distância Euclidiana. Esta razão determina a dilatação daquele par de pontos na rede. Já a dilatação da rede construída em si é dada pela dilatação máxima sobre todos os pares de pontos. Nesta dissertação apresentamos métodos exatos para resolução dos problemas dedicados a encontrar uma árvore geradora ou uma triangulação planar de dilatação mínima, denominados, respectivamente, Problema da Árvore Geradora de Dilatação Mínima (MDSTP) e Problema da Triangulação de Dilatação Mínima (MDTP). Os métodos descritos são compostos principalmente pela formulação, redução e resolução de programas lineares inteiros mistos. A redução do tamanho destes modelos matemáticos é feita explorando-se a geometria dos problemas por meio de rotinas que determinam a presença ou da ausência de certos elementos da formulação em soluções com dilatação menor ou igual ao limitante primal fornecido por uma heurística. A aplicação destas rotinas em uma fase de pré-processamento permite uma redução significativa do tamanho do modelo levando à aceleração do seu tempo de resolução. Com a combinação destas técnicas obteve-se, pela primeira vez, soluções comprovadamente ótimas de instâncias até 20 pontos para o MDSTP e até 70 pontos para o MDTP. Os problemas e suas formulações, bem como suas formas de redução e de resolução, são apresentados em detalhes. Além disso, são feitas análises de desempenho computacional não só dos métodos exatos, mas também de algoritmos propostas por outros autores / Abstract: Let P be a set of points in the plane. The geometric graph of P, G(P) =(P, E), is the complete weighted graph whose vertices correspond to the points of P and in which the cost of an edge {i, j} is given by the Euclidean distance between the points i and j. Initially, consider a general problem where one wants to build a network with good connection quality joining a set of sites represented by points in the plane. In many applications of this kind, the problem can be modeled with the aid of a geometric graph. This occurs when, for example, for a pair of points, the quality measure is defined as the ratio of the length of the shortest path that connects them in the designed network and their Euclidean distance. This ratio determines the dilation of that pair of points in the network. On the other hand, the dilation of the built network itself is given by the maximum dilation over all pair of points. In this dissertation we present exact methods for solving problems dedicated to finding a spanning tree or a planar triangulation of minimum dilation, named, respectively, the Minimum Dilation Spanning Tree Problem (MDSTP) and Minimum Dilation Triangulation Problem (MDTP). The described methods are composed primarily by the formulation, downsizing and resolution of mixed integer linear programs. The downsizing of these mathematical models is done by exploiting the geometry of the problems by means of routines that determine the need of the presence or the absence of certain elements of the formulation in solutions with dilation less than or equal to the primal bound supplied by a heuristic. Applying these routines in a pre-processing phase allows a significant reduction of the model size leading to the acceleration of its resolution time. With the combination of these techniques, for the first time, proven optimal solutions of instances with up to 20 points for the MDSTP and up to 70 points to the MDTP were obtained. The problems and their formulations, as well as ways of reducing and solving them, are presented in detail. Furthermore, analyzes of computational performance not only of the exact methods, but also of algorithms proposed by other authors are made / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Flavio Keidi Miyazawa, Mauricio Guilherme de Carvalho Resende / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T21:53:09Z (GMT). No. of bitstreams: 1 Andrade_CarlosEduardode_D.pdf: 4654702 bytes, checksum: 566cb3ea8fc876147ffa6df2ec8482b3 (MD5) Previous issue date: 2015 / Resumo: Nos últimos anos, as redes de telecomunicação tem experienciado um grande aumento no fluxo de dados. Desde a utilização massiva de vídeo sob demanda até o incontável número de dispositivos móveis trocando texto e vídeo, o tráfego alcançou uma escala capaz de superar a capacidade das redes atuais. Portanto, as companhias de telecomunicação ao redor do mundo tem sido forçadas a aumentar a capacidade de suas redes para servir esta crescente demanda. Como o custo de instalar uma infraestrutura de rede é geralmente muito grande, o projeto de redes usa fortemente ferramentas de otimização para manter os custos tão baixos quanto possível. Nesta tese, nós analisamos vários aspectos do projeto e implementação de redes de telecomunicação. Primeiramente, nós apresentamos um novo problema de projeto de redes usado para servir demandas sem fio de dispositivos móveis e rotear tal tráfego para a rede principal. Tais redes de acesso são baseadas em tecnologias sem fio modernos como Wi-Fi, LTE e HSPA. Este problema consideramos várias restrições reais e é difícil de ser resolvido. Nós estudamos casos reais nas vizinhanças de uma grande cidade nos Estados Unidos. Em seguida, nós apresentamos uma variação do problema de localização de hubs usado para modelar as redes principais (backbones ou laços centrais). Este problema também pode ser utilizado para modelar redes de transporte de cargas e passageiros. Nós também estudamos o problema de clusterização correlacionada com sobreposições usado para modelar o comportamento dos usuários quando utilizam seus equipamentos móveis. Neste problema, nós podemos rotular um objeto usando múltiplos rótulos e analisar a conexão entre eles. Este problema é adequado para análise de mobilidade de equipamentos que pode ser usada para estimar o tráfego em uma dada região. E finalmente, nós analisamos o licenciamento de espectro sobre uma perspectiva governamental. Nestes casos, uma agência do governo deseja vender licenças para companhias de telecomunicação para que operem em uma dada faixa de espectro. Este processo usualmente é conduzido usando leilões combinatoriais. Para todos problemas, nós propomos algoritmos genéticos de chaves aleatórias viciadas e modelos de programação linear inteira mista para resolvê-los (exceto para o problema de clusterização correlacionada com sobreposição, devido sua natureza não-linear). Os algoritmos que propusemos foram capazes de superar algoritmos do estado da arte para todos problemas / Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances / Abstract: In last twenty years, telecommunication networks have experienced a huge increase in data utilization. From massive on-demand video to uncountable mobile devices exchanging text and video, traffic reached scales that overcame the network capacities. Therefore, telecommunication companies around the world have been forced to increase their capacity to serve this increasing demand. As the cost to deploy network infrastructure is usually very large, the design of a network heavily uses optimization tools to keep costs as low as possible. In this thesis, we analyze several aspects of the design and deployment of communication networks. First, we present a new network design problem used to serve wireless demands from mobile devices and route the traffic to the core network. Such access networks are based on modern wireless access technologies such as Wi-Fi, LTE, and HSPA. This problem has several real world constraints and it is hard to solve. We study real cases of the vicinity of a large city in the United States. Following, we present a variation of the hub-location problem used to model these core networks. Such problem is also suitable to model transportation networks. We also study the overlapping correlation clustering problem used to model the user's behavior when using their mobile devices. In such problem, one can label an object with multiple labels and analyzes the connections between them. Although this problem is very generic, it is suitable to analyze device mobility which can be used to estimate traffic in geographical regions. Finally, we analyze spectrum licensing from a governmental perspective. In these cases, a governmental agency wants to sell rights for telecommunication companies to operate over a given spectrum range. This process usually is conducted using combinatorial auctions. For all problems we propose biased random-key genetic algorithms and mixed integer linear programming models (except in the case of the overlapping correlation clustering problem due its non-linear nature). Our algorithms were able to overcome the state of the art algorithms for all problems / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Funções submodulares aparecem naturalmente em diversas áreas, tais como probabilidade, geometria e otimização combinatória. Pode-se dizer que o papel desempenhado por essas funções em otimização discreta é similar ao desempenhado por convexidade em otimização contínua. Com efeito, muitos problemas em otimização combinatória podem ser formulados como um problema de minimizar uma função submodular sobre um conjunto apropriado. Além disso, submodularidade está presente em vários teoremas ou problemas combinatórios e freqüentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Nesta dissertação, estudamos aspectos estruturais e algorítmicos de funções submodulares, com ênfase nos recentes avanços em algoritmos combinatórios para minimização dessas funções. Descrevemos com detalhes os primeiros algoritmos combinatórios e fortemente polinomiais para esse propósito, devidos a Schrijver e Iwata, Fleischer e Fujishige, além de algumas outras extensões. Aplicações de submodularidade em otimização combinatória também estão presentes neste trabalho. / Submodular functions arise naturally in various fields, including probability, geometry and combinatorial optimization. The role assumed by these functions in discrete optimization is similar to that played by convexity in continuous optimization. Indeed, we can state many problems in combinatorial optimization as a problem of minimizing a submodular function over an appropriate set. Moreover, submodularity appears in many combinatorial theorems or problems and frequently plays an essencial role in a proof or an algorithm. In this dissertation, we study structural and algorithmic aspects of submodular functions. In particular, we focus on the recent advances in combinatorial algorithms for submodular function minimization. We describe in detail the first combinatorial strongly polynomial-time algorithms for this purpose, due to Schrijver and Iwata, Fleischer, and Fujishige, as well as some extensions. Some applications of submodularity in combinatorial optimization are also included in this work.

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.