Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times

This paper addresses the problem of scheduling jobs in a single machine with sequence dependent setup times in order to minimize the total tardiness with respect to job due dates. We propose variants of the GRASP metaheuristic that incorporate memory-based mechanisms for solving this problem. There are two mechanisms proposed in the literature that utilize a long-term memory composed of an elite set of high quality and sufficiently distant solutions. The first mechanism consists of extracting attributes from the elite solutions in order to influence the construction of an initial solution. The second one makes use of path relinking to connect a GRASP local minimum with a solution of the elite set, and also to connect solutions from the elite set. Reactive GRASP, which probabilistically determines the degree of randomness in the GRASP construction throughout the iterations, is also investigated. Computational tests for instances involving up to 150 jobs are reported, and the proposed method is compared with heuristic and exact methods from the literature.     

Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic

Metaheuristics represent an important class of techniques to solve, approximately, hard combinatorial optimization problems for which the use of exact methods is impractical. Some researches have been combining machine learning techniques with metaheuristics to adaptively guide and improve the search for near optimal solutions. An example of such development is the DM-GRASP, a hybrid version of the Greedy Randomized Adaptative Search Procedures (GRASP) metaheuristic which incorporates a data mining process. In this hybrid proposal, after executing half of the total number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following half GRASP iterations in the search through the solution space. In this work, we explore new versions of the DM-GRASP metaheuristic to experiment, not a single activation, but multiple and adaptive executions of the data mining process during the metaheuristic execution. We also applied the data mining technique into a reactive GRASP to show that a more sophisticated and not memoryless GRASP approach can also benefit from the use of this technique. In order to evaluate these new proposals, we adopted the server replication for reliable multicast problem since the best known results for this problem were obtained by GRASP and DM-GRASP implementations. The computational experiments, comparing traditional GRASP, DM-GRASP, and the new proposals, showed that multiple and adaptive executions of the data mining process can improve the results obtained by the DM-GRASP hybrid metaheuristic—the new proposals were able to find better results in less computational time for the reliable multicast problem.     

Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem

A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.     

Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking

The two-echelon location-routing problem (LRP-2E) arises from recent transportation applications like city logistics. In this problem, still seldom studied, first-level trips serve from a main depot a set of satellite depots, which must be located, while second-level trips visit customers from these satellites. After a literature review on the LRP-2E, we present four constructive heuristics and a hybrid metaheuristic: A greedy randomized adaptive search procedure (GRASP) complemented by a learning process (LP) and path relinking (PR). The GRASP and learning process involve three greedy randomized heuristics to generate trial solutions and two variable neighbourhood descent (VND) procedures to improve them. The optional path relinking adds a memory mechanism by combining intensification strategy and post-optimization. Numerical tests show that the GRASP with LP and PR outperforms the simple heuristics and an adaptation of a matheuristic initially published for a particular case, the capacitated location-routing problem (CLRP). Additional tests on the CLRP indicate that the best GRASP competes with the best metaheuristics published.     

A hybrid algorithm for the manufacturing cell formation problem

In this paper we compare different heuristic methods for the manufacturing cell formation problem considering part process sequence: a GRASP algorithm, a reactive GRASP algorithm and a hybrid algorithm which combines reactive GRASP and tabu search. All algorithms are tested with a set of instances from the literature. The results from the GRASP algorithm are compared to those of the reactive GRASP in order to evaluate the advantages of automatically adjusting the parameter value within the randomized greedy procedure. Also the reactive GRASP results are compared to those of the hybrid algorithm to evaluate the contribution to solution quality of replacing the local search phase of the GRASP algorithm with tabu search.     

The maximum balanced subgraph of a signed graph: Applications and solution approaches

The Maximum Balanced Subgraph Problem (MBSP) is the problem of finding a subgraph of a signed graph that is balanced and maximizes the cardinality of its vertex set. This paper is the first one to discuss applications of the MBSP arising in three different research areas: the detection of embedded structures, portfolio analysis in risk management and community structure. The efficient solution of the MBSP is also in the focus of this paper. We discuss pre-processing routines and heuristic solution approaches to the problem. a GRASP metaheuristic is developed and improved versions of a greedy heuristic are discussed. Extensive computational experiments are carried out on a set of instances from the applications previously mentioned as well as on a set of random instances.     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

