A New Heuristic Providing an Effective Initial Solution for a Simulated Annealing approach to Energy Resource Scheduling in Smart Grids

An intensive use of dispersed energy resources is expected for future power systems, including distributed generation, especially based on renewable sources, and electric vehicles. The system operation methods and tool must be adapted to the increased complexity, especially the optimal resource scheduling problem. Therefore, the use of metaheuristics is required to obtain good solutions in a reasonable amount of time. This paper proposes two new heuristics, called naive electric vehicles charge and discharge allocation and generation tournament based on cost, developed to obtain an initial solution to be used in the energy resource scheduling methodology based on simulated annealing previously developed by the authors. The case study considers two scenarios with 1000 and 2000 electric vehicles connected in a distribution network. The proposed heuristics are compared with a deterministic approach and presenting a very small error concerning the objective function with a low execution time for the scenario with 2000 vehicles.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

Crop rotation scheduling with adjacency constraints

In this article we propose a 0-1 optimization model to determine a crop rotation schedule for each plot in a cropping area. The rotations have the same duration in all the plots and the crops are selected to maximize plot occupation. The crops may have different production times and planting dates. The problem includes planting constraints for adjacent plots and also for sequences of crops in the rotations. Moreover, cultivating crops for green manuring and fallow periods are scheduled into each plot. As the model has, in general, a great number of constraints and variables, we propose a heuristics based on column generation. To evaluate the performance of the model and the method, computational experiments using real-world data were performed. The solutions obtained indicate that the method generates good results.

Product mix: The approach of throughput per day

Defining product mix is very important for organisations because it determines how productive resources are allocated among various operations. However, it is often defined subjectively. The methods commonly used for this definition are Integer Linear Programming and heuristics based in Theory of Constraints, which use maximum throughput as a performance measure. Although this measure provides maximum throughput to specific problem, it does not consider aspects of time, as days, utilised to make the throughput. Taking this into account, the aim of this paper is to present a throughput per day approach to define product mix, as well as to propose a constructive heuristic to help in this process. The results show that the proposed heuristic obtained satisfactory approximation when compared to the optimum values obtained by enumeration. © 2013 Copyright Taylor and Francis Group, LLC.

Contribuições para o problema de corte de estoque bidimensional na indústria moveleira

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Modelos Matemáticos e Métodos de Solução para Problemas de Dimensionamento de Lotes

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Asynchronous teams for joint lot-sizing and scheduling problem in flow shops

The integrated production scheduling and lot-sizing problem in a flow shop environment consists of establishing production lot sizes and allocating machines to process them within a planning horizon in a production line with machines arranged in series. The problem considers that demands must be met without backlogging, the capacity of the machines must be respected, and machine setups are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimise the setup, production and inventory costs. A mathematical model from the literature is presented, as well as procedures for obtaining feasible solutions. However, some of the procedures have difficulty in obtaining feasible solutions for large-sized problem instances. In addition, we address the problem using different versions of the Asynchronous Team (A-Team) approach. The procedures were compared with literature heuristics based on Mixed Integer Programming. The proposed A-Team procedures outperformed the literature heuristics, especially for large instances. The developed methodologies and the results obtained are presented.

Palette-colouring: a belief propagation approach

We consider a variation of the prototype combinatorial optimization problem known as graph colouring. Our optimization goal is to colour the vertices of a graph with a fixed number of colours, in a way to maximize the number of different colours present in the set of nearest neighbours of each given vertex. This problem, which we pictorially call palette-colouring, has been recently addressed as a basic example of a problem arising in the context of distributed data storage. Even though it has not been proved to be NP-complete, random search algorithms find the problem hard to solve. Heuristics based on a naive belief propagation algorithm are observed to work quite well in certain conditions. In this paper, we build upon the mentioned result, working out the correct belief propagation algorithm, which needs to take into account the many-body nature of the constraints present in this problem. This method improves the naive belief propagation approach at the cost of increased computational effort. We also investigate the emergence of a satisfiable-to-unsatisfiable 'phase transition' as a function of the vertex mean degree, for different ensembles of sparse random graphs in the large size ('thermodynamic') limit.

Tax morale and tax evasion: Social preferences and bounded rationality

We study a family of models of tax evasion, where a flat-rate tax finances only the provision of public goods, neglecting audits and wage differences. We focus on the comparison of two modeling approaches. The first is based on optimizing agents, who are endowed with social preferences, their utility being the sum of private consumption and moral utility. The second approach involves agents acting according to simple heuristics. We find that while we encounter the traditionally shaped Laffer-curve in the optimizing model, the heuristics models exhibit (linearly) increasing Laffercurves. This difference is related to a peculiar type of behavior emerging within the heuristics based approach: a number of agents lurk in a moral state of limbo, alternating between altruism and selfishness.

