A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

Improved Tabu search heuristics for the dynamic space allocation problem

The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.     

Decomposition based hybrid VNS–TS algorithm for distributed parallel factories scheduling with virtual corporation

The main purpose of this paper is to develop a decomposition based hybrid variable neighborhood search/tabu search (DVT) algorithm for multi-factory production network scheduling problem where a number of different individual factories collaborate despite their different objectives. It is assumed some of the network's factories are interested in total processing cost minimization whereas the remaining factories are interested in the production profits maximization. It is also assumed that jobs can migrate from their original factory to other factories but a transportation time is incurred. Our proposed algorithm comprises of a tabu search and a variable neighborhood search with several local search algorithms. In this hybridization, to improve the search ability of the algorithm, we make use of guiding principles with ordering of neighborhood structures by mixed integer linear programming relaxation. In the proposed algorithm, the parallel search strategy is designed for a scalar bi-objective. Multiple objectives are combined with L₁-metric technique then each sub-search procedure evolves separately until a good approximation of the Pareto-front is obtained. The non-dominated sets obtained from our algorithm and original heuristic (algorithm without ordering concept) are compared using three different indices. Furthermore, the problem is modeled as a mixed integer linear programming and solved by improved ϵ-constraint approach (IEA) with CPLEX solver. The results of comparisons between IEA and DVT algorithm showed the proposed algorithm yielded most of the solutions in the net non-dominated front.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

一种用于PFSP节能优化的混合禁忌搜索算法

为了追求节能减排与净利润最大化,建立一种置换流水车间订单接受与调度模型。禁忌搜索是一类启发式全局搜索算法,传统禁忌搜索对初始解依赖较大,没有对考虑能效的置换流水车间调度问题进行更深入的优化。鉴于问题的复杂性,提出了一种节能混合禁忌搜索算法,结合了NEH构造启发式算法的优势,并在该算法中设计了订单接受与拒绝编码方式、能耗调整与交货期配置策略。最后采用大量随机实例对性能进行分析。实验结果表明,通过上述改进,改善了算法的全局搜索能力与解决复杂模型的寻优能力,节能混合禁忌搜索较单一算法而言性能更优,可以有效增加企业总净利润,降低能源消耗。     

Genetic tabu search for the fuzzy flexible job shop problem

This paper tackles the flexible job-shop scheduling problem with uncertain processing times. The uncertainty in processing times is represented by means of fuzzy numbers, hence the name fuzzy flexible job-shop scheduling. We propose an effective genetic algorithm hybridised with tabu search and heuristic seeding to minimise the total time needed to complete all jobs, known as makespan. To build a high-quality and diverse set of initial solutions we introduce a heuristic method which benefits from the flexible nature of the problem. This initial population will be the starting point for the genetic algorithm, which then applies tabu search to every generated chromosome. The tabu search algorithm relies on a neighbourhood structure that is proposed and analysed in this paper; in particular, some interesting properties are proved, such as feasibility and connectivity. Additionally, we incorporate a filtering mechanism to reduce the neighbourhood size and a method that allows to speed-up the evaluation of new chromosomes. To assess the performance of the resulting method and compare it with the state-of-the-art, we present an extensive computational study on a benchmark with 205 instances, considering both deterministic and fuzzy instances to enhance the significance of the study. The results of these experiments clearly show that not only does the hybrid algorithm benefit from the synergy among its components but it is also quite competitive with the state-of-the-art when solving both crisp and fuzzy instances, providing new best-known solutions for a number of these test instances.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

Tabu search for scheduling on identical parallel machines to minimize mean tardiness

This paper presents a tabu search approach for scheduling jobs on identical parallel machines with the objective of minimizing the mean tardiness. Initially, we consider a basic tabu search that uses short term memory only. Local search is performed on a neighborhood defined by two types of moves. Insert moves consist of transferring each job from one machine to another and swap moves are those obtained by exchanging each pair of jobs between two machines. Next, we analyze the incorporation of two diversification strategies with the aim of exploring unvisited regions of the solution space. The first strategy uses long term memory to store the frequency of the moves executed throughout the search and the second makes use of influential moves. Computational tests are performed on problems with up to 10 machines and 150 jobs. The heuristic performance is evaluated through a lower bound given by Lagrangean relaxation. A comparison is also made with respect to the best constructive heuristic reported in the literature.     

