A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times

In this paper, we contemplate the problem of scheduling a set of n jobs in a no-wait flexible flow shop manufacturing system with sequence dependent setup times to minimising the maximum completion time. With respect to NP-hardness of the considered problem, there seems to be no avoiding application of metaheuristic approaches to achieve near-optimal solutions for this problem. For this reason, three novel metaheuristic algorithms, namely population based simulated annealing (PBSA), adapted imperialist competitive algorithm (AICA) and hybridisation of adapted imperialist competitive algorithm and population based simulated annealing (AICA?+?PBSA), are developed to solve the addressed problem. Because of the sensitivity of our proposed algorithm to parameter's values, we employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm to enhance solutions accuracy. These proposed algorithms were coded and tested on randomly generated instances, then to validate the effectiveness of them computational results are examined in terms of relative percentage deviation. Moreover, some sensitive analyses are carried out for appraising the behaviour of algorithms versus different conditions. The computational evaluations manifestly support the high performance of our proposed novel hybrid algorithm against other algorithms which were applied in literature for related production scheduling problems.     

A hybrid particle swarm optimisation for scheduling just-in-time single machine with preemption,machine idle time and unequal release times

This paper addresses preemption in just-in-time (JIT) single–machine-scheduling problem with unequal release times and allowable unforced machine idle time as realistic assumptions occur in the manufacturing environments aiming to minimise the total weighted earliness and tardiness costs. Delay in production systems is a vital item to be focussed to counteract lost sale and back order. Thus, JIT concept is targeted including the elements required such as machine preemption, machine idle time and unequal release times. We proposed a new mathematical model and as the problem is proven to be NP-hard, three meta-heuristic approaches namely hybrid particle swarm optimisation (HPSO), genetic algorithm and imperialist competitive algorithm are employed to solve the problem in larger sizes. In HPSO, cloud theory-based simulated annealing is employed with a certain probability to avoid being trapped in a local optimum. Taguchi method is applied to calibrate the parameters of the proposed algorithms. A number of numerical examples are solved to demonstrate the effectiveness of the proposed approach. The performance of the proposed algorithms is evaluated in terms of relative percent deviation and computational time where the computational results clarify better performance of HPSO than other algorithms in quality of solutions and computational time.     

A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem

This paper deals with the two-stage assembly flowshop scheduling problem with minimisation of weighted sum of makespan and mean completion time as the objective. The problem is NP-hard, hence we proposed a meta-heuristic named imperialist competitive algorithm (ICA) to solve it. Since appropriate design of the parameters has a significant impact on the algorithm efficiency, we calibrate the parameters of this algorithm using the Taguchi method. In comparison with the best algorithm proposed previously, the ICA indicates an improvement. The results have been confirmed statistically.     

Multi-facility location problems in the presence of a probabilistic line barrier: a mixed integer quadratic programming model

We consider a multi-facility location problem in the presence of a line barrier with the starting point of the barrier uniformly distributed. The objective is to locate n new facilities among m existing facilities minimising the summation of the weighted expected rectilinear barrier distances of the locations of new facilities and new and existing facilities. The proposed problem is designed as a mixed-integer nonlinear programming model, conveniently transformed into a mixed-integer quadratic programming model. The computational results show that the LINGO 9.0 software package is effective in solving problems with small sizes. For large problems, we propose two meta-heuristic algorithms, namely the genetic algorithm and the imperialist competitive algorithm for optimisation. The numerical investigations illustrate the effectiveness of the proposed algorithms.     

Automated test data generation for branch testing using incremental genetic algorithm

Cost of software testing can be reduced by automated test data generation to find a minimal set of data that has maximum coverage. Search-based software testing (SBST) is one of the techniques recently used for automated testing task. SBST makes use of control flow graph (CFG) and meta-heuristic search algorithms to accomplish the process. This paper focuses on test data generation for branch coverage. A major drawback in using meta-heuristic techniques is that the CFG paths have to be traversed from the starting node to end node for each automated test data. This kind of traversal could be improved by branch ordering, together with elitism. But still the population size and the number of iterations are maintained as the same to keep all the branches alive. In this paper, we present an incremental genetic algorithm (IGA) for branch coverage testing. Initially, a classical genetic algorithm (GA) is used to construct the population with the best parents for each branch node, and the IGA is started with these parents as the initial population. Hence, it is not necessary to maintain a huge population size and large number of iterations to cover all the branches. The performance is analyzed with five benchmark programs studied from the literature. The experimental results indicate that the proposed IGA search technique outperforms the other meta-heuristic search techniques in terms of memory usage and scalability.     

Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm

The multi-objective reentrant hybrid flowshop scheduling problem (RHFSP) exhibits significance in many industrial applications, but appears under-studied in the literature. In this study, an iterated Pareto greedy (IPG) algorithm is proposed to solve a RHFSP with the bi-objective of minimising makespan and total tardiness. The performance of the proposed IPG algorithm is evaluated by comparing its solutions to existing meta-heuristic algorithms on the same benchmark problem set. Experimental results show that the proposed IPG algorithm significantly outperforms the best available algorithms in terms of the convergence to optimal solutions, the diversity of solutions and the dominance of solutions. The statistical analysis manifestly shows that the proposed IPG algorithm can serve as a new benchmark approach for future research on this extremely challenging scheduling problem.     

Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy,particle swarm optimisation,and genetic algorithm

Determining the locations of departments or machines in a shop floor is classified as a facility layout problem. This article studies unequal-area stochastic facility layout problems where the shapes of departments are fixed during the iteration of an algorithm and the product demands are stochastic with a known variance and expected value. These problems are non-deterministic polynomial-time hard and very complex, thus meta-heuristic algorithms and evolution strategies are needed to solve them. In this paper, an improved covariance matrix adaptation evolution strategy (CMA ES) was developed and its results were compared with those of two improved meta-heuristic algorithms (i.e. improved particle swarm optimisation [PSO] and genetic algorithm [GA]). In the three proposed algorithms, the swapping method and two local search techniques which altered the positions of departments were used to avoid local optima and to improve the quality of solutions for the problems. A real case and two problem instances were introduced to test the proposed algorithms. The results showed that the proposed CMA ES has found better layouts in contrast to the proposed PSO and GA.     

An effective genetic algorithm for the resource levelling problem with generalised precedence relations

Resource levelling aims to obtain a feasible schedule to minimise the resource usage fluctuations during project execution. It is of crucial importance in project scheduling to ensure the effective use of scarce and expensive renewable resources, and has been successfully applied to production environments, such as make-to-order and engineering-to-order systems. In real-life projects, general temporal relationships are often needed to model complex time-dependencies among activities. We develop a novel genetic algorithm (GA) for the resource levelling problem with generalised precedence relations. Our design and implementation of GA features an efficient schedule generation scheme, built upon a new encoding mechanism that combines the random key representation and the shift vector representation. A two-pass local search-based improvement procedure is devised and integrated into the GA to enhance the algorithmic performance. Our GA is able to obtain near optimal solutions with less than 2% optimality gap for small instances in fractions of a second. It outperforms or is competitive with the state-of-the-art algorithms for large benchmark instances with size up to 1000 activities.     

Group scheduling in flexible flow shops: a hybridised approach of imperialist competitive algorithm and electromagnetic-like mechanism

This paper applied a novel evolutionary algorithm, imperialist competitive algorithm (ICA), for a group scheduling problem in a hybrid flexible flow shop with sequence-dependent setup times by minimising maximum completion time. This algorithm simulates a social-economical procedure, imperialistic competition. Initial population is generated randomly and evolution is carried out during the algorithm. Firstly individuals, countries, are divided into two categories: imperialists and colonies. Imperialist competition will occur among these empires. This competition will increase some empires authority by ruining a weak empire and dividing its colonies among others. Electromagnetic-like mechanism concepts are employed here to model the influence of the imperialist on their colonies. The algorithm will continue until one imperialist exists and possesses all countries. In order to prevent carrying out extensive experiments to find optimum parameters of the algorithm, we apply the Taguchi approach. The computational results are compared with the outstanding benchmark on the flow shop scheduling problem, random key genetic algorithms (RKGA), and it shows superiority of the ICA.     

Evaluation of the influence of dominance rules for the assembly line design problem under consideration of product design alternatives

The current competitive situation increases the importance of realistically estimating product costs during the early phases of product and assembly line planning projects. In this article, several multi-objective algorithms using difference dominance rules are proposed to solve the problem associated with the selection of the most effective combination of product and assembly lines. The list of developed algorithms includes variants of ant colony algorithms, evolutionary algorithms and imperialist competitive algorithms. The performance of each algorithm and dominance rule is analysed by five multi-objective quality indicators and fifty problem instances. The algorithms and dominance rules are ranked using a non-parametric statistical test.     

Parameters identification of excitation system models using genetic algorithms

A methodology is presented to identify parameters of non-linear models of excitation systems (ESs). Based on the use of genetic algorithms (GAs), the proposed methodology carries out simultaneous parameter identification of linear and non-linear model components. The computational algorithm allows to adequately identify model parameters and it is not affected by the noise present in the measurements. The application of this methodology was developed to identify and validate ES models of different technologies that are used in stability studies through dynamic simulations. First, model parameters of DC1A and ST1A type ES were determined in a simulation environment. The performance of two identifiers based on a GA paradigm is analysed: GA with arithmetic and intermediate recombination operators (GA-BASE) and GA based on differential evolution (GA-DE) mutation. Then the GA-DE identifier is applied to estimate parameters of a static ES (EXE) model of a Brazilian hydro power plant utilising measurements corrupted by noise and registered during field tests. The results obtained are satisfactory and the responses of the identified models are close to real system measurements.     

One- and two-sided assembly line balancing problems with real-world constraints

In this study, we consider balancing problems of one- and two-sided assembly lines with real-world constraints like task or machine incompatibilities. First, we study the one-sided assembly line balancing problem (ALBP) with a limited number of machine types per workstation. Using a genetic algorithm (GA), we find optimal results for real-world instances. A set of larger test cases is used to compare two well-established solution approaches, namely GA and tabu search (TS). Additionally, we apply a specific differential evolution algorithm (DE), which has recently been proposed for the considered ALBP. Our computational results show that DE is clearly dominated by GA. Furthermore, we show that GA outperforms TS in terms of computational time, if capacity constraints are tight. Given the algorithm’s computational performance as well as the fact that it can easily be adapted to additional constraints, we then use it to solve two-sided ALBP. Three types of constraints and two different objectives are considered. We outperform all previously published methods in terms of solution quality and computational time. Finally, we are the first to provide feasible test instances as well as benchmark results for fully constrained two-sided ALB.     

Parallel machine scheduling problem with ready times,due times and sequence-dependent setup times using meta-heuristic algorithms

This article considers a parallel machine scheduling problem with ready times, due times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the weighted sum of setup times, delay times and tardy times. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristics, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution algorithm (SEA), are proposed. The performances of the meta-heuristic algorithms are evaluated through comparison with optimal solutions using several randomly generated examples.     

Non-discrete ant colony optimisation (NdACO) to optimise the development cycle time and cost in overlapped product development

In order to expedite the process of introducing a product to market, organisations have shifted their paradigm towards concurrent engineering. This involves the simultaneous execution of successive activities on the basis of information available in rudimentary form. For this, cross-functional teams sporadically communicate to exchange available updated information at the cost of augmented time and money. Therefore, the aim of this paper is to present a model-based methodology to estimate the optimal amount of overlapping and communication policy with a view to minimising the product development cycle time at the lowest additional cost. In the first step of the methodology, an objective function comprising the cycle time and the cost of the complete project is formulated mathematically. To reach the optimal solution, a novel meta-heuristic, non-discrete ant colony optimisation, is proposed. The algorithm derives its governing traits from the traditional ant algorithms over a discrete domain, but has been modified to search results in a continuous search space. The salient feature of the proposed meta-heuristic is that it utilises the weighted sum of numerous probability distribution functions (PDFs) to represent the long-term pheromone information. This paper utilises a novel approach for pheromone maintenance to adequately update the PDFs after each tour by the ants. The performance of the proposed algorithm has been tested on a hypothetical illustrative example of mobile phones and its robustness has been authenticated against variants of particle swarm optimisation.     

Applying an electromagnetism-like mechanism algorithm on parameter optimisation of a multi-pass milling process

Multi-pass milling is a common manufacturing process in practical production. Parameter optimisation is of great significance since the parameters largely affect the production time, quality, cost and some other process performance measures. However, the parameter optimisation of the multi-pass milling process is a nonlinear constrained optimisation problem. It is very difficult to obtain satisfactory results by the traditional optimisation methods. Therefore, in this paper, a new optimisation technique based on the electromagnetism-like mechanism (EM) algorithm is proposed to solve the parameter optimisation problem in a multi-pass milling process. The EM algorithm is a population based meta-heuristic algorithm for unconstrained optimisation problems. As the parameter optimisation problem is a constrained problem, the proposed approach handles the constraints of the problem by improving the charge calculation formula combined with the feasibility and dominance rules at the same time. This paper also puts forward flexible cutting strategies to simultaneously optimise the depth of cut for each pass, cutting speed and feed to improve solutions. A case study is presented to verify the effectiveness of the proposed approach. The results show that the proposed method is better than other algorithms and achieves significant improvement.     

