Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

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.

Simultaneous feature selection and feature weighting using Hybrid Tabu Search/K-nearest neighbor classifier

Feature selection and feature weighting are useful techniques for improving the classification accuracy of K-nearest-neighbor (K-NN) rule. The term feature selection refers to algorithms that select the best subset of the input feature set. In feature weighting, each feature is multiplied by a weight value proportional to the ability of the feature to distinguish pattern classes. In this paper, a novel hybrid approach is proposed for simultaneous feature selection and feature weighting of K-NN rule based on Tabu Search (TS) heuristic. The proposed TS heuristic in combination with K-NN classifier is compared with several classifiers on various available data sets. The results have indicated a significant improvement in the performance in classification accuracy. The proposed TS heuristic is also compared with various feature selection algorithms. Experiments performed revealed that the proposed hybrid TS heuristic is superior to both simple TS and sequential search algorithms. We also present results for the classification of prostate cancer using multispectral images, an important problem in biomedicine.

FPGA-based Tabu Search for Detection in Large-Scale MIMO Systems

The increasing scale of Multiple-Input Multiple- Output (MIMO) topologies employed in forthcoming wireless communications standards presents a substantial implementation challenge to designers of embedded baseband signal processing architectures for MIMO transceivers. Specifically the increased scale of such systems has a substantial impact on the perfor- mance/cost balance of detection algorithms for these systems. Whilst in small-scale systems Sphere Decoding (SD) algorithms offer the best quasi-ML performance/cost balance, in larger systems heuristic detectors, such Tabu-Search (TS) detectors are superior. This paper addresses a dearth of research in architectures for TS-based MIMO detection, presenting the first known realisations of TS detectors for 4 × 4 and 10 × 10 MIMO systems. To the best of the authors’ knowledge, these are the largest single-chip detectors on record.

Economic, environmental and mixed objective functions in non-linear process optimization using simulated annealing and tabu search

Screening of topologies developed by hierarchical heuristic procedures can be carried out by comparing their optimal performance. In this work we will be exploiting mono-objective process optimization using two algorithms, simulated annealing and tabu search, and four different objective functions: two of the net present value type, one of them including environmental costs and two of the global potential impact type. The hydrodealkylation of toluene to produce benzene was used as case study, considering five topologies with different complexities mainly obtained by including or not liquid recycling and heat integration. The performance of the algorithms together with the objective functions was observed, analyzed and discussed from various perspectives: average deviation of results for each algorithm, capacity for producing high purity product, screening of topologies, objective functions robustness in screening of topologies, trade-offs between economic and environmental type objective functions and variability of optimum solutions.

Multi-objective assembly job shop scheduling using genetic algorithm and tabu search

Assembly job shop scheduling problem (AJSP) is one of the most complicated combinatorial optimization problem that involves simultaneously scheduling the processing and assembly operations of complex structured products. The problem becomes even more complicated if a combination of two or more optimization criteria is considered. This thesis addresses an assembly job shop scheduling problem with multiple objectives. The objectives considered are to simultaneously minimizing makespan and total tardiness. In this thesis, two approaches viz., weighted approach and Pareto approach are used for solving the problem. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. Two metaheuristic techniques namely, genetic algorithm and tabu search are investigated in this thesis for solving the multiobjective assembly job shop scheduling problems. Three algorithms based on the two metaheuristic techniques for weighted approach and Pareto approach are proposed for the multi-objective assembly job shop scheduling problem (MOAJSP). A new pairing mechanism is developed for crossover operation in genetic algorithm which leads to improved solutions and faster convergence. The performances of the proposed algorithms are evaluated through a set of test problems and the results are reported. The results reveal that the proposed algorithms based on weighted approach are feasible and effective for solving MOAJSP instances according to the weight assigned to each objective criterion and the proposed algorithms based on Pareto approach are capable of producing a number of good Pareto optimal scheduling plans for MOAJSP instances.

Tabu search algorithm for network synthesis

