Subgraph ejection chains and tabu search for the crew scheduling problem

The tabu search algorithms for the Crew Scheduling Problem (CSP) reported in this paper are part of a decision support system for crew scheduling management of the Lisbon Underground. The CPS is formulated as the minimum number of duties necessary to cover a pre-defined timetable under a set of contractual rules. An initial solution is constructed following a traditional run-cutting approach. Two alternative improvement algorithms are subsequently used to reduce the number of duties in the initial solution. Both algorithms are embedded in a tabu search framework: Tabu-crew takes advantage of a form of strategic oscillation for the neighbourhood search while the run-ejection algorithm considers compound moves based on a subgraph ejection chain method. Computational results are reported for a set of real problems.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

A tabu search tutorial based on a real-world scheduling problem

We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n ³) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).     

Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion

For the no-wait flowshop scheduling problem with maximum lateness criterion, properties are developed to speed up three kinds of basic operations generating candidate solutions, i.e., the insertion of a new job into a partial sequence, and the insertion and exchange neighborhood moves. The properties reduce the time to evaluate a candidate from O(nm)$O(\mathit{nm})$ to O  (1) and simplify the implementation of the heuristics based on the basic operations by evaluating candidates before their generation. The properties also reduce from O(n³m)$O(n^{3}m)$ to O(n²)$O(n^2)$ the time complexity of well-known NEH heuristic and the complete evaluation of the insertion and exchange neighborhoods. Tabu search (TS) is applied to the considered problem, since TS tries to find the best neighbor of the current solution in each iteration and therefore can much benefit from the speedups. Three different ways to use insertion and exchange neighborhoods are compared in TS. Computational experiments show that the speedups are more helpful as job number increases and all proposed TS algorithms are more effective and robust than the existing algorithms. Although two- and single-neighborhood TS algorithms are not significantly different, two-neighborhood TS algorithms are more preferable.     

Solving a nurse scheduling problem with knapsacks,networks and tabu search

This paper illustrates how a modern heuristic and two classical integer programming models have been combined to provide a solution to a nurse rostering problem at a major UK hospital. Neither a heuristic nor an exact approach based on a standard IP package was able to meet all the practical requirements. This was overcome by using a variant of tabu search as the core method, but applying knapsack and network flow models in pre- and post-processing phases. The result is a successful software tool that frees senior nursing staff from a time consuming administrative task.     

A tabu search experience in production scheduling

During the last four years, tabu search has been shown to be a remarkably effective method in solving difficult combinatorial optimization problems. Nowhere has this success been more marked than in the timely and very important area of production scheduling. In this paper, we review some of the research that has contributed to that success. We also give a synthesis of the various tabu search mechanisms that have been employed, giving special attention to advances that have led to major improvements. In the final section of the paper, we suggest directions for future research.     

A composite-neighborhood tabu search approach to the traveling tournament problem

The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature.     

Iterated tabu search for the car sequencing problem

This paper introduces an iterated tabu search heuristic for the daily car sequencing problem in which a set of cars must be sequenced so as to satisfy requirements from the paint shop and the assembly line. The iterated tabu search heuristic combines a classical tabu search with perturbation operators that help escape from local optima. The resulting heuristic is flexible, easy to implement, and fast. It has produced very good results on a set of test instances provided by the French car manufacturer Renault.     

A tabu search algorithm for scheduling pharmaceutical packaging operations

This paper addresses a practical scheduling problem arising in the packaging department of a pharmaceutical industrial plant. The problem is modeled as a multi-purpose machine scheduling problem with setup and removal times, release and due dates and additional constraints related to the scarce availability of tools and human operators. The objective functions are minimization of makespan and maximum tardiness in lexicographic order. Representing a solution with a directed graph allows us to devise an effective tabu search algorithm to solve the problem. Computational experiments, carried on real and randomly generated instances, show the effectiveness of this approach.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.     

Dynamic tabu search strategies for the traveling purchaser problem

Tabu search is a metastrategy for guiding known heuristics to overcome local optimality with a large number of successful applications reported in the literature. In this paper we investigate two dynamic strategies, the reverse elimination method and the cancellation sequence method. The incorporation of strategic oscillation as well as a combination of these methods are developed. The impact of the different methods is shown with respect to the traveling purchaser problem, a generalization of the classical traveling salesman problem. The traveling purchaser problem is the problem of determining a tour of a purchaser buying several items in different shops by minimizing the total amount of travel and purchase costs. A comparison of the tabu search strategies with a simulated annealing approach is presented, too.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

A tabu search algorithm for the covering design problem

A (v,k,t)-covering design is a collection of k-subsets (called blocks) of a v-set V{\mathcal{V}} such that every t-subset of V{\mathcal{V}} is contained in at least one block. Given v, k and t, the goal of the covering design problem is to find a covering made of a minimum number of blocks. In this paper, we present a new tabu algorithm for tackling this problem. Our algorithm exploits a new implementation designed in order to evaluate efficiently the performance of the neighbors of the current configuration. The new implementation is much less space-consuming than the currently used technique, making it possible to tackle much larger problem instances. It is also significantly faster. Thanks to these improved data structures, our tabu algorithm was able to improve the upper bound of more than 50 problem instances.     

Backbone guided tabu search for solving the UBQP problem

We propose a backbone-guided tabu search (BGTS) algorithm for the Unconstrained Binary Quadratic Programming (UBQP) problem that alternates between two phases: (1) a basic tabu search procedure to optimize the objective function as far as possible; (2) a strategy using the TS notion of strongly determined variables to alternately fix and free backbone components of the solutions which are estimated likely to share values in common with an optimal solution. Experimental results show that the proposed method is capable of finding the best-known solutions for 21 large random instances with 3000 to 7000 variables and boosts the performance of the basic TS in terms of both solution quality and computational efficiency.     

Multi-neighborhood tabu search for the maximum weight clique problem

Given an undirected graph G=(V,E) with vertex set V={1,??,n} and edge set E?V×V. Let w:V??Z ⁺ be a weighting function that assigns to each vertex i??V a positive integer. The maximum weight clique problem (MWCP) is to determine a clique of maximum weight. This paper introduces a tabu search heuristic whose key features include a combined neighborhood and a dedicated tabu mechanism using a randomized restart strategy for diversification. The proposed algorithm is evaluated on a total of 136 benchmark instances from different sources (DIMACS, BHOSLIB and set packing). Computational results disclose that our new tabu search algorithm outperforms the leading algorithm for the maximum weight clique problem, and in addition rivals the performance of the best methods for the unweighted version of the problem without being specialized to exploit this problem class.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

A reactive tabu search for the vehicle routing problem

The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems.     

Massively parallel tabu search for the quadratic assignment problem

A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation usesn ² processors, wheren is the size of the problem. The elements of the algorithm, calledPar_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time.     

Iterated tabu search for the circular open dimension problem

This paper investigates the circular open dimension problem (CODP), which consists of packing a set of circles of known radii into a strip of fixed width and unlimited length without overlapping. The objective is to minimize the length of the strip. In this paper, CODP is solved by a series of sub-problems, each corresponding to a fixed strip length. For each sub-problem, an iterated tabu search approach, named ITS, is proposed. ITS starts from a randomly generated solution and attempts to gain improvements by a tabu search procedure. After that, if the obtained solution is not feasible, a perturbation operator is subsequently employed to reconstruct the incumbent solution and an acceptance criterion is implemented to determine whether or not accept the perturbed solution. As a supplementary method, the length of the strip is determined in monotonously decreasing way, with the aid of some post-processing techniques. The search terminates and returns the best found solution after the allowed computation time has been elapsed. Computational experiments based on numerous well-known benchmark instances show that ITS produces quite competitive results, with respect to the best known results, while the computational time remains reasonable for each instance.