An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables

In this paper, we present an investigation into using fuzzy methodologies to guide the construction of high quality feasible examination timetabling solutions. The provision of automated solutions to the examination timetabling problem is achieved through a combination of construction and improvement. The enhancement of solutions through the use of techniques such as metaheuristics is, in some cases, dependent on the quality of the solution obtained during the construction process. With a few notable exceptions, recent research has concentrated on the improvement of solutions as opposed to focusing on investigating the ‘best’ approaches to the construction phase. Addressing this issue, our approach is based on combining multiple criteria in deciding on how the construction phase should proceed. Fuzzy methods were used to combine three single construction heuristics into three different pair wise combinations of heuristics in order to guide the order in which exams were selected to be inserted into the timetable solution. In order to investigate the approach, we compared the performance of the various heuristic approaches with respect to a number of important criteria (overall cost penalty, number of skipped exams, number of iterations of a rescheduling procedure required and computational time) on 12 well-known benchmark problems. We demonstrate that the fuzzy combination of heuristics allows high quality solutions to be constructed. On one of the 12 problems, we obtained lower penalty than any previously published constructive method and for all 12 we obtained lower penalty than when any of the single heuristics were used alone. Furthermore, we demonstrate that the fuzzy approach used less backtracking when constructing solutions than any of the single heuristics. We conclude that this novel fuzzy approach is a highly effective method for heuristically constructing solutions and, as such, has particular relevance to real-world situations in which the construction of feasible solutions is often a difficult task in its own right.     

A beam-search-based constructive heuristic for the PFSP to minimise total flowtime

In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the literature. The proposed algorithm is inspired in the logic of the beam search, although it remains a fast constructive heuristic.The results obtained by the proposed algorithm outperform those obtained by other constructive heuristics in the literature for the problem, thus modifying substantially the state-of-the-art of efficient approximate procedures for the problem. In addition, the proposed algorithm even outperforms two of the best metaheuristics for many instances of the problem, using much lesser computation effort. The excellent performance of the proposal is also proved by the fact that the new heuristic found new best upper bounds for 35 of the 120 instances in Taillard’s benchmark.     

ILP heuristics and a new exact method for bi-objective 0/1 ILPs: Application to FTTx-network design

Heuristics and metaheuristics are inevitable ingredients of most of the general purpose ILP solvers today, because of their contribution to the significant boost of the performance of exact methods. In the field of bi/multi-objective optimization, to the best of our knowledge, it is still not very common to integrate ILP heuristics into exact solution frameworks. This paper aims to bring a stronger attention of both the exact and metaheuristic communities to still unexplored possibilities for performance improvements of exact and heuristic multi-objective optimization algorithms.We focus on bi-objective optimization problems whose feasible solutions can be described as 0/1 integer linear programs and propose two ILP heuristics, boundary induced neighborhood search (BINS) and directional local branching. Their main idea is to combine the features and explore the neighborhoods of solutions that are relatively close in the objective space. A two-phase ILP-based heuristic framework relying on BINS and directional local branching is introduced. Moreover, a new exact method called adaptive search in objective space (ASOS) is also proposed. ASOS combines features of the ϵ-constraint method with the binary search in the objective space and uses heuristic solutions produced by BINS for guidance. Our new methods are computationally evaluated on two problems of particular relevance for the design of FTTx-networks. Comparison with other known exact methods (relying on the exploration of the objective space) is conducted on a set of realistic benchmark instances representing telecommunication access networks from Germany.     

Comparing descent heuristics and metaheuristics for the vehicle routing problem

Three improvement heuristics for the vehicle routing problem are considered: a descent heuristic and two metaheuristics Simulated Annealing and Tabu Search. In order to make an in-depth comparison of the performance of these improvement heuristics, their behavior is analyzed on a heuristic, time-sensitive level as well as on a parametric level. The design and the results of the experiments are outlined. The external validity of the conclusions is discussed.Scope and purposeTabu Search (TS) and Simulated Annealing (SA) have demonstrated to be appropriate metaheuristics for solving NP-hard combinatorial optimization problems, such as the vehicle routing problem with side-constraints. In order to compare the performances of both metaheuristics with each other and with a traditional descent implementation, a comparison of the best solution independent of computing times is fundamentally wrong because metaheuristics have no unambiguous stopping criteria, as opposed to traditional descent implementations.     