Large scale combinatorial problems such as the network expansion problem present an amazingly high number of alternative configurations with practically the same investment, but with substantially different structures (configurations obtained with different sets of circuit/transformer additions). The proposed parallel tabu search algorithm has shown to be effective in exploring this type of optimization landscape. The algorithm is a third generation tabu search procedure with several advanced features. This is the most comprehensive combinatorial optimization technique available for treating difficult problems such as the transmission expansion planning. The method includes features of a variety of other approaches such as heuristic search, simulated annealing and genetic algorithms. In all test cases studied there are new generation, load sites which can be connected to an existing main network: such connections may require more than one line, transformer addition, which makes the problem harder in the sense that more combinations have to be considered.

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.

Tabu search for the cyclic bandwidth problem

International audience

A fast tabu search algorithm for the group shop scheduling problem

Three types of shop scheduling problems, the flow shop, the job shop and the open shop scheduling problems, have been widely studied in the literature. However, very few articles address the group shop scheduling problem introduced in 1997, which is a general formulation that covers the three above mentioned shop scheduling problems and the mixed shop scheduling problem. In this paper, we apply tabu search to the group shop scheduling problem and evaluate the performance of the algorithm on a set of benchmark problems. The computational results show that our tabu search algorithm is typically more efficient and faster than the other methods proposed in the literature. Furthermore, the proposed tabu search method has found some new best solutions of the benchmark instances.

Low-Complexity Near-ML Decoding of Large Non-Orthogonal STBCs using Reactive Tabu Search

Non-orthogonal space-time block codes (STBC) with large dimensions are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) as well as full transmit diversity. Decoding of non-orthogonal STBCs with large dimensions has been a challenge. In this paper, we present a reactive tabu search (RTS) based algorithm for decoding non-orthogonal STBCs from cyclic division algebras (CDA) having largedimensions. Under i.i.d fading and perfect channel state information at the receiver (CSIR), our simulation results show that RTS based decoding of 12 X 12 STBC from CDA and 4-QAM with 288 real dimensions achieves i) 10(-3) uncoded BER at an SNR of just 0.5 dB away from SISO AWGN performance, and ii) a coded BER performance close to within about 5 dB of the theoretical MIMO capacity, using rate-3/4 turbo code at a spectral efficiency of 18 bps/Hz. RTS is shown to achieve near SISO AWGN performance with less number of dimensions than with LAS algorithm (which we reported recently) at some extra complexity than LAS. We also report good BER performance of RTS when i.i.d fading and perfect CSIR assumptions are relaxed by considering a spatially correlated MIMO channel model, and by using a training based iterative RTS decoding/channel estimation scheme.

A Reactive Tabu Search Based Equalizer for Severely Delay-Spread UWB MIMO-ISI Channels

We propose a novel equalizer for ultrawideband (UWB) multiple-input multiple-output (MIMO) channels characterized by severe delay spreads. The proposed equalizer is based on reactive tabu search (RTS), which is a heuristic originally designed to obtain approximate solutions to combinatorial optimization problems. The proposed RTS equalizer is shown to perform increasingly better for increasing number of multipath components (MPC), and achieve near maximum likelihood (ML) performance for large number of MPCs at a much less complexity than that of the ML detector. The proposed RTS equalizer is shown to perform close to within 0.4 dB of single-input multiple-output AWGN performance at 10(-3) uncoded BER on a severely delay-spread UWB MIMO channel with 48 equal-energy MPCs.

Random-Restart Reactive Tabu Search Algorithm for Detection in Large-MIMO Systems

We present a low-complexity algorithm based on reactive tabu search (RTS) for near maximum likelihood (ML) detection in large-MIMO systems. The conventional RTS algorithm achieves near-ML performance for 4-QAM in large-MIMO systems. But its performance for higher-order QAM is far from ML performance. Here, we propose a random-restart RTS (R3TS) algorithm which achieves significantly better bit error rate (BER) performance compared to that of the conventional RTS algorithm in higher-order QAM. The key idea is to run multiple tabu searches, each search starting with a random initial vector and choosing the best among the resulting solution vectors. A criterion to limit the number of searches is also proposed. Computer simulations show that the R3TS algorithm achieves almost the ML performance in 16 x 16 V-BLAST MIMO system with 16-QAM and 64-QAM at significantly less complexities than the sphere decoder. Also, in a 32 x 32 V-BLAST MIMO system, the R3TS performs close to ML lower bound within 1.6 dB for 16-QAM (128 bps/Hz), and within 2.4 dB for 64-QAM (192 bps/Hz) at 10(-3) BER.