The segmentation problem arises in the elaboration of a radiation therapy plan. After the cancer has been diagnosed and the radiation therapy sessions have been prescribed, the physician has to locate the tumor as well as the organs situated in the radiation field, called the organs at risk. The physician also has to determine the different dosage he wants to deliver in each of them and has to define a lower bound on the dosage for the tumor (which represents the minimum amount of radiation that is needed to have a sufficient control of the tumor) and an upper bound for each organ at risk (which represents the maximum amount of radiation that an organ can receive without damaging). Designing a radiation therapy plan that respects these different bounds of dosage is a complex optimization problem that is usually tackled in three steps. The segmentation problem is one of them.<p><p>Mathematically, the segmentation problem amounts to decomposing a given nonnegative integer matrix A into a nonnegative integer linear combination of some binary matrices. These matrices have to respect the consecutive ones property. In clinical applications several constraints may arise that reduce the set of binary matrices which respect the consecutive ones property that we can use. We study some of them, as the interleaf distance constraint, the interleaf motion constraint, the tongue-and-groove constraint and the minimum separation constraint.<p><p>We consider here different versions of the segmentation problem with different objective functions. Hence we deal with the beam-on time problem in order to minimize the total time during which the patient is irradiated. We study this problem under the interleaf distance and the interleaf motion constraints. We consider as well this last problem under the tongue-and-groove constraint in the binary case. We also take into account the cardinality and the lex-min problem. Finally, we present some results for the approximation problem. <p><p>/Le problème de segmentation intervient lors de l'élaboration d'un plan de radiothérapie. Après que le médecin ait localisé la tumeur ainsi que les organes se situant à proximité de celle-ci, il doit aussi déterminer les différents dosages qui devront être délivrés. Il détermine alors une borne inférieure sur le dosage que doit recevoir la tumeur afin d'en avoir un contrôle satisfaisant, et des bornes supérieures sur les dosages des différents organes situés dans le champ. Afin de respecter au mieux ces bornes, le plan de radiothérapie doit être préparé de manière minutieuse. Nous nous intéressons à l'une des étapes à réaliser lors de la détermination de ce plan: l'étape de segmentation.<p><p>Mathématiquement, cette étape consiste à décomposer une matrice entière et positive donnée en une combinaison positive entière linéaire de certaines matrices binaires. Ces matrices binaires doivent satisfaire la contrainte des uns consécutifs (cette contrainte impose que les uns de ces matrices soient regroupés en un seul bloc sur chaque ligne). Dans les applications cliniques, certaines contraintes supplémentaires peuvent restreindre l'ensemble des matrices binaires ayant les uns consécutifs (matrices 1C) que l'on peut utiliser. Nous en avons étudié certaines d'entre elles comme celle de la contrainte de chariots, la contrainte d'interdiciton de chevauchements, la contrainte tongue-and-groove et la contrainte de séparation minimum.<p><p>Le premier problème auquel nous nous intéressons est de trouver une décomposition de la matrice donnée qui minimise la somme des coefficients des matrices binaires. Nous avons développé des algorithmes polynomiaux qui résolvent ce problème sous la contrainte de chariots et/ou la contrainte d'interdiction de chevauchements. De plus, nous avons pu déterminer que, si la matrice donnée est une matrice binaire, on peut trouver en temps polynomial une telle décomposition sous la contrainte tongue-and-groove.<p><p>Afin de diminuer le temps de la séance de radiothérapie, il peut être désirable de minimiser le nombre de matrices 1C utilisées dans la décomposition (en ayant pris soin de préalablement minimiser la somme des coefficients ou non). Nous faisons une étude de ce problème dans différents cas particuliers (la matrice donnée n'est constituée que d'une colonne, ou d'une ligne, ou la plus grande entrée de celle-ci est bornée par une constante). Nous présentons de nouvelles bornes inférieures sur le nombre de matrices 1C ainsi que de nouvelles heuristiques.<p><p>Finalement, nous terminons par étudier le cas où l'ensemble des matrices 1C ne nous permet pas de décomposer exactement la matrice donnée. Le but est alors de touver une matrice décomposable qui soit aussi proche que possible de la matrice donnée. Après avoir examiné certains cas polynomiaux nous prouvons que le cas général est difficile à approximer avec une erreur additive de O(mn) où m et n représentent les dimensions de la matrice donnée. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé. / Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab.

Embedded system designers face multiple challenges in fulfilling the runtime requirements of programs. Effective scheduling of programs is required to extract as much parallelism as possible. These scheduling algorithms must also improve speedup after instruction-set extensions have occurred. Scheduling of dynamic code at run time is made more difficult when the static components of the program are scheduled inefficiently. This research aims to optimize a program’s static code at compile time. This is achieved with four algorithms designed to schedule code at the task and instruction level. Additionally, the algorithms improve scheduling using instruction set extended code on symmetrical homogeneous multiprocessor systems. Using these algorithms, we achieve speedups up to 3.86X over sequential execution for a 4-issue 2-processor system, and show better performance than recent heuristic techniques for small programs. Finally, the algorithms generate speedup values for a 64-point FFT that are similar to the test runs.

The consumer market of today is characterized by emphasis on superior customer satisfaction and personalization of services. This entails higher customer expectations on organizations, which also includes the workforce scheduling processes in which the consumers expect more decision-power to dictate what they want, when and where they want services to be delivered. For organizations that deliver on-site services, the routing aspect becomes an important part of the scheduling process. Literature on Workforce Scheduling and Routing Problems (WSRP) seldom relate to characteristics of the more dynamic consumer market. As the markets and consumer needs become more flexible, the relevance for research concerning these characteristics increases. This study addresses this by reviewing current literature and present common solution methodologies applied to WSRP, as well as the effects of the online scheduling characteristics. With this as a foundation, a discussion is provided of how WSRP and online scheduling can be combined in order to improve resource utilization and minimize travel time for an on-site service provider. The overall aim of the study is to investigate how an online WSRP with exact time windows can be formulated and solved. The result is a four-stage hybrid method including linear integer programming and constructive heuristics with the objective to minimize travel time, idle time, and the makespan in the schedules. A case study has been conducted on an on-site service provider, and by applying the proposed hybrid methodology on the case company’s scheduling process, results have been obtained that demonstrates improvements of travel time and resource utilization. The study also demonstrate that the appliance of flexible travel times and product dependent service times have positive impact on the quality of the generated schedules. A key insight is that organizations working with exact time windows have to be aware of the trade-off between customer preferences and operational efficiency in day-to-day operations. Thus, organizations have to decide what holds most importance to the organization’s long-term success.

The subject of the thesis is the optimization of one the key processes in a book company, namely warehouse logistics. This problem consist of two parts; first part focuses on route optimization of completion of customers' orders on daily basis, second part focuses on assigning of storage subsystems and their interconnection. The proposed solution uses a traveller salesman problem implemented into intranet application. Second problem was designed as quadratic assignment problem with use of ex post data analysis. On the basis of achieved results, we presented effective procedures for solving both of aforementioned problems and suggested their implementation into the company's enterprise resource planning system. Keywords:

Orientador: Paulo de Barros Correia / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-27T01:59:39Z (GMT). No. of bitstreams: 1 Silva_ElisaBastos_D.pdf: 2776184 bytes, checksum: 20b2252b72c7204d062893f8dcb3d304 (MD5) Previous issue date: 2015 / Resumo: Leilões de novos empreendimentos de energia envolvem o compromisso de construí-los e o direito de explorá-los por meio de contratos de outorga. O leiloeiro, cujo objetivo é minimizar o pagamento pela energia contratada, buscando a redução de seu preço para os consumidores finais, fornece o direito de outorga da usina para o vencedor. O licitante é um investidor, e.g., uma empresa de geração que procura maximizar seu benefício com a venda de energia proveniente do empreendimento. Quando a natureza desses empreendimentos é complementar, torna-se possível proporcionar maiores benefícios aos licitantes, e maior eficiência ao leilão, caso sejam negociados em conjunto. Atualmente, o projeto de leilão instituído é composto por uma abordagem híbrida, sequencial e simultânea, que não permite a extração das sinergias entre empreendimentos. Esta tese examina duas metodologias híbridas de leilões reversos, considerando-se o ponto de vista do leiloeiro. O primeiro modelo, centralizado, é composto por duas fases: uma simultânea de lance aberto e outra combinatória de lance fechado. A fase simultânea incentiva a revelação do preço da energia, enquanto a fase combinatória oferece oportunidade aos licitantes de submeterem ofertas mais agressivas através de pacotes de empreendimentos complementares. O modelo centralizado é formulado como um problema de otimização inteiro e combinatório. A função-objetivo consiste em minimizar o pagamento, isso é, energia multiplicada pelo preço (lance) para todas as usinas. A estratégia de solução identifica os vencedores, resolvendo um problema de set-packing restrito. A segunda metodologia utiliza uma abordagem, também, em duas fases. A primeira é um projeto simultâneo de lance aberto, e a segunda fase um projeto combinatório descentralizado. Nesse modelo, a dificuldade do problema aumenta progressivamente à medida que os pacotes são ofertados. A dificuldade da alocação é distribuída entre os licitantes e, por isso, o leiloeiro não necessita resolver um problema de otimização. As metodologias propostas são aplicadas aos leilões de energia nova para o setor elétrico brasileiro. Os resultados mostram que a utilização de ambas as metodologias resolvem o problema de alocação com um tempo computacional aceitável / Abstract: Auctions for new power plants involve a commitment of constructing and the right of exploring them through power sales contracts. The auctioneer -- whose objective is to minimize the payment for the contracted energy, seeking to reduce prices for consumers -- provides the power plant's right for the winner. The bidder is an investor, for example, a generation company, which aims to maximize benefits of energy sales. When the power plant's nature is complementary, it is possible to provide more benefits to bidders and greater efficiency to the auction if these plants were traded together. Currently, the instituted auction design consists of a hybrid approach -- sequential and simultaneous -- which does not allow the extraction of synergies among plants. This thesis examines two hybrid methods of reverse auctions from the auctioneer's view point. The first model, centralized, consists of two phases: a simultaneous open bid and a combinatorial sealed bid. The simultaneous phase encourages the energy prices revelation. The combinatorial phase allows aggressive bidders to acquire bundles of complementary plants. The centralized model is formulated as an integer and combinatorial optimization problem. The objective function consists of minimizing the payment, that is, energy multiplied by the price (bid) for all plants. The solution strategy identifies the winners solving a restricted set-packing problem. The second method also uses a two phase approach. The first phase is a simultaneous open bid design and the second phase is a decentralized combinatorial design. In this model, the problem difficulty increases gradually. The allocation difficulty is distributed among the bidders; therefore, the auctioneer does not need to solve an optimization problem. The proposed methodologies are applied to new energy auctions on Brazilian electrical energy sector. The results show the use of both methods solving the problem of allocation with an acceptable computational time / Doutorado / Planejamento de Sistemas Energeticos / Doutora em Planejamento de Sistemas Energéticos

O problema abordado nesta pesquisa consiste na distribuição de água em redes urbanas para o atendimento de demandas conhecidas, com o objetivo de minimizar o custo da energia elétrica necessária para o funcionamento de bombas hidráulicas. As bombas hidráulicas são utilizadas para captar água de poços artesianos ou estações de tratamento de água para abastecer reservatários distribuídos por bairros de uma cidade, de onde a população será atendida por força gravitacional. Como o custo da energia elétrica varia ao longo do dia, se faz necessário um planejamento do funcionamento das bombas para que não sejam ligadas nos horários em que a energia elétrica é mais cara. O problema de planejamento de estoque de água em reservatórios (PPEAR) consiste em decidir em quais períodos ou frações dos períodos do horizonte de planejamento as bombas hidráulicas que abastecem os reservatórios devem permanecer ligadas e em quais períodos ou frações dos períodos deve haver transporte de água entre os reservatórios para que a demanda de cada reservatório seja atendida em cada período e sejam respeitados os níveis mínimos e máximos de água nos reservatórios. Uma solução heurística para resolver o PPEAR é proposta e analisada por comparação com as soluções obtidas pelo método de enumeração implícita. Resultados computacionais comprovam a eficiência da abordagem, tanto pela qualidade das soluções como pelo baixo tempo de resposta / The problem focused in this study consists of reducing the eletrical energy cost necessary to the operation of hydraulic pumps. The hydraulic pumps are used to catch water from artesians wells or Water Treatment Station to supply tanks which are located in districts in a city, from which the population will be supplied by gravitational force. As the cost of electrical energy varies along the day, a schedule of the pumps run is necessary to avoid that they are not turned in the periods when the energy cost is more expensive. The problem of water stock schedule in tanks (WSST) consists of deciding in which periods or parts of them of the horizon planning the hydraulic pumps have to put on, and in which periods or parts of them should transfer water among the tanks so that the demand of each tank is met for each period and lower and upper limits of water shouldn\'t be violated. A heuristic solution is proposed and analyzed by comparing its solutions with the solutions obtained by the branch and bound method. Computational experiments show the efficiency of the heuristic

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Nas últimas décadas, diversas propostas de técnicas e de processos visando aumentar a sustentabilidade da agricultura ganharam evidência. Tais propostas geram novos modelos de planejamento em que devem ser considerados aspectos técnicos e ecológicos de produção, bem como o acesso de pequenos agricultores familiares ao mercado consumidor. Neste tipo de planejamento da produção, a rotação de culturas desempenha um papel fundamental, pois contribui para a manutenção dos recursos produtivos, para a minimização do uso de recursos não-renováveis e para o controle biológico da população de herbívoros, patógenos e plantas espontâneas. Nesta tese abordamos dois problemas de Programação de Rotação de Culturas (PRC) focados na produção de base sustentável de hortaliças: o problema de PRC com restrições de Adjacências (PRC-A) e o problema de PRC com atendimento da Demanda (PRC-D). O planejamento da produção de hortaliças é complexo pois envolve, em geral, um grande número de culturas com limitações específicas quanto à época de plantio e com períodos de cultivo e produtividades muito variáveis. A programação de rotação de culturas para as áreas de plantio é formulada como um modelo de otimização 01 e, para os dois problemas, em cada programação considera se tanto aspectos técnicos (época de plantio e colheita etc.) quanto ecológicos (adubação verde, pousio etc.). No problema PRC-A o objetivo é a maximização da ocupação das áreas produtivas em que as restrições de plantio são estendidas às áreas adjacentes. Como a formulação matemática para o problema tem, em geral, um número muito grande de restrições e variáveis, com matriz de restrições esparsa e bloco-diagonal, o modelo é reformulado com a Decomposição DantzigWolfe, o que permitiu sua resolução por procedimentos baseados em geração de colunas, heurísticos e exatos. No problema PRC-D desejase suprir a demanda de um conjunto de hortaliças tendo-se disponível um conjunto de áreas heterogêneas. As culturas passíveis de plantio, bem como as suas produtividades, dependem da área considerada. O problema foi formulado como um modelo de otimização linear em que cada variável está associada a uma programação de rotação de culturas. O modelo contém potencialmente um número grande de programações de rotação e é resolvido por geração de colunas. Experimentos computacionais usando instâncias baseadas em dados reais confirmam a eficácia dos modelos e das metodologias propostos para os problemas / Over the last decades, various proposals for techniques and processes to increase agricultural sustainability have been put forward. These proposals bring new planning models in which technical and ecological production aspects must be considered, as well as the access of small farmers to the consumer market. In this type of agricultural production planning, crop rotation plays a fundamental role as it contributes to maintaining productive resources, to reducing the use of non-renewable resources, and to biologically controlling the population of herbivores, pathogens and spontaneous plants. In this thesis, two problems concerning the Crop Rotation Schedule (CRS) focusing on sustainable production vegetables are addressed: the problem of the CRS having Adjacent constraints (CRS-A) and the problem of the CRS under Demand constraints (CRS-D). Production planning of vegetables is complex as it generally involves a large number of crop species having specific limitations regarding the planting season and very varied production times and productivity. The crop rotation schedule problem is formulated as an optimization model 0-1, and for both problems, in each schedule technical (planting and harvesting season etc.) and ecological (green manure, fallow etc.) aspects are considered. Concerning the CRS-A problem, the aim is to maximize the occupation of cropping areas in which planting constraints are extended to adjacent areas. As the mathematical formulation for the problem generally has a large number of restrictions and variables and the structure of the constraint matrix of the problem is sparse and block-diagonal, the model has been reformulated using the Dantzig-Wolfe Decomposition strategy, which has enabled the use of a heuristic and exact procedures based on the column generation approach for its resolution. In the CRS-D problem, the aim is to meet the market demands for vegetables having a set of heterogeneous cropping areas available. The potential planting crops, as well as their productivity, depend on the considered cropping area. The problem is formulated as an optimization linear model in which each variable is associated to a crop rotation schedule. The model may include a large number of rotation schedules and is solved by the column generation approach. Computational experiments using instances based on real-world data confirm the efficiency of models and methodologies proposed for the problems

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries