دانلود رایگان ترجمه مقاله الگوریتم ژنتیک چند هدفی در برنامه زمان بندی جریان کارگاهی (نشریه الزویر 1996)

الگوریتم ژنتیک چند هدفی و کاربردهای آن در برنامه زمان بندی جریان کارگاهی

Multi-objective genetic algorithm and its applications to flowshop scheduling

Abstract

ln this paper, we propose a multi-objective genetic algorithm and apply it to flowshop scheduling. The characteristic features of our algorithm are its selection procedure and elite preserve strategy. The selection procedure in our multi-objective genetic algorithm selects individuals for a crossover operation based on a weighted sum of multiple objective functions with variable weights. The elite preserve strategy in our algorithm uses multiple elite solutions instead of a single elite solution. That is, a certain number of individuals are selected from a tentative set of Pareto optimal solutions and inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply the proposed genetic algorithm to a two-objective function optimization problem with a concave Pareto front. Last, the performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime.

1 Introduction

Flowshop scheduling problems are one of the most well known problems in the area of scheduling. The objective of minimizing the makespan is often employed as a criterion of flowshop scheduling since Johnson’s work [1]. Various heuristic approaches (e.g., Dannenbring [2], Nawaz et al. [3], Osman and Potts [4] and Widmer and Hertz [5]) as well as optimization techniques (e.g., Ignall and Schrage [6] and Lomnicki [7]) have been proposed for minimizing the makespan. While these studies treated a single objective, many real-world problems involve multiple objectives. Recently several researchers have tackled multi-objective flowshop scheduling problems. For example, Ho and Chan [8] proposed a heuristic method for flowshop scheduling with bicriteria, Gangadharan et al. [9] proposed a simulated annealing heuristic for flowshop scheduling with bicriteria, and Morizawa et al. [10] proposed a complex random sampling method for multi-objective problems.

Genetic algorithms have been mainly applied to single-objective optimization problems. When we apply a single-objective genetic algorithm to a multi-objective optimization problem, multiple objective functions should be combined into a scalar fitness function. If we assign a constant weight to each of the multiple objective functions for combining them, the direction of search in the genetic algorithm is constant in the multi-dimensional objective space as shown in Fig. 1. In Fig. I, f~(.) is an objective function to be maximized and J~(.) is to be minimized. The closed circle in Fig. 1 represents the final solution by the single-objective genetic algorithm.

Some studies have been attempted for designing multi-objective genetic algorithms since Schaffer’s work [11]. Schaffer proposed the Vector Evaluated Genetic Algorithm (VEGA) for finding Pareto optimal solutions of multi-objective optimization problems. In Schaffer’s VEGA, a population was divided into disjoint subpopulations, then each subpopulation was governed by its own objective function. Although Schaffer [11] reported some successful results, his approach seems to be able to find only extreme solutions on Pareto fronts as shown in Fig. 2 because its search directions are parallel to the axes of the objective space. Schaffer suggested two approaches to improve his approach in his paper [11]. One is to provide a heuristic selection preference for non-dominated individuals in each generation. The other is to crossbreed among the “species” by adding some mate selection.

The point of multi-objective optimization problems is how to find all possible tradeoffs among multiple objective functions that are usually conflicting. Since it is difficult to choose a single solution for a multi-objective optimization problem without iterative interaction with the decision maker, one general approach is to show the set of Pareto optimal solutions to the decision maker. Then the decision maker can choose any one of the Pareto optimal solutions. To find out all the Pareto optimal solutions by genetic algorithms, the variety of individuals should be kept in each generation. Recently Gen et al. [12] proposed a genetic algorithm for solving a bicriteria transportation problem, Tamaki et al. [13] proposed a genetic algorithm for scheduling problems with multi-criteria, and Horn et al. [14] proposed the Niched Pareto Genetic Algorithm by incorporating the concept of Pareto domination in the selection procedure and applying a niching pressure to spend the population out along Pareto fronts.

In this paper, we propose a multi-objective genetic algorithm with various search directions as shown in Fig. 3. There are two characteristic features of our algorithm. One is its selection procedure. In the selection procedure, our multi-objective genetic algorithm uses a weighted sum of multiple objective functions to combine them into a scalar fitness function. The weights attached to the multiple objective functions are not constant but randomly specified for each selection. Therefore the direction of the search in our multi-objective genetic algorithm is not constant. The other characteristic feature of our algorithm is its elite preserve strategy. A tentative set of Pareto optimal solutions is preserved in the execution of our multi-objective genetic algorithm. A certain number of individuals in this set are inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply our proposed genetic algorithm to a two-objective function optimization problem with concave Pareto fronts. The performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime.