Coupling ant colony optimization and the extended great deluge algorithm for the discrete facility layout problem

This article uses a hybrid optimization approach to solve the discrete facility layout problem (FLP), modelled as a quadratic assignment problem (QAP). The idea of this approach design is inspired by the ant colony meta-heuristic optimization method, combined with the extended great deluge (EGD) local search technique. Comparative computational experiments are carried out on benchmarks taken from the QAP-library and from real life problems. The performance of the proposed algorithm is compared to construction and improvement heuristics such as H63, HC63-66, CRAFT and Bubble Search, as well as other existing meta-heuristics developed in the literature based on simulated annealing (SA), tabu search and genetic algorithms (GAs). This algorithm is compared also to other ant colony implementations for QAP. The experimental results show that the proposed ant colony optimization/extended great deluge (ACO/EGD) performs significantly better than the existing construction and improvement algorithms. The experimental results indicate also that the ACO/EGD heuristic methodology offers advantages over other algorithms based on meta-heuristics in terms of solution quality.     

SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration

This paper presents a single instruction multiple data tabu search (SIMD-TS) algorithm for the quadratic assignment problem (QAP) with graphics hardware acceleration. The QAP is a classical combinatorial optimisation problem that is difficult to solve optimally for even small problems with over 30 items. By using graphic hardware acceleration, the developed SIMD-TS algorithm executes 20 to 45 times faster than traditional CPU code. The computational improvement is made possible by the utilisation of the parallel computing capability of a graphics processing unit (GPU). The speed and effectiveness of this algorithm are demonstrated on QAP library problems. The main contribution of this paper is a fast and effective SIMD-TS algorithm capable of producing results for large QAPs on a desktop personal computer equivalent to the results achieved with a CPU cluster.     

A tabu‐search‐based algorithm for continuous multiminima problems

Tabu search algorithms are becoming very popular in operational research community. A lot of works and studies were carried out from the first presentation of Glover. The development of tabu search techniques concerns in almost all cases combinatorial problems, and we found very few papers about continuous problems. In this work, we briefly classify and describe the main continuous approaches to tabu search, then we will present a novel algorithm which explores a grid of points with a distance dynamically defined, it collapses to a local minimum then it continues the search from that point accepting some non‐improving points to allow the exploration of new regions of the domain. The proposed algorithm is deterministic with a little random component triggered only when loop conditions are detected and it contains a simple vocabulary building mechanism and a diversification procedure. Finally we show some comparisons with other optimization algorithms and a possible application of this method to an engineering problem. Copyright © 2001 John Wiley & Sons, Ltd.     

Modelling and a tabu search solution for the slab reallocation problem in the steel industry

This paper considers a slab reallocation problem arising from operations planning in the steel industry. The problem involves reallocating steel slabs to customer orders to improve the utilisation of slabs and the level of customer satisfaction. It can be viewed as an extension of a multiple knapsack problem. We firstly formulate the problem as an integer nonlinear programming (INLP) model. With variable replacement, the INLP model is then transformed into a mixed integer linear programming (MILP) model, which can be solved to optimality by MILP optimisers for very small instances. To obtain satisfactory solutions efficiently for practical-sized instances, a heuristic algorithm based on tabu search (TS) is proposed. The algorithm employs multiple neighbourhoods including swap, insertion and ejection chain in local search, and adopts solution space decomposition to speed up computation. In the ejection chain neighbourhood, a new and more effective search method is also proposed to take advantage of the structural properties of the problem. Computational experiments on real data from an advanced iron and steel company in China show that the algorithm generates very good results within a short time. Based on the model and solution approach, a decision support system has been developed and implemented in the company.     

A capacitated vehicle routing problem with order available time in e-commerce industry

In this article, a variant of the well-known capacitated vehicle routing problem (CVRP) called the capacitated vehicle routing problem with order available time (CVRPOAT) is considered, which is observed in the operations of the current e-commerce industry. In this problem, the orders are not available for delivery at the beginning of the planning period. CVRPOAT takes all the assumptions of CVRP, except the order available time, which is determined by the precedent order picking and packing stage in the warehouse of the online grocer. The objective is to minimize the sum of vehicle completion times. An efficient tabu search algorithm is presented to tackle the problem. Moreover, a Lagrangian relaxation algorithm is developed to obtain the lower bounds of reasonably sized problems. Based on the test instances derived from benchmark data, the proposed tabu search algorithm is compared with a published related genetic algorithm, as well as the derived lower bounds. Also, the tabu search algorithm is compared with the current operation strategy of the online grocer. Computational results indicate that the gap between the lower bounds and the results of the tabu search algorithm is small and the tabu search algorithm is superior to the genetic algorithm. Moreover, the CVRPOAT formulation together with the tabu search algorithm performs much better than the current operation strategy of the online grocer.     

Flexible job shop with continuous material flow

A new scheduling problem, the continuous flow flexible job shop (CF-FJS) is proposed. The formulation combines the well-known flexible job shop (FJS) problem and a dedicated continuous material flow model (MFM). In the MFM, operations are represented by material flow functions derived by integration of arbitrarily defined speed patterns. Two main concepts of the MFM formalism, i.e. variable speed of processing and continuous material flow, lead to position-dependent processing times and overlapping in operations which extend standard FJS formulation. Properties of the CF-FJS are investigated. A tabu search sched uling algorithm utilising these properties is proposed. Effective neighbourhood functions are defined based on elimination approaches. Two auxiliary procedures: search intensification level switching and fast feasibility detection are added to improve algorithm efficiency. The algorithm is verified using dedicated benchmark instances which comprise non-trivial representations of the CF-FJS specific features, i.e. machine efficiency patterns and minimum inter-operation buffers. The research is motivated by task scheduling in a fastener factory, but the presented results can be useful in many domains, such as production of granular goods, steel details, glass and fluids. The solution can be used in real-world applications. The published results can be helpful in testing new CF-FJS scheduling algorithms.     

A scatter search approach to sequence-dependent setup times job shop scheduling

Scheduling jobs on multiple machines is a difficult problem when real-world constraints such as the sequence setup time, setup times for jobs and multiple criteria are used for solution goodness. It is usually sufficient to obtain a near-optimal solution quickly when an optimal solution would require days or weeks of computation. Common scheduling heuristics such as Shortest Processing Time can be used to obtain a feasible schedule quickly, but are not designed for multiple simultaneous objectives. We use a new meta-heuristic known as a scatter search (SS) to solve these types of job shop scheduling problems. The results are compared with solutions obtained by common heuristics, a tabu search, simulated annealing, and a genetic algorithm. We show that by combining the mechanism of diversification and intensification, SS produces excellent results in a very reasonable computation time. The study presents an efficient alternative for companies with a complicated scheduling and production situation.     

A hybrid genetic algorithm for the multi-depot open vehicle routing problem

This paper studies the multi-depot open vehicle routing problem (MDOVRP), a variant of the vehicle routing problem (VRP), in which vehicles start from several depots and are not required to return to the depot. Despite the vast amount of literature about VRPs, the MDOVRP has received very little attention from researchers. In this paper, a new hybrid genetic algorithm is presented for finding the routes that minimize the traveling cost of the vehicles. Computational results on a number of test instances indicate the proposed algorithm dominates the CPLEX solver and the existing approach in the literature. Meanwhile, experiments are conducted on multi-depot VRP benchmarks, and the results are compared with a sophisticated tabu search approach and an exact method.     

New Tabu search heuristics for the dynamic facility layout problem

A manufacturing facility is a dynamic system that constantly evolves due to changes such as changes in product demands, product designs, or replacement of production equipment. As a result, the dynamic facility layout problem (DFLP) considers these changes and is defined as the problem of assigning departments to locations during a multi-period planning horizon such that the sum of the material handling and re-arrangement costs is minimised. In this paper, three tabu search (TS) heuristics are presented for this problem. The first heuristic is a simple TS heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic TS heuristic. To test the performances of the heuristics, two sets of test problems from the literature are used in the analysis. The results show that the second heuristic out-performs the other proposed heuristics and the heuristics available in the literature.     

Tabu search approach based on a similarity coefficient for cell formation in generalized group technology

Both a similarity coefficient method (SCM)-based algorithm and meta-heuristics have been widely applied to various cell formation problems; however, few studies have explored the combination of the two methods. This paper addresses a hybrid algorithm, in which, based on the initial solution produced by a new SCM-based hierarchical clustering method, a fast and effective tabu search approach is presented to solve cell formation in group technology (GT). The proposed algorithm is applied to several problems from literature and a group of the randomly generated instances with alternative process plans and compared with simulated annealing (SA) and other TS; the results demonstrate that the proposed algorithm is available and efficient for cell formation in generalized GT.     

A hybrid artificial bee colony algorithm for a flexible job shop scheduling problem with overlapping in operations

Overlapping in operations is an effective technology for productivity improvement in modern manufacturing systems. Thus far, however, there are still rare works on flexible job shop scheduling problems (FJSPs) concerning this strategy. In this paper, we present a hybrid artificial bee colony (hyABC) algorithm to minimise the total flowtime for a FJSP with overlapping in operations. In the proposed hyABC, a dynamic scheme is introduced to fine-tune the search scope adaptively. In view of poor exploitation ability of artificial bee colony algorithm, a modified migrating birds optimisation algorithm (MMBO) is developed and integrated into the search process for better balancing global exploration and local exploitation. In MMBO, a forward share strategy with one-job based crossover is designed to make good use of valuable information from behind solutions. Besides, an improved downward share scheme is adopted to increase diversification of the population, and thus alleviate the premature convergence. Extensive experiments based on benchmark instances with different scales are carried out and comparisons with other recent algorithms identify the effectiveness of the proposed hyABC.     

An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem

The permutation flowshop scheduling problem (PFSP) has been extensively studied in the scheduling literature. In this paper, we present an improved memetic algorithm (MA) to solve the PFSP to minimise the total flowtime. In the proposed MA, we develop a stochastic local search based on a dynamic neighbourhood derived from the NEH method. During the evolution process, the size of the neighbourhood is dynamically adjusted to change the search focus from exploration to exploitation. In addition, we introduce a new population generation mechanism to guarantee both the quality and diversity of the new populations. We also design a diversity index for the population to monitor the diversity of the current population. If the diversity index is less than a given threshold value, the current population will be replaced by a new one with good diversity so that the proposed MA has good ability to overcome local optima. We conduct computational experiments to test the effectiveness of the proposed algorithm. The computational results on randomly generated problem instances and benchmark problem instances show that the proposed MA is effective and superior or comparable to other algorithms in the literature.     

A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem

This paper proposes a tabu search (TS) algorithm to solve an NP-hard cyclic robotic scheduling problem. The objective is to find a cyclic robot schedule that maximises the throughput. We first formulate the problem as a linear program, provided that the robot move sequence is given, and reduce the problem to searching for an optimal robot move sequence. We find that the solution space can be divided into some specific subspaces by the maximal number of works-in-process. Then, we propose a TS algorithm to synchronously perform local searches in each subspace. To speed up our algorithm, dominated subspaces are eliminated by lower and upper bounds of the cycle time during the iterations. In the TS, a constructive heuristic is developed to generate initial solutions for each subspace and a repairing procedure is proposed to maintain the feasibility of the solutions generated in the initialisation stage and the neighbours search process. Computational comparison both on benchmark instances and randomly generated instances indicates that our algorithm is efficient for the cyclic robotic scheduling problem.     

Simulation-based optimisation approach for the stochastic two-echelon logistics problem

This work proposes a simulation-based optimisation approach for the two-echelon vehicle routing problem with stochastic demands (2E-VRPSD). In the proposed 2E-VRPSD, freight delivery from the depot to the customers is managed by shipping the freight through intermediate satellites, while each customer has a stochastic demand. The 2E-VRPSD is an extension of the famous capacitated vehicle routing problem with stochastic demands and the two-echelon vehicle routing problem (2E-VRP). A tabu search algorithm is designed to solve the 2E-VRPSD, in which Monte Carlo sampling is adopted to tackle the issue of stochastic demands. Modified two-echelon vehicle routing problem benchmark instances are used in the numerical experiments. The computational results show the advantage of the proposed simulation-based approach.     

不确定车数的随机车辆路径问题模型及算法

研究了一类有时间约束、车辆数量不确定的随机车辆路径问题;建立了该类问题的随机规划数学模型;设计了模型求解的遗传算法、禁忌搜索算法和遗传-禁忌混合算法.禁忌算法采用了对当前解的车辆-顾客分配结构和解的路径顺序分别禁忌的双层禁忌算法,使算法全局性更好,同时也降低了搜索时间.把禁忌算法作为变异算子应用于遗传算法形成了混合算法.最后给出了计算示例,对算法进行了比较分析.     

Optimization of a line-cutting procedure for ship hull construction by an effective tabu search

A problem of a line-cutting procedure is discussed for ship hull construction. This procedure includes five steps: stock arrangement, piece arrangement, marking, cutting and special processes, and delivering the work. The line-cutting procedure will be optimized when two objectives are considered: minimizing the total trim loss and keeping the working efficiency of the cutting procedure. The developed way for the discussed problem is to optimize the stock arrangement associated with a proposed rule-based piece arrangement where the former is optimized for minimizing the total trim loss and the latter for keeping the working efficiency. A tabu search is chosen for the optimization of stock arrangement. In addition, two proposed replacement moves, the aggregative and the breaking, are adopted to improve the effectiveness of the tabu search. Two real cases and some random instances are used for test and comparison. The results show that the stock arrangement was optimized satisfyingly by the tabu search and the rule-based piece arrangement is capable of keeping the working efficiency as usual. In addition, the effectiveness of the tabu search was apparently improved by two proposed replacement moves.     

A memetic algorithm with iterated local search for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this paper, a memetic algorithm with iterated local search (MAILS) is proposed to solve this problem. The proposed MAILS incorporates a new crossover operator, i.e., the longest common substring crossover (LCSX), an iterated local search (ILS) and a perturbation mechanism into the framework of the memetic algorithm (MA). The proposed MAILS is evaluated on the CARP benchmark instances and computational results show that the MAILS is very competitive.     

A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem

The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-known instances from the QAPLIB library. By increasing the number of processors, generations and population sizes we have been able to find solutions that are the same as (or very close to) the best reported solutions for large QAP instances in QAPLIB. In order to parallelise the Genetic Algorithm we generate and evolve separate solution pools on each cluster processor, using an island model. This model exchanges 10% of each processor’s solutions at the initial stages of optimisation. We show experimentally that both execution times and solution qualities are improved for large QAP instances by using our Island Parallel Genetic Algorithm.     

基于连续函数优化的禁忌搜索算法

提出了一种连续禁忌搜索算法,用于求解连续函数优化问题.邻域规则及禁忌规则是禁忌搜索算法的核心,针对连续函数解空间的连续性,提出了一种邻域分割法来进行邻域搜索,并对禁忌规则进行了设计.通过经典函数测试可以看出,禁忌搜索算法在连续函数优化问题中显示出很强的"爬山"能力,优化结果与实际最优值非常接近,是一种有效的全局优化算法.     

A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem

The problem that we consider in this article is a flexible job shop scheduling problem issued from the printing and boarding industry. Two criteria have to be minimised, the makespan and the maximum lateness. Two tabu search algorithms are proposed for finding a set of non-dominated solutions: the first is based on the minimisation of one criterion subject to a bound on the second criterion (ε-constraint approach) and the second is based on the minimisation of a linear combination of criteria. These algorithms are tested on benchmark instances from the literature and the results are discussed. The total tardiness is considered as a third criterion for the second tabu search and results are presented and discussed.