Discrete–continuous project scheduling with discounted cash flows—A tabu search approach

In this paper discrete–continuous project scheduling problems with discounted cash flows are considered. In discrete–continuous project scheduling activities require for their processing discrete and continuous resources. The processing rate of an activity depends on the amount of the continuous resource allotted to this activity at a time. A positive cash flow is associated with each activity. Two common payment models—lump-sum payment and payments at activities’ completion times—are considered. The objective is the maximization of the net present value of all cash flows of the project. Some properties of optimal schedules are discussed, and the formulation of a mathematical programming problem for an optimal continuous resource allocation is presented. Applications of a local search metaheuristic—tabu search, as well as simple search methods—multi-start iterative improvement and random sampling are described. The algorithms are compared on the basis of a computational experiment, the results are analyzed and discussed. Some conclusions as well as directions for further research are given.     

A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations

This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.     

Capacitated single-allocation hub location model for a flood relief distribution network

In disaster management, the logistics for disaster relief must deal with uncontrolled variables, including transportation difficulties, limited resources, and demand variations. In this work, an optimization model based on the capacitated single-allocation hub location problem is proposed to determine an optimal location of flood relief facilities with the advantage of economies of scale to transport commodities during a disaster. The objective is to minimize the total transportation cost, which depends on the flood severity. The travel time is bounded to ensure that survival packages will be delivered to victims in a reasonable time. Owing to complexity of the problem, a hybrid algorithm is developed based on a variable neighborhood search and tabu search (VNS-TS). The computational results show that the VNS found the optimal solutions within a 2% gap, while the proposed VNS-TS found the optimal solution with a 0% gap. A case study of severe flooding in Thailand is presented with consideration of related parameters such as water level, hub capacity, and discount factors. Sensitivity analyses on the number of flows, discount factors, capacity, and bound length are provided. The results indicated that demand variation has an impact on the transportation cost, number of hubs, and route patterns.     

A tabu search algorithm for the job shop problem with sequence dependent setup times

This paper addresses the classic job shop scheduling problem where sequence dependent setup times are present. Based on a modified disjunctive graph, we further investigate and generalize structural properties for the problem under study. A tabu search algorithm with a sophisticated neighbourhood structure is then developed. Compared to most studies in this research area, we are interested in moving internal critical operations rather than merely focusing on non-internal ones. Moreover, neighbourhood functions are defined using insertion techniques instead of simple swaps. Test results show that our algorithm outperforms a simulated annealing algorithm which is recently published. We have also conducted experiments considering the efficiency of developed propositions.     

Problem difficulty for tabu search in job-shop scheduling

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.     

物流动态车辆调度问题的混合禁忌搜索算法

在分析动态车辆调度问题的基础上,建立了基于时间轴的动态模型;接着针对该问题在实际中的应用,设计了基于并行节约法和禁忌搜索的混合算法以对动态车辆调度问题进行求解;最后给出算法实现和算例模拟,验证了该算法的有效性。     

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.     

Optimizing urban traffic light scheduling problem using harmony search with ensemble of local search

This study addresses urban traffic light scheduling problem (UTLSP). A centralized model is employed to describe the urban traffic light control problem in a scheduling framework. In the proposed model, the concepts of cycles, splits, and offsets are not adopted, making UTLSP fall in the class of model-based optimization problems, where each traffic light is assigned in a real-time manner by the network controller. The objective is to minimize the network-wise total delay time in a given finite horizon. A swarm intelligent algorithm, namely discrete harmony search (DHS), is proposed to solve the UTLSP. In the DHS, a novel new solution generation strategy is proposed to improve the algorithm’s performance. Three local search operators with different structures are proposed based on the feature of UTLSP to improve the performance of DHS in local space. An ensemble of local search methods is proposed to integrate different neighbourhood structures. Extensive computational experiments are carried out using the traffic data from partial traffic network in Singapore. The DHS algorithm with and without local search operators and ensemble is evaluated and tested. The comparisons and discussions verify the effectiveness of DHS algorithms with local search operators and ensemble for solving UTLSP.     

An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes

This paper addresses a sequence- and machine-dependent batch scheduling problem on a set of unrelated-parallel machines where the objective is to minimize a linear combination of total weighted completion time and total weighted tardiness. In particular, batch scheduling disregards the group technology assumptions by allowing for the possibility of splitting pre-determined groups of jobs into batches with respect to desired lower bounds on batch sizes. With regard to bounds on batch sizes, the MILP model is developed as two integrated batching and scheduling phases to present the problem. A benchmark of small-size instances on group scheduling shows the superior performance of batch scheduling up to 37% reduction in the objective function value. An efficient meta-heuristic algorithm based on tabu search with multi-level diversification and multi-tabu structure is developed at three levels, which moves back and forth between batching and scheduling phases. To eliminate searching in ineffective neighborhoods and thus enhance computational efficiency of search algorithms, several lemmas are proposed and proven. The results of applying lemmas reflect up to 40% reduction in computational times. Comparing the optimal solutions found by CPLEX and tabu search shows that the tabu search algorithm could find solutions, at least as good as CPLEX but in incredibly shorter computational time. In order to trigger the search algorithm, two different initial solution finding mechanisms have been developed and implemented. Also, due to lack of a qualified benchmark for unrelated-parallel machines, a comprehensive data generation mechanism has been developed in a way that it fairly reflects the real world situations encountered in practice. The machine availability times and job release times are considered to be dynamic and the run time of each job differs on different machines based upon the capability of the machines.     

A tabu search algorithm based on new block properties and speed-up method for permutation flow-shop with finite intermediate storage

This paper deals with a permutation flow-shop scheduling problem with finite intermediate storage (PFSFIS) between successive machines so as to minimize makespan. In such a problem the intermediate storage capacity constraints are considered besides the machine-related constraints usually discussed in the general permutation flow-shop. This feature adds extra difficulties to the scheduling problem. In this paper, we present some new block properties and a speed-up method using a forward-backward hybrid algorithm to compute makespan. Applied in a tabu search algorithm, the new block properties greatly reduce the neighborhood size and thus shorten the search time. Also, the speed-up method eliminates redundant computation for the objective function and reduces a majority of the running time. Computational experiments (up to 200 jobs and 20 machines) are given to demonstrate the effectiveness of new block neighborhood characteristics and the speed-up method. Compared with the results yielded by the best-known algorithm, the objective function is improved by 0.14% if the new block neighborhood characteristics are used; furthermore, the running time is reduced by 53.7% on the average if the speed-up method is used. Under the condition that both of the algorithms have the same running time the objective function is improved by 0.24% if both of the two above improvement methods are applied in the original tabu search.     

A tabu search approach to the truck scheduling problem with multiple docks and time windows

While organizing the cross-docking operations, cross-dock managers are confronted with many decision problems. One of these problems is the truck scheduling problem. This paper presents a truck scheduling problem that is concerned with both inbound and outbound trucks at multiple dock doors. The objective is to minimize the total travel time and the total tardiness. The truck scheduling problem under study is described in detail and a mathematical model of the problem is provided which can be solved to optimality with a mixed integer programming solver, at the expense of a high computation time. Next, a tabu search approach is presented. Experimental results on new benchmark instances indicate that the proposed tabu search is able to find good quality results in a short time period, thus offering potential for integration in cross-docking decision support systems.     

基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术,提出一种用于解决有限资源、不同重要性要求的任务路径规划问题的有效算法,通过对不同重要程度的任务进行分层调度,得到较为满意的决策结果.该算法具有搜索空间小、求解速度快的优点.仿真结果验证了算法的有效性.     

A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers

This paper investigates the hybrid flowshop scheduling with finite intermediate buffers, whose objective is to minimize the sum of weighted completion time of all jobs. Since this problem is very complex and has been proven strongly NP-hard, a tabu search heuristic is proposed. In this heuristic there are two main features. One is that a scatter search mechanism is incorporated to improve the diversity of the search procedure. And the other is that a permutation of N jobs representing their processing order in the first stage instead of a complex complete schedule is used to denote a solution. Computational experiments on randomly generated instances with different structures show that the proposed tabu search heuristic can provide good solutions compared to both the lower bounds and the algorithm proposed for this problem in a lately published literature.     

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.     

JAMES: An object‐oriented Java framework for discrete optimization using local search metaheuristics

This paper describes the Java Metaheuristics Search framework (JAMES, v1.1): an object‐oriented Java framework for discrete optimization using local search algorithms that exploits the generality of such metaheuristics by clearly separating search implementation and application from problem specification. A wide range of generic local searches are provided, including (stochastic) hill climbing, tabu search, variable neighbourhood search and parallel tempering. These can be applied to any user‐defined problem by plugging in a custom neighbourhood for the corresponding solution type. Using an automated analysis workflow, the performance of different search algorithms can be compared in order to select an appropriate optimization strategy. Implementations of specific components are included for subset selection, such as a predefined solution type, generic problem definition and several subset neighbourhoods used to modify the set of selected items. Additional components for other types of problems (e.g. permutation problems) are provided through an extensions module which also includes the analysis workflow. In comparison with existing Java metaheuristics frameworks that mainly focus on population‐based algorithms, JAMES has a much lower memory footprint and promotes efficient application of local searches by taking full advantage of move‐based evaluation. Releases of JAMES are deployed to the Maven Central Repository so that the framework can easily be included as a dependency in other Java applications. The project is fully open source and hosted on GitHub. More information can be found at http://www.jamesframework.org . Copyright © 2016 John Wiley & Sons, Ltd.     

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.     

Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search

The capacitated clustering problem (CCP) is the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster ‘capacity’). The objective is to minimize the total scatter of objects from the ‘centre’ of the cluster to which they have been allocated. A simple constructive heuristic, a R-interchange generation mechanism, a hybrid simulated annealing (SA) and tabu search (TS) algorithm which has computationally desirable features using a new non-monotonic cooling schedule, are developed. A classification of the existing SA cooling schedules is presented. The effects on the final solution quality of the initial solutions, the cooling schedule parameters and the neighbourhood search strategies are investigated. Computational results on randomly generated problems with size ranging from 50 to 100 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.     

求解无等待流水调度的基于禁忌搜索的混合算法

本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。     

A tabu search procedure based on a random Roulette diversification for the weighted maximal planar graph problem

An efficient and effective tabu search implementation for the weighted maximal planar graph problem is proposed. The search incorporates a number of novel features including: the introduction of a new set of two-move operators; a move-cache-memory structure for efficiently searching the neighbourhood space; and a random roulette selection from a ranked list of best moves for diversification. The effects of these and other features on solution quality are investigated. Computational results are reported on a set of 100 benchmark instances of sizes varying from 20 to 100 vertices. The results demonstrate that the new probabilistic tabu search algorithm is very competitive with state of the art algorithms in the literature in terms of both solution quality and computational effort.Scope