A hybrid intelligent system for distributed dynamic scheduling

This chapter addresses the resolution of dynamic scheduling by means of meta-heuristic and multi-agent systems. Scheduling is an important aspect of automation in manufacturing systems. Several contributions have been proposed, but the problem is far from being solved satisfactorily, especially if scheduling concerns real world applications. The proposed multi-agent scheduling system assumes the existence of several resource agents (which are decision-making entities based on meta-heuristics) distributed inside the manufacturing system that interact with other agents in order to obtain optimal or near-optimal global performances.

Day-ahead resource scheduling in smart grids considering Vehicle-to-Grid and network constraints

Energy resource scheduling becomes increasingly important, as the use of distributed resources is intensified and massive gridable vehicle use is envisaged. The present paper proposes a methodology for dayahead energy resource scheduling for smart grids considering the intensive use of distributed generation and of gridable vehicles, usually referred as Vehicle- o-Grid (V2G). This method considers that the energy resources are managed by a Virtual Power Player (VPP) which established contracts with V2G owners. It takes into account these contracts, the user´s requirements subjected to the VPP, and several discharge price steps. Full AC power flow calculation included in the model allows taking into account network constraints. The influence of the successive day requirements on the day-ahead optimal solution is discussed and considered in the proposed model. A case study with a 33 bus distribution network and V2G is used to illustrate the good performance of the proposed method.

MASDScheGATS: a prototype system for dynamic scheduling

A manufacturing system has a natural dynamic nature observed through several kinds of random occurrences and perturbations on working conditions and requirements over time. For this kind of environment it is important the ability to efficient and effectively adapt, on a continuous basis, existing schedules according to the referred disturbances, keeping performance levels. The application of Meta-Heuristics and Multi-Agent Systems to the resolution of this class of real world scheduling problems seems really promising. This paper presents a prototype for MASDScheGATS (Multi-Agent System for Distributed Manufacturing Scheduling with Genetic Algorithms and Tabu Search).

Distribution network short term scheduling in Smart Grid context

The large increase of Distributed Generation (DG) in Power Systems (PS) and specially in distribution networks makes the management of distribution generation resources an increasingly important issue. Beyond DG, other resources such as storage systems and demand response must be managed in order to obtain more efficient and “green” operation of PS. More players, such as aggregators or Virtual Power Players (VPP), that operate these kinds of resources will be appearing. This paper proposes a new methodology to solve the distribution network short term scheduling problem in the Smart Grid context. This methodology is based on a Genetic Algorithms (GA) approach for energy resource scheduling optimization and on PSCAD software to obtain realistic results for power system simulation. The paper includes a case study with 99 distributed generators, 208 loads and 27 storage units. The GA results for the determination of the economic dispatch considering the generation forecast, storage management and load curtailment in each period (one hour) are compared with the ones obtained with a Mixed Integer Non-Linear Programming (MINLP) approach.

Optimization techniques for power distribution planning with uncertainties: a comparative study

Important research effort has been devoted to the topic of optimal planning of distribution systems. The non linear nature of the system, the need to consider a large number of scenarios and the increasing necessity to deal with uncertainties make optimal planning in distribution systems a difficult task. Heuristic techniques approaches have been proposed to deal with these issues, overcoming some of the inherent difficulties of classic methodologies. This paper considers several methodologies used to address planning problems of electrical power distribution networks, namely mixedinteger linear programming (MILP), ant colony algorithms (AC), genetic algorithms (GA), tabu search (TS), branch exchange (BE), simulated annealing (SA) and the Bender´s decomposition deterministic non-linear optimization technique (BD). Adequacy of theses techniques to deal with uncertainties is discussed. The behaviour of each optimization technique is compared from the point of view of the obtained solution and of the methodology performance. The paper presents results of the application of these optimization techniques to a real case of a 10-kV electrical distribution system with 201 nodes that feeds an urban area.

Technical and economic resources management in smart grids using heuristic optimization methods

Intensive use of Distributed Generation (DG) represents a change in the paradigm of power systems operation making small-scale energy generation and storage decision making relevant for the whole system. This paradigm led to the concept of smart grid for which an efficient management, both in technical and economic terms, should be assured. This paper presents a new approach to solve the economic dispatch in smart grids. The proposed methodology for resource management involves two stages. The first one considers fuzzy set theory to define the natural resources range forecast as well as the load forecast. The second stage uses heuristic optimization to determine the economic dispatch considering the generation forecast, storage management and demand response

Case-based reasoning for meta-heuristics self-parameterization in a multi-agent scheduling system

A novel agent-based approach to Meta-Heuristics self-configuration is proposed in this work. Meta-heuristics are examples of algorithms where parameters need to be set up as efficient as possible in order to unsure its performance. This paper presents a learning module for self-parameterization of Meta-heuristics (MHs) in a Multi-Agent System (MAS) for resolution of scheduling problems. The learning is based on Case-based Reasoning (CBR) and two different integration approaches are proposed. A computational study is made for comparing the two CBR integration perspectives. In the end, some conclusions are reached and future work outlined.

Swarm intelligence for scheduling: a review

Swarm Intelligence generally refers to a problem-solving ability that emerges from the interaction of simple information-processing units. The concept of Swarm suggests multiplicity, distribution, stochasticity, randomness, and messiness. The concept of Intelligence suggests that problem-solving approach is successful considering learning, creativity, cognition capabilities. This paper introduces some of the theoretical foundations, the biological motivation and fundamental aspects of swarm intelligence based optimization techniques such Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO) and Artificial Bees Colony (ABC) algorithms for scheduling optimization.

Meta-heuristics tunning using CBR for dynamic scheduling

This paper addresses the problem of Biological Inspired Optimization Techniques (BIT) parameterization, considering the importance of this issue in the design of BIT especially when considering real world situations, subject to external perturbations. A learning module with the objective to permit a Multi-Agent Scheduling System to automatically select a Meta-heuristic and its parameterization to use in the optimization process is proposed. For the learning process, Casebased Reasoning was used, allowing the system to learn from experience, in the resolution of similar problems. Analyzing the obtained results we conclude about the advantages of its use.

Análise e melhoria de processo de pintura e vulcanização na Continental

A indústria automóvel é um dos setores mais exigentes do mercado global, por este motivo empresas como a Continental Mabor S.A, líderes de mercado, necessitam estar na linha da frente no que toca a programas de melhoria contínua e de uma gestão orientada para um crescimento rentável e sustentado. Nesta perspetiva, este estudo de dissertação tem como objetivo encontrar uma solução para a gestão de stock e FiFo (First in First out) de pneus em verde na supracitada empresa, situada em Lousado, Vila Nova de Famalicão. Este projeto de dissertação iniciou-se com uma análise e diagnóstico do processo produtivo do pneu, entre a Construção e a Vulcanização. Nesta análise, foi possível identificar vários problemas, sendo o mais crítico associado à logística interna de transporte do pneu “em curso”, de fabrico entre as fases do mesmo, Construção e Vulcanização. Devido a condicionantes estruturais e de organização, a logística interna de transporte entre estes dois sectores enfrenta estrangulamentos nos fluxos, a falta de espaço para acomodar o material em curso, problemas organizacionais de controlo e monitorização do processo produtivo, dificuldades de regulação do fluxo e localização dos carros de transporte dos pneus em verde. Face aos problemas detetados ao longo do estudo, foram analisadas várias soluções para a resolução ou minimização dos mesmos. Entre as soluções propostas salientam-se: o alargamento do sistema de transporte por tapetes rolantes GTC (Green Tire Conveying) a todos os módulos de construção. Esta solução diminui o fluxo de carros para a área da construção, descongestionando a zona próxima do sistema de carregamento automático GTAL (Green Tire Automatic Loading) na vulcanização. A implementação dum sistema Wi-Fi RFID, que permite identificar e localizar artigos em curso utilizando etiquetas inteligentes numa rede wireless, conseguindo melhorar a programação de produção e o respetivo sequenciamento. Sabendo também que a Continental se encontra numa fase de expansão, designada Projeto Route 17/20, as soluções propostas tomaram em consideração essa nova realidade futura. Assim, foram estudados e propostos novos layouts para esse atual processo. Nestes novos layouts, procurou-se uma reorganização dos processos de fabrico, bem como um redimensionamento dos espaços de parqueamento de carros de pneus verdes adequado aos volumes produtivos. De igual forma, adequou-se os espaços físicos à possível implementação de um sistema de FiFo de pneus em verde na planta fabril, quando concluída a expansão. Este trabalho de dissertação apresenta como vantagens diretas da sua implementação: gerar a menor perturbação no atual método de trabalho seguido na empresa; previsivelmente aumentar a eficiência do processo produtivo; potenciar o crescimento tecnológico programado pela empresa; e oferecer uma boa relação custo/benefício no investimento necessário. Como apreciação final, pode-se concluir que este estudo foi finalizado com sucesso, visto que as soluções propostas foram apreciadas positivamente pela Administração da Continental Mabor S.A. e estão correntemente a ser avaliadas pelo grupo.

Balanceamento de linhas de produção usando algoritmos genéticos

