A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem

In this paper, a novel multi-objective location model within multi-server queuing framework is proposed, in which facilities behave as M/M/m queues. In the developed model of the problem, the constraints of selecting the nearest-facility along with the service level restriction are considered to bring the model closer to reality. Three objective functions are also considered including minimizing (I) sum of the aggregate travel and waiting times, (II) maximum idle time of all facilities, and (III) the budget required to cover the costs of establishing the selected facilities plus server staffing costs. Since the developed model of the problem is of an NP-hard type and inexact solutions are more probable to be obtained, soft computing techniques, specifically evolutionary computations, are generally used to cope with the lack of precision. From different terms of evolutionary computations, this paper proposes a Pareto-based meta-heuristic algorithm called multi-objective harmony search (MOHS) to solve the problem. To validate the results obtained, two popular algorithms including non-dominated sorting genetic algorithm (NSGA-II) and non-dominated ranking genetic algorithm (NRGA) are utilized as well. In order to demonstrate the proposed methodology and to compare the performances in terms of Pareto-based solution measures, the Taguchi approach is first utilized to tune the parameters of the proposed algorithms, where a new response metric named multi-objective coefficient of variation (MOCV) is introduced. Then, the results of implementing the algorithms on some test problems show that the proposed MOHS outperforms the other two algorithms in terms of computational time.     

A genetic algorithm with the heuristic procedure to solve the multi-line layout problem

The paper presents a genetic algorithm-based meta-heuristic to solve the facility layout problem (FLP) in a manufacturing system, where the material flow pattern of the multi-line layout is considered with the multi-products. The matrix encoding technique has been used for the chromosomes under the objective of minimizing the total material handling cost. The proposed algorithm produces a table with the descending order of the data corresponding to the input values of the flow and cost data. The generated table is used to create a schematic representation of the facilities, which in turn is utilized to heuristically generate the initial population of the chromosomes and to handle the heuristic crossover and mutation operators. The efficiency of the proposed algorithm has been proved through solving the two examples with the total cost less than the other genetic algorithms, CRAFT algorithm, and entropy-based algorithm.     

Solving an extended multi-row facility layout problem with fuzzy clearances using GA

Multi-row facility layout problem (MRFLP) is a class of facility layout problems, which decides upon the arrangement of facilities in some fixed numbers of rows in order to minimize material handling cost. Nowadays, according to the new layout requirements, the facility layout problems (FLPs) have many applications such as hospital layout, construction site layout planning and layout of logistics facilities. Therefore, we study an extended MRFLP, as a novel layout problem, with the following main assumptions: 1) the facilities are arranged in a two-dimensional area and without splitter rows, 2) multiple products are available, 3) distance between each pair of facilities, due to inaccurate and flexible manufacturing processes and other limitations (such as WIPs, industrial instruments, transportation lines and etc.), is considered as fuzzy number, and 4) the objective function is considered as minimizing the material handling and lost opportunity costs. To model these assumptions, a nonlinear mixed-integer programming model with fuzzy constraints is presented and then converted to a linear mixed-integer programming model. Since the developed model is an NP-hard problem, a genetic algorithm approach is suggested to find the best solutions with a minimum cost function. Additionally, three different crossover methods are compared in the proposed genetic algorithm and finally, a sensitivity analysis is performed to discuss important parameters.     

Multiobjective differential evolution using homeostasis based mutation for application in software cost estimation

The problem in software cost estimation revolves around accuracy. To improve the accuracy, heuristic/meta-heuristic algorithms have been known to yield better results when it is applied in the domain of software cost estimation. For the sake of accuracy in results, we are still modifying these algorithms. Here we have proposed a new meta-heuristic algorithm based on Differential Evolution (DE) by Homeostasis mutation operator. Software development requires high prediction and low Root Mean Squared Error (RMSE) and mean magnitude relative error(MMRE). The problem in software cost estimation relates to accurate prediction and minimization of RMSE and MMRE, which are used to solve multiobjective optimization. Many versions of DE were proposed, however multi-objective versions where the concept of Pareto optimality is used, are most popular. Pareto-Based Differential Evolution (PBDE) is one of them. Although the performance of this algorithm is very good, its convergence rate can be further improved by minimizing the time complexity of nondominated sorting, and by improving the diversity of solutions. This has been implemented by using efficient nondominated algorithm whose time complexity is better than the previous one and a new mutation scheme is implemented in DE which can provide more diversity among solutions. The proposed variant multiplies the Homeostasis value with one more vector, named the Homeostasis mutation vector, in the existing mutation vector to provide more bandwidth for selecting effective mutant solutions. The proposed approach provides more promising solutions to guide the evolution and helps DE escape the situation of stagnation. The performance of the proposed algorithm is evaluated on twelve benchmark test functions (bi-objective and tri-objective) on the Pareto-optimal front. The performance of the proposed algorithm is compared with other state-of-the-art algorithms on five multi-objective evolutionary algorithms (MOEAs). The result verifies that our proposed Homeostasis mutation strategy performs better than other state-of-the-art algorithms. Finally, application of MODE-HBM is applied to solve in terms of Pareto front, representing the trade-off between development RMSE, MMRE, and prediction for COCOMO model.     

A fast two-stage hybrid meta-heuristic algorithm for robust corridor allocation problem

The optimisation of the corridor allocation problem (CAP) belongs to the optimisation of the efficiency of the automated production line. The goal is to reduce the material handling cost (MHC) in the production process through a reasonable layout of the facilities, so as to save expenses for the enterprise. In recent years, with the acceleration of market changes, product design and production process adjustments have become more frequent, and more attention has been paid to the research on the layout of facilities under the condition of changes in the flow of materials between production facilities over time. On the basis of the CAP model, this paper considers the optimisation problem of row layout when the flow of materials between facilities fluctuates in a certain range. The new model can be utilised to obtain the overall optimisation solution under the condition of the floating material flow matrix, so as to achieve the goal of optimising the total MHC in the entire production process. As the new model introduces more variables and intermediate parameters, a two-stage solution method is previously required, which greatly increases the time to solve the problem. This paper proposes a targeted meta-heuristic algorithm optimisation method combining the advantages of tabu search algorithm and harmony search algorithm, which simplifies the solution phase of calling the precise solver in the two-stage algorithm of row facility layout problem, improves the problem solving efficiency, and makes the solution of large-scale problems become possible. The proposed model is verified through Lingo software, and then the model and the hybrid algorithm in the MATLAB environment are verified with each other. Finally, the proposed simplified algorithm is utilised to solve the large-scale problems that could not be solved by the two-stage algorithm before.     

Genetic application in a facility location problem with random demand within queuing framework

In many service and industrial applications of the facility location problem, the number of required facilities along with allocation of the customers to the facilities are the two major questions that need to be answered. In this paper, a facility location problem with stochastic customer demand and immobile servers is studied. Two objectives considered in this problem are: (1) minimizing the average customer waiting time and (2) minimizing the average facility idle-time percentage. We formulate this problem using queuing theory and solve the model by a genetic algorithm within the desirability function framework. Several examples are presented to demonstrate the applications of the proposed methodology.     

Optimizing a bi-objective multi-product EPQ model with defective items,rework and limited orders: NSGA-II and MOPSO algorithms

In this paper, a bi-objective multi-products economic production quantity (EPQ) model is developed, in which the number of orders is limited and imperfect items that are re-workable are produced. The objectives of the problem are minimization of the total inventory costs as well as minimizing the required warehouse space. The model is shown to be of a bi-objective nonlinear programming type, and in order to solve it two meta-heuristic algorithms namely, the non-dominated sorting genetic algorithm (NSGA-II) and multi-objective particle swarm optimization (MOPSO) algorithm, are proposed. To verify the solution obtained and to evaluate the performance of proposed algorithms, two-sample t-tests are employed to compare the means of the first objective value, the means of the second objective values, and the mean required CPU time of solving the problem using two algorithms. The results show while both algorithms are efficient to solve the model and the solution qualities of the two algorithms do not differ significantly, the computational CPU time of MOPSO is considerably lower than that of NSGA-II.     

混合群体增量学习算法求解闭环布局问题

闭环布局问题（CLLP）是一种NP-困难的混合优化问题,它在大小可调的矩形环上寻找设施最佳放置次序,目标是最小化设施之间物料流的运输成本。现有方法均采用元启发式算法来寻找最优的设施放置次序,并且通过枚举方法来获得最优的矩形环大小,而枚举方法的计算效率不高。为了解决这个问题,提出了求解CLLP的混合群体增量学习（HPBIL）算法,分别使用离散群体增量学习（DPBIL）算子和连续PBIL（CPBIL）算子同时对设施放置次序和矩形环大小进行优化,提高了搜索效率;同时还设计了一个局部搜索算法来优化每代中的部分优质解,以提高算法的求精能力。在13个CLLP测试实例上进行实验,结果表明HPBIL算法在9个测试实例上找到了新的最优布局,它对CLLP的寻优能力明显优于对比算法。     

A memetic genetic algorithm for the vertex p-center problem

Abstract The p-center problem is one of choosing p facilities from a set of candidates to satisfy the demands of n clients in order to minimize the maximum cost between a client and the facility to which it is assigned. In this article, PBS, a population based meta-heuristic for the p-center problem, is described. PBS is a genetic algorithm based meta-heuristic that uses phenotype crossover and directed mutation operators to generate new starting points for a local search. For larger p-center instances, PBS is able to effectively utilize a number of computer processors. It is shown empirically that PBS has comparable performance to state-of-the-art exact and approximate algorithms for a range of p-center benchmark instances.     

A new approach to cooperative competition in facility location problems: Mathematical formulations and an approximation algorithm

This paper deals with cooperative competition in facility location problems in which potential players (investors) are in competition (or conflict) over acquiring suitable sites and clients. In order to formulate the problem, a game-theoretical multi-objective model with the objective of maximizing investor utility is presented. In the proposed method, an acceptance threshold constraint is applied to facility allocation that is based on a combination of distance between a facility and clients, and investors’ product prices. Since the common solution methods for multi-objective optimization, such as weighted sums, ε-constraints, multi-objective meta-heuristic algorithms, etc. are not efficient enough, and cannot guarantee achieving Nash equilibrium points, a new approach is developed to solve the presented problem. Moreover, according to the computational complexity of the problem, an approximation algorithm is introduced for large-sized problems. Finally, the computational results demonstrate that the proposed algorithm performs efficiently in obtaining Nash equilibrium points.     

An energy-efficient reliable grid scheduling model using NSGA-II

Job scheduling in computational grid is a complex problem and various heuristics and meta-heuristics have been proposed for the same. These approaches usually optimize specific characteristic parameters while allocating the jobs on the grid resources. Many a times, it is desired to optimize multiple parameters during job scheduling. Non-dominated sorting genetic algorithm (NSGA-II) has been observed to be the best meta-heuristic to solve such multi-objective optimization problem. The proposed work applies NSGA-II for job scheduling in computational grid with three conflicting objectives: maximizing reliability of the system for job allocation, minimizing energy consumption and balancing the load on the system. Performance study of the proposed model is done by simulating it on some real data. The result indicates that the proposed model performs well with multiple objectives.     

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times

Electromagnetism-like mechanism (EM) is a novel meta-heuristic, inspired by the attraction–repulsion mechanism of electromagnetic theory. There are very few applications of EM in scheduling problems. This paper presents a discrete EM (DEM) algorithm for minimizing the total weighted tardiness in a single-machine scheduling problem with sequence-dependent setup times. Unlike other discrete EM algorithms that use a random key method to deal with the discreteness, the proposed DEM algorithm employs a completely different approach, with an attraction–repulsion mechanism involving crossover and mutation operators. The proposed algorithm not only accomplishes the intention of an EM algorithm but also can be applied in other combinatorial optimization problems. To verify the algorithm, it is compared with a discrete differential evolution (DDE) algorithm, which is the best meta-heuristic for the considered problem. Computational experiments show that the performance of the proposed DEM algorithm is better than that of the DDE algorithm in most benchmark problem instances. Specifically, 30 out of 120 aggregated best-known solutions in the literature are further improved by the DEM algorithm, while other another 70 instances are solved to an equivalent degree.     

Modeling and solving a capacitated stochastic location-allocation problem using sub-sources

We study a capacitated multi-facility location-allocation problem in which the customers have stochastic demands based on Bernoulli distribution function. We consider the capacitated sub-sources of facilities to satisfy demands of customers. In the discrete stochastic problem, the goal is to find optimal locations of facilities among candidate locations and optimal allocations of existing customers to operating facilities so that the total sum of fixed costs of operating facilities, allocation cost of the customers, expected values of servicing and outsourcing costs is minimized. The model is formulated as a mixed-integer nonlinear programming problem. Since finding an optimal solution may require an excessive amount of time depending on nonlinear constraints, we transform the nonlinear constraints of the problem to linear ones to arrive at a simple formulation of the model. Numerical results show that the LINGO 9.0 software is capable of solving small size problems. For medium and large-size problems, we propose two meta-heuristic algorithms, namely a genetic algorithm and a discrete version of colonial competitive algorithm. Computational results show that the proposed algorithms efficiently obtain effective solutions.     

A grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness

In this paper we address the problem of minimizing the weighted sum of makespan and maximum tardiness in an m-machine flow shop environment. This is a NP-hard problem in the strong sense. An attempt has been made to solve this problem using a metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is a competitive algorithm and is a meta-heuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a bicriteria flow shop problem and a new algorithm named B-GRASP (Bicriteria GRASP algorithm) is proposed. The new proposed algorithm is evaluated using benchmark problems taken from Taillard and compared with the existing simulated annealing based heuristic developed by Chakravarthy and Rajendran. Computational experiments indicate that the proposed algorithm is much better than the existing one in all cases.     

Two-sided assembly line balancing problem of type I: Improvements,a simple algorithm and a comprehensive study

Many meta-heuristic methods have been applied to solve the two-sided assembly line balancing problem of type I with the objective of minimizing the number of stations, but some of them are very complex or intricate to be extended. In addition, different decoding schemes and different objectives have been proposed, leading to the different performances of these algorithms and unfair comparison. In this paper, two new decoding schemes with reduced search space are developed to balance the workload within a mated-station and reduce sequence-depended idle time. Then, graded objectives are employed to preserve the minor improvements on the solutions. Finally, a simple iterated greedy algorithm is extended for the two-sided assembly line balancing problem and modified NEH-based heuristic is introduced to obtain a high quality initial solution. And an improved local search with referenced permutation and reduced insert operators is developed to accelerate the search process. Computational results on benchmark problems prove the efficiency of the proposed decoding schemes and the new graded objectives. A comprehensive computational comparison among 14 meta-heuristics is carried out to demonstrate the efficiency of the improved iterated greedy algorithm.     

Spherical evolution for solving continuous optimization problems

In these years, more and more nature-inspired meta-heuristic algorithms have been proposed; search operators have been their core problem. The common characteristics or mechanism of search operators in different algorithms have not been represented by a standard format. In this paper, we first propose the concept of a search pattern and a search style represented by a mathematical model. Second, we propose a new search style, namely a spherical search style, inspired by the traditional hypercube search style. Furthermore, a spherical evolution algorithm is proposed based on the search pattern and spherical search style. At the end, 30 benchmark functions of CEC2017 and a real-world optimization problem are tested. Experimental results and analysis demonstrate that the proposed method consistently outperforms other state-of-the-art algorithms.     

Solving a single-machine scheduling problem with maintenance,job deterioration and learning effect by simulated annealing

This paper presents a new nonlinear multi-objective mathematical model for a single-machine scheduling problem with three objectives: (1) minimizing the sum of the weighted jobs completion, (2) minimizing the sum of the weighted delay times, and (3) maximizing the sum of the job values in makespan. In addition, a number of constraints are incorporated in this presented model, such as repairing and maintenance periods, deterioration of jobs, and learning effect of the work process. Since this type of scheduling problem belongs to a class of NP-hard ones, its solution by common software packages is almost impossible, or at best very time consuming. Thus, a meta-heuristic algorithm based on simulated annealing (SA) is proposed to solve such a hard problem. At a final stage, the related results obtained by the proposed SA are compared with those results reported by the Lingo 8 software in order to demonstrate the efficiency and capability of our proposed SA algorithm.     

A multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a Make-To-Order environment,considering order priority

Nowadays, mixed-model assembly line is used increasingly as a result of customers’ demand diversification. An important problem in this field is determining the sequence of products for entering the line. Before determining the best sequence of products, a new procedure is introduced to choose important orders for entering the shop floor. Thus the orders are sorted using an analytical hierarchy process (AHP) approach based on three criteria: critical ratio of each order (CR_o), Significance degree of customer and innovation in a product, while the last one is presented for the first time. In this research, six objective functions are presented: minimizing total utility work cost, total setup cost and total production rate variation cost are the objectives which were presented previously, another objective is minimizing total idle cost, meanwhile two other new objectives regarding minimizing total operator error cost and total tardiness cost are presented for the first time. The total tardiness cost tries to choose a sequence of products that minimizes the tardiness cost for customers with high priority. First, to check the feasibility of the model, GAMS software is used. In this case, GAMS software could not search all of the solution space, so it is tried in two stages and because this problem is NP-hard, particle swarm optimization (PSO) and simulated annealing (SA) algorithms are used. For small sized problems, to compare exact method with proposed algorithms, the problem must be solved using meta-heuristic algorithms in two stages as GAMS software, whereas for large sized problems, the problem can be solved in two ways (one stage and two stages) by using proposed algorithms; the computational results and pairwise comparisons (based on sign test) show GAMS is a proper software to solve small sized problems, whereas for a large sized problem the objective function is better when solved in one stage than two stages; therefore it is proposed to solve the problem in one stage for large sized problems. Also PSO algorithm is better than SA algorithm based on objective function and pairwise comparisons.