Estudo e análise do sequenciamento de tarefas de produção: job shop scheduling

Esta dissertação apresenta um estudo sobre os problemas de sequenciamento de tarefas de produção do tipo job shop scheduling. Os problemas de sequenciamento de tarefas de produção pretendem encontrar a melhor sequência para o processamento de uma lista de tarefas, o instante de início e término de cada tarefa e a afetação de máquinas para as tarefas. Entre estes, encontram-se os problemas com máquinas paralelas, os problemas job shop e flow shop. As medidas de desempenho mais comuns são o makespan (instante de término da execução de todas as tarefas), o tempo de fluxo total, a soma dos atrasos (tardiness), o atraso máximo, o número de tarefas que são completadas após a data limite, entre outros. Num problema do tipo job shop, as tarefas (jobs) consistem num conjunto de operações que têm de ser executadas numa máquina pré-determinada, obedecendo a um determinado sequenciamento com tempos pré-definidos. Estes ambientes permitem diferentes cenários de sequenciamento das tarefas. Normalmente, não são permitidas interrupções no processamento das tarefas (preemption) e pode ainda ser necessário considerar tempos de preparação dependentes da sequência (sequence dependent setup times) ou atribuir pesos (prioridades) diferentes em função da importância da tarefa ou do cliente. Pretende-se o estudo dos modelos matemáticos existentes para várias variantes dos problemas de sequenciamento de tarefas do tipo job shop e a comparação dos resultados das diversas medidas de desempenho da produção. Este trabalho contribui para demonstrar a importância que um bom sequenciamento da produção pode ter na sua eficiência e consequente impacto financeiro.

Scalable Intelligence for Scheduling Systems

A personalização é um aspeto chave de uma interação homem-computador efetiva. Numa era em que existe uma abundância de informação e tantas pessoas a interagir com ela, de muitas maneiras, a capacidade de se ajustar aos seus utilizadores é crucial para qualquer sistema moderno. A criação de sistemas adaptáveis é um domínio bastante complexo que necessita de métodos muito específicos para ter sucesso. No entanto, nos dias de hoje ainda não existe um modelo ou arquitetura padrão para usar nos sistemas adaptativos modernos. A principal motivação desta tese é a proposta de uma arquitetura para modelação do utilizador que seja capaz de incorporar diferentes módulos necessários para criar um sistema com inteligência escalável com técnicas de modelação. Os módulos cooperam de forma a analisar os utilizadores e caracterizar o seu comportamento, usando essa informação para fornecer uma experiência de sistema customizada que irá aumentar não só a usabilidade do sistema mas também a produtividade e conhecimento do utilizador. A arquitetura proposta é constituída por três componentes: uma unidade de informação do utilizador, uma estrutura matemática capaz de classificar os utilizadores e a técnica a usar quando se adapta o conteúdo. A unidade de informação do utilizador é responsável por conhecer os vários tipos de indivíduos que podem usar o sistema, por capturar cada detalhe de interações relevantes entre si e os seus utilizadores e também contém a base de dados que guarda essa informação. A estrutura matemática é o classificador de utilizadores, e tem como tarefa a sua análise e classificação num de três perfis: iniciado, intermédio ou avançado. Tanto as redes de Bayes como as neuronais são utilizadas, e uma explicação de como as preparar e treinar para lidar com a informação do utilizador é apresentada. Com o perfil do utilizador definido torna-se necessária uma técnica para adaptar o conteúdo do sistema. Nesta proposta, uma abordagem de iniciativa mista é apresentada tendo como base a liberdade de tanto o utilizador como o sistema controlarem a comunicação entre si. A arquitetura proposta foi desenvolvida como parte integrante do projeto ADSyS - um sistema de escalonamento dinâmico - utilizado para resolver problemas de escalonamento sujeitos a eventos dinâmicos. Possui uma complexidade elevada mesmo para utilizadores frequentes, daí a necessidade de adaptar o seu conteúdo de forma a aumentar a sua usabilidade. Com o objetivo de avaliar as contribuições deste trabalho, um estudo computacional acerca do reconhecimento dos utilizadores foi desenvolvido, tendo por base duas sessões de avaliação de usabilidade com grupos de utilizadores distintos. Foi possível concluir acerca dos benefícios na utilização de técnicas de modelação do utilizador com a arquitetura proposta.

