For classical non-cyclic scheduling problems, we are given a set of operations,each of which has to be processed exactly once. The aim is to minimize or maximizea given objective function such as makespan or sum of all (weighted) completion times for a given set of constraints. The set of constraints is usually given by precedence constraints between the operations. In contrast to these problems, for cyclic scheduling problems we are given a set of operations, each of which has to be processed infinitely often. Such types of scheduling problems arise in different application areas like compiler design, manufacturing, digital signal processing, railway scheduling, timetabling, etc. The problem is to find a periodic schedule which minimizes a given objective function. There exist two objective functions which are important in this area of cyclic scheduling. The objective which is considered throughout this work is to minimize the time difference between two succeeding occurrences of one operation for a given set of constraints. This time difference is called cycle time. In this thesis, we develop a general framework to model and to describe cyclic scheduling problems with resource constraints. Furthermore, we extend the model to describe blocking constraints for cyclic scheduling problems. In order to solve the problem, we develop a local search approach.

As the older population grows larger there is a growing need to provide health care at home. This services are generally done without operational research. As more people will require home care there will be a need to increase the efficiency of the service while keeping the quality high. The purpose of this thesis is to investigate how we can use operation research in home care as well as define how we can model the quality and use those quality parameters in order to offer the best possible service. The model uses VRP with Time windows in order to schedule the routes and incorporates service requirements at the customers. A solution is obtained by first constructing an initial solution that fulfills the duration constraint. Then it uses a local search with a dynamic insertion heuristic to improve on the solution. Tabu search is used as a meta-heuristic to prevent the solution the get stuck in a local minima. The solver is used in order to optimize the quality parameters. The result obtained can be used to help home care providers to determine the level of quality they can supply with a limited budget / När den äldre befolkningen blir större växer behovet av att tillhandahålla vård i hemmet. Denna tjänst använder i allmänhet inte systemteori. Eftersom fler människor kommer att behöva hemtjänst kommer det att finnas behov av att öka effektiviteten samtidigt som kvaliteten hålls hög. Syftet med denna avhandling är att undersöka hur vi kan använda systemteori och optimering inom hemtjänst samt definiera hur vi kan modellera kvaliteten och använda dessa kvalitetsparametrar för att erbjuda bästa möjliga service. Modellen använder VRP med Time windows för att schemalägga rutterna och inkorporerar servicebehov hos kunderna. En lösning erhålles genom att först bygga en initial lösning. Sedan använder den en lokal sökning med en dynamisk heuristisk för att förbättra lösningen. Tabu search används som en meta-heuristik för att förhindra att lösningen fastnar i lokala minima. Algoritmen används för att optimera kvalitetsparametrarna. Resultatet kan användas för att hjälpa leverantörer av hemtjänst att bestämma vilken kvalitetsnivå de kan leverera med en begränsad budget

The vehicle routing problem (VRP) determines preferred vehicle routes to visit multiple customer locations from a depot location based on a defined objective function. The VRP is an NP-hard network optimization problem that is challenging to solve to optimality. Over the past 60 years, multitudes of heuristics and metaheuristics have been developed in order to minimize the computational burden of solving the VRP. In order to compare the performance of VRP heuristics, researchers have developed bench-marking datasets. These datasets, however, lack properties found in industry datasets. In this dissertation, we explore how properties of industry datasets influence VRP heuristics and objective functions. In Chapter 2, we quantify and compare features of bench-marking and industry datasets. In order to determine if these features influence heuristic performance, we conduct extensive computational runs on three heuristics, Tabu Search, Genetic Algorithm, and Clarke-Wright Savings Procedure, on standard and industry datasets. In Chapter 3, we derive worst-case analysis on how VRP objective functions and metrics relate to one another. These bounds depend on properties of customer locations. These bounds illustrate how customer locations can influence how different routes behave for different routing metrics. Finally, in Chapter 4, we improve two VRP heuristics, Clarke-Wright Saving Procedure and Hybrid Genetic Search Algorithm, by developing new enhancements to the algorithms. These enhancements rely on certain properties of the datasets in order to perform well. Thus, these heuristics perform better on specific VRP dataset types. / Doctor of Philosophy / The vehicle routing problem (VRP) creates vehicle routes that have the shortest travel distance. The routes determine how vehicles should visit multipl customer locations, to deliver or pickup goods, and return to a depot location. While explaining what the VRP entails is simple, the VRP is actually very difficult for even the most sophisticated algorithms on the best computers to solve. Over the past 60 years, many algorithms have been developed in order to more easily and quickly solve the VRP. In order to compare the performance of VRP algorithms, researchers have developed bench-marking datasets. However, these datasets lack properties of datasets found in industry. In this dissertation, we look to connect the disconnect between industry and bench-marking datasets by 1) comparing feature differences between these two types of datasets, 2) determining if differences in datasets imply differences in algorithm performance, 3) proving how problem differences influence VRP routes, and 4) enhancing existing VRP algorithms to perform better on specific VRP dataset types.

No description available.

No description available.