Integrated process planning and scheduling using an imperialist competitive algorithm

Effective performance of modern manufacturing systems requires integrating process planning and scheduling more tightly, which is consistently challenged by the intrinsic interrelation and intractability of these two problems. Traditionally, these two problems are treated sequentially or separately. Integration of process planning and scheduling (IPPS) provides a valuable approach to improve system performance. However, IPPS is more complex than job shop scheduling or process planning. IPPS is strongly NP-hard in that, compared to an NP-hard job shop scheduling problem with a determined process plan, the process plan for each job in IPPS is also to be optimised. So, an imperialist competitive algorithm (ICA) is proposed to address the IPPS problem with an objective of makespan minimisation. An extended operation-based representation scheme is presented to include information on various flexibilities of process planning with respect to determined job shop scheduling. The main steps of the proposed ICA, including empires construction, assimilation, imperialistic competition, revolution and elimination, are elaborated using an illustrative example. Performance of the proposed ICA was evaluated on four sets of experiments taken from the literature. Computational results of the ICA were compared with that of some existing algorithms developed for IPPS, which validates the efficiency and effectiveness of the ICA in solving the IPPS problem.     

A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

Using response surface design to determine the optimal parameters of genetic algorithm and a case study

Genetic algorithms (GAs) are efficient stochastic search techniques for approximating optimal solutions within complex search spaces and used widely to solve NP-hard problems. Genetic algorithm includes a number of parameters whose different levels strictly affect the performance of the algorithm. The general approach to determine the appropriate parameter combination of GA depends on too many trials of different combinations, and the best one of them that produces good results is selected for the programme, which would be used for problem solving. A few researchers studied on the parameter optimisation of GA. In this paper, response surface-dependent parameter optimisation is proposed to determine the optimal parameters of GA. Results are tested for benchmark problems that are most common in mixed-model assembly line balancing problems of type-I.     

Assembly line balancing by a new multi-objective differential evolution algorithm based on TOPSIS

In this paper, we propose a multi-objective differential evolution algorithm (MODEA) to solve the multi-objective simple assembly line balancing problem type-2 (SALBP-2). This problem arises when in an existing assembly line, changes in the production process or demand structure take place and the organisation wants to produce the optimum number of items using a fixed number of workstations, which is associated with optimally assigning the tasks to an ordered sequence of stations such that the precedence relations are not violated and some measures of performance are optimised. The two considered objectives are: minimising the cycle time and the smoothness index of the assembly line. To that purpose, we develop a MODEA which unlike the existing algorithms deals with the considered objectives separately in selecting the next population members by proposing a new acceptance scheme based on the Pareto dominance concept and a new evaluation scheme based on TOPSIS. Also, by using the Taguchi method, we tune the effective factors of the developed algorithm. Then its efficiency is tested over available assembly line balancing benchmarks and compared to a new algorithm provided recently in the bi-objective SALBP-2 literature. Computational experiments indicate that the developed algorithm outperforms the existing meta-heuristic over a large group of benchmarks.     

Coupling ant colony optimization and the extended great deluge algorithm for the discrete facility layout problem

This article uses a hybrid optimization approach to solve the discrete facility layout problem (FLP), modelled as a quadratic assignment problem (QAP). The idea of this approach design is inspired by the ant colony meta-heuristic optimization method, combined with the extended great deluge (EGD) local search technique. Comparative computational experiments are carried out on benchmarks taken from the QAP-library and from real life problems. The performance of the proposed algorithm is compared to construction and improvement heuristics such as H63, HC63-66, CRAFT and Bubble Search, as well as other existing meta-heuristics developed in the literature based on simulated annealing (SA), tabu search and genetic algorithms (GAs). This algorithm is compared also to other ant colony implementations for QAP. The experimental results show that the proposed ant colony optimization/extended great deluge (ACO/EGD) performs significantly better than the existing construction and improvement algorithms. The experimental results indicate also that the ACO/EGD heuristic methodology offers advantages over other algorithms based on meta-heuristics in terms of solution quality.