Meta-heuristics self-parameterization in a multi-agent scheduling system using case-based reasoning

This paper proposes a novel agent-based approach to Meta-Heuristics self-configuration. Meta-heuristics are algorithms with parameters which need to be set up as efficient as possible in order to unsure its performance. A learning module for self-parameterization of Meta-heuristics (MH) in a Multi-Agent System (MAS) for resolution of scheduling problems is proposed in this work. The learning module 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. Finally, some conclusions are reached and future work outlined.

Modified particle swarm optimization for day-ahead distributed energy resources scheduling including vehicle-to-grid

Mestrado em Engenharia Electrotécnica – Sistemas Eléctricos de Energia

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

An optimization approach for the job shop scheduling problem

This paper presents an optimization approach for the job shop scheduling problem (JSSP). The JSSP is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. The proposed approach is based on a genetic algorithm technique. The scheduling rules such as SPT and MWKR are integrated into the process of genetic evolution. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities and delay times of the operations are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed approach.

Control of a 6-DOF parallel manipulator through a mechatronic approach

This paper shows that a hierarchical architecture, distributing several control actions in growing levels of complexity and using resources of reconfigurable computing, enables one to take into account the ease of future modifications, updates and improvements in robotic applications. An experimental example of a Stewart—Gough platform control (a platform applied as the solution to countless practical problems) is presented using reconfigurable computing. The software and hardware developed are structured in independent blocks. This open architecture implementation allows easy expansion of the system and better adaptation of the platform to its related tasks.

Afetação de recursos em sistemas de produção

O problema do escalonamento, por ser um dos factores fundamentais na tomada de decisão para uma boa gestão das operações, tem sido alvo de um amplo estudo, tanto na sua componente teórica como na sua componente prática. A importância de um escalonamento correto das operações é preponderante, quando as pequenas diferenças, em termos de tempos de produção, podem ter um grande impacto na competitividade da organização. Em muitas unidades produtivas, existem máquinas capazes de realizar as mesmas operações com diferentes desempenhos. Isto pode dever-se à necessidade de flexibilizar os recursos ou mesmo a uma atualização da capacidade produtiva. Embora os problemas de máquinas diferentes em paralelo tenham sido alvo de um vasto estudo, muitos deles não são passíveis de ser resolvidos através de métodos exatos. O problema de minimização do makespan (Rm||Cmax), é NP-hard, sendo habitualmente abordado através de heurísticas. Entre as heurísticas utilizadas em problemas de minimização do makespan em máquinas diferentes em paralelo, é possível identificar duas filosofias de afectação: a que utiliza os tempos de processamento para alocar as tarefas e a que utiliza as datas de conclusão. Nesta dissertação, pretende-se dar uma contribuição para a resolução do problema de afectação de recursos em sistemas de produção. Para tal, foram propostas as heurísticas OMTC 3 e Suffrage One. A contribuição consiste na proposta de versões híbridas e modificadas das heurística MCT e Suffrage, uma vez identificadas várias características que podem limitar o seu desempenho, como o facto da heurística MCT alocar as tarefas numa ordem aleatória ou a heurística Suffrage alocar mais que uma tarefa por iteração. Finalmente, procedeu-se à realização de testes computacionais, para avaliar o desempenho das heurísticas propostas. Os testes realizados permitiram concluir que a heurística OMTC 3 apresentou um melhor desempenho que a heurística MCT.

Day-ahead Resource Scheduling Including Demand Response for Electric Vehicles

The energy resource scheduling is becoming increasingly important, as the use of distributed resources is intensified and massive gridable vehicle (V2G) use is envisaged. This paper presents a methodology for day-ahead energy resource scheduling for smart grids considering the intensive use of distributed generation and V2G. The main focus is the comparison of different EV management approaches in the day-ahead energy resources management, namely uncontrolled charging, smart charging, V2G and Demand Response (DR) programs i n the V2G approach. Three different DR programs are designed and tested (trip reduce, shifting reduce and reduce+shifting). Othe r important contribution of the paper is the comparison between deterministic and computational intelligence techniques to reduce the execution time. The proposed scheduling is solved with a modified particle swarm optimization. Mixed integer non-linear programming is also used for comparison purposes. Full ac power flow calculation is included to allow taking into account the network constraints. A case study with a 33-bus distribution network and 2000 V2G resources is used to illustrate the performance of the proposed method.

Modified Particle Swarm Optimization Applied to Integrated Demand Response and DG Resources Scheduling

The elastic behavior of the demand consumption jointly used with other available resources such as distributed generation (DG) can play a crucial role for the success of smart grids. The intensive use of Distributed Energy Resources (DER) and the technical and contractual constraints result in large-scale non linear optimization problems that require computational intelligence methods to be solved. This paper proposes a Particle Swarm Optimization (PSO) based methodology to support the minimization of the operation costs of a virtual power player that manages the resources in a distribution network and the network itself. Resources include the DER available in the considered time period and the energy that can be bought from external energy suppliers. Network constraints are considered. The proposed approach uses Gaussian mutation of the strategic parameters and contextual self-parameterization of the maximum and minimum particle velocities. The case study considers a real 937 bus distribution network, with 20310 consumers and 548 distributed generators. The obtained solutions are compared with a deterministic approach and with PSO without mutation and Evolutionary PSO, both using self-parameterization.

Negotiation mechanism for self-organized scheduling system with collective intelligence

Current Manufacturing Systems challenges due to international economic crisis, market globalization and e-business trends, incites the development of intelligent systems to support decision making, which allows managers to concentrate on high-level tasks management while improving decision response and effectiveness towards manufacturing agility. This paper presents a novel negotiation mechanism for dynamic scheduling based on social and collective intelligence. Under the proposed negotiation mechanism, agents must interact and collaborate in order to improve the global schedule. Swarm Intelligence (SI) is considered a general aggregation term for several computational techniques, which use ideas and inspiration from the social behaviors of insects and other biological systems. This work is primarily concerned with negotiation, where multiple self-interested agents can reach agreement over the exchange of operations on competitive resources. Experimental analysis was performed in order to validate the influence of negotiation mechanism in the system performance and the SI technique. Empirical results and statistical evidence illustrate that the negotiation mechanism influence significantly the overall system performance and the effectiveness of Artificial Bee Colony for makespan minimization and on the machine occupation maximization.

Multi-agent system for distributed manufacturing scheduling with genetic algorithms and tabu search

Computerized scheduling methods and computerized scheduling systems according to exemplary embodiments. A computerized scheduling method may be stored in a memory and executed on one or more processors. The method may include defining a main multi-machine scheduling problem as a plurality of single machine scheduling problems; independently solving the plurality of single machine scheduling problems thereby calculating a plurality of near optimal single machine scheduling problem solutions; integrating the plurality of near optimal single machine scheduling problem solutions into a main multi-machine scheduling problem solution; and outputting the main multi-machine scheduling problem solution.

Dynamic cluster scheduling for cluster-tree WSNs

While Cluster-Tree network topologies look promising for WSN applications with timeliness and energy-efficiency requirements, we are yet to witness its adoption in commercial and academic solutions. One of the arguments that hinder the use of these topologies concerns the lack of flexibility in adapting to changes in the network, such as in traffic flows. This paper presents a solution to enable these networks with the ability to self-adapt their clusters’ duty-cycle and scheduling, to provide increased quality of service to multiple traffic flows. Importantly, our approach enables a network to change its cluster scheduling without requiring long inaccessibility times or the re-association of the nodes. We show how to apply our methodology to the case of IEEE 802.15.4/ZigBee cluster-tree WSNs without significant changes to the protocol. Finally, we analyze and demonstrate the validity of our methodology through a comprehensive simulation and experimental validation using commercially available technology on a Structural Health Monitoring application scenario.

Compositional multiprocessor scheduling: the GMPR interface

Composition is a practice of key importance in software engineering. When real-time applications are composed, it is necessary that their timing properties (such as meeting the deadlines) are guaranteed. The composition is performed by establishing an interface between the application and the physical platform. Such an interface typically contains information about the amount of computing capacity needed by the application. For multiprocessor platforms, the interface should also present information about the degree of parallelism. Several interface proposals have recently been put forward in various research works. However, those interfaces are either too complex to be handled or too pessimistic. In this paper we propose the generalized multiprocessor periodic resource model (GMPR) that is strictly superior to the MPR model without requiring a too detailed description. We then derive a method to compute the interface from the application specification. This method has been implemented in Matlab routines that are publicly available.

Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set τ of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m k processors of type-k, where k∈{1,2,…,t}. The execution time of a task depends on the type of processor on which it executes. The set of shared resources is denoted by R. For each task τ i , there is a resource set R i ⊆R such that for each job of τ i , during one phase of its execution, the job requests to hold the resource set R i exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set R i and (ii) at all times, when a job of τ i holds R i , no other job holds any resource in R i . Each job of task τ i may request the resource set R i at most once during its execution. A job is allowed to migrate when it requests a resource set and when it releases the resource set but a job is not allowed to migrate at other times. Our goal is to design a scheduling algorithm for this problem and prove its performance. We propose an algorithm, LP-EE-vpr, which offers the guarantee that if an implicit-deadline sporadic task set is schedulable on a t-type heterogeneous multiprocessor platform by an optimal scheduling algorithm that allows a job to migrate only when it requests or releases a resource set, then our algorithm also meets the deadlines with the same restriction on job migration, if given processors 4×(1+MAXP×⌈|P|×MAXPmin{m1,m2,…,mt}⌉) times as fast. (Here MAXP and |P| are computed based on the resource sets that tasks request.) For the special case that each task requests at most one resource, the bound of LP-EE-vpr collapses to 4×(1+⌈|R|min{m1,m2,…,mt}⌉). To the best of our knowledge, LP-EE-vpr is the first algorithm with proven performance guarantee for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors.

Optimal scheduling of aircrafts’ engines repair process

We address a real world scheduling problem concerning the repair process of aircrafts’ engines by TAP - Maintenance & Engineering (TAP-ME). TAP-ME is the maintenance, repair and overhaul organization of TAP Portugal, Portugal’s leading airline, which employs about 4000 persons to provide maintenance and engineering services in aircraft, engines and components. TAP-ME is aiming to optimize its maintenance services, focusing on the reduction of the engines repair turnaround time.

Scheduling aircraft’s engines repair process: a mathematical model

In this talk, we discuss a scheduling problem that originated at TAP - Maintenance & Engineering - the maintenance, repair and overhaul organization of Portugal’s leading airline. In the repair process of aircrafts’ engines, the operations to be scheduled may be executed on a certain workstation by any processor of a given set, and the objective is to minimize the total weighted tardiness. A mixed integer linear programming formulation, based on the flexible job shop scheduling, is presented here, along with computational experiment on a real instance, provided by TAP-ME, from a regular working week. The model was also tested using benchmarking instances available in literature.