A comparison of five hybrid metaheuristic algorithms for unrelated parallel-machine scheduling and inbound trucks sequencing in multi-door cross docking systems

The objective of this paper is to develop five hybrid metaheuristic algorithms, including three hybrid ant colony optimization (hACO) variants, and compare their performances in two related applications: unrelated parallel machine scheduling and inbound truck sequencing in a multi-door cross docking system in consideration of sequence dependent setup, and both zero and nonzero release time. The three hACO variants were modified and adapted from the existing literature and they differ mainly in how a solution is coded and decoded, how a pheromone matrix is represented, and the local search methods employed. The other two hybrids are newly constructed hybrid simulated annealing (hSA) algorithms, which are built based on the authors’ knowledge and experience. The evaluation criteria are computational time and the objective function value, i.e., makespan. Based on the results of computational experiments the simulated annealing-tabu search hybrid turns out to be the best if maximal CPU time is used as the stopping criterion and the 2-stage hACO variant is the best if maximal number of evaluations is the stopping criterion. The contributions of this paper are: (i) being the first to carry out a comparative study of hybrid metaheuristics for the two selected applications, (ii) being the first to consider nonzero truck arrival time in multi-door cross docking operations, (iii) identifying which hACO variant is the best among the three, and (iv) investigating the effect of release time on the makespan.     

Design optimization of truss structures using cuckoo search algorithm

A new metaheuristic optimization algorithm is developed to solve truss optimization problems. The new algorithm, called cuckoo search (CS), is examined by solving five truss design optimization problems with increasing numbers of design variables and complexity in constraints. The performance of the CS algorithm is further compared with various classical and advanced algorithms, selected from a wide range of the state‐of‐the‐art algorithms in the area. The results identify that the final solutions obtained by the CS are superior compared with the best solutions obtained by the other algorithms. Finally, the unique search features used in the CS and the implications for future researches are discussed in detail. Copyright © 2012 John Wiley & Sons, Ltd.     

An improved harmony search algorithm with dynamically varying bandwidth

The present work demonstrates a new variant of the harmony search (HS) algorithm where bandwidth (BW) is one of the deciding factors for the time complexity and the performance of the algorithm. The BW needs to have both explorative and exploitative characteristics. The ideology is to use a large BW to search in the full domain and to adjust the BW dynamically closer to the optimal solution. After trying a series of approaches, a methodology inspired by the functioning of a low-pass filter showed satisfactory results. This approach was implemented in the self-adaptive improved harmony search (SIHS) algorithm and tested on several benchmark functions. Compared to the existing HS algorithm and its variants, SIHS showed better performance on most of the test functions. Thereafter, the algorithm was applied to geometric parameter optimization of a friction stir welding tool.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

An electromagnetism-like mechanism for the single machine total stepwise tardiness problem with release dates

In recent years, a new type of tardiness cost, called stepwise tardiness, has received attention. To the authors’ knowledge, only a few studies have investigated this type of tardiness in the scheduling problem. This study considered the single machine total stepwise tardiness problem with release dates, which is strongly NP hard. Because of the essential complexity of the problem, heuristics were first developed to quickly generate initial solutions. Subsequently, a new electromagnetism-like mechanism (EM), which is a novel metaheuristic, was proposed to improve the solution quality. The new EM includes a natural encoding scheme, a new distance measure between solutions, and effective attraction and repulsion operators. Comparisons with a current EM and other metaheuristics were performed to verify the proposed EM. The computational results show that the proposed EM exhibits good performance for the considered problem.     

Discrete size optimization of steel trusses using a refined big bang–big crunch algorithm

This article presents a methodology that provides a method for design optimization of steel truss structures based on a refined big bang–big crunch (BB-BC) algorithm. It is shown that a standard formulation of the BB-BC algorithm occasionally falls short of producing acceptable solutions to problems from discrete size optimum design of steel trusses. A reformulation of the algorithm is proposed and implemented for design optimization of various discrete truss structures according to American Institute of Steel Construction Allowable Stress Design (AISC-ASD) specifications. Furthermore, the performance of the proposed BB-BC algorithm is compared to its standard version as well as other well-known metaheuristic techniques. The numerical results confirm the efficiency of the proposed algorithm in practical design optimization of truss structures.     

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p-hub median problem

This paper deals with the uncapacitated multiple allocation p-hub median problem (UMApHMP). An electromagnetism-like (EM) method is proposed for solving this NP-hard problem. Our new scaling technique, combined with the movement based on the attraction–repulsion mechanism, directs the EM towards promising search regions. Numerical results on a battery of benchmark instances known from the literature are reported. They show that the EM reaches all previously known optimal solutions, and gives excellent results on large-scale instances. The present approach is also extended to solve the capacitated version of the problem. As it was the case in the uncapacitated version, EM also reached all previously known optimal solutions.