An implementation of the iterated tabu search algorithm for the quadratic assignment problem

In this paper, we describe an implementation of the iterated tabu search (ITS) algorithm for the quadratic assignment problem (QAP), which is one of the well-known problems in combinatorial optimization. The medium- and large-scale QAPs are not, to this date, practically solvable to optimality, therefore heuristic algorithms are widely used. In the proposed ITS approach, intensification and diversification mechanisms are combined in a proper way. The goal of intensification is to search for good solutions in the neighbourhood of a given solution, while diversification is responsible for escaping from local optima and moving towards new regions of the search space. In particular, the following enhancements were implemented: new formula for fast evaluation of the objective function and efficient data structure; extended intensification mechanisms (including randomized tabu criterion, combination of tabu search and local search, dynamic tabu list maintaining); enhanced diversification strategy using periodic tabu tenure and special mutation procedure. The ITS algorithm is tested on the different instances taken from the QAP library QAPLIB. The results from the experiments demonstrate promising efficiency of the proposed algorithm, especially for the random QAP instances.     

An integrated CPU–GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups

Environmental issues have become increasingly important to industry and business in recent days. This trend forces the companies to take responsibility for product recovery, and proper recycling and disposal, moving towards the design of sustainable green supply chains. This paper addresses the backward stream in transportation of products, by means of reverse logistics applied to vehicle routing. This problem, called single vehicle routing problem with deliveries and selective pickups, consists in finding a route that starts from the depot and visits all delivery customers. Some pickup customers may also be visited, since the capacity of the truck is not exceeded, and there is also a revenue associated with each pickup. We develop an algorithm inspired on the variable neighbourhood search metaheuristic that explores the power of modern graphics processing unit (GPU) to provide routes in reasonable computational time. The proposed algorithm called four-neighbourhood variable neighbourhood search (FN-VNS) includes a novel high-quality initial solution generator, a CPU–GPU integrated perturbation strategy and four different neighbourhood searches implemented purely in GPU for the local search phase. Our experimental results show that FN-VNS is able to improve the quality of the solution for 51 instances out of 68 instances taken from the literature. Finally, we obtained speedups up to 14.49 times, varying from 17.42 up to 76.84 for each local search, measured over a set of new large-size instances.     

A new multi-objective evolutionary algorithm: neighbourhood exploring evolution strategy

This article proposes a new multi-objective evolutionary algorithm, called neighbourhood exploring evolution strategy (NEES). This approach incorporates the idea of neighbourhood exploration together with other techniques commonly used in the multi-objective evolutionary optimization literature (namely, non-dominated sorting and diversity preservation mechanisms). The main idea of the proposed approach was derived from a single-objective evolutionary algorithm, called the line-up competition algorithm (LCA), and it consists of assigning neighbourhoods of different sizes to different solutions. Within each neighbourhood, new solutions are generated using a (1+λ)-ES (evolution strategy). This scheme naturally balances the effect of local search (which is performed by the neighbourhood exploration mechanism) with that of the global search performed by the algorithm, and gradually impels the population to progress towards the true Pareto-optimal front of the problem to explore the extent of that front. Three versions of the proposal are studied: a (1+1)-NEES, a (1+2)-NEES and a (1+4)-NEES. Such approaches are validated on a set of standard test problems reported in the specialized literature. Simulation results indicate that, for continuous numerical optimization problems, the proposal (particularly the (1+1)-NEES) is competitive with respect to NSGA-II, which is an algorithm representative of the state-of-the-art in evolutionary multi-objective optimization. Moreover, all the versions of NEES improve on the results of NSGA-II when dealing with a discrete optimization problem. Although preliminary, such results might indicate a potential application area in which the proposed approach could be particularly useful.     

Harmony search optimization algorithm for a novel transportation problem in a consolidation network