最小赋权支配集的迭代禁忌搜索算法

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。     

A graph coloring heuristic using partial solutions and a reactive tabu scheme

Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO-PARTIALCOL), which is based on tabu search, considers feasible but partial solutions and tries to increase the size of the current partial solution. A solution consists of k disjoint stable sets (and, therefore, is a feasible, partial k-coloring) and a set of uncolored vertices. We introduce a reactive tabu tenure which substantially enhances the performance of both our heuristic as well as the classical tabu algorithm (called TABUCOL) proposed by Hertz and de Werra [Using tabu search techniques for graph coloring, Computing 1987;39:345–51]. We will report numerical results on different benchmark graphs and we will observe that FOO-PARTIALCOL, though very simple, outperforms TABUCOL on some instances, provides very competitive results on a set of benchmark graphs which are known to be difficult, and outperforms the best-known methods on the graph flat300_28_0. For this graph, FOO-PARTIALCOL finds an optimal coloring with 28 colors. The best coloring achieved to date uses 31 colors. Algorithms very close to TABUCOL are still used as intensification procedures in the best coloring methods, which are evolutionary heuristics. FOO-PARTIALCOL could then be a powerful alternative. In conclusion FOO-PARTIALCOL is one of the most efficient simple local search coloring methods yet available.     

Tabu search for attribute reduction in rough set theory

In this paper, we consider a memory-based heuristic of tabu search to solve the attribute reduction problem in rough set theory. The proposed method, called tabu search attribute reduction (TSAR), is a high-level TS with long-term memory. Therefore, TSAR invokes diversification and intensification search schemes besides the TS neighborhood search methodology. TSAR shows promising and competitive performance compared with some other CI tools in terms of solution qualities. Moreover, TSAR shows a superior performance in saving the computational costs.     

Tabu search heuristic for two-machine flowshop with batch processing machines

Batch processing machines are frequently encountered in many industrial environments. A batch processing machine is one which can process several jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time of any job in the batch. This study deals with the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. A heuristic based on Tabu search (TS) technique is proposed. The proposed heuristic is compared with a heuristic based on mixed integer linear programming (MILP). Because the complexity of the MILP-based heuristic is depended on the number of job batches, the comparison is under up-to-eight batches problem. In order to measure the proposed TS-based heuristic in larger batch problem, the relative error percentage with the lower bound (REP_LB) is used. The results show that the proposed heuristic is efficient and effective for the problems with relative large job sizes.     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines,setup times,and dual criteria

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0–1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

A novel hybrid tabu search approach to container loading

The container loading problem, which is significant for a number of industrial sectors, aims to obtain a high space utilisation in the container while satisfying practical constraints. This paper presents a novel hybrid tabu search approach to the container loading problem. A loading heuristic is devised to incorporate heuristic strategies with a handling method for remaining spaces to generate optimal loading arrangements of boxes with stability considered. The tabu search technique, which covers the encoding, evaluation criteria and configuration of neighbourhood and candidate solutions, is used to improve the performance of the loading heuristic. Experimental results with benchmark data show that the hybrid approach provides a better space utilisation than the published approaches under the condition of all loaded boxes with one hundred percent support from below. Moreover, it is shown that the hybrid tabu search can solve problems with the constraints of weight limit and weight distribution with real world data.     

Bicriteria scheduling problem for unrelated parallel machines with release dates

This research proposes a heuristic and a tabu search algorithm (TSA) to find non-dominated solutions to bicriteria unrelated parallel machine scheduling problems with release dates. The two objective functions considered in this problem are to minimize both makespan and total weighted tardiness. The computational results show that the proposed heuristic is computationally efficient and provides solutions of reasonable quality. The proposed TSA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。