Real-time Task-Splitting scheduling algorithms framework

Nos dias de hoje, os sistemas de tempo real crescem em importância e complexidade. Mediante a passagem do ambiente uniprocessador para multiprocessador, o trabalho realizado no primeiro não é completamente aplicável no segundo, dado que o nível de complexidade difere, principalmente devido à existência de múltiplos processadores no sistema. Cedo percebeu-se, que a complexidade do problema não cresce linearmente com a adição destes. Na verdade, esta complexidade apresenta-se como uma barreira ao avanço científico nesta área que, para já, se mantém desconhecida, e isto testemunha-se, essencialmente no caso de escalonamento de tarefas. A passagem para este novo ambiente, quer se trate de sistemas de tempo real ou não, promete gerar a oportunidade de realizar trabalho que no primeiro caso nunca seria possível, criando assim, novas garantias de desempenho, menos gastos monetários e menores consumos de energia. Este último fator, apresentou-se desde cedo, como, talvez, a maior barreira de desenvolvimento de novos processadores na área uniprocessador, dado que, à medida que novos eram lançados para o mercado, ao mesmo tempo que ofereciam maior performance, foram levando ao conhecimento de um limite de geração de calor que obrigou ao surgimento da área multiprocessador. No futuro, espera-se que o número de processadores num determinado chip venha a aumentar, e como é óbvio, novas técnicas de exploração das suas inerentes vantagens têm de ser desenvolvidas, e a área relacionada com os algoritmos de escalonamento não é exceção. Ao longo dos anos, diferentes categorias de algoritmos multiprocessador para dar resposta a este problema têm vindo a ser desenvolvidos, destacando-se principalmente estes: globais, particionados e semi-particionados. A perspectiva global, supõe a existência de uma fila global que é acessível por todos os processadores disponíveis. Este fato torna disponível a migração de tarefas, isto é, é possível parar a execução de uma tarefa e resumir a sua execução num processador distinto. Num dado instante, num grupo de tarefas, m, as tarefas de maior prioridade são selecionadas para execução. Este tipo promete limites de utilização altos, a custo elevado de preempções/migrações de tarefas. Em contraste, os algoritmos particionados, colocam as tarefas em partições, e estas, são atribuídas a um dos processadores disponíveis, isto é, para cada processador, é atribuída uma partição. Por essa razão, a migração de tarefas não é possível, acabando por fazer com que o limite de utilização não seja tão alto quando comparado com o caso anterior, mas o número de preempções de tarefas decresce significativamente. O esquema semi-particionado, é uma resposta de caráter hibrido entre os casos anteriores, pois existem tarefas que são particionadas, para serem executadas exclusivamente por um grupo de processadores, e outras que são atribuídas a apenas um processador. Com isto, resulta uma solução que é capaz de distribuir o trabalho a ser realizado de uma forma mais eficiente e balanceada. Infelizmente, para todos estes casos, existe uma discrepância entre a teoria e a prática, pois acaba-se por se assumir conceitos que não são aplicáveis na vida real. Para dar resposta a este problema, é necessário implementar estes algoritmos de escalonamento em sistemas operativos reais e averiguar a sua aplicabilidade, para caso isso não aconteça, as alterações necessárias sejam feitas, quer a nível teórico quer a nível prá

Multicore Scheduling of Real-Time Irregular Parallel Algorithms in Linux

Face à estagnação da tecnologia uniprocessador registada na passada década, aos principais fabricantes de microprocessadores encontraram na tecnologia multi-core a resposta `as crescentes necessidades de processamento do mercado. Durante anos, os desenvolvedores de software viram as suas aplicações acompanhar os ganhos de performance conferidos por cada nova geração de processadores sequenciais, mas `a medida que a capacidade de processamento escala em função do número de processadores, a computação sequencial tem de ser decomposta em várias partes concorrentes que possam executar em paralelo, para que possam utilizar as unidades de processamento adicionais e completar mais rapidamente. A programação paralela implica um paradigma completamente distinto da programação sequencial. Ao contrário dos computadores sequenciais tipificados no modelo de Von Neumann, a heterogeneidade de arquiteturas paralelas requer modelos de programação paralela que abstraiam os programadores dos detalhes da arquitectura e simplifiquem o desenvolvimento de aplicações concorrentes. Os modelos de programação paralela mais populares incitam os programadores a identificar instruções concorrentes na sua lógica de programação, e a especificá-las sob a forma de tarefas que possam ser atribuídas a processadores distintos para executarem em simultâneo. Estas tarefas são tipicamente lançadas durante a execução, e atribuídas aos processadores pelo motor de execução subjacente. Como os requisitos de processamento costumam ser variáveis, e não são conhecidos a priori, o mapeamento de tarefas para processadores tem de ser determinado dinamicamente, em resposta a alterações imprevisíveis dos requisitos de execução. `A medida que o volume da computação cresce, torna-se cada vez menos viável garantir as suas restrições temporais em plataformas uniprocessador. Enquanto os sistemas de tempo real se começam a adaptar ao paradigma de computação paralela, há uma crescente aposta em integrar execuções de tempo real com aplicações interativas no mesmo hardware, num mundo em que a tecnologia se torna cada vez mais pequena, leve, ubíqua, e portável. Esta integração requer soluções de escalonamento que simultaneamente garantam os requisitos temporais das tarefas de tempo real e mantenham um nível aceitável de QoS para as restantes execuções. Para tal, torna-se imperativo que as aplicações de tempo real paralelizem, de forma a minimizar os seus tempos de resposta e maximizar a utilização dos recursos de processamento. Isto introduz uma nova dimensão ao problema do escalonamento, que tem de responder de forma correcta a novos requisitos de execução imprevisíveis e rapidamente conjeturar o mapeamento de tarefas que melhor beneficie os critérios de performance do sistema. A técnica de escalonamento baseado em servidores permite reservar uma fração da capacidade de processamento para a execução de tarefas de tempo real, e assegurar que os efeitos de latência na sua execução não afectam as reservas estipuladas para outras execuções. No caso de tarefas escalonadas pelo tempo de execução máximo, ou tarefas com tempos de execução variáveis, torna-se provável que a largura de banda estipulada não seja consumida por completo. Para melhorar a utilização do sistema, os algoritmos de partilha de largura de banda (capacity-sharing) doam a capacidade não utilizada para a execução de outras tarefas, mantendo as garantias de isolamento entre servidores. Com eficiência comprovada em termos de espaço, tempo, e comunicação, o mecanismo de work-stealing tem vindo a ganhar popularidade como metodologia para o escalonamento de tarefas com paralelismo dinâmico e irregular. O algoritmo p-CSWS combina escalonamento baseado em servidores com capacity-sharing e work-stealing para cobrir as necessidades de escalonamento dos sistemas abertos de tempo real. Enquanto o escalonamento em servidores permite partilhar os recursos de processamento sem interferências a nível dos atrasos, uma nova política de work-stealing que opera sobre o mecanismo de capacity-sharing aplica uma exploração de paralelismo que melhora os tempos de resposta das aplicações e melhora a utilização do sistema. Esta tese propõe uma implementação do algoritmo p-CSWS para o Linux. Em concordância com a estrutura modular do escalonador do Linux, ´e definida uma nova classe de escalonamento que visa avaliar a aplicabilidade da heurística p-CSWS em circunstâncias reais. Ultrapassados os obstáculos intrínsecos `a programação da kernel do Linux, os extensos testes experimentais provam que o p-CSWS ´e mais do que um conceito teórico atrativo, e que a exploração heurística de paralelismo proposta pelo algoritmo beneficia os tempos de resposta das aplicações de tempo real, bem como a performance e eficiência da plataforma multiprocessador.

ANN-Based LMP forecasting in a distribution network with large penetration of DG

In recent years, power systems have experienced many changes in their paradigm. The introduction of new players in the management of distributed generation leads to the decentralization of control and decision-making, so that each player is able to play in the market environment. In the new context, it will be very relevant that aggregator players allow midsize, small and micro players to act in a competitive environment. In order to achieve their objectives, virtual power players and single players are required to optimize their energy resource management process. To achieve this, it is essential to have financial resources capable of providing access to appropriate decision support tools. As small players have difficulties in having access to such tools, it is necessary that these players can benefit from alternative methodologies to support their decisions. This paper presents a methodology, based on Artificial Neural Networks (ANN), and intended to support smaller players. In this case the present methodology uses a training set that is created using energy resource scheduling solutions obtained using a mixed-integer linear programming (MIP) approach as the reference optimization methodology. The trained network is used to obtain locational marginal prices in a distribution network. The main goal of the paper is to verify the accuracy of the ANN based approach. Moreover, the use of a single ANN is compared with the use of two or more ANN to forecast the locational marginal price.

Intelligent management of end consumers loads including electric vehicles through a SCADA system

The large penetration of intermittent resources, such as solar and wind generation, involves the use of storage systems in order to improve power system operation. Electric Vehicles (EVs) with gridable capability (V2G) can operate as a means for storing energy. This paper proposes an algorithm to be included in a SCADA (Supervisory Control and Data Acquisition) system, which performs an intelligent management of three types of consumers: domestic, commercial and industrial, that includes the joint management of loads and the charge/discharge of EVs batteries. The proposed methodology has been implemented in a SCADA system developed by the authors of this paper – the SCADA House Intelligent Management (SHIM). Any event in the system, such as a Demand Response (DR) event, triggers the use of an optimization algorithm that performs the optimal energy resources scheduling (including loads and EVs), taking into account the priorities of each load defined by the installation users. A case study considering a specific consumer with several loads and EVs is presented in this paper.

LMP based bid formation for virtual power players operating in smart grids

Power system organization has gone through huge changes in the recent years. Significant increase in distributed generation (DG) and operation in the scope of liberalized markets are two relevant driving forces for these changes. More recently, the smart grid (SG) concept gained increased importance, and is being seen as a paradigm able to support power system requirements for the future. This paper proposes a computational architecture to support day-ahead Virtual Power Player (VPP) bid formation in the smart grid context. This architecture includes a forecasting module, a resource optimization and Locational Marginal Price (LMP) computation module, and a bid formation module. Due to the involved problems characteristics, the implementation of this architecture requires the use of Artificial Intelligence (AI) techniques. Artificial Neural Networks (ANN) are used for resource and load forecasting and Evolutionary Particle Swarm Optimization (EPSO) is used for energy resource scheduling. The paper presents a case study that considers a 33 bus distribution network that includes 67 distributed generators, 32 loads and 9 storage units.

Optimal dispatch with reactive power compensation by Genetic Algorithm

This paper presents a Unit Commitment model with reactive power compensation that has been solved by Genetic Algorithm (GA) optimization techniques. The GA has been developed a computational tools programmed/coded in MATLAB. The main objective is to find the best generations scheduling whose active power losses are minimal and the reactive power to be compensated, subjected to the power system technical constraints. Those are: full AC power flow equations, active and reactive power generation constraints. All constraints that have been represented in the objective function are weighted with a penalty factors. The IEEE 14-bus system has been used as test case to demonstrate the effectiveness of the proposed algorithm. Results and conclusions are dully drawn.

Distributed energy resources management with cyber-physical SCADA in the context of future smart grids

In the energy management of a small power system, the scheduling of the generation units is a crucial problem for which adequate methodologies can maximize the performance of the energy supply. This paper proposes an innovative methodology for distributed energy resources management. The optimal operation of distributed generation, demand response and storage resources is formulated as a mixed-integer linear programming model (MILP) and solved by a deterministic optimization technique CPLEX-based implemented in General Algebraic Modeling Systems (GAMS). The paper deals with a vision for the grids of the future, focusing on conceptual and operational aspects of electrical grids characterized by an intensive penetration of DG, in the scope of competitive environments and using artificial intelligence methodologies to attain the envisaged goals. These concepts are implemented in a computational framework which includes both grid and market simulation.

