Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

O presente trabalho tem por objetivo a proposição de uma abordagem para gestão integrada da operação do sistema elétrico em tempo real pelo diagnóstico da interrupção e determinação de planos de atenuação dos efeitos pela definição da topologia do sistema, com propostas de cortes seletivos da carga em condições de esgotamento da capacidade de transferência. A metodologia proposta abrange sistemas elétricos de grande porte e de diferentes níveis de tensão, tais como sistemas de sub-transmissão e distribuição, simultaneamente e com geração distribuída. Como técnica de solução é aplicada a Busca Tabu para minimização do total de seções desconectadas (desenergizadas) e o número de manobras realizadas para atendimento em casos contingenciais, com atendimento de clientes prioritários e alívio de carga e geração distribuída. A codificação e estrutura de dados aplicados propiciam uma melhor eficiência computacional, favorecendo a aplicação em sistemas operacionais de tempo real. A modelagem proposta é avaliada em sistemas de testes adaptados da literatura, demonstrando a qualidade, robustez e eficiência computacional nos resultados obtidos da abordagem proposta. / The present work aims at proposing an automatic computational methodology to electrical systems operational management in real time via the interruption diagnosis and effect attenuation plan definition by means of system topology determination with load curtailment in load transference capacity exhaustion conditions. The proposed methodology tackles large electrical systems with different voltage levels, such as sub-transmission and distribution systems simultaneously with distributed generators. The Tabu Search is applied to minimize the out-of-service area and the number of switching operations during contingencies with priority customer, load curtailment and distributed generators. The software codification and data structure applied provide computational efficiency, favoring the application to electrical systems operation in real time and the proposed model is validated with test systems from the literature, ensuring the computational efficiency and quality of results.

Agricultural producers consider utilizing multiple machines to reduce field completion times for improving effective field capacity. Using a number of smaller machines rather than a single big machine also has benefits such as sustainability via less compaction risk, redundancy in the event of an equipment failure, and more flexibility in machinery management. However, machinery management is complicated due to logistics issues. In this work, the allocation and ordering of field paths among a number of available machines have been transformed into a solvable Vehicle Routing Problem (VRP). A basic heuristic algorithm (a modified form of the Clarke-Wright algorithm) and a meta-heuristic algorithm, Tabu Search, were employed to solve the VRP. The solution considered optimization of field completion time as well as improving the field efficiency. Both techniques were evaluated through computer simulations with 2, 3, 5, or 10 vehicles working simultaneously to complete the same operation. Furthermore, the parameters of the VRP were changed into a dynamic, multi-depot representation to enable the re-route of vehicles while the operation is ongoing. The results proved both the Clarke-Wright and Tabu Search algorithms always generated feasible solutions. The Tabu Search solutions outperformed the solutions provided by the Clarke-Wright algorithm. As the number of the vehicles increased, or the field shape became more complex, the Tabu Search generated better results in terms of reducing the field completion times. With 10 vehicles working together in a real-world field, the benefit provided by the Tabu Search over the Modified Clarke-Wright solution was 32% reduction in completion time. In addition, changes in the parameters of the VRP resulted in a Dynamic, Multi-Depot VRP (DMDVRP) to reset the routes allocated to each vehicle even as the operation was in progress. In all the scenarios tested, the DMDVRP was able to produce new optimized routes, but the impact of these routes varied for each scenario. The ability of this optimization procedure to reduce field work times were verified through real-world experiments using three tractors during a rotary mowing operation. The time to complete the field work was reduced by 17.3% and the total operating time for all tractors was reduced by 11.5%. The task of a single large machine was also simulated as a task for 2 or 3 smaller machines through computer simulations. Results revealed up to 11% reduction in completion time using three smaller machines. This time reduction improved the effective field capacity.

