An efficient meta-heuristic algorithm for grid computing

A grid computing system consists of a group of programs and resources that are spread across machines in the grid. A grid system has a dynamic environment and decentralized distributed resources, so it is important to provide efficient scheduling for applications. Task scheduling is an NP-hard problem and deterministic algorithms are inadequate and heuristic algorithms such as particle swarm optimization (PSO) are needed to solve the problem. PSO is a simple parallel algorithm that can be applied in different ways to resolve optimization problems. PSO searches the problem space globally and needs to be combined with other methods to search locally as well. In this paper, we propose a hybrid-scheduling algorithm to solve the independent task- scheduling problem in grid computing. We have combined PSO with the gravitational emulation local search (GELS) algorithm to form a new method, PSO–GELS. Our experimental results demonstrate the effectiveness of PSO–GELS compared to other algorithms.

A hybrid cuckoo search and variable neighborhood descent for single and multiobjective scheduling problems

Cuckoo search (CS) is a relatively new meta-heuristic that has proven its strength in solving continuous optimization problems. This papers applies cuckoo search to the class of sequencing problems by hybridizing it with a variable neighborhood descent local search for enhancing the quality of the obtained solutions. The Lévy flight operator proposed in the original CS is modified to address the discrete nature of scheduling problems. Two well-known problems are used to demonstrate the effectiveness of the proposed hybrid CS approach. The first is the NP-hard single objective problem of minimizing the weighted total tardiness time (Formula presented.) and the second is the multiobjective problem of minimizing the flowtime ¯ and the maximum tardiness Tmaxfor single machine (Formula presented.). For the first problem, computational results show that the hybrid CS is able to find the optimal solutions for all benchmark test instances with 40, 50, and 100 jobs and for most instances with 150, 200, 250, and 300 jobs. For the second problem, the hybrid CS generated solutions on and very close to the exact Pareto fronts of test instances with 10, 20, 30, and 40 jobs. In general, the results reveal that the hybrid CS is an adequate and robust method for tackling single and multiobjective scheduling problems.

Hybrid technique of ant colony and particle swarm optimization for short term wind energy forecasting

Wind farms are producing a considerable portion of the world renewable energy. Since the output power of any wind farm is highly dependent on the wind speed, the power extracted from a wind park is not always a constant value. In order to have a non-disruptive supply of electricity, it is important to have a good scheduling and forecasting system for the energy output of any wind park. In this paper, a new hybrid swarm technique (HAP) is used to forecast the energy output of a real wind farm located in Binaloud, Iran. The technique consists of the hybridization of the ant colony optimization (ACO) and particle swarm optimization (PSO) which are two meta-heuristic techniques under the category of swarm intelligence. The hybridization of the two algorithms to optimize the forecasting model leads to a higher quality result with a faster convergence profile. The empirical hourly wind power output of Binaloud Wind Farm for 364 days is collected and used to train and test the prepared model. The meteorological data consisting of wind speed and ambient temperature is used as the inputs to the mathematical model. The results indicate that the proposed technique can estimate the output wind power based on the wind speed and the ambient temperature with an MAPE of 3.513%.

Evaluation of hybrid models for static and multistage transmission system planning

Neste trabalho é analisada a aplicação de algoritmos heurísticos para o Modelo Híbrido Linear - Hybrid Linear Model (HLM) - no problema de planejamento da expansão de sistemas de transmissão. O HLM é um modelo relaxado que ainda não foi suficientemente explorado. Assim, é realizada uma análise das características do modelo matemático e das técnicas de solução que podem ser usadas para resolver este tipo de modelo. O trabalho analisa em detalhes um algoritmo heurístico construtivo para o HLM e faz uma extensão da modelagem e da técnica de solução para o planejamento multi-estágio da expansão de sistemas de transmissão. Dentro deste contexto, também é realizada uma avaliação da qualidade das soluções encontradas pelo HLM e as possibilidades de aplicação deste modelo em planejamento de sistemas de transmissão. Finalmente, são apresentados testes com sistemas conhecidos na literatura especializada.