A graph coloring heuristic using partial solutions and a reactive tabu scheme

Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO-PARTIALCOL), which is based on tabu search, considers feasible but partial solutions and tries to increase the size of the current partial solution. A solution consists of k disjoint stable sets (and, therefore, is a feasible, partial k-coloring) and a set of uncolored vertices. We introduce a reactive tabu tenure which substantially enhances the performance of both our heuristic as well as the classical tabu algorithm (called TABUCOL) proposed by Hertz and de Werra [Using tabu search techniques for graph coloring, Computing 1987;39:345–51]. We will report numerical results on different benchmark graphs and we will observe that FOO-PARTIALCOL, though very simple, outperforms TABUCOL on some instances, provides very competitive results on a set of benchmark graphs which are known to be difficult, and outperforms the best-known methods on the graph flat300_28_0. For this graph, FOO-PARTIALCOL finds an optimal coloring with 28 colors. The best coloring achieved to date uses 31 colors. Algorithms very close to TABUCOL are still used as intensification procedures in the best coloring methods, which are evolutionary heuristics. FOO-PARTIALCOL could then be a powerful alternative. In conclusion FOO-PARTIALCOL is one of the most efficient simple local search coloring methods yet available.     

A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime

In recent years, a large number of heuristics have been proposed for the minimization of the total or mean flowtime/completion time of the well-known permutation flowshop scheduling problem. Although some literature reviews and comparisons have been made, they do not include the latest available heuristics and results are hard to compare as no common benchmarks and computing platforms have been employed. Furthermore, existing partial comparisons lack the application of powerful statistical tools. The result is that it is not clear which heuristics, especially among the recent ones, are the best. This paper presents a comprehensive review and computational evaluation as well as a statistical assessment of 22 existing heuristics. From the knowledge obtained after such a detailed comparison, five new heuristics are presented. Careful designs of experiments and analyses of variance (ANOVA) techniques are applied to guarantee sound conclusions. The comparison results identify the best existing methods and show that the five newly presented heuristics are competitive or better than the best performing ones in the literature for the permutation flowshop problem with the total completion time criterion.     

Hybrid Nested Partitions and Mathematical Programming Approach and Its Applications

Large-scale discrete optimization problems are difficult to solve, especially when different kinds of real constraints are considered. Conventionally, standard mathematical programming is a general approach for discrete optimization, but may suffer from the unacceptable long solution time in applications. On the other hand, some heuristics/metaheuristics methods are more powerful in finding approximate solutions efficiently, but mostly are problem and constraint dependent. In this paper, we develop a new hybrid nested partitions and mathematical programming approach, which creates compliance between mathematical programming and the heuristics/metaheuristics methods. Potentially applicable to many different types of problems, the hybrid approach can provide approximate solutions efficiently, and in the meantime can easily handle different kinds of constraints. The applications of the hybrid approach to the local pickup and delivery problem (LPDP) and the discrete facility location problem (DFLP) are presented in this paper.     

A Memetic Chaotic Gravitational Search Algorithm for unconstrained global optimization problems

Metaheuristic optimization algorithms address two main tasks in the process of problem solving: i) exploration (also called diversification) and ii) exploitation (also called intensification). Guaranteeing a trade-off between these operations is critical to good performance. However, although many methods have been proposed by which metaheuristics can achieve a balance between the exploration and exploitation stages, they are still worse than exact algorithms at exploitation tasks, where gradient-based mechanisms outperform metaheuristics when a local minimum is approximated. In this paper, a quasi-Newton method is introduced into a Chaotic Gravitational Search Algorithm as an exploitation method, with the purpose of improving the exploitation capabilities of this recent and promising population-based metaheuristic. The proposed approach, referred to as a Memetic Chaotic Gravitational Search Algorithm, is used to solve forty-five benchmark problems, both synthetic and real-world, to validate the method. The numerical results show that the adding of quasi-Newton search directions to the original (Chaotic) Gravitational Search Algorithm substantially improves its performance. Also, a comparison with the state-of-the-art algorithms: Particle Swarm Optimization, Genetic Algorithm, Rcr-JADE, COBIDE and RLMPSO, shows that the proposed approach is promising for certain real-world problems.     

Metaheuristics and cooperative approaches for the Bi-objective Ring Star Problem

This paper presents and investigates different approaches to solve a new bi-objective routing problem called the ring star problem. It consists of locating a simple cycle through a subset of nodes of a graph while optimizing two kinds of cost. The first objective is the minimization of a ring cost that is related to the length of the cycle. The second one is the minimization of an assignment cost from non-visited nodes to visited ones. In spite of its obvious bi-objective formulation, this problem has always been investigated in a single-objective way. To tackle the bi-objective ring star problem, we first investigate different stand-alone search methods. Then, we propose two cooperative strategies that combine two multi-objective metaheuristics: an elitist evolutionary algorithm and a population-based local search. We apply these new hybrid approaches to well-known benchmark test instances and demonstrate their effectiveness in comparison to non-hybrid algorithms and to state-of-the-art methods.     

New metaheuristic approaches for the edge-weighted k-cardinality tree problem

In this paper we propose three metaheuristic approaches, namely a Tabu Search, an Evolutionary Computation and an Ant Colony Optimization approach, for the edge-weighted k-cardinality tree (KCT) problem. This problem is an NP-hard combinatorial optimization problem that generalizes the well-known minimum weight spanning tree problem. Given an edge-weighted graph G=(V,E), it consists of finding a tree in G with exactly k⩽|V|−1 edges, such that the sum of the weights is minimal. First, we show that our new metaheuristic approaches are competitive by applying them to a set of existing benchmark instances and comparing the results to two different Tabu Search methods from the literature. The results show that these benchmark instances are not challenging enough for our metaheuristics. Therefore, we propose a diverse set of benchmark instances that are characterized by different features such as density and variance in vertex degree. We show that the performance of our metaheuristics depends on the characteristics of the tackled instance, as well as on the cardinality. For example, for low cardinalities the Ant Colony Optimization approach is best, whereas for high cardinalities the Tabu Search approach has advantages.     

Metaheuristics based on decision hierarchies for the traveling purchaser problem

In this paper we address the traveling purchaser problem, an NP‐hard problem that generalizes the traveling salesman problem. We present several metaheuristics that combine genetic algorithms and local search. The genetic algorithms are induced by different hierarchic orderings of the decision making regarding the route and the acquisition of the items. Computational experiments were carried out with benchmark instances and the results show that the proposed metaheuristics are a suitable tool to solve high‐dimensioned instances for which the exact methods do not provide solutions within a reasonable CPU time. For several instances, best new upper bounds for the optimum value of the objective function were obtained.     

An ant colony optimization algorithm for DNA sequencing by hybridization

The reconstruction of DNA sequences from DNA fragments is one of the most challenging problems in computational biology. In recent years the specific problem of DNA sequencing by hybridization has attracted quite a lot of interest in the optimization community. Several metaheuristics such as tabu search and evolutionary algorithms have been applied to this problem. However, the performance of existing metaheuristics is often inferior to the performance of recently proposed constructive heuristics. On the basis of these new heuristics we develop an ant colony optimization algorithm for DNA sequencing by hybridization. An important feature of this algorithm is the implementation in a so-called multi-level framework. The computational results show that our algorithm is currently a state-of-the-art method for the tackled problem.     

Population-based optimization in structural engineering: a review

Structural engineering is focused on the safe and efficient design of infrastructure. Projects can range in size and complexity, many requiring massive amounts of materials and expensive construction and operational costs. Therefore, one of the primary objectives for structural engineers is a cost-effective design. Incorporating optimality criteria into the design procedure introduces additional complexities that result in problems that are nonlinear, nonconvex, and have a discontinuous solution space. Population-based optimization algorithms (known as metaheuristics) have been found to be very efficient approaches to these problems. Many researchers have developed and applied state-of-art metaheuristics to automate and optimize the design of real-world civil engineering problems. While there is a large body of published papers in this area, there are few comprehensive reviews that list, summarize, and categorize metaheuristic optimization in structural engineering. This paper provides an extensive survey of a wide range of metaheuristic techniques to structural engineering optimization problems. Also, information is provided on available structural engineering benchmark problems, the formulation of different objective functions, and the handling of various types of constraints. The performance of different optimization techniques is compared for many benchmark problems.

     

An agent based approach for the implementation of cooperative proactive S-Metaheuristics

This paper introduces several cooperative proactive S-Metaheuristics, i.e. single-solution based metaheuristics, which are implemented taking advantage of two singular characteristics of the agent paradigm: proactivity and cooperation. Proactivity is applied to improve traditional versions of Threshold Accepting and Great Deluge Algorithm metaheuristics. This approach follows previous work for the definition of proactive versions of the Record-to-Record Travel and Local Search metaheuristics. Proactive metaheuristics are implemented as agents that cooperate in the environment of the optimization process with the goal of avoiding stagnation in local optima by adjusting their parameters. Based on the environmental information about previous solutions, the proactive adjustment of the parameters is focused on keeping a minimal level of acceptance for the new solutions. In addition, simple forms of cooperation by competition are used to develop cooperative metaheuristics based on the combination of the four proactive metaheuristics. The proposed metaheuristics have been validated through experimentation with 28 benchmark functions on binary strings, and several instances of knapsack problems and travelling salesman problems.     

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some NP-hard problems in graph and set theory via clique finding.

Many graph- and set-theoretic problems, because of their tremendous application potential and theoretical appeal, have been well investigated by the researchers in complexity theory and were found to be NP-hard. Since the combinatorial complexity of these problems does not permit exhaustive searches for optimal solutions, only near-optimal solutions can be explored using either various problem-specific heuristic strategies or metaheuristic global-optimization methods, such as simulated annealing, genetic algorithms, etc. In this paper, we propose a unified evolutionary algorithm (EA) to the problems of maximum clique finding, maximum independent set, minimum vertex cover, subgraph and double subgraph isomorphism, set packing, set partitioning, and set cover. In the proposed approach, we first map these problems onto the maximum clique-finding problem (MCP), which is later solved using an evolutionary strategy. The proposed impatient EA with probabilistic tabu search (IEA-PTS) for the MCP integrates the best features of earlier successful approaches with a number of new heuristics that we developed to yield a performance that advances the state of the art in EAs for the exploration of the maximum cliques in a graph. Results of experimentation with the 37 DIMACS benchmark graphs and comparative analyses with six state-of-the-art algorithms, including two from the smaller EA community and four from the larger metaheuristics community, indicate that the IEA-PTS outperforms the EAs with respect to a Pareto-lexicographic ranking criterion and offers competitive performance on some graph instances when individually compared to the other heuristic algorithms. It has also successfully set a new benchmark on one graph instance. On another benchmark suite called Benchmarks with Hidden Optimal Solutions, IEA-PTS ranks second, after a very recent algorithm called COVER, among its peers that have experimented with this suite.     

Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates

We consider the NP-hard problem of scheduling jobs on a single machine against common due dates with respect to earliness and tardiness penalties. The paper covers two aspects: Firstly, we develop a problem generator and solve 280 instances with two new heuristics to obtain upper bounds on the optimal objective function value. Secondly, we demonstrate computationally that our heuristics are efficient in obtaining near-optimal solutions for small problem instances. The generated problem instances in combination with the upper bounds can be used as benchmarks for future approaches in the field of common due-date scheduling.Scope and purposeIn connection with just-in-time production and delivery, earliness as well as tardiness penalties are of interest. Thus scheduling against common due dates has received growing attention during the last decade. Many algorithms have been developed to solve the different variants of this problem. But whenever a new algorithm for scheduling against common due dates is proposed, its quality is assessed only on a few self-generated examples. Hence it is difficult to evaluate the various approaches, particularly in comparison with each other. Therefore the goal of this paper is to present numerous benchmark problems together with some upper bounds on the optimal objective function value.     

Do multiple-objective metaheuristics deliver on their promises? A computational experiment on the set-covering problem

In this paper, we compare the computational efficiency of three state-of-the-art multiobjective metaheuristics (MOMHs) and their single-objective counterparts on the multiple-objective set-covering problem (MOSCP). We use a methodology that allows consistent evaluation of the quality of approximately Pareto-optimal solutions generated by of both MOMHs and single-objective metaheuristics (SOMHs). Specifically, we use the average value of the scalarization functions over a representative sample of weight vectors. Then, we compare computational efforts needed to generate solutions of approximately the same quality by the two kinds of methods. In the computational experiment, we use two SOHMs - the evolutionary algorithm (EA) and memetic algorithm (MA), and three MOMH-controlled elitist nondominated sorting genetic algorithm, the strength Pareto EA, and the Pareto MA. The methods are compared on instances of the MOSCP with 2, 3, and 4 objectives, 20, 40, 80 and 200 rows, and 200, 400, 800 and 1000 columns. The results of the experiment indicate good computational efficiency of the multiple-objective metaheuristics in comparison to their single-objective counterparts.     

Scheduling flow lines with buffers by ant colony digraph

This work starts from modeling the scheduling of n jobs on m machines/stages as flowshop with buffers in manufacturing. A mixed-integer linear programing model is presented, showing that buffers of size n ? 2 allow permuting sequences of jobs between stages. This model is addressed in the literature as non-permutation flowshop scheduling (NPFS) and is described in this article by a disjunctive graph (digraph) with the purpose of designing specialized heuristic and metaheuristics algorithms for the NPFS problem. Ant colony optimization (ACO) with the biologically inspired mechanisms of learned desirability and pheromone rule is shown to produce natively eligible schedules, as opposed to most metaheuristics approaches, which improve permutation solutions found by other heuristics. The proposed ACO has been critically compared and assessed by computation experiments over existing native approaches. Most makespan upper bounds of the established benchmark problems from Taillard (1993) and Demirkol, Mehta, and Uzsoy (1998) with up to 500 jobs on 20 machines have been improved by the proposed ACO.