A memetic algorithm with dynamic population management for an integrated production–distribution problem

This paper studies an NP-hard multi-period production–distribution problem to minimize the sum of three costs: production setups, inventories and distribution. This problem is solved by a very recent form of metaheuristic called memetic algorithm with population management (MA∣PM). Contrary to classical two-phase methods (production planning, then distribution planning), the algorithm simultaneously tackles production and distribution decisions. Several versions with different population management strategies are evaluated and compared with a two-phase heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP), on 90 randomly generated instances with 20 periods and 50, 100 or 200 customers. The significant savings obtained compared to the two other methods confirm both the interest of integrating production and distribution decisions and of using the MA∣PM template.     

Expanding neighborhood search–GRASP for the probabilistic traveling salesman problem

The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm gives a new best solution.     

Greedy Randomized Adaptive Search Procedures

Today, a variety of heuristic approaches are available to the operations research practitioner. One methodology that has a strong intuitive appeal, a prominent empirical track record, and is trivial to efficiently implement on parallel processors is GRASP (Greedy Randomized Adaptive Search Procedures). GRASP is an iterative randomized sampling technique in which each iteration provides a solution to the problem at hand. The incumbent solution over all GRASP iterations is kept as the final result. There are two phases within each GRASP iteration: the first intelligently constructs an initial solution via an adaptive randomized greedy function; the second applies a local search procedure to the constructed solution in hope of finding an improvement. In this paper, we define the various components comprising a GRASP and demonstrate, step by step, how to develop such heuristics for combinatorial optimization problems. Intuitive justifications for the observed empirical behavior of the methodology are discussed. The paper concludes with a brief literature review of GRASP implementations and mentions two industrial applications.     

A GRASP and Path Relinking Heuristic for Rural Road Network Development

This paper presents a model for rural road network design that involves two objectives: maximize all season road connectivity among villages in a region and maximize route efficiency, while allocating a fix budget among a number of possible road projects. The problem is modeled as a bicriterion optimization problem and solved heuristically through a greedy randomized adaptive search procedure (GRASP) in conjunction with a path relinking procedure. The implementation of GRASP and path relinking includes two novel modifications, a new form of reactive GRASP and a new form of path relinking. Overall, the heuristic approach is streamlined through the incorporation of advanced network flow reoptimization techniques. Results indicate that this implementation outperforms both GRASP as well as a straightforward form of GRASP with path relinking. For small problem instances, for which optimality could be verified, this new, modified form of GRASP with path relinking solved all but one known instance optimally.     

Effective Heuristic Procedures for a Field Technician Scheduling Problem

This paper addresses a field technician scheduling problem faced by many service providers in telecommunication industry. The problem is to assign a set of jobs, at different locations with time windows, to a group of field technicians with different job skills. Such a problem can be viewed as a generalization of the well-known vehicle routing problem with time windows since technician skills need to be matched with job types. We designed and tested several heuristic procedures for solving the problem, namely a greedy heuristic, a local search algorithm, and a greedy randomized adaptive search procedure (GRASP). Our computational results indicate that GRASP is the most effective among them but requires more CPU time. However, the unique structure of GRASP allows us to exploit parallelism to achieve linear speed-up with respect to the number of machines used.     

Restart strategies for GRASP with path-relinking heuristics

GRASP with path-relinking is a hybrid metaheuristic, or stochastic local search (Monte Carlo) method, for combinatorial optimization. A restart strategy in GRASP with path-relinking heuristics is a set of iterations {i ₁, i ₂, …} on which the heuristic is restarted from scratch using a new seed for the random number generator. Restart strategies have been shown to speed up stochastic local search algorithms. In this paper, we propose a new restart strategy for GRASP with path-relinking heuristics. We illustrate the speedup obtained with our restart strategy on GRASP with path-relinking heuristics for the maximum cut problem, the maximum weighted satisfiability problem, and the private virtual circuit routing problem.     