This article presents a new harmony search optimization algorithm to solve a novel integer programming model developed for a consolidation network. In this network, a set of vehicles is used to transport goods from suppliers to their corresponding customers via two transportation systems: direct shipment and milk run logistics. The objective of this problem is to minimize the total shipping cost in the network, so it tries to reduce the number of required vehicles using an efficient vehicle routing strategy in the solution approach. Solving several numerical examples confirms that the proposed solution approach based on the harmony search algorithm performs much better than CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for realistic size problem instances.     

Multiple-variable neighbourhood search for the single-machine total weighted tardiness problem

The single-machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. This problem has been proved to be NP hard and thus provides a challenging area for metaheuristics, especially the variable neighbourhood search algorithm. In this article, a multiple variable neighbourhood search (m-VNS) algorithm with multiple neighbourhood structures is proposed to solve the problem. Special mechanisms named matching and strengthening operations are employed in the algorithm, which has an auto-revising local search procedure to explore the solution space beyond local optimality. Two aspects, searching direction and searching depth, are considered, and neighbourhood structures are systematically exchanged. Experimental results show that the proposed m-VNS algorithm outperforms all the compared algorithms in solving the SMTWT problem.     

An adaptive multi-population genetic algorithm for job-shop scheduling problem

Job-shop scheduling problem (JSP) is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm (AMGA) has been proposed to solve this problem. Firstly, using multi-populations and adaptive crossover probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some classical benchmark JSPs taken from the literature and compared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.     

An adaptive genetic algorithm for large-size open stack problems

The problem of minimising the maximum number of open stacks arises in many contexts (production planning, cutting environments, very-large-scale-integration circuit design, etc.) and consists of finding a sequence of tasks (products, cutting patterns, circuit gates, etc.) that determines an efficient utilisation of resources (stacks). We propose a genetic approach that combines classical genetic operators (selection, order crossover and pairwise interchange mutation) with an adaptive search strategy, where intensification and diversification phases are obtained by neighbourhood search and by a composite and dynamic fitness function that suitably modifies the search landscape. Computational tests on random and real-world benchmarks show that the proposed approach is competitive with the state of the art for large-size problems, providing better results for some classes of instances.     

Variable neighbourhood search for dual-resource constrained flexible job shop scheduling

Dual-resource constrained flexible job shop scheduling problem (FJSP) is considered and an effective variable neighbourhood search (VNS) is presented, in which the solution to the problem is indicated as a quadruple string of the ordered operations and their resources. Two neighbourhood search procedures are sequentially executed to produce new solutions for two sub-problems of the problem, respectively. The search of VNS is restarted from a slightly perturbed version of the current solution of VNS when the determined number of iterations is reached. VNS is tested on some instances and compared with methods from literature. Computational results show the significant advantage of VNS on the problem.     

A collaborative ant colony metaheuristic for distributed multi-level uncapacitated lot-sizing

The paper presents an ant colony optimization metaheuristic for collaborative planning. Collaborative planning is used to coordinate individual plans of self-interested decision-makers with private information in order to increase the overall benefit of the coalition. The method consists of a new search graph based on encoded solutions. Distributed and private information are integrated via voting mechanisms and via a simple but effective collaborative local search procedure. The approach is applied to a distributed variant of the multi-level lot-sizing problem and evaluated by means of 352 benchmark instances from the literature. The proposed approach clearly outperforms existing approaches on the sets of medium- and large-sized instances. While the best method in the literature so far achieves an average deviation from the best-known non-distributed solutions of 75% for the set of the largest instances, for example, the presented approach reduces the average deviation to 7%.     

Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm

The flow shop scheduling problem with blocking has important applications in a variety of industrial systems but is under-represented in the research literature. In this paper, a modified fruit fly optimisation (MFFO) algorithm is proposed to solve the above scheduling problem for makespan minimisation. The MFFO algorithm mainly contains three key operators. One is related to the initialisation scheme in which a problem-specific heuristic is adopted to generate an initial fruit fly swarm location with high quality. The second is concerned with the smell-based search in which a neighbourhood strategy is designed to generate a new location. To further enhance the exploitation of the proposed algorithm considered, a speed-up insert-neighbourhood-based local search is applied with a probability. Finally, the last is for the vision-based search in which an update criterion is proposed to induce the fruit fly into a better searching space. The simulation experimental results demonstrated the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. Moreover, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

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.     

Two enhanced differential evolution algorithms for job shop scheduling problems

This paper proposes two new differential evolution algorithms (DE) for solving the job shop scheduling problem (JSP) that minimises two single objective functions: makespan and total weighted tardiness. The proposed algorithms aim to enhance the efficiency of the search by dynamically balancing exploration and exploitation ability in DE and avoiding the problem of premature convergence. The first algorithm allows DE population to simultaneously perform different mutation strategies in order to extract the strengths of various strategies and compensate for the weaknesses of each individual strategy to enhance the overall performance. The second algorithm allows the whole DE population to change the search behaviour whenever the solutions do not improve. This study also introduces a modified local mutation operation embedded in the two proposed DE algorithms to promote exploitation in different areas of the search space. In addition, a local search technique, called Critical Block (CB) neighbourhood, is applied to enhance the quality of solutions. The performances of the proposed algorithms are evaluated on a set of benchmark problems and compared with results obtained from an efficient existing Particle Swarm Optimisation (PSO) algorithm. The numerical results demonstrate that the proposed DE algorithms yield promising results while using shorter computing times and fewer numbers of function evaluations.     

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.     

Optimization of truss topology using tabu search

A design procedure for integrating topological considerations in the framework of structural optimization is presented. The proposed approach is capable of considering multiple load conditions, stress, displacement and local/global buckling constraints, and multiple objective functions in the problem formulation. Further, since the proposed method permits members to be added to or deleted from an existing topology and the topology is not defined by member areas, the difficulty of not being able to reach singular optima is also avoided. These objectives are accomplished using a discrete optimization procedure which uses 0–1 topological variables to optimize alternate designs. Since the topological variables are discrete in nature and the member cross-sections are assumed to be continuous, the topological optimization problem has mixed discrete-continuous variables. This non-linear programming problem is solved using a memory-based combinatorial optimization technique known as tabu search. Numerical results obtained using tabu search for single and multiobjective topological optimization of truss structures are presented. To model the multiple objective functions in the problem formulation, a cooperative game theoretic approach is used. The results indicate that the optimum topologies obtained using tabu search compare favourably, and in some instances, outperform the results obtained using the ground–structure approach. However, this improvement occurs at the expense of a significant increase in computational burden owing to the fact that the proposed approach necessitates that the geometry of each trial topology be optimized.     

Single and multiobjective structural optimization in discrete-continuous variables using simulated annealing

A multivariable optimization technique based on the Monte-Carlo method used in statistical mechanics studies of condensed systems is adapted for solving single and multiobjective structural optimization problems. This procedure, known as simulated annealing, draws an analogy between energy minimization in physical systems and objective function minimization in structural systems. The search for a minimum is simulated by a relaxation of the statistical mechanical system where a probabilistic acceptance criterion is used to accept or reject candidate designs. To model the multiple objective functions in the problem formulation, a cooperative game theoretic approach is used. Numerical results obtained using three different annealing strategies for the single and multiobjective design of structures with discrete-continuous variables are presented. The influence of cooling schedule parameters on the optimum solutions obtained is discussed. Simulation results indicate that, in several instances, the optimum solutions obtained using simulated annealing outperform the optimum solutions obtained using some gradient-based and discrete optimization techniques. The results also indicate that simulated annealing has substantial potential for additional applications in optimization, especially for problems with mixed discrete-continuous variables.     

Multiobjective design of actively controlled structures using a hybrid optimization method

A multiobjective approach to the combined structure and control optimization problem for flexible space structures is presented. The proposed formulation addresses robustness considerations for controller design, as well as a simultaneous determination of optimum actuator locations. The structural weight, controlled system energy, stability robustness index and damping augmentation provided by the active controller are considered as objective functions of the multiobjective problem which is solved using a cooperative game-theoretic approach. The actuator locations and the cross-sectional areas of structural members are treated as design variables. Since the actuator locations are spatially discrete, whereas the cross-sectional areas are continuous, the optimization problem has mixed discrete-continuous design variables. A solution approach to this problem based on a hybrid optimization scheme is presented. The hybrid optimizer is a synergetic blend of artificial genetic search and gradient-based search techniques. The computational procedure is demonstrated through the design of an ACOSS-FOUR space structure. The optimum solutions obtained using the hybrid optimizer are shown to outperform the optimum results obtained using gradient-based search techniques.     

A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time.     

On the optimal design of water distribution networks: a practical MINLP approach

We propose a practical solution method for real-world instances of a water-network optimization problem with fixed topology using a nonconvex continuous NLP (NonLinear Programming) relaxation and a MINLP (Mixed Integer NonLinear Programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, with the goal of calculating only good feasible solutions, complicated algorithmics can be confined to the MINLP solver. We report successful computational experience using available open-source MINLP software on problems from the literature and on difficult real-world instances. An important contribution of this paper is that the solutions obtained, besides being low cost, are immediately usable in practice because they are characterized by an allocation of diameters to pipes that leads to a correct hydraulic operation of the network. This is not the case for most of the other methods presented in the literature.     

Integrated process planning and scheduling for large-scale flexible job shops using metaheuristics

In this paper, we discuss an integrated process planning and scheduling problem in large-scale flexible job shops (FJSs). We assume that products can be manufactured in different ways, i.e. using different bills of materials (BOM) and routes for the same product. The total weighted tardiness is the performance measure of interest. A Mixed Integer Programming formulation is provided for the researched problem. Because of the NP-hardness of the investigated problem, an iterative scheme is designed that is based on variable neighbourhood search (VNS) on the process planning level. Appropriate neighbourhood structures for VNS are proposed. Because the evaluation of each move within VNS requires the solution of a large-scale FJS scheduling problem instance, efficient heuristics based on local search from previous research are considered on the scheduling level. Extensive computational experiments based on new randomly generated problem instances are conducted. In addition, a parallel version of the VNS is investigated within the computational experiments. The proposed iterative scheme is benchmarked against a genetic algorithm (GA) from the literature that simultaneously considers process planning and scheduling for the special case where a single BOM is available for each product. It turns out that the new iterative scheme outperforms the GA and a memetic algorithm based on the GA. It is able to solve even large-size problem instances in reasonable amount of time.     

Job shop scheduling with a non-regular objective: A comparison of neighbourhood structures based on a sequencing/timing decomposition

Commercial software packages for production management are characterized by a gap between MRP logic, based on a backward scheduling approach, and finite capacity scheduling, usually based on forward scheduling. In order to partially bridge that gap, we need scheduling algorithms able to meet due dates while keeping WIP and inventory costs low. This leads us to consider job shop scheduling problems characterized by non-regular objective functions; such problems are even more difficult than classical job shop scheduling, and suitable heuristics are needed. One possibility is to consider local search strategies based on the decomposition of the overall problem into sequencing and timing sub-problems. For given job sequences, the optimal timing problem can be solved as a node potential problem on a graph. Since solving the timing problem is a relatively time-consuming task, we need to define a suitable neighbourhood structure to explore the space of job sequences; this can be done by generalizing well-known results for the minimum makespan problem. A related issue is if solving timing problems exactly is really necessary, or if an approximate solution is sufficient; hence, we also consider solving the timing problem approximately by a fast heuristic. We compare different neighbourhood structures, by embedding them within a pure local improvement strategy. Computational experiments show that the overall approach performs better than release/dispatch rules, although the performance improvement depends on the problem characteristics, and that the fast heuristic is quite competitive with the optimal timing approach. On the one hand, these results pave the way to the development of better local search algorithms (based e.g. on tabu search); on the other hand, it is worth noting that the heuristic timing approach, unlike the optimal one, can be extended to cope with the complicating features typical of practical scheduling problems.