Constructive heuristic algorithm in branch-and-bound structure applied to transmission network expansion planning

A constructive heuristic algorithm to solve the transmission system expansion planning problem is proposed with the aim of circumventing some critical problems of classical heuristic algorithms that employ relaxed mathematical models to calculate a sensitivity index that guides the circuit additions. The proposed heuristic algorithm is in a branch-and-bound algorithm structure, which can be used with any planning model, such as Transportation model, DC model, AC model or Hybrid models. Tests of the proposed algorithm are presented on real Brazilian systems.

A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging

The present paper proposes a new hybrid multi-population genetic algorithm (HMPGA) as an approach to solve the multi-level capacitated lot sizing problem with backlogging. This method combines a multi-population based metaheuristic using fix-and-optimize heuristic and mathematical programming techniques. A total of four test sets from the MULTILSB (Multi-Item Lot-Sizing with Backlogging) library are solved and the results are compared with those reached by two other methods recently published. The results have shown that HMPGA had a better performance for most of the test sets solved, specially when longer computing time is given. © 2012 Elsevier Ltd.

Genetic algorithm, MIP and improvement heuristic applied to the MLCLP with backlogging

The present paper solves the multi-level capacitated lot sizing problem with backlogging (MLCLSPB) combining a genetic algorithm with the solution of mixed-integer programming models and the improvement heuristic fix and optimize. This approach is evaluated over sets of benchmark instances and compared to methods from literature. Computational results indicate competitive results applying the proposed method when compared with other literature approaches. © 2013 IEEE.

Transmission Expansion Planning Via a Constructive Heuristic Algorithm in Restructured Electricity Industry

The transmission expansion planning problem in modern power systems is a large-scale, mixed-integer, nonlinear and non-convex problem. this paper presents a new mathematical model and a constructive heuristic algorithm (CHA) for solving transmission expansion planning problem under new environment of electricity restructuring. CHA finds an acceptable solution in an iterative process, where in each step a circuit is chosen using a sensitivity index and added to the system. The proposed model consider multiple generation scenarios therefore the methodology finds high quality solution in which it allows the power system operate adequacy in an environment with multiple generators scenarios. Case studies and simulation results using test systems show possibility of using Constructive heuristic algorithm in an open access system.

A hybrid method for the probabilistic maximal covering location-allocation problem

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

Hybrid methods for lot sizing on parallel machines

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

Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Multicelled Behaviour in E. coli: Design and experimental characterization of an engineered library of hybrid promoters.

