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 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.     

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.     

Bounds and Tabu Search for a Cyclic Max-Min Scheduling Problem

A cyclic scheduling problem with applications to transport efficiency is considered. Given a set of regular polygons, whose vertices represent regularly occurring events and are lying on a common circle line, the objective is to maximize the distance between the closest vertices of different polygons on the circle line. Lower and upper bounds for the optimal solution of this NP-hard scheduling problem are presented. They are used to improve the quality of a procedure which is applied to solve this problem heuristically. It consists of a greedy starting algorithm and a Tabu Search algorithm. The numerical results show the efficiency of the procedure proposed.     

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.     

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.     

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.     

Solution of the Cumulative Assignment Problem With a Well-Structured Tabu Search Method

The Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.     

No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems

This paper deals with the no-wait job shop problem with a makespan objective. We present some new theoretical properties on the complexity of subproblems associated with a well-known decomposition approach. Justified by the complexity results, we implement a fast tabu search algorithm for the problem at hand. It is extensively tested on known benchmark instances and compares favorably to the best existing algorithms for the no-wait job shop as well as the no-wait flow shop.     

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.     

Efficient Filtering and Tabu Search on a Consistent Neighbourhood for the Frequency Assignment Problem with Polarisation

This article presents a specific filtering algorithm for the Frequency Assignment Problem with Polarisation, which combines arc-consistency and path-inverse-consistency adapted to the specificities of the constraints. The effectiveness of this filtering algorithm enabled us to improve the Tabu Search on a Consistent Neighbourhood (CN-Tabu) using two different approaches. So, after a short recall of this general methodology and a presentation of its obtained results on the FAPP, we propose a behavioural study of the two approaches by comparing the results.     

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.     

求解带组换装时间单机调度问题的禁忌搜索算法

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.     

A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland

In this paper, we consider a real-life vehicle routeing problem that occurs in a major Swiss company producing pet food and flour. In contrast with usual hypothetical problems, a large variety of restrictions has to be considered. The main constraints are relative to the accessibility and the time windows at customers, the carrying capacities of vehicles, the total duration of routes and the drivers' breaks. To find good solutions to this problem, we propose two heuristic methods: a fast straightforward insertion procedure and a method based on tabu search techniques. Next, the produced solutions are compared with the routes actually covered by the company. Our outcomes indicate that the total distance travelled can be reduced significantly when such methods are used.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

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 Heuristic for a Full-Load, Multi-Terminal, Vehicle Scheduling Problem with Backhauling and Time Windows

The problem considered is the full-load pickup and delivery problem with time windows (PDPTW), and heterogeneous products and vehicles, where the assignment of pickup points to requests is not predetermined. Elements associated with tabu search, such as diversification by reversion to junctions and the use of soft aspiration criteria, are embedded into our tabu search implementation. This metaheuristic is evaluated using random instances and selected data from a construction company in the U.K. The obtained results are compared against lower bounds from LP relaxation and also solutions from an existing multi-level heuristic.     

On the Convergence of Tabu Search

The Tabu Search (TS) meta-heuristic has proved highly successful for solving combinatorial and nonlinear problems. A key aspect of TS consists of using adaptive forms of memory to forbid the search process to revisit solutions already examined unless the trajectory to reach it is different. In Glover (ORSA Journal on Computing, 1990, 2, 4–32) a special memory design was proposed together with a choice rule for handling the situation where the method was compelled to revisit solutions already encountered. This proposal, which specified the exploration should resume from the earliest solution visited in the past, as accompanied by the conjecture that such a choice has implications for finiteness in the zero-one integer program and optimal set membership examples. Up to now numerous applications of TS in various areas of research are available, however, we are aware of only a few results concerning the convergence of TS. In this paper, we prove that Glover's conjecture is true if the neighborhood employed is strongly connected, yielding a reversible path from each solution to every other solution.     

Protein Conformation of a Lattice Model Using Tabu Search

We apply tabu search techniques to the problem of determining the optimal configuration of a chain of protein sequences on a cubic lattice. The problem under study is difficult to solve because of the large number of possible conformations and enormous amount of computations required. Tabu search is an iterative heuristic procedure which has been shown to be a remarkably effective method for solving combinatorial optimization problems. In this paper, an algorithm is designed for the cubic lattice model using tabu search. The algorithm has been tested on a chain of 27 monomers. Computational results show that our method outperforms previously reported approaches for the same model.     

Parallelizing Tabu Search on a Cluster of Heterogeneous Workstations

In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation.