A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this paper, we consider minimizing the total weighted earliness and tardiness with a restrictive common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this paper, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature.     

A population-based variable neighborhood search for the single machine total weighted tardiness problem

This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of all jobs. This problem is known to be strongly NP-hard, and thus provides a challenging area for metaheuristics. A population-based variable neighborhood search (PVNS) algorithm is developed to solve it. This algorithm differs from the basic variable neighborhood search (VNS). First, the PVNS consists of a number of iterations of the basic VNS, and in each iteration a population of solutions is used to simultaneously generate multiple trial solutions in a neighborhood so as to improve the search diversification. Second, the PVNS adopts a combination of path-relinking, variable depth search and tabu search to act as the local search procedure so as to improve the search intensification. Computational experiments show that the proposed PVNS algorithm can obtain the optimal or best known solutions within a reasonable computation time for all standard benchmark problem instances from the literature.     

A parallel variable neighborhood search approach for the obnoxious p‐median problem

The obnoxious p‐median problem consists of selecting p locations, considered facilities, in a way that the sum of the distances from each nonfacility location, called customers, to its nearest facility is maximized. This is an ‐hard problem that can be formulated as an integer linear program. In this paper, we propose the application of a variable neighborhood search (VNS) method to effectively tackle this problem. First, we develop new and fast local search procedures to be integrated into the basic VNS methodology. Then, some parameters of the algorithm are tuned in order to improve its performance. The best VNS variant is parallelized and compared with the best previous methods, namely branch and cut, tabu search, and GRASP over a wide set of instances. Experimental results show that the proposed VNS outperforms previous methods in the state of the art. This fact is finally confirmed by conducting nonparametric statistical tests.     

A parallel hybrid metaheuristic for bicluster editing

The bicluster editing problem (BEP) consists of editing (adding or removing) the edges of a bipartite graph G in order to transform it into a vertex‐disjoint union of complete bipartite subgraphs, in such a way that the sum of the weights of the edited edges is minimum. In this paper, we propose five parallel strategies for the implementation of a hybrid metaheuristic for the BEP, consisting of a GRASP with VNS as local search. Computational experiments show near‐linear speedups on Linux cluster with 64 processors and better solutions than those of the sequential approach.     

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.     

The strategies and parameters of tabu search for job-shop scheduling

This paper presents a tabu search approach for the job-shop scheduling problem. Although the problem is NP-hard, satisfactory solutions have been obtained recently by tabu search. However, tabu search has a problem-specific and parametric structure. Therefore, in the paper, we focussed on the tabu search strategies and parameters such as initial solution, neighborhood structure, tabu list, aspiration criterion, elite solutions list, intensification, diversification and the number of iteration. In order to compare some neighborhood strategies and tabu list length methods, a computational study is done on the benchmark problems.     

A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems

This paper investigates the first hybrid scatter search and path relinking meta-heuristic for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. The underpinning mathematic model of the DCLC multicast routing problem is the constrained Steiner tree problem in graphs, a well known NP-complete problem. After combining a path relinking method as the solution combination method in scatter search, we further explore two improvement strategies: tabu search and variable neighborhood search, to intensify the search in the hybrid scatter search algorithm. A large number of simulations on some benchmark instances from the OR-library and a group of random graphs of different characteristics demonstrate that the improvement strategy greatly affects the performance of the proposed scatter search algorithm. The hybrid scatter search algorithm intensified by a variable neighborhood descent search is highly efficient in solving the DCLC multicast routing problem in comparison with other algorithms and heuristics in the literature.     

Genetic-variable neighborhood search with thread replication for mobile cloud computing

The resource-intensive resettlement procedure and inherent restrictions of the wireless medium obstruct the understanding of faultless implementation in mobile cloud computing (MCC) surroundings. In MCC, transfer of thread execution to high end servers allows the processing of those jobs which demand more resources on the mobile equipment. Hence, implementing the application with stumpy cost, least overhead and non-obtrusive relocation is a demanding research area in MCC. Many scheduling mechanisms have been proposed so far to balance the load between the given set of mobile servers, but it is found to be NP-Hard problem. Therefore, evolutionary techniques are required to balance the load among mobile servers. Genetic Algorithm (GA) has been verified to be fine by jumble up the key values, but it becomes unsuccessful to strengthen the exploration in the rising areas. In Variable Neighborhood Search (VNS), local exploration technique is implemented continually to evaluate optimistic outcomes in neighborhood to attain local best solution. But VNS is still prone to premature convergence traps only because of limited search capability. Therefore hybridization with non-global finding techniques may conquer the limitations and guide the dominant search mechanisms to some extent. The GA along with VNS using thread replication (GVNSTR) is implemented to set stability of non-local searching and local utilization for an evolutionary processing period and get the optimized solution.     