Aquando da definição de um layout por fluxo de produto, ou linha de produção, é necessário proceder-se à melhor selecção de combinações de tarefas a serem executadas em cada estação / posto de trabalho para que o trabalho seja executado numa sequência exequível e sejam necessárias quantidades de tempo aproximadamente iguais em cada estação / posto de trabalho. Este processo é chamado de balanceamento da linha de produção. Verifica-se que as estações de trabalho e equipamentos podem ser combinados de muitas maneiras diferentes; daí que a necessidade de efectuar o balanceamento das linhas de produção implique a distribuição de actividades sequenciais por postos de trabalho de modo a permitir uma elevada utilização de trabalho e de equipamentos e a minimizar o tempo de vazio. Os problemas de balanceamento de linhas são tipicamente problemas complexos de tratar, devido ao elevado número de combinações possíveis. Entre os métodos utilizados para resolver estes problemas encontram-se métodos de tentativa e erro, métodos heurísticos, métodos computacionais de avaliação de diferentes opções até se encontrar uma boa solução e métodos de optimização. O objectivo deste trabalho passou pelo desenvolvimento de uma ferramenta computacional para efectuar o balanceamento de linhas de produção recorrendo a algoritmos genéticos. Foi desenvolvida uma aplicação que implementa dois algoritmos genéticos, um primeiro que obtém soluções para o problema e um segundo que optimiza essas soluções, associada a uma interface gráfica em C# que permite a inserção do problema e a visualização de resultados. Obtiveram-se resultados exequíveis demonstrando vantagens em relação aos métodos heurísticos, pois é possível obter-se mais do que uma solução. Além disso, para problemas complexos torna-se mais prático o uso da aplicação desenvolvida. No entanto, esta aplicação permite no máximo seis precedências por cada operação e resultados com o máximo de nove estações de trabalho.

Stochastic short-term maintenance scheduling of GENCOs in an oligopolistic electricity market

In the proposed model, the independent system operator (ISO) provides the opportunity for maintenance outage rescheduling of generating units before each short-term (ST) time interval. Long-term (LT) scheduling for 1 or 2 years in advance is essential for the ISO and the generation companies (GENCOs) to decide their LT strategies; however, it is not possible to be exactly followed and requires slight adjustments. The Cournot-Nash equilibrium is used to characterize the decision-making procedure of an individual GENCO for ST intervals considering the effective coordination with LT plans. Random inputs, such as parameters of the demand function of loads, hourly demand during the following ST time interval and the expected generation pattern of the rivals, are included as scenarios in the stochastic mixed integer program defined to model the payoff-maximizing objective of a GENCO. Scenario reduction algorithms are used to deal with the computational burden. Two reliability test systems were chosen to illustrate the effectiveness of the proposed model for the ST decision-making process for future planned outages from the point of view of a GENCO.

Non pre-emptive scheduling of messages on SMTV token-passing networks

Fieldbus communication networks aim to interconnect sensors, actuators and controllers within distributed computer-controlled systems. Therefore, they constitute the foundation upon which real-time applications are to be implemented. A specific class of fieldbus communication networks is based on a simplified version of token-passing protocols, where each station may transfer, at most, a single message per token visit (SMTV). In this paper, we establish an analogy between non-preemptive task scheduling in single processors and the scheduling of messages on SMTV token-passing networks. Moreover, we clearly show that concepts such as blocking and interference in non-preemptive task scheduling have their counterparts in the scheduling of messages on SMTV token-passing networks. Based on this task/message scheduling analogy, we provide pre-run-time schedulability conditions for supporting real-time messages with SMTV token-passing networks. We provide both utilisation-based and response time tests to perform the pre-run-time schedulability analysis of real-time messages on SMTV token-passing networks, considering RM/DM (rate monotonic/deadline monotonic) and EDF (earliest deadline first) priority assignment schemes

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound

Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound. A clustered variant of the algorithm, for systems made of multicore chips, eliminates (costly) off-chip task migrations, by dividing processors into disjoint clusters, formed by cores on the same chip (with the cluster size being a parameter). Clusters are independently scheduled (each, using non-clustered NPS-F). The utilisation bound is only moderately affected. We also formulate an important extension (applicable to both clustered and non-clustered NPS-F) which optimises the supply of processing time to executing tasks and makes it more granular. This reduces processing capacity requirements for schedulability without increasing preemptions.

Online intra-task device scheduling for hard real-time systems

A large part of power dissipation in a system is generated by I/O devices. Increasingly these devices provide power saving mechanisms, inter alia to enhance battery life. While I/O device scheduling has been studied in the past for realtime systems, the use of energy resources by these scheduling algorithms may be improved. These approaches are crafted considering a very large overhead of device transitions. Technology enhancements have allowed the hardware vendors to reduce the device transition overhead and energy consumption. We propose an intra-task device scheduling algorithm for real time systems that allows to shut-down devices while ensuring system schedulability. Our results show an energy gain of up to 90% when compared to the techniques proposed in the state-of-the-art.