A comprehensive review and evaluation of permutation flowshop heuristics

In this work we present a review and comparative evaluation of heuristics and metaheuristics for the well-known permutation flowshop problem with the makespan criterion. A number of reviews and evaluations have already been proposed. However, the evaluations do not include the latest heuristics available and there is still no comparison of metaheuristics. Furthermore, since no common benchmarks and computing platforms are used, the results cannot be generalised. We propose a comparison of 25 methods, ranging from the classical Johnson's algorithm or dispatching rules to the most recent metaheuristics, including tabu search, simulated annealing, genetic algorithms, iterated local search and hybrid techniques. For the evaluation we use the standard test of Taillard [Eur. J. Operation. Res. 64 (1993) 278] composed of 120 instances of different sizes. In the evaluations we use the experimental design approach to obtain valid conclusions on the effectiveness and efficiency of the different methods tested.     

Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks

Variable neighborhood search (VNS) and Greedy randomized adaptive search procedure (GRASP) are among the well studied local search based metaheuristics providing good results for many combinatorial optimization problems throughout the last decade. While they are usually explored in different environments one may encounter quite obvious commonalities. Based on previous successful applications of these two types of metaheuristics on various network design problems in telecommunications, we further enhance these approaches by incorporating ideas from the pilot method. The different heuristics are compared among each other as well as against objective function values obtained from a mathematical programming formulation based on a commercial solver. The problem instances cover a large variety of networks and demand patterns.     

Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls

Metaheuristics are a class of approximate methods designed to solve hard combinatorial optimization problems arising within various different areas. The importance of metaheuristics results from their ability to continue the search beyond a local optimum so that near-optimal or optimal solutions are efficiently found. In order to solve the backhauling problem associated with mixed and simultaneous delivery and pick-ups, this paper presents a hybrid algorithm which is comprised of the two metaheuristics of tabu search and variable neighbourhood descent. The primary challenge associated with backhauling consists of creating routes in which vehicles are not only required to deliver goods, but also to perform pick-ups at customer locations. The problems associated with these two categories of problems, however, have received little attention in the literature to date. A set of examples taken from the literature with Euclidean cost matrices are presented. Finally, some numerical results are illustrated to show the effectiveness of the proposed approach.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

A variable neighborhood search for graph coloring

Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial solution which improve each time the value of an objective function until a local optimum is found. Several metaheuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this new method to the graph coloring problem.     

Ant colony optimization and local search for bin packing and cutting stock problems

The Bin Packing Problem and the Cutting Stock Problem are two related classes of NP-hard combinatorial optimization problems. Exact solution methods can only be used for very small instances, so for real-world problems, we have to rely on heuristic methods. In recent years, researchers have started to apply evolutionary approaches to these problems, including Genetic Algorithms and Evolutionary Programming. In the work presented here, we used an ant colony optimization (ACO) approach to solve both Bin Packing and Cutting Stock Problems. We present a pure ACO approach, as well as an ACO approach augmented with a simple but very effective local search algorithm. It is shown that the pure ACO approach can compete with existing evolutionary methods, whereas the hybrid approach can outperform the best-known hybrid evolutionary solution methods for certain problem classes. The hybrid ACO approach is also shown to require different parameter values from the pure ACO approach and to give a more robust performance across different problems with a single set of parameter values. The local search algorithm is also run with random restarts and shown to perform significantly worse than when combined with ACO.     

The generalized balanced academic curriculum problem with heterogeneous classes

We propose an extension of the Generalized Balanced Academic Curriculum Problem (GBACP), a relevant planning problem arising in many universities. The problem consists of assigning courses to teaching terms and years, satisfying a set of precedence constraints and balancing students’ load among terms. Differently from the original GBACP formulation, in our case, the same course can be assigned to different years for different curricula (i.e., the predetermined sets of courses from which a student can choose), leading to a more complex solution space. The problem is tackled by both Integer Programming (IP) methods and combinations of metaheuristics based on local search. The experimental analysis shows that the best results are obtained by means of a two-stage metaheuristic that first computes a solution for the underlying GBACP and then refines it by searching in the extended solution space.     

Landscape analysis and efficient metaheuristics for solving the n-queens problem

The n-queens problem is a classical combinatorial optimization problem which has been proved to be NP-hard. The goal is to place n non-attacking queens on an n×n chessboard. In this paper, two single-solution-based (Local Search (LS) and Tuned Simulated Annealing (SA)) and two population-based metaheuristics (two versions of Scatter Search (SS)) are presented for solving the problem. Since parameters of heuristic and metaheuristic algorithms have great influence on their performance, a TOPSIS-Taguchi based parameter tuning method is proposed, which not only considers the number of fitness function evaluations, but also aims to minimize the runtime of the presented metaheuristics. The performance of the suggested approaches was investigated through computational analyses, which showed that the Local Search method outperformed the other two algorithms in terms of average runtimes and average number of fitness function evaluations. The LS was also compared to the Cooperative PSO (CPSO) and SA algorithms, which are currently the best algorithms in the literature for finding the first solution to the n-queens problem, and the results showed that the average fitness function evaluation of the LS is approximately 21 and 8 times less than that of SA and CPSO, respectively. Also, a fitness analysis of landscape for the n-queens problem was conducted which indicated that the distribution of local optima is uniformly random and scattered over the search space. The landscape is rugged and there is no significant correlation between fitness and distance of solutions, and so a local search heuristic can search a rugged plain landscape effectively and find a solution quickly. As a result, it was statistically and analytically proved that single-solution-based metaheuristics outperform population-based metaheuristics in finding the first solution of the n-queens problem.     

An effective greedy heuristic for the Social Golfer Problem

The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone. In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark instances from the literature.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems

In the last few years, a significant number of multi-objective metaheuristics have been proposed in the literature in order to address real-world problems. Local search methods play a major role in many of these metaheuristic procedures. In this paper, we adapt a recent and popular indicator-based selection method proposed by Zitzler and Künzli in 2004, in order to define a population-based multi-objective local search. The proposed algorithm is designed in order to be easily adaptable, parameter independent and to have a high convergence rate. In order to evaluate the capacity of our algorithm to reach these goals, a large part of the paper is dedicated to experiments. Three combinatorial optimisation problems are tested: a flow shop problem, a ring star problem and a nurse scheduling problem. The experiments show that our algorithm can be applied with success to different types of multi-objective optimisation problems and that it outperforms some classical metaheuristics. Furthermore, the parameter sensitivity analysis enables us to provide some useful guidelines about how to set the parameters.     

Approximations and Randomization to Boost CSP Techniques

In recent years we have seen an increasing interest in combining constraint satisfaction problem (CSP) formulations and linear programming (LP) based techniques for solving hard computational problems. While considerable progress has been made in the integration of these techniques for solving problems that exhibit a mixture of linear and combinatorial constraints, it has been surprisingly difficult to successfully integrate LP-based and CSP-based methods in a purely combinatorial setting. Our approach draws on recent results on approximation algorithms based on LP relaxations and randomized rounding techniques, with theoretical guarantees, as well on results that provide evidence that the runtime distributions of combinatorial search methods are often heavy-tailed. We propose a complete randomized backtrack search method for combinatorial problems that tightly couples CSP propagation techniques with randomized LP-based approximations. We present experimental results that show that our hybrid CSP/LP backtrack search method outperforms the pure CSP and pure LP strategies on instances of a hard combinatorial problem.     

Metaheuristics for multiobjective optimisation

This is a summary of the author’s PhD thesis supervised by Laetitia Jourdan and El-Ghazali Talbi and defended on 8 December 2009 at the Université Lille 1. The thesis is written in French and is available from . This work deals with the design, implementation and experimental analysis of metaheuristics for solving multiobjective optimisation problems, with a particular interest on hard and large combinatorial problems from the field of logistics. After focusing on a unified view of multiobjective metaheuristics, we propose new cooperative, adaptive and parallel approaches. The performance of these methods are experimented on a scheduling and a routing problem involving two or three objective functions. We finally discuss how to adapt such metaheuristics during the search process in order to handle uncertainty that may occur from many different sources.     

Enhancing the performance of constraint programming through the introduction of linear programming

Constraint Programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer Programming (IP), can still give a better performance on the same problem types. Central to IP's success is its reliance on a fast Linear Programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IP. Overall, CP+LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.     

A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem

This paper presents a genetic algorithms (GA) simulation approach in solving a multi-attribute combinatorial dispatching (MACD) decision problem in a flow shop with multiple processors (FSMP) environment. The simulation is capable of modeling a non-linear and stochastic problem. GA are one of the commonly used metaheuristics and are a proven tool for solving complex optimization problems. The proposed GA simulation approach addresses a complex MACD problem. Its solution quality is illustrated by a case study from a multi-layer ceramic capacitor (MLCC) manufacturing plant. Because GA search results are often sensitive to the search parameters, this research optimized the GA parameters by using regression analysis. Empirical results showed that the GA simulation approach outperformed several commonly used dispatching rules. The improvements are ranging from 33% to 61%. On the other hand, the increased shop-floor-control complexity may hinder the implementation of the system. Finally, future research directions are discussed.     

DC-GRASP: directing the search on continuous-GRASP

Several papers in the scientific literature use metaheuristics to solve continuous global optimization. To perform this task, some metaheuristics originally proposed for solving combinatorial optimization problems, such as Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search and Simulated Annealing, among others, have been adapted to solve continuous global optimization problems. Proposed by Hirsch et al., the Continuous-GRASP (C-GRASP) is one example of this group of metaheuristics. The C-GRASP is an adaptation of GRASP proposed to solve continuous global optimization problems under box constraints. It is simple to implement, derivative-free and widely applicable method. However, according to Hedar, due to its random construction, C-GRASP may fail to detect promising search directions especially in the vicinity of minima, which may result in a slow convergence. To minimize this problem, in this paper we propose a set of methods to direct the search on C-GRASP, called Directed Continuous-GRASP (DC-GRASP). The proposal is to combine the ability of C-GRASP to diversify the search over the space with some efficient local search strategies to accelerate its convergence. We compare the DC-GRASP with the C-GRASP and other metaheuristics from literature on a set of standard test problems whose global minima are known. Computational results show the effectiveness and efficiency of the proposed methods, as well as their ability to accelerate the convergence of the C-GRASP.     

Recovering Beam Search: Enhancing the Beam Search Approach for Combinatorial Optimization Problems

A hybrid heuristic method for combinatorial optimization problems is proposed that combines different classical techniques such as tree search procedures, bounding schemes and local search. The proposed method enhances the classic beam search approach by applying to each partial solution corresponding to a node selected by the beam, a further test that checks whether the current partial solution is dominated by another partial solution at the same level of the search tree. If this is the case, the latter solution becomes the new current partial solution. This step allows to partially recover from previous wrong decisions of the beam search procedure and can be seen as a local search step on the partial solution. We present here the application to two well known combinatorial optimization problems: the two-machine total completion time flow shop scheduling problem and the uncapacitated p-median location problem. In both cases the method strongly improves the performances with respect to the basic beam search approach and is competitive with the state of the art heuristics.     

Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times

The Job Shop Scheduling Problem (JSP) is an example of a combinatorial optimization problem that has interested researchers for several decades. In this paper we confront an extension of this problem called JSP with Sequence Dependent Setup Times (SDST-JSP). The approach extends a genetic algorithm and a local search method that demonstrated to be efficient in solving the JSP. For local search, we have formalized neighborhood structures that generalize three well-know structures defined for the JSP. We have conducted an experimental study across conventional benchmark instances showing that the genetic algorithm exploited in combination with the local search, considering all three neighborhoods at the same time, provides the best results. Moreover, this approach outperforms the current state-of-the-art methods.     

A recipe for finding good solutions to MINLPs

Finding good (or even just feasible) solutions for Mixed-Integer Nonlinear Programming problems independently of the specific problem structure is a very hard but practically important task, especially when the objective and/or the constraints are nonconvex. With this goal in mind, we present a general-purpose heuristic based on Variable Neighborhood Search, Local Branching, a local Nonlinear Programming algorithm and Branch-and-Bound. We test the proposed approach on MINLPLib, comparing with several existing heuristic and exact methods. An implementation of the proposed heuristic is freely available and can employ all NLP/MINLP solvers with an AMPL interface as the main search tools.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.