Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems

Storage or buffer capacities between successive machines in flowshop problems may be unlimited, limited or null. The last two cases can lead to blocking situations. In flowshop scheduling literature, many studies have been performed about classical flowshop problems and also about some problems with only one blocking situation between all machines.     

Efficient metaheuristics to solve the intermodal terminal location problem

The objective of the intermodal terminal location problem is to determine which of a set of potential terminal locations to use and how to route the supply and demand of a set of customers (representing zones of supply and demand) through the network (by both uni- and intermodal transport) so as to minimize the total cost. Two different metaheuristic procedures are developed that both consist of two phases: a solution construction phase (either GRASP or attribute based hill climber) and a solution improvement phase based on local search. Innovative in this approach is the integration of a fast heuristic procedure to approximate the total cost given the set of open terminals. Both metaheuristics are compared to the results of an MIP solver. A thorough performance assessment uncovers that both metaheuristics generate close-to-optimal solutions in very short computing times. An argument in favor of the ABHC approach is that it is parameter-free and hence more transparent and likely to be accepted in a business or policy environment.     

A reactive GRASP for a commercial territory design problem with multiple balancing requirements

In this paper we present a reactive GRASP approach to a commercial territory design problem motivated by a real-world application in a beverage distribution firm. The mathematical framework includes, as planning criteria, minimizing a measure of territory dispersion, balancing the different node activity measures among territories and territory contiguity. The proposed GRASP approach incorporates several features such as reactivity, by allowing self-adjustment of the restricted candidate list quality parameter, and filtering, which avoids executing the local search phase in unpromising bad solutions generated by the construction phase. The algorithm has been tested in several data sets. The results show the effectiveness of the proposed approach. It was observed that the reactivity and the filtering proved very useful in terms of feasibility with respect to the balancing constraints, and find more robust solutions when tested over the basic GRASP. The local search scheme proved to be very effective as well. Moreover, the proposed approach obtained solutions of much better quality (in terms of both its dispersion measure and its feasibility with respect to the balancing constraints) than those found by the firm method in relatively fast computation times.     

Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach

This work proposes a hybrid metaheuristic (HMH) approach which integrates several features from tabu search (TS), simulated annealing (SA) and variable neighbourhood search (VNS) in a new configurable scheduling algorithm. In particular, either a deterministic or a random candidate list strategy can be used to generate the neighbourhood of a solution, both a tabu list mechanism and the SA probabilistic rule can be adopted to accept solutions, and the dimension of the explored neighbourhood can be dynamically modified. The considered class of scheduling problems is characterized by a set of independent jobs to be executed on a set of parallel machines with non-zero ready times and sequence dependent setups. In particular, the NP-hard generalized parallel machine total tardiness problem (GPMTP) recently defined by Bilge et al. [A tabu search algorithm for parallel machine total tardiness problem. Computers & Operations Research 2004;31:397–414], is faced. Several alternative configurations of the HMH have been tested on the same benchmark set used by Bilge et al. The results obtained highlight the appropriateness of the proposed approach.     

A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet

Nowadays genetic algorithms stand as a trend to solve NP-complete and NP-hard problems. In this paper, we present a new hybrid metaheuristic which uses parallel genetic algorithms and scatter search coupled with a decomposition-into-petals procedure for solving a class of vehicle routing and scheduling problems. The parallel genetic algorithm presented is based on the island model and its performance is evaluated for a heterogeneous fleet problem, which is considered a problem much harder to solve than the homogeneous vehicle routing problem.     

The dynamic space allocation problem: Applying hybrid GRASP and Tabu search metaheuristics

This work is devoted to the Dynamic Space Allocation Problem, where project duration is divided into a number of consecutive periods, each of them associated with a number of activities. The resources required by the activities have to be available in the corresponding workspaces and those sitting idle during a period have to be stored. This problem contains the Quadratic Assignment Problem (QAP) as a particular case, which puts it in the NP-hard class. In this context, the difficulty of identifying optimal solutions, even for instances of medium size, justifies the use of heuristic techniques. This work proposes a construction and a hybrid algorithm (HGT) based on the GRASP and Tabu search metaheuristics. Comparisons are presented for values obtained by HGT, pure GRASP versions, Tabu search and literature results. Computational results show the proposed methods to be competitive in relation to instances in the literature and to existing techniques.     

A survey on metaheuristics for optimization in food manufacturing industry

This paper surveys recent articles on the applications of metaheuristics for solving optimization problems in the food manufacturing industry. Metaheuristics for decision making has attracted significant research and industry attention due to the increasing complexity of models and quick decision making requirements in the industry. Metaheuristics have been applied to food processing/production technologies including fermentation, thermal drying and distillation and other system wide optimization such as transportation, storage (warehousing), production planning and scheduling. In terms of metaheuristics algorithms, Genetic Algorithm and Differential Evolution are the most popular while other algorithms have also demonstrated their effectiveness in addressing various optimization problems. Most problems were typically formulated as single objective mathematical models constructed from experimental or collected data. Recently, multi-objective optimization is becoming more popular because it is able to consider problems from several perspectives and attain more practical results.     

Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops

We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules.     

A toolbox for the design,planning and operation of manufacturing networks in a mass customisation environment

The task of design, planning and operation of manufacturing networks is becoming more and more challenging for companies, as globalisation, mass customisation and the turbulent economic landscape create demand volatility, uncertainties and high complexity. In this context, this paper investigates the performance of decentralised manufacturing networks through a set of methods developed into a software framework in a toolbox approach. The Tabu Search and Simulated Annealing metaheuristic methods are used together with an Artificial Intelligence method, called Intelligent Search Algorithm. A multi-criteria decision making procedure is carried out for the evaluation of the quality of alternative manufacturing network configurations using multiple conflicting criteria including dynamic complexity, reliability, cost, time, quality and environmental footprint. A comparison of the performance of each method based on the quality of the solutions that it provided is carried out. The statistical design of experiments robust engineering technique is used for the calibration of the adjustable parameters of the methods. Moreover, the impact of demand fluctuation to the operational performance of the alternative networks, expressed thorough a dynamic complexity indicator, is investigated through simulation. The developed framework is validated through a real life case, with data coming from the CNC machine building industry.     

Memetic algorithms for the job shop scheduling problem with operators

The job-shop scheduling problem with operators (JSO) is an extension of the classic job-shop problem in which an operation must be assisted by one of a limited set of human operators, so it models many real life situations. In this paper we tackle the JSO by means of memetic algorithms with the objective of minimizing the makespan. We define and analyze a neighborhood structure which is then exploited in local search and tabu search algorithms. These algorithms are combined with a conventional genetic algorithm to improve a fraction of the chromosomes in each generation. We also consider two different schedule builders for chromosome decoding. All these elements are combined to obtain memetic algorithms which are evaluated over an extensive set of instances. The results of the experimental study show that they reach high quality solutions in very short time, comparing favorably with the state-of-the-art methods.