Manipulatív marketing: fogyasztói észlelések és reakciók

A marketing koncepciónak kezdetektől fogva a vevőorientáció az egyik kulcsfogalma. Tulajdonképpen annak a szemléletváltásnak köszönheti felemelkedését és más menedzsmentdiszciplínától való elhatárolását is, amellyel a vevői igényeket helyezte a vállalati gondolkodás középpontjába. Későbbiekben azonban a kutatók rájöttek arra, hogy maguk az igények az üzleti gyakorlat során nagymértékben kontrollálhatók, és az eladói oldal azóta is él ezekkel a lehetőségekkel. A kutatás arra volt kíváncsi, hogy a vállalatok manipulációs gyakorlata hogyan csapódik le a fogyasztókban, melyek azok a manipulációs eszközök, amelyeket észlelnek, és azokra milyen válaszreakciókat adnak. Azonosíthatók-e tipikus gondolkodási sémák, magatartási mintázatok, amelyek jól jellemzik egyes vevők viszonyát a vállalati manipulációval. A tanulmány feltáró interjúkra épít, amely segít megérteni a fogyasztókban végbe menő komplex mechanizmusokat. Az eredmények azt sugallják, hogy kétfajta folyamat játszódik le a vevői oldalon Egyrészt a fogyasztók idővel rutinszerű magatartásmintákat vesznek fel, amely során a manipulációs eszközök érvényesülése nem tudatos, és a vállalatoknak kedvező reakciókat vált ki. Másrészt, a fogyasztói társadalom is egyfajta érési folyamaton megy át, aminek hatására megtanulják a vállalatok gondolkodásmódját, és – bár a kognitív korlátok miatt azokat nem tudják teljes mértékben lekövetni – igyekeznek önvédő heurisztikákat beépíteni a követett magatartásukba. A kutatás alapján hipotetikusan öt vevőtípust azonosítottunk, akiket egymástól eltérő reakciók jellemeznek. Customer orientation has been the key concept of marketing since the beginning. As a matter of fact, the emergence of marketing and the conceptual distinction between marketing and the related management disciplines can be attributed to this new approach, which put customer needs in the focus of company attention. Later, researchers revealed that the needs themselves can be controlled to a greater extent and sellers have been taking advantage of it since then. The main focus of the research concentrated on the effects of manipulation practices of companies on consumers, which manipulation tools are recognised and how consumers react to them. Furthermore the research also investigated whether typical cognitive, emotional and behavioural patterns, which reflect the relationship between consumers and the manipulation practices of companies, can be identified. The study relies on explorative interviews, which help understand the complex mechanisms of consumer attitudes. The results indicates that the opposite process occur on the consumer side. On the one hand, consumers tend to follow behavioural routines after a while, which help manipulation tools work in an unconscious way that triggers reactions for the favour of companies. On the other hand, the generations of consumers are getting more and more mature and learning the companies’ mentality and, despite having cognitive limitations to identify all the tricks and deceptive attempts, they try to develop and follow defensive heuristics. Based on the data explored we identified five customer types and we described their diverse reactions to manipulation.

Cooperation mechanism for team-work based multi-agent system in dynamic scheduling through meta-heuristics

This paper describes a Multi-agent Scheduling System that assumes the existence of several Machines Agents (which are decision-making entities) distributed inside the Manufacturing System that interact and cooperate with other agents in order to obtain optimal or near-optimal global performances. Agents have to manage their internal behaviors and their relationships with other agents via cooperative negotiation in accordance with business policies defined by the user manager. Some Multi Agent Systems (MAS) organizational aspects are considered. An original Cooperation Mechanism for a Team-work based Architecture is proposed to address dynamic scheduling using Meta-Heuristics.

Rule-based quality heuristics formalization and identification

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

A review and evaluation on constructive heuristics to optimise product mix based on the Theory of Constraints

In this paper, we address the problem of defining the product mix in order to maximise a system's throughput. This problem is well known for being NP-Complete and therefore, most contributions to the topic focus on developing heuristics that are able to obtain good solutions for the problem in a short CPU time. In particular, constructive heuristics are available for the problem such as that by Fredendall and Lea, and by Aryanezhad and Komijan. We propose a new constructive heuristic based on the Theory of Constraints and the Knapsack Problem. The computational results indicate that the proposed heuristic yields better results than the existing heuristic.