Vehicle routing problems with time windows and multiple service workers: a systematic comparison between ACO and GRASP

This paper systematically compares an ant colony optimization (ACO) and a greedy randomized adaptive search procedure (GRASP) metaheuristic. Both are used to solve the vehicle routing problem with time windows and multiple service workers. In order to keep the results comparable, the same route construction heuristic and local search procedures are used. It is shown that ACO clearly outperforms GRASP in the problem under study. Additionally, new globally best results for the used benchmark problems are presented.     

GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times

In this work, we tackle the problem of scheduling a set of jobs on a set of non-identical parallel machines with the goal of minimising the total weighted completion times. GRASP is a multi-start method that consists of two phases: a solution construction phase, which randomly constructs a greedy solution, and an improvement phase, which uses that solution as an initial starting point. In the last few years, the GRASP methodology has arisen as a prospective metaheuristic approach to find high-quality solutions for several difficult problems in reasonable computational times. With the aim of providing additional results and insights along this line of research, this paper proposes a new GRASP model that combines the basic scheme with two significant elements that have been shown to be very successful in order to improve GRASP performance. These elements are path-relinking and evolutionary path-relinking. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

GRASP and path relinking for the matrix bandwidth minimization

In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the non-zero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a path relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with path relinking is also found to be competitive with a recently published Tabu search algorithm that is considered one of the best currently available for bandwidth minimization.     

A nonmonotone GRASP

A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP).     

Algorithms for single machine total tardiness scheduling with sequence dependent setups

We consider the problem of scheduling a single machine to minimize total tardiness with sequence dependent setup times. We present two algorithms, a problem space-based local search heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) for this problem. With respect to GRASP, our main contributions are—a new cost function in the construction phase, a new variation of Variable Neighborhood Search in the improvement phase, and Path Relinking using three different search neighborhoods. The problem space-based local search heuristic incorporates local search with respect to both the problem space and the solution space. We compare our algorithms with Simulated Annealing, Genetic Search, Pairwise Interchange, Branch and Bound and Ant Colony Search on a set of test problems from literature, showing that the algorithms perform very competitively.     

Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem

This paper studies heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree using edges that are as similar as possible. Given an undirected labelled connected graph, the minimum labelling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. This problem has been shown to be NP-hard. A Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighbourhood Search (VNS) are proposed in this paper. They are compared with other algorithms recommended in the literature: the Modified Genetic Algorithm and the Pilot Method. Nonparametric statistical tests show that the heuristics based on GRASP and VNS outperform the other algorithms tested. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristics.     

A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy

In this paper, we present a parallel greedy randomized adaptive search procedure (GRASP) for the Steiner problem in graphs. GRASP is a two-phase metaheuristic. In the first phase, solutions are constructed using a greedy randomized procedure. Local search is applied in the second phase, leading to a local minimum with respect to a specified neighborhood. In the Steiner problem in graphs, feasible solutions can be characterized by their non-terminal nodes (Steiner nodes) or by their key-paths. According to this characterization, two GRASP procedures are described using different local search strategies. Both use an identical construction procedure. The first uses a node-based neighborhood for local search, while the second uses a path-based neighborhood. Computational results comparing the two procedures show that while the node-based variant produces better quality solutions, the path-based variant is about twice as fast. A hybrid GRASP procedure combining the two neighborhood search strategies is then proposed. Computational experiments with a parallel implementation of the hybrid procedure are reported, showing that the algorithm found optimal solutions for 45 out of 60 benchmark instances and was never off by more than 4% of the optimal solution value. The average speedup results observed for the test problems show that increasing the number of processors reduces elapsed times with increasing speedups. Moreover, the main contribution of the parallel algorithm concerns the fact that larger speedups of the same order of the number of processors are obtained exactly for the most difficult problems.