Case-based reasoning for self-optimizing behavior

In this paper we present a Self-Optimizing module, inspired on Autonomic Computing, acquiring a scheduling system with the ability to automatically select a Meta-heuristic to use in the optimization process, so as its parameterization. Case-based Reasoning was used so the system may be able of learning from the acquired experience, in the resolution of similar problems. From the obtained results we conclude about the benefit of its use.

Self-optimizing through CBR learning

In this paper, we foresee the use of Multi-Agent Systems for supporting dynamic and distributed scheduling in Manufacturing Systems. We also envisage the use of Autonomic properties in order to reduce the complexity of managing systems and human interference. By combining Multi-Agent Systems, Autonomic Computing, and Nature Inspired Techniques we propose an approach for the resolution of dynamic scheduling problem, with Case-based Reasoning Learning capabilities. The objective is to permit a system to be able to automatically adopt/select a Meta-heuristic and respective parameterization considering scheduling characteristics. From the comparison of the obtained results with previous results, we conclude about the benefits of its use.

AI in power systems and energy markets

In a world increasingly conscientious about environmental effects, power and energy systems are undergoing huge transformations. Electric energy produced from power plants is transmitted and distributed to end users through a power grid. The power industry performs the engineering design, installation, operation, and maintenance tasks to provide a high-quality, secure energy supply while accounting for its systems’ abilities to withstand uncertain events, such as weather-related outages. Competitive, deregulated electricity markets and new renewable energy sources, however, have further complicated this already complex infrastructure.Sustainable development has also been a challenge for power systems. Recently, there has been a signifi cant increase in the installation of distributed generations, mainly based on renewable resources such as wind and solar. Integrating these new generation systems leads to more complexity. Indeed, the number of generation sources greatly increases as the grid embraces numerous smaller and distributed resources. In addition, the inherent uncertainties of wind and solar energy lead to technical challenges such as forecasting, scheduling, operation, control, and risk management. In this special issue introductory article, we analyze the key areas in this field that can benefi t most from AI and intelligent systems now and in the future.We also identify new opportunities for cross-fertilization between power systems and energy markets and intelligent systems researchers.

QoS em WIMAX – Análise e avaliação de módulos para simulação com o ns-2

Mestrado em Engenharia Electrotécnica e de Computadores

Análise de risco em sequenciamento de actividades com restrições de recursos

Mestrado em Engenharia Electrotécnica e de Computadores. Área de Especialização em Sistemas e Planeamento Industrial.

Resolução do problema do escalonamento da produção de energia eléctrica usando programação lógica por restrições

A operação dos Mercados de Energia Eléctrica passa, actualmente, por uma profunda reestruturação, com o principal foco nas transacções do sistema de transmissão entre os diferentes agentes. Tendo isso em conta, o serviço de transmissão neste novo esquema de funcionamento do Mercado de Energia Eléctrica deve ser provido de máxima eficiência económica, atendendo sempre às restrições de segurança do sistema. Com esta reorganização do sector eléctrico da última década surgiu também a necessidade de rever os modelos tradicionais de optimização económica do Sistema Eléctrico de Energia, como por exemplo o despacho e prédespacho (unit commitment). A reestruturação e liberalização dos mercados de energia eléctrica trouxeram novas restrições a alguns dos problemas tradicionais associados aos Sistemas Eléctricos de Energia. Um desses problemas é o Escalonamento da Produção de Energia Eléctrica, que no contexto actual, implica quase sempre negociação entre os diferentes agentes do mercado e consequentemente reescalonamento. A maioria dos métodos usados para a resolução do problema não permitem reformular o prédespacho, algo para que a Programação Lógica por Restrições é extremamente adequada. O trabalho desenvolvido nesta dissertação visa criar uma aplicação computacional com base na Programação Lógica por Restrições, através da plataforma ECLiPSe, para resolver o problema do Escalonamento da Produção de Energia Eléctrica dos grupos térmicos, demonstrando assim a versatilidade e flexibilidade deste tipo de programação aplicada a problema combinatoriais deste género.