Cellular manufacturing, which is also referred to as group technology among researchers, has primarily been used as a means to increase productivity, efficiency and flexibility. Under group technology, similar jobs, which have similar shape, material, and processing operations are assigned to the same group. Moreover, dissimilar machines are assigned to the same cell to meet the processing requirements of jobs in a group or multiple groups. Group scheduling problems have been studied extensively in the past as implementation of group technology became more prevalent in industry. However, most of the work that has been done has focused on single-criterion optimization. A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this research. Cellular manufacturing and flow shop are two popular scenarios in industry. To mimic real industry practice, dynamic job releases and dynamic machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which satisfy the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two goals. Two different initial solution finding mechanisms are proposed, and a tabu-search based two-level search algorithm is developed to find near optimal solutions for the problem. An example problem is used to demonstrate the applicability of the search algorithm. A mathematical model is developed and implemented to evaluate the quality of the solutions obtained from the heuristics in small problem instances. Further, to uncover the difference in performance of initial solution finding mechanisms and heuristics, a detailed experimental design is performed. The results show that different heuristics have different performance in solving problems generated with different parameters. / Graduation date: 2012

There is an increasing interest in sustainability and a growing debate about environmental policy measures aiming at the reduction of green house gas emissions across di erent economic sectors worldwide. The transportation sector is one major greenhouse gas emitter which is heavily regulated to reduce its dependance on oil. These regulations along with the growing customer awareness about global warming has led vehicle manufacturers to seek di erent technologies to improve vehicle e ciencies and reduce the green house gases emissions while at the same time meeting customer's expectation of mobility and exibility. Plug-in hybrid electric vehicles (PHEV) is one major promising solution for a smooth transition from oil dependent transportation sector to a clean electric based sector while not compromising the mobility and exibility of the drivers. In the medium term, plug-in hybrid electric vehicles (PHEV) can lead to signi cant reductions in transportation emissions. These vehicles are equipped with a larger battery than regular hybrid electric vehicles which can be recharged from the grid. For short trips, the PHEV can depend solely on the electric engine while for longer journeys the alternative fuel can assist the electric engine to achieve extended ranges. This is bene cial when the use pattern is mixed such that and short long distances needs to be covered. The plug-in hybrid electric vehicles are well-suited for logistics since they can avoid the possible disruption caused by charge depletion in case of all-electric vehicles with tight time schedules. The use of electricity and fuel gives rise to a new variant of the classical vehicle routing with time windows which we call the plug-in hybrid electric vehicle routing problem with time windows (PHEVRPTW). The objective of the PHEVRPTW is to minimize the routing costs of a eet of PHEVs by minimizing the time they run on gasoline while meeting the demand during the available time windows. As a result, the driver of the PHEV has two decisions to make at each node: (1) recharge the vehicle battery to achieve a longer range using electricity, or (2) continue to the next open time window with the option of using the alternative fuel. In this thesis, we present a mathematical formulation for the plug-in hybrid-electric vehicle routing problem with time windows. We solve this problem using a Lagrangian relaxation and we propose a new tabu search algorithm. We also present the rst results for the full adapted Solomon instances.

Due to the significant effects on the performance and competitiveness of aircraft, high lift devices are of extreme importance in aircraft design. The flow physics of high lift devices is so complex, that traditional one pass and multi-pass design approaches can’t reach the most optimised concept and multi-objective design optimisation (MDO) methods are increasingly explored in relation to this design task. The accuracy of the optimisation, however, depends on the accuracy of the underlying Computational Fluid Dynamics (CFD) solver. The complexity of the flow around high-lift configuration, namely transition and separation effects leads to a substantial uncertainty associated with CFD results. Particularly, the uncertainty related to the turbulence modelling aspect of the CFD becomes important. Furthermore, employing full viscous flow solvers within MDO puts severe limitations on the density of computational meshes in order to achieve a computationally feasible solution, thereby adding to the uncertainty of the outcome. This thesis explores the effect of uncertainties in CFD modelling when detailed aerodynamic analysis is required in computational design of aircraft configurations. For the purposes of this work, we select the benchmark NLR7301 multi-element airfoil (main wing and flap). This flow around this airfoil features all challenges typical for the high-lift configurations, while at the same time there is a wealth of experimental and computational data available in the literature for this case. A benchmark shape bi-objective optimization problem is formed, by trying to reveal the trade-off between lift and drag coefficients at near stall conditions. Following a detailed validation and grid convergence study, three widely used turbulence models are applied within Reynolds-Averaged Navier-Stokes (RANS) approach. K- Realizable, K- SST and Spalart-Allmaras. The results show that different turbulent models behave differently in the optimisation environment, and yield substantially different optimised shapes, while maintaining the overall optimisation trends (e.g. tendency to maximise camber for the increased lift). The differences between the models however exhibit systemic trends irrespective of the criteria for the selection of the target configuration in the Pareto front. A-posteriori error analysis is also conducted for a wide range of configurations of interest resulting from the optimisation process. Whereas Spalart-Allmaras exhibits best accuracy for the datum airfoil, the overall arrangement of the results obtained with different models in the (Lift, Drag) plane is consistent for all optimisation scenarios leading to increased confidence in the MDO/RANS CFD coupling.

