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.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

GRASP with path relinking for the orienteering problem

In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adaptive Search Procedure (GRASP) and the Path Relinking methodologies—for finding approximate solutions to this optimization problem. We explore different constructive methods and combine two neighbourhoods in the local search of GRASP. Our experimentation with 196 previously reported instances shows that the proposed procedure obtains high-quality solutions employing short computing times.     

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.     

Solving the weighted MAX-SAT problem using the dynamic convexized method

Satisfiability (SAT) and maximum satisfiability (MAX-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper we investigate the performance of the dynamic convexized method based heuristics on the weighted MAX-SAT problem. We first present an auxiliary function which is constructed based on a penalty function, and minimize the function by a local search method which can escape successfully from previously converged local minimizers by increasing the value of a parameter. Two algorithms of the approach are implemented and compared with the Greedy Randomized Adaptive Search Procedure (GRASP) and the GRASP with Path Relinking (GRASP + PR). Experimental results illustrate efficient and faster convergence of our two algorithms.     

Piecewise Linear Time Series Estimation with GRASP

This paper describes a heuristic to build piecewise linear statistical models with multivariate thresholds, based on a Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is an iterative randomized sampling technique that has been shown to quickly produce good quality solutions for a wide variety of optimization problems. In this paper we describe a GRASP to sequentially split an n-dimensional space in order to build a piecewise linear time series model.     

A Set of Greedy Randomized Adaptive Local Search Procedure (GRASP) Implementations for the Multidimensional Assignment Problem

The focal problem for centralized multisensor multitarget tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Large classes of these association problems can be formulated as multidimensional assignment problems, which are known to be NP-hard for three dimensions or more. The assignment problems that result from tracking are large scale, sparse and noisy. Solution methods must execute in real-time. The Greedy Randomized Adaptive Local Search Procedure (GRASP) has proven highly effective for solving many classes NP-hard optimization problems. This paper introduces four GRASP implementations for the multidimensional assignment problem, which are combinations of two constructive methods (randomized reduced cost greedy and randomized max regret) and two local search methods (two-assignment-exchange and variable depth exchange). Numerical results are shown for a two random problem classes and one tracking problem class.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.     

An improved heuristic for the far from most strings problem

The Far From Most Strings Problem (FFMSP) asks for a string that is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are far if their Hamming distance is greater than or equal to a given threshold. FFMSP belongs to the class of sequence consensus problems which have applications in molecular biology, amongst others. FFMSP is NP-hard. It does not admit a constant-ratio approximation either, unless P=NP. In the last few years, heuristic and metaheuristic algorithms have been proposed for the problem, which use local search and require a heuristic, also called an evaluation function, to evaluate candidate solutions during local search. The heuristic function used, for this purpose, in these algorithms is the problem’s objective function. However, since many candidate solutions can be of the same objective value, the resulting search landscape includes many points which correspond to local maxima. In this paper, we devise a new heuristic function to evaluate candidate solutions. We then incorporate the proposed heuristic function within a Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic originally proposed for the problem by Festa. The resulting algorithm outperforms state-of-the-art with respect to solution quality, in some cases by orders of magnitude, on both random and real data in our experiments. The results indicate that the number of local optima is considerably reduced using the proposed heuristic.     

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.     

Fixed set search applied to the multi-objective minimum weighted vertex cover problem

Journal of Heuristics - The Fixed Set Search (FSS) is a novel metaheuristic that adds a learning mechanism to the Greedy Randomized Adaptive Search Procedure (GRASP). In recent publications, its...     

An improved multi-staged algorithmic process for the solution of the examination timetabling problem

The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition () is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.     

Applying GRASP to solve the multi-item three-echelon uncapacitated facility location problem

This paper considers a production–distribution problem that consists of defining the flow of produced products from manufacturing plants to clients (markets) via a set of warehouses. The problem also consists of defining the location of such warehouses that have unlimited storage capacity. This problem is known in the literature as the three-echelon uncapacitated facility location problem (TUFLP), and is known to be NP-hard when the objective function is to minimize the total cost of warehouse location and production and distribution of products. This paper proposes a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the multi-item version of the TUFLP. Computational experiments are conducted using known instances from the literature. Solutions obtained using GRASP are compared against both optimal solutions and lower bounds obtained using mathematical programming. Results show that proposed algorithm performs well, obtaining good solutions (and even the optimal values) in less computational time than the mixed-integer linear programming model.     

团队成员选择的模型及算法

本针对组织中组建团队或重组现有团队时的成员选择问题，提出了反映团队成员之间、成员和团队之间关系的群体效用模型，并根据此模型进行团队成员的选择，从而把团队成员选择问题转化为一个组合优化问题。证明了基于群体效用模型进行团队成员选择的问题是NP-hard问题，并且提出了基于ORASP技术和禁忌算法的启发式算法，最后给出了算例。     

A GRASP-based approach for technicians and interventions scheduling for telecommunications

The Technicians and Interventions Scheduling Problem for Telecommunications embeds the scheduling of interventions, the assignment of teams to interventions and the assignment of technicians to teams. Every intervention is characterized, among other attributes, by a priority. The objective of this problem is to schedule interventions such that the interventions with the highest priority are scheduled at the earliest time possible while satisfying a set of constraints like the precedence between some interventions and the minimum number of technicians needed with the required skill levels for the intervention. We present a Greedy Randomized Adaptive Search Procedure (GRASP) for solving this problem. In the proposed implementation, we integrate learning to the GRASP framework in order to generate good-quality solutions using information brought by previous ones. We also compute lower bounds and present experimental results that validate the effectiveness of this approach.     

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.     

Tabu Search with Simple Ejection Chains for Coloring Graphs

We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP).     

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.     

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.