O desafio de se escalar pessoas em turnos flexíveis em uma empresa consiste na elaboração de um cronograma para alocação de recursos necessários para executar uma atividade em um determinado período de tempo. Este trabalho tem o objetivo de propor uma otimização na programação de horários de turnos das faxineiras de um supermercado, através de um modelo matemático baseado no método de Programação Linear Inteira Mista, atendendo às restrições do Departamento de Recursos Humanos e às leis trabalhistas (CLT). O modelo foi desenvolvido no Lingo em interface com o MS Excel 2013. Os dados de entrada foram iterados no Lingo até que uma solução ótima fosse encontrada. A solução obtida pelo modelo apresentou um resultado satisfatório para o supermercado, pois minimizou a variação de horas trabalhadas durante a semana e distribuiu as funcionárias de maneira uniforme nas escalas de horário.
This work deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times, with the objective of minimizing the makespan. It is proposed an Adaptive Large Neighborhood Search (ALNS) metaheuristic using Learning Automata (LA) to adapt the probabilities of using removal and insertion heuristics and methods. A computable function in the LA updates the probability vector for selecting the actions, corresponding to six removal and six insertion methods. We also propose a new insertion method based on Hungarian algorithm, which is applied to solve subproblems optimally. Computational experiments are performed to verify the performance of the proposed method. A set of instances available in the literature with problems up to 150 jobs and 10 machines is employed in the experiments. The proposed LA-ALNS is compared against three other algorithms from the literature. The results suggest that our algorithm has better performance in most of cases (88%) under the defined conditions of experiments. Statistical tests also suggest that LA-ALNS is better than the other algorithms from the literature. The proposed method is able to automatically choose the most suitable heuristics for the instance of the problem, through adaptation and learning in the Learning Automata.
A fuzzy inference framework based on fuzzy relations is developed, adapted and applied to temperature and humidity measurements from a specific coffee crop site in Brazil. This framework consists of fuzzy relations over possibility distributions, resulting in a model analogous to a Bayesian inference process. The application of this fuzzy model to a data set of experimental measurements and its correspondent forecasts of temperature and humidity resulted in a set of revised forecasts, that incorporate information from a historical record of the problem. Each set of revised forecasts was compared with the correspondent set of experimental data using two different statistical measures, MAPE (Mean Absolute Percentage Error) and Willmott's D. This comparison showed that the sets of forecasts revised by the fuzzy model exhibited better results than the original forecasts on both statistical measures for more than two thirds of the evaluated cases.
Este trabalho objetiva descrever e apresentar algumas das variáveis determinantes para a formação dos preços praticados no mercado imobiliário de compra, venda e aluguéis residenciais da cidade de João Monlevade-MG. Trata-se de uma pesquisa baseada em dados reais do ano de 2016 obtidos por meio de pesquisas em websites e visitas de campo em locais públicos e privados. Os dados da oferta e da demanda foram coletados e organizados em planilhas eletrônicas, a partir de critérios: (i) estruturais, por tipo de imóvel (apartamento ou casa) e quantidade de cômodos; (ii) geográficos, através da divisão por bairros e suas vias de acesso; e (iii) geradores de informação, pelas diferentes fontes de coleta; resultando em uma análise estatística descritiva do mercado. Para justificar os resultados obtidos na análise estatística foram levantados dados referentes à infraestrutura de saneamento básico e ao acesso a serviços de utilidade pública (saúde, educação, transporte, comércio e segurança), que poderiam influenciar na decisão de escolha dos consumidores. Fatores como a violência e a localização dos bairros em relação ao centro comercial foram elementos de maior impacto na formação dos preços.
The incomplete hub location problem with and without hop-constraints is modeled using a Leontief substitution system approach. The Leontief formalism provides a set of important theoretical properties and delivers formulations with tight linear bounds that can explicitly incorporate hop constraints for each origin-destination pair of demands. Furthermore, the proposed formulations are amenable to a Benders decomposition technique which can solve large scale test instances. The performance of the devised algorithm is primarily due to a new general scheme for separating Benders feasibility cuts. The novel cuts render a stabilizing effect that is directly responsible for the solution of instances up to 80 nodes.
Educational timetabling problems require the assignment of times and resources to events, while sets of required and desirable constraints must be considered. The XHSTT format was adopted in this work because it models the main features of educational timetabling and it is the most used format in recent studies in the field. This work presents new cuts and reformulations for the existing integer programming model for XHSTT. The proposed cuts improved hugely the linear relaxation of the formulation, leading to an average gap reduction of 32%. Applied to XHSTT-2014 instance set, the alternative formulation provided four new best known lower bounds and, used in a matheuristic framework, improved eleven best known solutions. The computational experiments also show that the resulting integer programming models from the proposed formulation are more effectively solved for most of the instances.
Design of Hub-and-spoke networks is an extension of classical facility location problem and it is very important due to its applications in cargo, passenger and telecommunication systems. The problem consists in determining the number and location of the hubs, besides define the allocation of non-hub nodes to the installed hubs, aiming to minimize the total costs. This problem is known to be NP-hard and it has been tackled by heuristic based approaches. In this paper it is proposed an efficient multi-start heuristic composed by a simple construction phase, a perturbation mechanism and an adaptive local search. Computational experiments using standard benchmark problems shows that the proposed approach is competitive when compared with the best heuristics in the literature.
This paper portrays the Braziliam truck industry from the perspective of the products (trucks) offered by the main truck assembler of this market. For this purpose it is used the concept of product ontology, where all products of this industry are grouped in a single hierarchical structure, where it is outlined their common aspects, as well as, their singularities. For attain this goal it was used the archival method, whereas it was identified all product lines of trucks offered for the six main manufactures, where together are responsible for more than 95% of sales in this market. The use of the ontology concept to map all trucks offered in this industry, allowed to present a comprehensive and deep view, where it was possible to identify the dynamic of this industry, as well as, the strategic positioning of each assembler, according to this product portfolio.
This study focused on public health in the State of Minas Gerais, related to the attendance of medical specialties demands. The authors proposed a mathematical location and allocation optimization model of specialized medical centers (hospitals of medium complexity) in Minas Gerais. The model was adapted from the classic Maximal Covering Location Problem proposed in the Operational Research. The results were characterized as an analysis tool and decision support for the multidisciplinary research team, formed by engineers, physicians and government. From the results were approached also, analyzes considering the current scenario of economic crisis for resources optimization in the public health planning.
Neste problema de roteamento de veículos considera-se um conjunto de recursos que serão compartilhados por um conjunto de canteiros de obras. A distribuição destes recursos é feita através de um conjunto de veículos capacitados. Para cada veículo há um depósito distinto de onde deverá sair e para onde deverá retornar ao final da rota. Cada canteiro pode ser visitado mais deuma vez. Os recursos podem ser discretizados em itens e assim tanto coleta e entrega podem ser divisíveis. O objetivo do problema é atender as requisições com custo mínimo. Duas heurísticas construtivas foram propostas para solução do problema as quais foram testadas em instâncias reais e em instâncias de testes. Resultados mostram que as heurísticas fornecem resultados melhores queos obtidos atualmente pela empresa, dentro de um tempo computacional factível com o horizonte de tomada de decisão operacional.
This work deals with the unrelated parallel machine scheduling problem with sequencedependent setup times, with the objective of minimizing the makespan. This problem appears in different industries as textile and chemicals, and its resolution is challenging due to its complexity. It was proposed for its resolution an algorithm based on the Adaptive Large Neighborhood Search method with learning automata to adapt the probabilities of using removal and insertion methods. One of the main insertion methods is inspired on the Hungarian algorithm, that is able to solve subproblems optimally. In the computational experiments were used a subset of instances of literature. The results were compared with two other algorithms of literature. For the experimental context the results suggest that the proposed algorithm found the best results in 93% of cases. This can indicate the efficiency of the proposed algorithm to the established conditions.
There are several factors related to Sports Competitions Problems, as economic interesting, competitiveness of teams, besides the sponsor gains. This work proposes a metaheuristic based on Evolution Strategy to deal with this class of problem. The objective is to minimize the average time spent for teams during competition. The Brazilian Football Championship was studied because of its properties and addition to the national interest to that issue. Some operators were defined to respect constraints imposed by the Brazilian Football Confederation. For the experimental context, the results suggest the proposed algorithm has a good performance. When it was compared with official tables from 2014, 2015 and 2016, the method found a smaller total travel time for teams.
Scheduling is more present in our daily lives than we can perceive and one of its main aspects is the employees’ scheduling, which is this paper object of study. The objective is to develop an automated method for the employees scheduling of a retail store that meets the labor laws, the preferences of employees and the internal rules of the organization. the study is justified by the difficulty and delay in the manual construction of these schedules as they are currently made in the company under study. In addition, a balanced roster ensures greater worker satisfaction, which affects positively on their productivity, and helps to reduce costs in the organization, which no more works with missing or overstaffed. The technique used was the metaheuristic simulated annealing and the results obtained were faced with an exact method previously used in solving the problem.
This paper introduces a cooperative parallel heuristic for the uncapacitated single allocation hub location problem. The proposed heuristic consists in combining multiple parallel ILS-RVND local search and Path-Relinking, cooperating through asynchronously exchanging solutions in a shared pool. This method as devised to tackle large scale instances up to 3038 nodes. Generally, papers in the literature solve problems up to 400 nodes. The combination of efficient methods of search allowed the proposed heuristic to explore efficiently the space of search, and outperformed four well known heuristics of the literature for the select instances.
The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances.
The fast globalization in which we operate has led companies to seek and to rethink the various techniques available in the market to remain competitive. Hence, in this scenario classic problems such as location and vehicle routing is constantly increasing its relevance when it comes to quality services. In this context, this article seeks to identify the best place to install a warehouse and what are the best routes. the is company located in Leeds, UK, which operates in the ingredients market “clean label” and than compare with the current model used by the company. thus, this paper seeks to merge classical concepts of production engineering with the expertise of a food company to create high value content for the studied company. Therefore, through the sweep algorithm were generated 39 routes totaling 18,297 km, the results also showed that with the new location suggested the company would obtain a 5% reduction in costs per year with distribution of its products.
A new approach for the problem of optimal task scheduling in flexible manufacturing systems is proposed in this work, as a combination of metaheuristic optimization techniques with the supervisory control theory of discrete-event systems. A specific encoding, the word-shuffling encoding, which avoids the generation of a large number of infeasible sequences, is employed. A metaheuristic method based on a Variable Neighborhood Search is then built using such an encoding. The optimization algorithm performs the search for the optimal schedules, while the supervisory control has the role of codifying all the problem constraints, allowing an efficient feasibility correction procedure, and avoiding schedules that are sensitive to uncertainties in the execution times associated with the plant operation. In this way, the proposed methodology achieves a system performance which is typical from model-predictive scheduling, combined with the robustness which is required from a structural control.
The Multi-Depot Vehicle Routing Problem (MDVRP) is an important variant of the classical Vehicle Routing Problem (VRP), where the customers can be served from a number of depots. This paper introduces a cooperative coevolutionary algorithm to minimize the total route cost of the MDVRP. Coevolutionary algorithms are inspired by the simultaneous evolution process involving two or more species. In this approach, the problem is decomposed into smaller subproblems and individuals from different populations are combined to create a complete solution to the original problem. This paper presents a problem decomposition approach for the MDVRP in which each subproblem becomes a single depot VRP and evolves independently in its domain space. Customers are distributed among the depots based on their distance from the depots and their distance from their closest neighbor. A population is associated with each depot where the individuals represent partial solutions to the problem, that is, sets of routes over customers assigned to the corresponding depot. The fitness of a partial solution depends on its ability to cooperate with partial solutions from other populations to form a complete solution to the MDVRP. As the problem is decomposed and each part evolves separately, this approach is strongly suitable to parallel environments. Therefore, a parallel evolution strategy environment with a variable length genotype coupled with local search operators is proposed. A large number of experiments have been conducted to assess the performance of this approach. The results suggest that the proposed coevolutionary algorithm in a parallel environment is able to produce high-quality solutions to the MDVRP in low computational time.
This work presents a local search approach to the High School Timetabling Problem. The addressed timetabling model is the one stated in the Third International Timetabling Competition (ITC 2011), which considered many instances from educational institutions around the world and attracted seventeen competitors. Our team, named GOAL (Group of Optimization and Algorithms), developed a solver built upon the Kingston High School Timetabling Engine. Several neighborhood structures were developed and used in a hybrid metaheuristic based on Simulated Annealing and Iterated Local Search. The developed algorithm was the winner of the competition and produced the best known solutions for almost all instances.
The application of the Late Acceptance Hill-Climbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.