Closed-loop supply chain (CLSC) management provides opportunity for cost savings through the integration of product recovery activities into traditional supply chains. Product recovery activities, such as remanufacturing, reclaim a portion of the previously added value in addition to the physical material. Our problem setting is motivated by the practice of an Original Equipment Manufacturer (OEM) in the automotive service parts industry, who operates a well established forward network. The OEM faces customer demand due to warranty and beyond warranty vehicle repairs. The warranty based demand induces part returns. We consider a case where the OEM has not yet established a product recovery network, but has a strategic commitment to implement remanufacturing strategy. In accomplishing this commitment, complications arise in the network design due to activities and material movement in both the forward and reverse networks, which are attributed to remanufacturing. Consequently, in implementing the remanufacturing strategy, the OEM should simultaneously consider both the forward and reverse flows for an optimal network design, instead of an independent and sequential modeling approach. In keeping with these motivations, and with the goal of implementing the remanufacturing strategy and transforming independent forward and reverse supply chains to CLSCs, we propose to investigate the following research questions: 1. How do the following transformation strategies leverage the CLSC?s overall cost performance? ? Extending the already existing forward channel to incorporate reverse channel activities. ? Designing an entire CLSC network. 2. How do the following network flow integration strategies influence the CLSC?s overall cost performance? ? Using distinct forward and reverse channel facilities to manage the corresponding flows. ? Using hybrid facilities to coordinate the flows. In researching the above questions, we address significant practical concerns in CLSC network design and provide cost measures for the above mentioned strategies. We also contribute to the current literature by investigating the optimal CLSC network design. More specifically, we propose three models and develop mathematical formulations and novel solution approaches that are based on decomposition techniques, heuristics, and meta-heuristic approaches to seek a solution that characterizes the configuration of the CLSC network, along with the coordinated forward and reverse flows.

Wire Bonder and Molding are the most costive equipments in the investment of IC packaging; and the packaging quality, cost and delivery are concerned most in the assembly processes. An inappropriate process scheduling may result in the wastes of resources and assembly bottleneck. Manager must allocate the resources appropriately to adapt the changeable products and production lines. We would introduce several heuristic search methods, especially the Tabu search. Tabu search is one of the most popular methods of heuristic search. We also use Tabu list to record several latest moves and avoid to the duplication of the paths or loops. It starts from an initial solution and keep moving the solution to the best neighborhood without stock by Tabu. The iterations would be repeated until the terminating condition is reached. At last of the report, an example will be designed to approach the best wire bonding and molding scheduling by Tabu search; and verify the output volume is more than those with FIFO in the same period of production time. Tabu search will be then confirmed to be effective for flexible flow shop.

<p> </p><p><strong> </strong></p><p><strong> </strong></p><p>Befintliga studier har påvisat att genetiska algoritmer presterar bättre om de ges en bra startpopulation. I denna rapport presenteras en lokal sökalgoritm för att skapa en population med fokus på ”vehicle routing”-problem. Algoritmen använder sig av heuristik i en blandning av simulated annealing och tabu search för att skapa individerna till populationen. Utvärderingar av algoritmen på ett praktiskt problem visar att den ger en bra start jämfört med en slumpmässig startpopulation, vilket är vanligt att använda. Resultaten av utvärderingen visar också att algoritmen ger bäst resultat vid mer komplexa problem, medan den har mindre effekt om problemet är enklare.</p><p> </p><p><strong>Nyckelord: </strong>Simulated annealing, Tabu search, Genetiska algoritmer , ”vehicle routing”-problem.</p><p> </p>