Evolutionary Algorithms for Multi-Objective Scheduling in a Hybrid Manufacturing System

Evolutionary Algorithms for Multi-Objective Scheduling in a Hybrid Manufacturing System

Ömer Faruk Yılmaz (Istanbul Technical University, Turkey & Yalova University, Turkey) and Mehmet Bülent Durmuşoğlu (Istanbul Technical University, Turkey)
DOI: 10.4018/978-1-5225-2944-6.ch008
OnDemand PDF Download:
List Price: $37.50


Problems encountered in real manufacturing environments are complex to solve optimally, and they are expected to fulfill multiple objectives. Such problems are called multi-objective optimization problems(MOPs) involving conflicting objectives. The use of multi-objective evolutionary algorithms (MOEAs) to find solutions for these problems has increased over the last decade. It has been shown that MOEAs are well-suited to search solutions for MOPs having multiple objectives. In this chapter, in addition to comprehensive information, two different MOEAs are implemented to solve a MOP for comparison purposes. One of these algorithms is the non-dominated sorting genetic algorithm (NSGA-II), the effectiveness of which has already been demonstrated in the literature for solving complex MOPs. The other algorithm is fast Pareto genetic algorithm (FastPGA), which has population regulation operator to adapt the population size. These two algorithms are used to solve a scheduling problem in a Hybrid Manufacturing System (HMS). Computational results indicate that FastPGA outperforms NSGA-II.
Chapter Preview


There are two important difficult to handle features of real-world problems. One is the size of the problem which is quite larger than the hypothetical problems and the other is presence of hard constraints to be satisfied. Therefore, finding solutions to such problems through classical optimization methods is difficult regarding the excessive computational time. It may take hours or even days to find a feasible solution to such problems. Metaheuristic or problem-specific heuristic methods are proposed to solve these types of problems. In this study, the evolutionary algorithms (EAs) that provide good solutions especially to large-sized problems are used (Das and Panigrahi, 2009). EAs are stochastic population-based algorithms which can be implemented to many real-world problems easily and inspire their structures from the original mechanism of nature. EAs are the most utilized population-based algorithms and have proved their effectiveness in many fields such as continuous or combinatorial optimization, system modeling and identification, planning and control, engineering design, data mining and machine learning (Talbi, 2009).

There are different optimization methods such as goal programming and variations, and min-max algorithms, which are used for solving multi-objective optimization problems. However, it is seen that multi-objective evolutionary algorithms have been extensively used in recent years including this study (Yilmaz and Erbiyik, 2016; Zhou et al., 2011; Tang and Wang, 2013). Moreoever, multi-objective evolutionary algorithms have proved their effectiveness to solve MOPs. (Yilmaz and Erbiyik, 2016; Deb, 2001; Deb et al., 2002; Zhou et al., 2011; Tang and Wang, 2013; Eskandari and Geiger, 2008).

It must also be noted that MOEAs are different than single-objective optimization algorithms regarding the fitness function, diversity preserving, and elitism and these ensure that many missing points faced in single-objective optimization algorithms are fulfilled (Tang and Wang, 2013).

In this study, two different MOEAs (NSGA-II and FastPGA) are used to solve multi-objective scheduling problem in HMS and their solutions are compared with one another. In this context, five different hypothetical cases are designed, each having different problem sizes. The NSGA-II algorithm has already demonstrated its effectiveness in many expensive MOPs. That is why it is considered suitable for MOPs. The FastPGA algorithm, on the other hand, is used in this study because it employs the adaptive population sizing strategy, which is known as effective to solve expensive MOPs.

One of the most important points of the current study is the multi-objective mathematical model that was developed for these types of problems (Yılmaz and Durmusoglu, 2017). In addition, the similarity of HMSs with real manufacturing environments increases the applicability of both the developed mathematical model and the study results in industrial applications. In this respect, the current study will also contribute to industrial applications. The developed mathematical model within this study may also be adapted and used for other manufacturing systems, including assembly lines, and cellular manufacturing systems (CMS).

The rest of the study is organized as follows: In the second section, the evolutionary algorithms for multi-objective optimization problems are given. In the third section, literature review is presented for the related studies. The fourth section covers the definition of the problem and its mathematical model. The detailed structures of MOEAs are addressed in the fifth part. The algorithms are run through hypothetical examples and the NSGA-II and the FastPGA are compared in the sixth section. The conclusions and future research directions are given in the sixth section.

Key Terms in this Chapter

Pareto Optimal Solution: A solution is called Pareto optimal, if none of the objective functions can be improved without degrading some of the other objective values.

Evolutionary Algorithm: An evolutionary algorithm is inspired by biological evolution and uses crossover, mutation, selection mechanisms.

Hybrid Manufacturing System: A manufacturing system that contains both cells and a functional area. It provides flexibility and allows the production of many kinds of products.

Pareto Front: The set that corresponds to Pareto set and is composed of all Pareto optimal decision vectors is called Pareto front.

Batch Scheduling in Hybrid Manufacturing: A type of operations research problem involving sequencing and scheduling of batches on cells and machines in functional area.

Multi-Objective Optimization: A topic of multiple-criteria decision-making dealing with mathematical optimization problems which consists of more than one objective to be optimized at the same time.

Complete Chapter List

Search this Book: