Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP.     

Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.     

Annealing-tabu PAES: a multi-objective hybrid meta-heuristic

Most real-life optimization problems require taking into account not one, but multiple objectives simultaneously. In most cases these objectives are in conflict, i.e. the improvement of some objectives implies the deterioration of others. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined, but rather a set of solutions. In the last decade most papers dealing with multi-objective optimization use the concept of Pareto-optimality. The goal of Pareto-based multi-objective strategies is to generate a front (set) of non-dominated solutions as an approximation to the true Pareto-optimal front. However, this front is unknown for problems with large and highly complex search spaces, which is why meta-heuristic methods have become important tools for solving this kind of problem. Hybridization in the multi-objective context is nowadays an open research area. This article presents a novel extension of the well-known Pareto archived evolution strategy (PAES) which combines simulated annealing and tabu search. Experiments on several mathematical problems show that this hybridization allows an improvement in the quality of the non-dominated solutions in comparison with PAES, and also with its extension M-PAES.     

A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities

This paper presents a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presents a unique solution representation where a food source is represented by two discrete vectors and tabu search (TS) is applied to each food source to generate neighboring food sources for the employed bees, onlooker bees, and scout bees. An efficient initialization scheme is introduced to construct the initial population with a certain level of quality and diversity. A self-adaptive strategy is adopted to enable the DABC algorithm with learning ability for producing neighboring solutions in different promising regions whereas an external Pareto archive set is designed to record the non-dominated solutions found so far. Furthermore, a novel decoding method is also presented to tackle maintenance activities in schedules generated. The proposed DABC algorithm is tested on a set of the well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

A one-step tabu search algorithm for manufacturing cell design

As part of the cellular manufacturing design process, machines must be grouped in cells and the corresponding part families must be assigned. Limits on both the number of machines per cell and the number of parts per family can be considered. A weighted sum of intracell voids and intercellular moves is used to evaluate the quality of the solutions. We present a tabu search algorithm that systematically explores feasible machine cells configurations determining the corresponding part families using a linear network flow model. The performance of this tabu search is benchmarked against two simulated annealing approaches, another tabu search approach and three heuristics: (ZODIAC, GRAFICS and MST).     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

Heuristics for a coupled-operation scheduling problem

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n²) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.     

Genetic local search for multi-objective combinatorial optimization

The paper presents a new genetic local search (GLS) algorithm for multi-objective combinatorial optimization (MOCO). The goal of the algorithm is to generate in a short time a set of approximately efficient solutions that will allow the decision maker to choose a good compromise solution. In each iteration, the algorithm draws at random a utility function and constructs a temporary population composed of a number of best solutions among the prior generated solutions. Then, a pair of solutions selected at random from the temporary population is recombined. Local search procedure is applied to each offspring. Results of the presented experiment indicate that the algorithm outperforms other multi-objective methods based on GLS and a Pareto ranking-based multi-objective genetic algorithm (GA) on travelling salesperson problem (TSP).     

A parallel competitive colonial algorithm for JIT flowshop scheduling

This paper proposes two parallel algorithms which are improved by heuristics for a bi-objective flowshop scheduling problem with sequence-dependent setup times in a just-in-time environment. In the proposed algorithms, the population will be decomposed into the several sub-populations in parallel. Multiple objectives are combined with min–max method then each sub-population evolves separately in order to obtain a good approximation of the Pareto-front. After unifying the obtained results, we propose a variable neighborhood algorithm and a hybrid variable neighborhood search/tabu search algorithm to improve the Pareto-front. The non-dominated sets obtained from our proposed algorithms, a genetic local search and restarted iterated Pareto greedy algorithm are compared. It is found that most of the solutions in the net non-dominated front are yielded by our proposed algorithms.     

Approximation algorithms for the oriented two-dimensional bin packing problem

Given a set of rectangular items which may not be rotated and an unlimited number of identical rectangular bins, we consider the problem of packing each item into a bin so that no two items overlap and the number of required bins is minimized. The problem is strongly NP-hard and finds practical applications in cutting and packing. We discuss a simple deterministic approximation algorithm which is used in the initialization of a tabu search approach. We then present a tabu search algorithm and analyze its average performance through extensive computational experiments.     

A tabu search algorithm for the Open Shop problem

In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.     

Optimizing the system of virtual paths by tabu search

In an asynchronous transfer mode (ATM) network, given the network topology and traffic demands, the establishment of the system of virtual paths (VPs), and the assignment of connections to them so that the network performance is optimized, entails a number of computationally hard subproblems. The optimization problem discussed here focuses on finding a system of VP routes for a given set of VP terminators and VP capacity demands. Although it has been proven that the existing random path algorithm yields the worst case time bound, the solution performance still depends highly on the number of iterations. In this paper, an exact solution procedure and a heuristic method based on a simple tabu search have been developed for optimizing the system of VPs. Computational results show that the proposed tabu search algorithm is effective in obtaining high quality solutions, and the performance of the proposed algorithm is increasingly attractive as the problem size becomes larger.     

Solving the flight perturbation problem with meta heuristics

When there is a perturbation in a carefully constructed aircraft schedule, e.g. an aircraft breakdown, it is important to minimize the negative consequences of this disturbance. Here, a tabu search and a simulated annealing approach to the flight perturbation problem are presented. The heuristics use a tree-search algorithm to find new schedules for the aircraft, and utilize a path relinking strategy to explore paths between structurally different solutions. The computational results indicate that the solution strategies, especially the tabu search, can be successfully used to solve the flight perturbation problem.     

Multi-objective tabu search using a multinomial probability mass function

A tabu search approach to solve multi-objective combinatorial optimization problems is developed in this paper. This procedure selects an objective to become active for a given iteration with a multinomial probability mass function. The selection step eliminates two major problems of simple multi-objective methods, a priori weighting and scaling of objectives. Comparison of results on an NP-hard combinatorial problem with a previously published multi-objective tabu search approach and with a deterministic version of this approach shows that the multinomial approach is effective, tractable and flexible.     

A dynamic neighborhood based tabu search algorithm for real-world flight instructor scheduling problems

The multi-objective flight instructor scheduling problem is an optimization problem that schedules instructors to teach a set of pilot training events. The objectives of the problem are to minimize labor cost, maximize workload consistency and maximize flight instructor satisfaction of their assignments. The problem is further complicated by various hard and soft constraints. We study a multi-objective cost function and convert it to a scalar-weighted objective function using a priori weighting scheme. We then design an efficient dynamic neighborhood based tabu search meta-heuristic to solve the problem. The algorithm exploits the special properties of different types of neighborhood moves. We also address issues of solution domination, tabu short-term memory, dynamic tabu tenure and aspiration rule. The application of the algorithm in a major US airline carrier is reported and the results show that our algorithm achieves significant benefits in practice.     

A tabu search approach for proportionate multiprocessor open shop scheduling

In the multiprocessor open shop scheduling problem, jobs are to be processed on a set of processing centers—each having one or more parallel identical machines, while jobs do not have a pre-specified obligatory route. A special case is the proportionate multiprocessor open shop scheduling problem (PMOSP) in which the processing time on a given center is not job-dependent. Applications of the PMOSP are evident in health care systems, maintenance and repair shops, and quality auditing and final inspection operations in industry. In this paper, a tabu search (TS) approach is presented for solving the PMOSP with the objective of minimizing the makespan. The TS approach utilizes a neighborhood search function that is defined over a network representation of feasible solutions. A set of 100 benchmark problems from the literature is used to evaluate the performance of the developed approach. Experimentations show that the developed approach outperforms a previously developed genetic algorithm as it produces solutions with an average of less than 5 % deviation from a lower bound, and 40 % of its solutions are provably optimal.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

Local search algorithms for the min-max loop layout problem

In the min-max loop layout problem, machines are to be arranged around a loop of conveyor belt. The ordering of the machines dictates the number of circuits of the conveyor belt required to manufacture each of several products. The goal is to find an ordering of the machines that minimises the maximum number of circuits required for the manufacture of any of the products. Since the problem is strongly NP-hard, the study of heuristic methods is of interest. This paper proposes iterated descent and tabu search algorithms, and a randomised insertion algorithm. Results of extensive computational tests show that all of our algorithms outperform a previously known algorithm that applies a greedy heuristic to the solution of a linear programming relaxation. The best quality solutions are obtained with iterated descent. This adds further evidence to the belief that iterated descent can produce high quality solutions to a variety of combinatorial optimisation problems. Moreover, unlike some other local search algorithms, iterated descent does not require much tuning in order to be competitive.