Discrete optimization problems are defined by a finite set of solutions together with an objective function value assigned to each solution. Local search algorithms provide useful tools for addressing a wide variety of intractable discrete optimization problems. Each such algorithm offers a distinct set of rules to intelligently exploit the solution space with the hope of finding an optimal/near optimal solution using a reasonable amount of computing time. This research studies and analyses randomly generated instances of 3-SATISFIABILITY to gain insights into the structure of the underlying solution space. Two random variables are defined and analyzed to assess the probability that a fixed solution will be assigned a particular objective function value in a randomly generated instance of 3-SATISFIABILITY. Then, a random vector is defined and analyzed to investigate how the solutions in the solution space are distributed over their objective function values. These results are then used to define a stopping criterion for local search algorithms applied to MAX 3-SATISFIABILITY. This research also analyses and compares the effectiveness of two local search algorithms, tabu search and random restart local search, on MAX 3-SATISFIABILITY. Computational results with tabu search and random restart local search on randomly generated instances of 3-SATISFIABILITY are reported. These results suggest that, given a limited computing budget, tabu search offers an effective alternative to random restart local search. On the other hand, these two algorithms yield similar results in terms of the best solution found. The computational results also suggest that for randomly generated instances of 3-SATISFIABILITY (of the same size), the globally optimal solution objective function values are typically concentrated over a narrow range. / Ph. D.

The computational power and algorithms needed to create a cognitive radio are quickly becoming available. There are many advantages to having a radio operated by cognitive engine, and so cognitive radios are likely to become very popular in the future. One of the main difficulties associated with the cognitive radio is ensuring the signal transmitted will follow all FCC rules. The work presented in this thesis provides a methodology to guarantee that all signals will be legal and valid. The first part to achieving this is a practical and easy to use software testing program based on the tabu search algorithm that tests the software off-line. The primary purpose of the software testing program is to find most of the errors, specially structural errors, while the radio is not in use so that it does not affect the performance of the system. The software testing program does not provide a complete assurance that no errors exist, so to supplement this deficit, a built-in self-test (BIST) is employed. The BIST is designed with two parts, one that is embedded into the cognitive engine and one that is placed into the radio's API. These two systems ensure that all signals transmitted by the cognitive radio will follow FCC rules while consuming a minimal amount of computational power. The software testing approach based on the tabu search is shown to be a viable method to test software with improved results over previous methods. Also, the software BIST demonstrated its ability to find errors in the signal production and is dem to only require an insignificant amount of computational power. Overall, the methods presented in this paper provide a complete and practical approach to assure the FCC of the legality of all signals in order to obtain a license for the product. / Master of Science

No / This paper presents a case study on the use of multi-agents for integrated dynamic scheduling of steel milling and casting. Steel production is an extremely complex problem requiring the consideration of several different constraints and objectives of a range of processes in a dynamic environment. Most research in steel production scheduling considers static scheduling of processes in isolation. In contrast to earlier approaches, the multi-agent architecture proposed consists of a set of heterogeneous agents which integrate and optimize a range of scheduling objectives related to different processes of steel production, and can adapt to changes in the environment while still achieving overall system goals. Each agent embodies its own scheduling model and realizes its local predictive-reactive schedule taking into account local objectives, real-time information and information received from other agents. Agents cooperate in order to find a globally good schedule, which is able to effectively react to real-time disruptions, and to optimize the original production goals whilst minimising disruption carried by unexpected events occurring in real-time. The inter-agent cooperation is based on the Contract Net Protocol with commitment

This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree. / Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.

Made available in DSpace on 2015-03-05T13:57:00Z (GMT). No. of bitstreams: 0 Previous issue date: 27 / Nenhuma / Problemas de pessoal, produtividade e contenção de custos afetam todas as áreas de negócio, inclusive os provedores de cuidados de saúde. Porém, nesta área o controle dos custos não pode comprometer a qualidade do atendimento. É neste contexto que uma ferramenta computacional para a elaboração das escalas de trabalho de pessoal de enfermagem torna-se importante. Esta é uma tarefa realizada manualmente na maioria dos hospitais e clínicas, consumindo muito tempo e nem sempre atendendo completamente a legislação e normas vigentes. No Brasil há falta de ferramentas computacionais para a elaboração destas escalas, ou mesmo para a avaliação das escalas desenvolvidas. O objetivo desta pesquisa é encontrar uma solução, computacionalmente viável, para a geração de escalas de trabalho mensais para os técnicos de enfermagem, de acordo com as regras operacionais dos hospitais e as restrições da legislação. Deseja-se ainda obter maior nível de satisfação dos funcionários atendendo preferências de dias de folga e distribui / Problems of personnel, productivity and cost restriction affect all areas of a business, including the health care providers. However, in this area, cost control cannot endanger the quality of service. In this context, a software for creating the schedule of nursing personnel becomes important. This is a hand-made task in the majority of hospitals and clinics. It is time consuming and does not always comply to the legislation and the valid rules. In Brazil, there is a lack of computer tools for the creation of these schedules or even for the evaluation of the ones already developed. This research aims at finding a technologically feasible solution for the generation of monthly schedules for the nursing technicians, according to the operational rules of hospitals and legislation restrictions. It also aims at giving the employees a higher level of satisfaction, concerning their day off preferences and equitable distribution of duties on Saturdays, Sundays and holidays. The proposal is to apply a Tabu Search me