Genetic algorithms, path relinking, and the flowshop sequencing problem

In a previous paper, a simple genetic algorithm (GA) was developed for finding (approximately) the minimum makespan of the n-job, m-machine permutation flowshop sequencing problem (PFSP). The performance of the algorithm was comparable to that of a naive neighborhood search technique and a proven simulated annealing algorithm. However, recent results have demonstrated the superiority of a tabu search method in solving the PFSP. In this paper, we reconsider the implementation of a GA for this problem and show that by taking into account the features of the landscape generated by the operators used, we are able to improve its performance significantly.     

Optimal sub-tree scheduling for wireless sensor networks with partial coverage

In this paper, we consider the problem of scheduling optimal sub-trees at different time intervals for wireless sensor network (WSN) communications with partial coverage. More precisely, we minimize the total power consumption of the network while taking into account time dimension and multichannel diversity where different disjoint subsets of nodes are required to be active and connected under a tree topology configuration. Optimization problems of these types may arise when designing new wireless communication protocols in order to increase network lifetime. We propose mixed integer quadratic and linear programming (resp. MIQP and MILP) models to compute optimal solutions for the problem. Subsequently, we propose Kruskal-based variable neighborhood search (VNS) and simulated annealing (SA) meta-heuristic procedures. In particular, we introduce a new embedded guided local search strategy in our VNS algorithm to further strengthen the solutions obtained. Our numerical results indicate that some of the proposed models allow to obtain optimal solutions with CPLEX in significantly less CPU time. Similarly, VNS and SA algorithms proved to be highly efficient when compared to the optimal solutions and allow to obtain near optimal solutions for large instances. In particular, VNS and guided VNS strategies allow to obtain solutions in less CPU time whilst SA methods can reach better solutions at higher CPU times. Finally, optimizing over time dimension allows one to obtain important reductions in power savings which has never been reported before in the literature.     

Implementing and testing the tabu cycle and conditional probability methods

The purpose of this paper is to describe the implementation and testing of the tabu cycle method and two variants of the conditional probability method. These methods were originally described in Glover and Laguna [Tabu search. Boston: Kluwer Academic Publishers; 1997] but have been largely ignored in the tabu search literature. For the purpose of testing, we employ a single-attribute implementation of a short-term memory procedure for the solution of a single machine scheduling problem. Computational experiments that employ instances with up to 200 jobs reveal the usefulness of the tabu cycle and the conditional probability methods as viable alternatives for managing the short-term memory in a tabu search implementation.     

Local Search Algorithms for the Maximal Planar Layout Problem

The problem of laying out facilities is practically important in a modern manufacturing environment. This problem can be formulated as a weighted maximal planar graph in which vertices represent facilities and edge weights represent desirability measures between facilities. The objective is to find a planar graph that can be drawn on a plane without any edges intersecting with the highest sum of edge weights. Exact solution method can only solve small sized problems. In this paper, local search algorithms based on steepest ascent, hybrid simulated annealing and tabu search with a non-monotonic cooling schedule, and tabu search with a hashing function are developed to obtain near-optimal solutions. Different search strategies are investigated. All the developed algorithms are compared with existing construction methods and a branch and bound exact algorithm on a set of practical size problems. The proposed algorithms performed very well in terms of solution quality and computation time.     

An adaptive tabu search algorithm for the capacitated clustering problem

In the Capacitated Clustering Problem, a given set of customers with distinct demands must be partitioned into p clusters with limited capacities. The objective is to find p customers, called medians, from which the sum of the distances to all other customers in the cluster is minimized. In this article, a new adaptive tabu search approach is applied to solve the problem. Initial solutions are obtained by four constructive heuristics that use weights and distances as optimization criteria. Two neighborhood generation mechanisms are used by the local search heuristic: pairwise interchange and insertion . Computational results from 20 instances found in the literature indicate that the proposed method outperforms alternative metaheuristics developed for solving this problem.     

A VNS heuristic for escaping local extrema entrapment in normalized cut clustering

Normalized cut is one of the most popular graph clustering criteria. The main approaches proposed for its resolution are spectral clustering methods and a multilevel approach of Dhillon et al. (TPAMI 29:1944–1957, 2007), called graclus. Their aim is to obtain good solutions in a small amount of time for large instances. Metaheuristics are general frameworks for stochastic searches often employed in global optimization to improve the solutions obtained by other heuristics. Variable neighborhood search (VNS) is a metaheuristic which exploits systematically the idea of neighborhood change during the search. In this paper, we propose a VNS heuristic for normalized cut segmentation. Computational experiments show that in most cases this VNS heuristic improves significantly, and in moderate time, the solutions obtained by the current state-of-the-art algorithms, i.e., graclus and a spectral method proposed by Yu and Shi (ICCV, 2003).     

Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique

In the literature of multi-objective problem, there are different algorithms to solve different optimization problems. This paper presents a min–max multi-objective procedure for a dual-objective, namely make span, and sum of the earliness and tardiness of jobs in due window machine scheduling problems, simultaneously. In formulation of min–max method when this method is combined with the weighting method, the decision maker can have the flexibility of mixed use of weights and distance parameter to yield a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) to solve parallel machines scheduling problems with sequence-dependent setup time that comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two VNS-based HMHs, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed to solve the addressed scheduling problems. A design of experiments approach is employed to calibrate the parameters. The non-dominated sets obtained from HMH and two best existing bi-criteria scheduling algorithms are compared in terms of various indices and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Aside, an extensive computational experience is carried out to analyze the different parameters of the algorithm.     

Two level General variable neighborhood search for Attractive traveling salesman problem

Attractive traveling salesman problem (AtTSP) consists of finding maximal profit tour starting and ending at a given depot after visiting some of the facilities. Total length of the tour must not exceed the given maximum distance. Each facility achieves profit from the customers, based on the distance between the facility and customers as well as on the attractiveness of that facility. Total profit of a tour is equal to a sum of profits of all visited facilities. In this paper, we develop a new variant of Variable neighborhood search, called 2-level General variable neighborhood search (2-GVNS) for solving AtTSP. At the second level, we use General variable neighborhood search in the local search lor building neighboring solution and checking its feasibility. Our 2-GVNS heuristic outperforms tabu search heuristic, the only one proposed in the literature so far, in terms of precision and running times. In addition, 2-GVNS finds all optimal known solutions obtained by Branch and cut algorithm and offers several new best known solutions.     

Improving simulated annealing with variable neighborhood search to solve the resource-constrained scheduling problem

The purpose of this paper is to improve the simulated annealing method with a variable neighborhood search to solve the resource-constrained scheduling problem. We also compare numerically this method with other neighborhood search (local search) techniques: threshold accepting methods and tabu search. Furthermore, we combine these techniques with multistart diversification strategies and with the variable neighborhood search technique. A thorough numerical study is completed to set the parameters of the different methods and to compare the quality of the solutions that they generate. The numerical results indicate that the simulated annealing method improved with a variable neighborhood search technique is indeed the best solution method. This research was supported by NSERC grant (OGP 0008312) the first author received a FCAR fellowship during her M.Sc. studies.     

Adaptive memory programing for the robust capacitated international sourcing problem

The International Sourcing Problem consists of selecting a subset from an available set of potential suppliers internationally located. The selected suppliers must meet the demand for items from a set of plants, which are also located worldwide. Since the costs are affected by macroeconomic conditions in the countries where the supplier and the plant are located, the formulation considers the uncertainty associated with changes in these conditions. We formulate the robust capacitated international sourcing problem by means of a scenario-optimization approach. When dealing with uncertainty, one of the most common approaches in the literature is to formulate the problem via a set of possible scenarios, this is the approach we follow here. In this paper we propose a constructive method based on memory structures to solve this problem. The method is coupled with a local search procedure followed by a path relinking for improved outcomes. We propose an innovative mechanism to achieve a good balance between intensification and diversification in the search process. Moreover, our path-relinking implementation uses constructive neighborhoods for extrapolated relinking. The computational experimentation favors this method when compared with a recent tabu search approach.     

大型钢铁企业原料场存储分配问题的研究

为钢铁企业原料存储分配问题建立了以降低成本并保持原料成分稳定为目标函数的非线性数学模型,并提出了改进禁忌搜索算法进行求解.该算法利用基于随机kick移动的迭代局域搜索策略作为跳出局部最优的策略,其中迭代局域搜索策略的邻域以环交换移动产生.通过150组随机数据的实验证明,引入迭代局域搜索策略的禁忌搜索算法具有较强的全局搜索能力,是解决该类实际工业问题的快速有效的近优算法.