A tabu search heuristic for the quay crane scheduling problem

This paper proposes a tabu search heuristic for the Quay Crane Scheduling Problem (QCSP), the problem of scheduling a fixed number of quay cranes in order to load and unload containers into and from a ship. The optimality criterion considered is the minimum completion time. Precedence and non-simultaneity constraints between tasks are taken into account. The former originate from the different kind of operations that each crane has to perform; the latter are needed in order to avoid interferences between the cranes. The QCSP is decomposed into a routing problem and a scheduling problem. The routing problem is solved by a tabu search heuristic, while a local search technique is used to generate the solution of the scheduling problem. This is done by minimizing the longest path length in a disjunctive graph. The effectiveness of our algorithm is assessed by comparing it to a branch-and-cut algorithm and to a Greedy Randomized Adaptive Search Procedure (GRASP).     

A tabu search approach for scheduling hazmat shipments

Vehicle routing and scheduling are two main issues in the hazardous material (hazmat) transportation problem. In this paper, we study the problem of managing a set of hazmat transportation requests in terms of hazmat shipment route selection and actual departure time definition. For each hazmat shipment, a set of minimum and equitable risk alternative routes from origin to destination points and a preferred departure time are given. The aim is to assign a route to each hazmat shipment and schedule these shipments on the assigned routes in order to minimize the total shipment delay, while equitably spreading the risk spatially and preventing the risk induced by vehicles traveling too close to each other. We model this hazmat shipment scheduling problem as a job-shop scheduling problem with alternative routes. No-wait constraints arise in the scheduling model as well, since, supposing that no safe area is available, when a hazmat vehicle starts traveling from the given origin it cannot stop until it arrives at the given destination. A tabu search algorithm is proposed for the problem, which is experimentally evaluated on a set of realistic test problems over a regional area, evaluating the provided solutions also with respect to the total route risk and length.     

Real-time scheduling for hybrid flowshop in ubiquitous manufacturing environment

This paper discusses the implementation of RFID technologies, which enable the shop floor visibility and reduce uncertainties in the real-time scheduling for hybrid flowshop (HFS) production. In the real-time HFS environment, the arriving of new jobs is dynamic, while the processes in work stages are not continuous. The decision makers in shop floor level and stage level have different objectives. Therefore, classical off-line HFS scheduling approaches cannot be used under these situations. In this research, two major measures are taken to deal with these specific real-time features. Firstly, a ubiquitous manufacturing (UM) environment is created by deploying advanced wireless devices into value-adding points for the collection and synchronization of real-time shop floor data. Secondly, a multi-period hierarchical scheduling (MPHS) mechanism is developed to divide the planning time horizon into multiple shorter periods. The shop floor manager and stage managers can hierarchically make decisions for their own objectives. Finally, the proposed MPHS mechanism is illustrated by a numerical case study.     

A search heuristic for just-in-time scheduling in parallel machines

In recent years the Just-in-Time (JIT) production philosophy as been adopted by many companies around the world. This has motivated the study of scheduling models that embrace the essential components of JIT systems. In this paper, we present a search heurustic for the weighted earliness penalty problem with deadlines in parallel identical machines. Our approach combines elements of the solution methods known as greedy randomized adaptive search procedure (GRASP) and tabu search. It also uses a branch-and-bound post-processor to optimize individually the sequence of the jobs assigned to each machine.     

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.     

A tabu search based hybrid evolutionary algorithm for the max-cut problem

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.     

A tabu search algorithm for the multi-period inspector scheduling problem

This paper introduces a multi-period inspector scheduling problem (MPISP), which is a new variant of the multi-trip vehicle routing problem with time windows (VRPTW). In the MPISP, each inspector is scheduled to perform a route in a given multi-period planning horizon. At the end of each period, each inspector is not required to return to the depot but has to stay at one of the vertices for recuperation. If the remaining time of the current period is insufficient for an inspector to travel from his/her current vertex A to a certain vertex B, he/she can choose either waiting at vertex A until the start of the next period or traveling to a vertex C that is closer to vertex B. Therefore, the shortest transit time between any vertex pair is affected by the length of the period and the departure time. We first describe an approach of computing the shortest transit time between any pair of vertices with an arbitrary departure time. To solve the MPISP, we then propose several local search operators adapted from classical operators for the VRPTW and integrate them into a tabu search framework. In addition, we present a constrained knapsack model that is able to produce an upper bound for the problem. Finally, we evaluate the effectiveness of our algorithm with extensive experiments based on a set of test instances. Our computational results indicate that our approach generates high-quality solutions.     

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.     

An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems

This paper proposes an effective hybrid tabu search algorithm (HTSA) to solve the flexible job-shop scheduling problem. Three minimization objectives – the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In this study, a tabu search (TS) algorithm with an effective neighborhood structure combining two adaptive rules is developed, which constructs improved local search in the machine assignment module. Then, a well-designed left-shift decoding function is defined to transform a solution to an active schedule. In addition, a variable neighborhood search (VNS) algorithm integrating three insert and swap neighborhood structures based on public critical block theory is presented to perform local search in the operation scheduling component. The proposed HTSA is tested on sets of the well-known benchmark instances. The statistical analysis of performance comparisons shows that the proposed HTSA is superior to four existing algorithms including the AL + CGA algorithm by Kacem, Hammadi, and Borne (2002b), the PSO + SA algorithm by Xia and Wu (2005), the PSO + TS algorithm by Zhang, Shao, Li, and Gao (2009), and the Xing’s algorithm by Xing, Chen, and Yang (2009a) in terms of both solution quality and efficiency.     

A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.     

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.     

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.     

Modeling realistic hybrid flexible flowshop scheduling problems

This paper aims to contribute to the recent research efforts to bridge the gap between the theory and the practice of scheduling by modelizing a realistic manufacturing environment and analyzing the effect of the inclusion of several characteristics in the problem formulation. There are several constraints and characteristics that affect the scheduling operations at companies. While these constraints are many times tackled in the literature, they are seldom considered together inside the same problem formulation. We propose a formulation along with a mixed integer modelization and some heuristics for the problem of scheduling n jobs on m stages where at each stage we have a known number of unrelated machines. The jobs might skip stages and, therefore, we have what we call a hybrid flexible flowshop problem. We also consider per machine sequence-dependent setup times which can be anticipatory and non-anticipatory along with machine lags, release dates for machines, machine eligibility and precedence relationships among jobs. Manufacturing environments like this appear in sectors like food processing, ceramic tile manufacturing and several others. The optimization criterion considered is the minimization of the makespan. The MIP model and the heuristics proposed are tested against a comprehensive benchmark and the results evaluated by advanced statistical tools that make use of decision trees and experimental designs. The results allow us to identify the constraints that increase the difficulty.     

Parallel tabu search algorithm for the hybrid flow shop problem

The paper deals with the parallel variant of the scheduling algorithm dedicated to the hybrid flow shop problem. The problem derives from practice of automated manufacturing lines, e.g. for printed packages. The overall goal is to design a new algorithm which merges the performance of the best known sequential approach with the efficient exploitation of parallel calculation environments. In order to fulfill the above aim, there are two methods proposed in this paper: the original fast method of parallel calculation of the criterion function and the local neighborhood parallel search method embedded in the tabu search approach. The theoretical analysis, as well as the original implementation, with the use of vector processing instructions SSE2 supported by suitable data organization, are presented below. Numerical properties of the proposed algorithm are empirically verified on the multi-core processor.     

A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines

This article addresses a two-stage hybrid flowshop scheduling problem with unrelated alternative machines. The problem to be studied has m unrelated alternative machines at the first machine center followed by a second machine center with a common processing machine in the system. The objective is to minimize the makespan of the system. For the processing of any job, it is assumed that the operation can be partially substituted by other machines in the first center, depending on its machining constraints. Such scheduling problems occur in certain practical applications such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production. We demonstrate that the addressed problem is NP-hard and then provide some heuristic algorithms to solve the problem efficiently. The experimental results show that the combination of the modified Johnson's rule and the First-Fit rule provides the best solutions within all proposed heuristics.Scope and purpose     

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.     

A fast hybrid tabu search algorithm for the no-wait job shop problem

This paper describes a hybrid tabu search algorithm dedicated to a job shop problem with a no-wait constraint with a makespan criterion. The proposed here algorithm complexity is that the superior algorithm based on the tabu search technique selects parameters controlling the work of a certain constructional algorithm. This approach limits the checked solutions only to a group of solutions being able to be generated by the structural algorithm in question. It bears serious consequences both positive, for example it limits the research scope for a small fraction of relatively extremely well quality of acceptable solutions, and negative that is the lack of possibility of finding the optimal solution. In this paper numerical researches of the proposed algorithm are conducted as well as a comparative analysis with reference to the literature algorithms of the algorithm in question is made.     

An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers

In this paper, an effective hybrid discrete differential evolution (HDDE) algorithm is proposed to minimize the maximum completion time (makespan) for a flow shop scheduling problem with intermediate buffers located between two consecutive machines. Different from traditional differential evolution algorithms, the proposed HDDE algorithm adopted job permutation to represent individuals and applies job-permutation-based mutation and crossover operations to generate new candidate solutions. Moreover, a one-to-one selection scheme with probabilistic jumping is used to determine whether the candidates will become members of the target population in next generation. In addition, an efficient local search algorithm based on both insert and swap neighborhood structures is presented and embedded in the HDDE algorithm to enhance the algorithm’s local searching ability. Computational simulations and comparisons based on the well-known benchmark instances are provided. It shows that the proposed HDDE algorithm is not only capable to generate better results than the existing hybrid genetic algorithm and hybrid particle swarm optimization algorithm, but outperforms two recently proposed discrete differential evolution (DDE) algorithms as well. Especially, the HDDE algorithm is able to achieve excellent results for large-scale problems with up to 500 jobs and 20 machines.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times

Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.