Synthetic biology has recently had a great development, many papers have been published and many applications have been presented, spanning from the production of biopharmacheuticals to the synthesis of bioenergetic substrates or industrial catalysts. But, despite these advances, most of the applications are quite simple and don’t fully exploit the potential of this discipline. This limitation in complexity has many causes, like the incomplete characterization of some components, or the intrinsic variability of the biological systems, but one of the most important reasons is the incapability of the cell to sustain the additional metabolic burden introduced by a complex circuit. The objective of the project, of which this work is part, is trying to solve this problem through the engineering of a multicellular behaviour in prokaryotic cells. This system will introduce a cooperative behaviour that will allow to implement complex functionalities, that can’t be obtained with a single cell. In particular the goal is to implement the Leader Election, this procedure has been firstly devised in the field of distributed computing, to identify the process that allow to identify a single process as organizer and coordinator of a series of tasks assigned to the whole population. The election of the Leader greatly simplifies the computation providing a centralized control. Further- more this system may even be useful to evolutionary studies that aims to explain how complex organisms evolved from unicellular systems. The work presented here describes, in particular, the design and the experimental characterization of a component of the circuit that solves the Leader Election problem. This module, composed of an hybrid promoter and a gene, is activated in the non-leader cells after receiving the signal that a leader is present in the colony. The most important element, in this case, is the hybrid promoter, it has been realized in different versions, applying the heuristic rules stated in [22], and their activity has been experimentally tested. The objective of the experimental characterization was to test the response of the genetic circuit to the introduction, in the cellular environment, of particular molecules, inducers, that can be considered inputs of the system. The desired behaviour is similar to the one of a logic AND gate in which the exit, represented by the luminous signal produced by a fluorescent protein, is one only in presence of both inducers. The robustness and the stability of this behaviour have been tested by changing the concentration of the input signals and building dose response curves. From these data it is possible to conclude that the analysed constructs have an AND-like behaviour over a wide range of inducers’ concentrations, even if it is possible to identify many differences in the expression profiles of the different constructs. This variability accounts for the fact that the input and the output signals are continuous, and so their binary representation isn’t able to capture the complexity of the behaviour. The module of the circuit that has been considered in this analysis has a fundamental role in the realization of the intercellular communication system that is necessary for the cooperative behaviour to take place. For this reason, the second phase of the characterization has been focused on the analysis of the signal transmission. In particular, the interaction between this element and the one that is responsible for emitting the chemical signal has been tested. The desired behaviour is still similar to a logic AND, since, even in this case, the exit signal is determined by the hybrid promoter activity. The experimental results have demonstrated that the systems behave correctly, even if there is still a substantial variability between them. The dose response curves highlighted that stricter constrains on the inducers concentrations need to be imposed in order to obtain a clear separation between the two levels of expression. In the conclusive chapter the DNA sequences of the hybrid promoters are analysed, trying to identify the regulatory elements that are most important for the determination of the gene expression. Given the available data it wasn’t possible to draw definitive conclusions. In the end, few considerations on promoter engineering and complex circuits realization are presented. This section aims to briefly recall some of the problems outlined in the introduction and provide a few possible solutions.

A hybrid method for large-scale short-term scheduling of make-and-pack production processes

Due to the ongoing trend towards increased product variety, fast-moving consumer goods such as food and beverages, pharmaceuticals, and chemicals are typically manufactured through so-called make-and-pack processes. These processes consist of a make stage, a pack stage, and intermediate storage facilities that decouple these two stages. In operations scheduling, complex technological constraints must be considered, e.g., non-identical parallel processing units, sequence-dependent changeovers, batch splitting, no-wait restrictions, material transfer times, minimum storage times, and finite storage capacity. The short-term scheduling problem is to compute a production schedule such that a given demand for products is fulfilled, all technological constraints are met, and the production makespan is minimised. A production schedule typically comprises 500–1500 operations. Due to the problem size and complexity of the technological constraints, the performance of known mixed-integer linear programming (MILP) formulations and heuristic approaches is often insufficient. We present a hybrid method consisting of three phases. First, the set of operations is divided into several subsets. Second, these subsets are iteratively scheduled using a generic and flexible MILP formulation. Third, a novel critical path-based improvement procedure is applied to the resulting schedule. We develop several strategies for the integration of the MILP model into this heuristic framework. Using these strategies, high-quality feasible solutions to large-scale instances can be obtained within reasonable CPU times using standard optimisation software. We have applied the proposed hybrid method to a set of industrial problem instances and found that the method outperforms state-of-the-art methods.

A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.

An integrated scheduling problem of PCB components on sequential pick-and-place machines:mathematical models and heuristic solutions

This paper formulates several mathematical models for determining the optimal sequence of component placements and assignment of component types to feeders simultaneously or the integrated scheduling problem for a type of surface mount technology placement machines, called the sequential pick-andplace (PAP) machine. A PAP machine has multiple stationary feeders storing components, a stationary working table holding a printed circuit board (PCB), and a movable placement head to pick up components from feeders and place them to a board. The objective of integrated problem is to minimize the total distance traveled by the placement head. Two integer nonlinear programming models are formulated first. Then, each of them is equivalently converted into an integer linear type. The models for the integrated problem are verified by two commercial packages. In addition, a hybrid genetic algorithm previously developed by the authors is adopted to solve the models. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total traveling distance.