Beam Search Algorithms for Minimizing Tool Switches on a Flexible Manufacturing System

In the minimization of tool switches problem we seek a sequence to process a set of jobs so that the number of tool switches required is minimized. In this work different variations of a heuristic based on partial ordered job sequences are implemented and evaluated. All variations adopt a depth first strategy of the enumeration tree. The computational test results indicate that good results can be obtained by a variation which keeps the best three branches at each node of the enumeration tree, and randomly choose, among all active nodes, the next node to branch when backtracking.

Tabu search to solve the Synchronized and Integrated Two-Level Lot Sizing and Scheduling Problem

This paper proposes a tabu search approach to solve the Synchronized and Integrated Two-Level Lot Sizing and Scheduling Problem (SITLSP). It is a real-world problem, often found in soft drink companies, where the production process has two integrated levels with decisions concerning raw material storage and soft drink bottling. Lot sizing and scheduling of raw materials in tanks and products in bottling lines must be simultaneously determined. Real data provided by a soft drink company is used to make comparisons with a previous genetic algorithm. Computational results have demonstrated that tabu search outperformed genetic algorithm in all instances. Copyright 2011 ACM.

Search schemes for random optimization algorithms that preserve the asymptotic distribution

Markovian algorithms for estimating the global maximum or minimum of real valued functions defined on some domain Omega subset of R-d are presented. Conditions on the search schemes that preserve the asymptotic distribution are derived. Global and local search schemes satisfying these conditions are analysed and shown to yield sharper confidence intervals when compared to the i.i.d. case.

PMUs optimized allocation using a tabu search algorithm for fault location in electric power distribution system

Phasor Measurement Units (PMUs) optimized allocation allows control, monitoring and accurate operation of electric power distribution systems, improving reliability and service quality. Good quality and considerable results are obtained for transmission systems using fault location techniques based on voltage measurements. Based on these techniques and performing PMUs optimized allocation it is possible to develop an electric power distribution system fault locator, which provides accurate results. The PMUs allocation problem presents combinatorial features related to devices number that can be allocated, and also probably places for allocation. Tabu search algorithm is the proposed technique to carry out PMUs allocation. This technique applied in a 141 buses real-life distribution urban feeder improved significantly the fault location results. © 2004 IEEE.

An efficient implementation of tabu search in feeder reconfiguration of distribution systems

This paper presents an efficient tabu search algorithm (TSA) to solve the problem of feeder reconfiguration of distribution systems. The main characteristics that make the proposed TSA particularly efficient are a) the way in which the neighborhood of the current solution was defined; b) the way in which the objective function value was estimated; and c) the reduction of the neighborhood using heuristic criteria. Four electrical systems, described in detail in the specialized literature, were used to test the proposed TSA. The result demonstrate that it is computationally very fast and finds the best solutions known in the specialized literature. © 2012 IEEE.

Comparative studies on non-convex optimization methods for transmission network expansion planning

We have investigated and extensively tested three families of non-convex optimization approaches for solving the transmission network expansion planning problem: simulated annealing (SA), genetic algorithms (GA), and tabu search algorithms (TS). The paper compares the main features of the three approaches and presents an integrated view of these methodologies. A hybrid approach is then proposed which presents performances which are far better than the ones obtained with any of these approaches individually. Results obtained in tests performed with large scale real-life networks are summarized.

Comparative studies on non-convex optimization methods for transmission network expansion planning

We have investigated and extensively tested three families of non-convex optimization approaches for solving the transmission network expansion planning problem: simulated annealing (SA), genetic algorithms (GA), and tabu search algorithms (TS). The paper compares the main features of the three approaches and presents an integrated view of these methodologies. A hybrid approach is then proposed which presents performances which are far better than the ones obtained with any of these approaches individually. Results obtained in tests performed with large scale real-life networks are summarized.

Integrated planning of electric power distribution networks

In this work, a heuristic model for integrated planning of primary distribution network and secondary distribution circuits is proposed. A Tabu Search (TS) algorithm is employed to solve the planning of primary distribution networks. Evolutionary Algorithms (EA) are used to solve the planning model of secondary networks. The planning integration of both networks is carried out by means a constructive heuristic taking into account a set of integration alternatives between these networks. These integration alternatives are treated in a hierarchical way. The planning of primary networks and secondary distribution circuits is carried out based on assessment of the effects of the alternative solutions in the expansion costs of both networks simultaneously. In order to evaluate this methodology, tests were performed for a real-life distribution system taking into account the primary and secondary networks.

Optimal switch allocation for automatic load transfer in distribution substations

This work proposes a methodology for optimized allocation of switches for automatic load transfer in distribution systems in order to improve the reliability indexes by restoring such systems which present voltage classes of 23 to 35 kV and radial topology. The automatic switches must be allocated on the system in order to transfer load remotely among the sources at the substations. The problem of switch allocation is formulated as nonlinear constrained mixed integer programming model subject to a set of economical and physical constraints. A dedicated Tabu Search (TS) algorithm is proposed to solve this model. The proposed methodology is tested for a large real-life distribution system. © 2011 IEEE.

Ergodic crossover in partially self-avoiding stochastic walks

Consider a one-dimensional environment with N randomly distributed sites. An agent explores this random medium moving deterministically with a spatial memory μ. A crossover from local to global exploration occurs in one dimension at a well-defined memory value μ1=log2N. In its stochastic version, the dynamics is ruled by the memory and by temperature T, which affects the hopping displacement. This dynamics also shows a crossover in one dimension, obtained computationally, between exploration schemes, characterized yet by the trajectory size (Np) (aging effect). In this paper we provide an analytical approach considering the modified stochastic version where the parameter T plays the role of a maximum hopping distance. This modification allows us to obtain a general analytical expression for the crossover, as a function of the parameters μ, T, and Np. Differently from what has been proposed by previous studies, we find that the crossover occurs in any dimension d. These results have been validated by numerical experiments and may be of great value for fixing optimal parameters in search algorithms. © 2013 American Physical Society.

Stochastic scheduling - A flow shop no wait application and solutions

Minimizing the makespan of a flow-shop no-wait (FSNW) schedule where the processing times are randomly distributed is an important NP-Complete Combinatorial Optimization Problem. In spite of this, it can be found only in very few papers in the literature. By considering the Start Interval Concept, this problem can be formulated, in a practical way, in function of the probability of the success in preserve FSNW constraints for all tasks execution. With this formulation, for the particular case with 3 machines, this paper presents different heuristics solutions: by integrating local optimization steps with insertion procedures and by using genetic algorithms for search the solution space. Computational results and performance evaluations are commented. Copyright (C) 1998 IFAC.

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (1) the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry's own practice. © 2006 Elsevier Ltd. All rights reserved.

Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups

A lot sizing and scheduling problem from a foundry is considered in which key materials are produced and then transformed into many products on a single machine. A mixed integer programming (MIP) model is developed, taking into account sequence-dependent setup costs and times, and then adapted for rolling horizon use. A relax-and-fix (RF) solution heuristic is proposed and computationally tested against a high-performance MIP solver. Three variants of local search are also developed to improve the RF method and tested. Finally the solutions are compared with those currently practiced at the foundry.

Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants

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

Heuristics and meta-heuristics for lot sizing and scheduling in the soft drinks industry: A comparison study

This chapter studies a two-level production planning problem where, on each level, a lot sizing and scheduling problem with parallel machines, capacity constraints and sequence-dependent setup costs and times must be solved. The problem can be found in soft drink companies where the production process involves two interdependent levels with decisions concerning raw material storage and soft drink bottling. Models and solution approaches proposed so far are surveyed and conceptually compared. Two different approaches have been selected to perform a series of computational comparisons: an evolutionary technique comprising a genetic algorithm and its memetic version, and a decomposition and relaxation approach. © 2008 Springer-Verlag Berlin Heidelberg.