A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem

The Prize Collecting Traveling Salesman Problem is a generalization of the Traveling Salesman Problem. A salesman collects a prize for each visited city and pays a penalty for each non visited city. The objective is to minimize the sum of the travel costs and penalties, but collecting a minimum pre-established amount of prizes. This problem is here addressed by a simple, but efficient tabu search approach which had improved several upper bounds of the considered instances.     

Categorized Assignment Scheduling: a Tabu Search Approach

The assignment problem (AP) and bottleneck assignment problem (BAP) are well studied in operational research literature. In this paper we consider two related problems which simultaneously generalize both AP and BAP. Unlike AP and BAP, these generalizations are strongly NP-complete. We propose two heuristics to solve these generalized problems: one based on a greedy principle and the other based on tabu search. Computational results are presented which show that these heuristics, when used together, produce good quality solutions. Our adaptation of tabu search also gives some new insight into the application of tabu search on permutation problems.     

A Tabu Search Based Approach for Solving a Class of Bilevel Programming Problems in Chemical Engineering

In this paper an approach based on the tabu search paradigm to tackle the bilevel programming problems is presented. The algorithm has been tested for a number of benchmark problems and the results obtained show superiority of the approach over the conventional methods in solving such problems.     

A Tabu Search Algorithm for Access Network Design

We present a fast tabu search method for the design of access tree networks. We connect a population of users to a set of switches using a variety of SONET channels on fiber optics links and ADM equipment at the nodes. We specifically take into account the economies of scale provided by the transmission systems and the transmission hierarchy of SONET systems.We describe in detail the parameters used for defining neighborhoods, penalty parameters, data structure and indicate how this can lead to substantial improvements of the overall computational time while providing costs lower than those of a more straightforward method. Results are provided for a set of random cases as well as for a real network.     

Single Machine Scheduling with Major and Minor Setup Times: A Tabu Search Approach

The paper deals with a single machine scheduling problem in which jobs are grouped into families that require major setup times, and where jobs within families require for processing minor setup times. The former are sequence independent and the latter have special triangular structure. The problem is to find a partition of families into batches, sequences of jobs in particular batches and a sequence of batches which minimize a general regular cost function. The tabu search algorithm for finding near-optimal schedules is proposed and results of computational experiments are presented.     

A Tabu Search Heuristic for Resource Management in Naval Warfare

Effective utilization of scarce resources, in particular weapon resources, is a prominent issue in naval anti-air warfare. In this paper, defence plans are constructed to guide the allocation and scheduling of different types of defence weapons against anti-ship missiles, subject to various physical and operational constraints. To reduce the frequency of replanning, decision trees are considered to explicitly account, in a probabilistic manner, for all possible outcomes of a particular action. A construction heuristic is first developed to generate an initial tree. A tabu search heuristic then improves this tree through the removal or addition of defence actions, followed by update operations aimed at maintaining the consistency. Numerical results obtained on scenarios with an increasing number of threats show that substantial improvements, in terms of survivability of the ship, can be obtained in reasonable computation times using tabu search.     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

A Tabu Search Algorithm for the Resource-Constrained Assignment Problem

Efficient algorithms are availabe to solve the unconstrained assignment problem. However, when resource or budgetary restrictions are imposed, the problem becomes difficult to solve. We consider such a resource-constrained assignment problem and present a tabu search heuristic to solve it. Extensive computational results are presented which establish the superiority of the proposed algorithm over the existing algorithms. Our adaptation of tabu search uses strategic oscillation, randomized short-term memory and multiple start as a means of search diversification.     

Adaptive Tabu Search for course timetabling

This paper presents an Adaptive Tabu Search algorithm (denoted by ATS) for solving a problem of curriculum-based course timetabling. The proposed algorithm follows a general framework composed of three phases: initialization, intensification and diversification. The initialization phase constructs a feasible initial timetable using a fast greedy heuristic. Then an adaptively combined intensification and diversification phase is used to reduce the number of soft constraint violations while maintaining the satisfaction of hard constraints. The proposed ATS algorithm integrates several distinguished features such as an original double Kempe chains neighborhood structure, a penalty-guided perturbation operator and an adaptive search mechanism. Computational results show the high effectiveness of the proposed ATS algorithm, compared with five reference algorithms as well as the current best known results. This paper also shows an analysis to explain which are the essential ingredients of the ATS algorithm.     

Job Shop Scheduling with Tooling Constraints: a Tabu Search Approach

Flexible manufacturing systems (FMSs) are automated factories in which many different part types are produced simultaneously. The tool-loading problem now adds further to the delicate task of finding an optimal schedule for such systems. In this paper, a tabu search approach is developed to solve the job shop scheduling problem with tooling constraints.     

A Tabu Search heuristic procedure in Markov chain bootstrapping

Markov chain theory is proving to be a powerful approach to bootstrap finite states processes, especially where time dependence is non linear. In this work we extend such approach to bootstrap discrete time continuous-valued processes. To this purpose we solve a minimization problem to partition the state space of a continuous-valued process into a finite number of intervals or unions of intervals (i.e. its states) and identify the time lags which provide “memory” to the process. A distance is used as objective function to stimulate the clustering of the states having similar transition probabilities. The problem of the exploding number of alternative partitions in the solution space (which grows with the number of states and the order of the Markov chain) is addressed through a Tabu Search algorithm. The method is applied to bootstrap the series of the German and Spanish electricity prices. The analysis of the results confirms the good consistency properties of the method we propose.     

A Tabu Search Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…     

Tabu Search for Frequency Assignment in Mobile Radio Networks

The main goal of the Frequency Assignment Problem in mobile radio networks consists of assigning a limited number of frequencies to each radio cell in a cellular network while minimizing electromagnetic interference due to the reuse of frequencies. This problem, known to be NP-hard, is of great importance in practice since better solutions will allow a telecommunications operator to manage larger cellular networks. This paper presents a new Tabu Search algorithm for this application. The algorithm is tested on realistic and large problem instances and compared with other methods based on simulated annealing, constraint programming and graph coloring algorithms. Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances.     

Cooperative Parallel Tabu Search for Capacitated Network Design

We present a cooperative parallel tabu search method for the fixed charge, capacitated, multicommodity network design problem. Several communication strategies are analyzed and compared. The resulting parallel procedure displays excellent performances in terms of solution quality and solution times. The experiments show that parallel implementations find better solutions than sequential ones. They also show that, when properly designed and implemented, cooperative search outperforms independent search strategies, at least on the class of problems of interest here.     

Tabu Search for the planar three-index assignment problem

Tabu Search is a very effective method for approximately solving hard combinatorial problems. In the current work we implement Tabu Search for solving the Planar Three-Index Assignment Problem. The problem deals with finding the minimum cost assignment between elements of three distinct sets demanding that every pair of elements, each representing a different set, appears in the same solution exactly once. The solutions of the problems correspond to Latin squares. These structures form the basis of the move generation mechanism employed by the Tabu Search procedures. Standard Tabu Search ideas such as candidate move list, variable tabu list size, and frequency-based memory are tested. Computational results for a range of problems of varying dimensions are presented.     

Design and Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling

Using a simple multiprocessor scheduling problem as a vehicle, we explore the behavior of tabu search algorithms using different tabu, local search and list management strategies. We found that random blocking of the tail of the tabu list always improved performance; but that the use of frequency-based penalties to discourage frequently selected moves did not. Hash coding without conflict resolution was an effective way to represent solutions on the tabu list. We also found that the most effective length of the tabu list depended on features of the algorithm being used, but not on the size and complexity of the problem being solved. The best combination of features included random blocking of the tabu list, tasks as tabus and a greedy local search. An algorithm using these features was found to outperform a recently published algorithm solving a similar problem.     

TSpack: A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems

We present a computer code that implements a general Tabu Search technique for the solution of two- and three-dimensional bin packing problems, as well as virtually any of their variants requiring the minimization of the number of bins. The user is only requested to provide a procedure that gives an approximate solution to the actual variant to be solved.     

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

Enhanced Adjacent Extreme-point Search and Tabu Search for the Minimum Concave-cost Uncapacitated Transshipment Problem

Practicable methods for optimising concave-cost, uncapacitated transshipment networks are non exact. In this paper, one such effective method, that of adjacent extreme point search, is further developed to enhance its overall computational efficiency. The enhanced search algorithm is then imbedded in a tabu search scheme which proved capable of finding better solutions, by a wide margin in some instances. Another tabu search scheme, somewhat inferior in terms of solution quality but computationally more efficient, is also developed to provide an alternative solution vehicle for larger networks. Results of extensive computational testing are included.