Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.16 No.2 pp.253-264
DOI : https://doi.org/10.7232/iems.2017.16.2.253

A Multi-Objective Evolutionary Algorithm for Scheduling Flexible Manufacturing Systems

Mehrdad Nouri Koupaei, Mohammad Mohammadi*, Bahman Naderi
Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran
Corresponding Author, Mohammadi@khu.ac.ir
December 31, 2016 March 2, 2017 April 3, 2017

ABSTRACT

In recent decades, flexible manufacturing systems have emerged as a response to market demands of high product diversity. Scheduling is one important phase in production planning in all manufacturing systems. Although scheduling in classical manufacturing systems, such as flow and job shops, are well studied. Rarely, any paper studies scheduling of the more recent flexible manufacturing system. Since the problem class is NP-hard, different scheduling algorithms such as genetic algorithm (GA), simulated annealing (SA) algorithm, memetic algorithm (MA) and particle swarm algorithm (PSA) can be designed to solve this problem. This paper investigates a multi-objective evolutionary algorithm for scheduling flexible manufacturing systems to minimizing makespan, earliness and tardiness and startup costs. The distinctive feature of the proposed multi-objective evolutionary algorithm is its ability to search the solution space by an intelligent method, which is unlike other meta-heuristic algorithms avoid the coincidental method. Also, answer with the best quality and highest dispersion to obtain the dominant answer is used. Finally, we carry out computational experiments to demonstrate the effectiveness of our algorithm. The results show that the proposed algorithm has the ability to achieve the good solutions in reasonable computational time.


초록


    1.INTRODUCTION AND LITERATURE REVIEW

    Nowadays, producers have concluded that the mass production system is not able to compete in this flexible environment. Generally, most approaches that used to sustain profitability on new products or upgrading existing products. Both of which require production systems that rely on its flexibility, can satisfy the diverse demands of market (Koupaei et al., 2016a). The optimal scheduling of FMS is a critical issue and it is a complex problem. Scheduling in FMSs differs from that in a conventional job shop because of the availability resulting in routing flexibility of alternating manufacturing resources. When alternate routes are not feasible, this output has been increased by eliminating the bottle-necks. FMS is a highly integrated manufacturing system with some amount of flexibility that allows the system to react in case of changes, whether predicted or unpredicted. Also, the inter- relationships between its various components are not well understood for a very complex system. Due to this complexity, it is difficult to accurately calculate the performance measures of the FMS which leads to its design through mathematical techniques. Flexible manufacturing systems have been developed to combine the flexibility of open shops and the productivity of job shops. A flexible manufacturing system (FMS) are includes a set of n jobs and a set of m machine. Each job consists of a chain of operations, each of which needs to be processed during an immediately on a given machine. Each machine can process at most one operation at a time. The goal of FMS is assigning the operations to each machine and sequenc- ing of operations for each machine. From the point of view of scheduling, FMS have been classified into four types: flexible manufacturing cells (FMCs); single flexible machines (SFMs); multi-cell flexible manufacturing systems (MCFMSs) and multi-machine flexible manufacturing systems (MMFMSs). In this paper, a multi-objective evolutionary algorithm for scheduling flexible manufacturing systems to minimizing makespan, earliness and tardiness and startup costs are presented.

    In the literature, different algorithms such as tabu search, Petri net, Artificial Immune System, ant colony, Simulated Annealing, branch and bound and integer programming have been used to solve the FMS scheduling problem. Solving a scheduling problem is to determine a sequence of operations in every job so that the makespan is minimized or the satisfying the manufacturing objectives have been maximized.

    There are few studies that refer to FMS scheduling. One such is Lee and Lee (2010), who using lower bound reach ability matrix with the heuristic function for the FMS scheduling problems with multiple lot size. In another research, Huang et al. (2014a), proposed an improved search strategy that applied in FMS scheduling with the P-timed Petri net framework. Also, Özpeynirci (2015) proposed a heuristic approach based on the mathematical model to solve the scheduling and tool loading problems in flexible manufacturing systems. To address the manufacturing system scheduling problem, Heuristic algorithm and Petri net (PN) has often been used by Han et al. (2013), Lei et al. (2014), Huang et al. (2014b) and Baruw and Piera (2015). Some research using a genetic algorithm to solve the FMS scheduling problem. Zakaria and Petrovic (2012) proposed a genetic algorithm for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by sequencing operations, respectively. Kumar et al. (2006) presented a new integrated approach to concurrently address the machine loading and the tool allocation problems in an FMS environment. This proposed CBGA enforced the procedure of traditional GA capabilities that specialized operators. Candan and Yazgan (2015) Studied on genetic algorithm parameter optimization using Taguchi method for a flexible manufacturing system scheduling problem. Also, the another research using genetic algorithm was studied by Wu et al. (2013), Soolaki and Zarrinpoor (2014), Abazari et al. (2012), Filho et al. (2012), Umar et al. (2015) and Koupaei et al. (2017).

    Pitts and Ventur (2009) addressed the scheduling FMS problem in a single facility. In this paper, a twostage Tabu Search (TS2) algorithm was created to solve various instances of the problem in a more time-efficient manner. Naderi and Azab (2015) solved a scheduling of a flexible manufacturing cell with parallel processing capability. They developed five metaheuristics based on the proposed encoding scheme, operators and local search. Then, the test cases are used to evaluate and compare the algorithms as well as the mathematical model.

    Also, the search problem using a Simulated Annealing approach was studied by Balaji and Porselvi (2014) and Koupaei et al. (2016b). To find the branch and bound approach in FMS scheduling problems, Özpeynirci and Azizoğlu (2009) and Kim and Yano (1994) have studied.

    2.PROBLEM FORMULATION

    Model Assumptions

    Assumptions considered for this model include:

    • Tasks can be processed on machines with any order.

    • The time processing of tasks on different machines, may be different.

    • Any task at any moment can only be processed on a machine and each machine at any moment can only perform one operation.

    • Tasks cutting and machines failure are not allowed.

    • Each task has a certain delivery date.

    • There is only one machine of any type in the workplace.

    • All machines are available from the beginning.

    • Setup time for each machines is zero.

    • The cost of setting up of each task on the machines, is depends to previous task on the same machine.

    • All processing time and delivery dates are considered definitive.

    Indices

    Indices used in the mathematical model are as follows:

    • i, j =  {1, …, n} Indices of tasks

    • k, l =  {1, …, m} Indices of machines

    The input parameters:

    • T(i, k) :  Processing time of task i on machine k

    • C(i, k) :  Completion time of task i on machine k

    • di :  Delivery time of task i

    • Oik :  Operation of task i on machine k

    • Si (j, k) :  The cost of setting up of machine k for task j, When the previous task was on machine i, k.

    Decision variables:

    • C(i, k) :  Completion time of task i on machine k

    • mc(i) :  Completion time of task i

    a i l k = { 1 T a s k i o n m a c h i n e k w a s d o n e a n d p r e v i o u s m a c h i n e w a s l 0           o t h e r w i s e

    x i j k = { 1 T a s k j o n m a c h i n e k w a s d o n e a n d p r e v i o u s t a s k o n m a c h i n e i k w a s 0           o t h e r w i s e

    Mathematical model(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)

    Min  Z 1
    (1)

    Min  Z 2
    (2)

    Min  Z 3
    (3)

    Z 1 c ( i , k ) i = 1 , , n ; k = 1 , , m
    (4)

    c ( i , k ) t ( i , k ) + M ( 1 a i j k ) c ( i , l )           i = 1 , , n ; k , l = 1 , , m
    (5)

    c ( j , k ) t ( j , k ) + M ( 1 x i j k ) c ( i , k )           i , j = 1 , , n ; k = 1 , , m
    (6)

    a i l k + a i k l = 1 i = 1 , , n ; k , l = 1 , , m
    (7)

    x i j k + x j i k = 1 i , j = 1 , , n k = ;      1 , m
    (8)

    c ( i , k ) t ( i , k ) 0 i = 1 , , n ;    k = 1 , , m
    (9)

    m c ( i ) = max { c ( i , k ) } i = 1 , , n ;    k = 1 , , m
    (10)

    Z 2 = i = 1 n max { | m c ( i ) d i | }
    (11)

    Z 2 = k = 1 m j = 1 n i = 1 n S i ( j , k ) x i j k
    (12)

    Equations 1, 2 and 3 are objective functions. Equation 1 is minimizing makespan, equation 2 is minimizing earliness and tardiness and equation 3 is minimizing the total startup costs. Equation 4 is auxiliary equation, to avoid using the Max function in the mathematical model. Since the objective function is to minimize Z1, and Z1 is larger than or equal to the maximum time to complete, therefore, the use of this constraint will be given priority to use the function Max. Equations 5 and 6 calculates the completion time of various operations of any tasks on machines. Equation 5 implies that the completion time of two successive operations of a job on two machine, should be away from their previous operation at least as much processing time. Equation 6 implies that the completion time of two successive task on one machine, should be away from their previous task at least as much processing time. Equations 7 and 8 are auxiliary equations that determined transposition of operations between each other and on the machines. Equation 9 is to set the time of first operation of each task on the machines. Equation 10 calculates the completion time of each task. This value is used to calculate the tardiness and earliness of tasks. Equation 11 calculates the total tardiness and earliness of tasks. Equation 12 calculates the total cost of setting up of each task.

    3.SCATTER SEARCH METHOD

    Scatter search method is based on an intelligent method to search the solution space which is unlike other meta-heuristic algorithms such as genetic algorithm, avoid the coincidental method. The distinctive feature of the proposed multi-objective evolutionary algorithm is its ability to search the solution space by an intelligent method, which is unlike other meta-heuristic algorithms avoid the coincidental method (Cotta, 2006). Also, answer with the best quality and highest dispersion to obtain the dominant answer is used. This algorithm searches the space of problem by product better answer (answers), with combining existing answers that have the potential to combine. In other words, in distributed search method, the approach of selecting answers has certain specific pattern that used to mergers and acquisitions the solutions by achieving the better solutions and searching the space of problem. The purpose of this method, enabling problem- solving process which can conclude the new answers from compositional elements.

    Scatter search methods combine the solution and use an online collection of reference solutions for combining set. This methodology is distinct from other population-based techniques. To create and maintain a reference collection, including b number of best found solution, due to the quality and variety of solutions come join to reference set. Combining solutions in this method is that a new solution is created from a linear combination of two other the solutions. So the resulting reference set is displayed as shown below (Figure 1).

    This figure assumes that the main reference set, covers the indicated circle of sections A, B, C. The solution 1 is created from a convex combination of reference solutions A, B that is added to the reference set as the only solution. In a similar way, combining of convex and nonconvex reference of new and original solutions are created points 2, 3 and 4. The complete reference set are including 7 solutions (members) that is shown in the figure above. In genetic algorithm, two solutions are selected randomly from the population and a crossover operator used for the production of one or more children. GA are including a sample population of 100 elements that are selected randomly to create crossover. But in scatter search, two or more of the reference set in a systematic approach in order to produce new solutions are choice. In general, the reference set in search of scattered have the number of 20 or less than 20 the solution. Generally, if the reference set have the number of b solutions, this procedure is evaluating approximately (3b-7)/2 combination of four different types. The base model is including a combination of two the answers, the next sample is including a combining three answers, and so will continue. The search area can be limited to a select group of any types of combinations such that was as a mechanism to control the number of possible combinations in a reference set.

    4.THE GENERAL STRUCTURE OF SCATTER SEARCH METHOD

    The general structure of Scatter search method is including five sections as following:

    • 1. The method of producing scattered solution: The first step is using a specific pattern to produce scattered answer in a critical level. Depending on the type of problem, to produce scattered solution, the initiative or metaheuristic methods such as Tabu search can be used. Using this method is one of the main benefits of scatter search method compared with other meta-heuristic methods. This advantage allows the algorithm has the ability to search the solution space in different directions.

    • 2. The method of improving produced scattered solution: At this stage it is tried improve the produced scattered solution in the previous step based on objective function, by an effective approach.

      This improved method can be solved by a local search in the simplest case. And can be solved by an Innovative and meta-heuristic methods in complex cases. It should be noted that the improved method should be able to act on infeasible solutions.

    • 3. Update of reference set: To create and update reference set two fundamental points should be considered:

      • 1) This collection should include solutions that better meet the objectives, in terms of quality.

      • 2) In addition to solution with high quality, other solutions that are causing scattering in search paths should also be considered in this set.

      Therefore, the main goal is using a smart updating method for a reference set, according to produced solutions in two previous stages and existence solution in reference set.

    • 4. Create subset: At this stage using an intelligent approach and non-coincidentally, answer that need to be combined are identified from the members of reference set. One advantage of this step is creating a subset that unlike genetic algorithms are not necessarily only has two members. This approach allows the solution space simultaneously affect more compounds for searching. So the probability of reaching better solutions increases.

    • 5. The combination of selected subsets: After forming subsets by a combination convex and nonconvex, possible solutions are combined to obtain new solutions.

    5.THE STRUCTURE OF PROPOSED SCATTER SEARCH METHOD

    In this section, components designed for structure of metaheuristic algorithm will be analysis. The following Figure 2 shows the general structure designed for multiobjective scatter search algorithm.

    5.1.The Display of Answers

    A possible solution for this problem, is shown in the figure below. In this paper, the display of answer is as a one-dimensional matrix with m×n that m is the number of machines and n is the number of tasks.

    For example, the above answer indicates that the first task 1 on the machine 2 is processed and then task 2 on the machine 4 is processed and finally, task i on the machine k is processed.

    5.2.Producing the Initial Answer

    Most evolutionary meta-heuristic methods to produce initial responses uses a random approach. But since the quality of final obtained solutions by these methods depends on the quality of the initial generated solutions, therefore, in this paper a genetic algorithm used to generate the initial solution. The main objective of using this method is producing initial responses that have an appropriate level in terms of solution quality and dispersion. Initial population with the size N completely random to start the algorithm is produced. The number of repetitions of GA is intended 200 iterations.

    Mutation operator: Mutation operator used in genetic algorithm is a reverse operation that has been used in previous research to implementation of the genetic algorithm. In this operator two points of input sequences are selected randomly. Then, the sequence between these two points will be reversed.

    Crossover operator: Crossover operator used for GA in this paper is ow-point Crossover. This means that, for example, child 1 takes first and third of parent 1identically and also middle part is taken from parent 2. In other words, all members who are not in children 1 respectively is taken from parent 2. This work was done in the case of child 2, just the parent 1 and parent 2 will replace:

    For example:

    Suppose that points 3 and 6 were selected.

    After running 200 iterations of genetic algorithm, N initial solution with high quality will exist. Obtaining the ideal point with exact components in hard optimization problems, in a reasonable computational time is impossible. This paper, to deal with the shortcoming used a new concept called dynamic ideal point. Dynamic ideal point is an approximate ideal point that its components is formed from local optimum solutions of objective function. In order to achieve the primary dynamic ideal point in this paper, after generating an initial population, N value obtained for each of the three objectives, individually in ascending order are sorted. The smallest value obtained for the objective function i is equal to corresponding component in dynamic ideal point that is selected.Figure 3

    5.3.Updating Dynamic Ideal Point

    For updating values of dynamic ideal point, the following process is done at the end of each iteration in multi- objective scatter search: N value obtained for each of the three objective function, are sorted individually in ascending order. If the smallest value obtained for objective function is smaller than corresponding component in dynamic ideal point, this value can be replaced, otherwise these component does not change.

    5.4.Pareto Solution Set

    Obviously, due to the contradiction between goals in solving multi-objective problems, there is not a same answer that optimizes all objectives, therefore, a set of answers dominant as the optimum solutions (near-optimal), will be presented. In this paper, a method based on Pareto solution set is used, in which the quality of available solutions in the set is very important. Therefore, this archive will be updated at each iteration scatter search algorithm. The method of updating set is designed in which the all non-recessive answers are kept. To update the Pareto set, all answer of the previous iteration set and answers of population in current iteration poured in a swimming pool. Then all answer that does not overcome no answer in pool, added to the new archive. In this paper, there is no limitation for the size of set.

    5.5.Method of Producing Scattered Solution

    In this paper, we used path relinking method to producing scattered solution (2006). This method, initially to coordinate the intensification and diversification strategies on Tabu search is used. According to this method, a new answer has been produced using explore the connecting routes between two high quality solutions. In this method, the search will start from the basic solution and a path in the neighborhood of the solution, in order to produce auxiliary solution.

    Although this method is not a necessary component of scatter search algorithm, but implementation of this algorithm with this method leads to better results. Therefore, in this paper, this method has been used in the scatter search algorithm. The initial solutions among existing solutions in the population is the solutions that have minimum Euclidean distance with the dynamical ideal solution. Path relinking method for each of the solutions in the population of solutions are used separately.

    In order to explain this method, a numerical example is presented. Two basic and auxiliary solutions are shown in the following Figure 4.

    Generally, using path relinking method for the problem that presented in this paper, maximum m*n solution in the neighborhood of two basic and auxiliary solutions are created. In the example above, 3 jobs and 2 machines are available. Each solution matrix is including 6 cells, so maximum 6 solutions will be produced in the path of two solutions. To produce path solutions that connected two mentioned solutions, at any stage, an operation considered in the initial solution. Next, schedule these solutions in a similar of auxiliary solution. Generated solutions between the two above solutions are shown in the following Figure 5.

    As can be seen in path between initial solution and auxiliary solution, 3 solutions are produced. For all solutions, the obtained solutions stored in a swimming pool. Finally, N required scattered answer, according to the Deb theory will be selected (Deb et al., 2002).

    5.6.Method of Improving the Produced Scattered Solution

    In this section, in order to increase the quality of solutions we presented an improved method for each produced scattered solution that offered in the previous step. In this paper, to design an improved solution the parallel neighborhood search operators are used.

    Therefore, neighborhood search operators to improve the solutions as two following operations have been used.

    • XP:  This operator replaces the location of two work together.

    • IP:  This operator allocates the job in location j in which should be scheduled in location i.

    These two operator simultaneously on a solution is applied. Finally, one solution is selected between the output of two operators. This process is shown below (Figure 6).

    5.7.Updating the Reference Set

    In this paper, the reference set is formed from two subsidiaries: Refset 1 (high quality solutions) and Refset 2 (scattered solutions). b1 and b2 is the maximum capacity of the two subsidiaries, respectively. in the other words | r e f s e t | = b b 1 + b 2 . To establish a reference set, it is necessary to be formed subsidiary Refset 1. For this purpose, maximum b1 unique solution is selected from Pareto set that have highest dispersion. These solutions are added to subsidiaries Refset 1. If the number of available solution in set are less than b1, other members of the set will be selected from the best available solution in population. To establish a subset Refset 2, b2 unique solution between the available solutions that are not found in Refset 1 and have maximum Euclidean distance with solutions of Refset 1 are selected and entered Refset 2. It should be noted that the Euclidean distance guarantees dispersion between the two subsidiary.

    5.8.Method of Producing Subsets

    In this method, the three subsets (S1, S2, S3) are composed as dual reference sets of solutions which is shown below:

    • S1:  All subsets of the dual Refset 1 that have | b 1 1 | .

    • S2:  All subsets of the dual Refset 2 that have | b 2 1 | .

    • S3:  This subset is consisting of the solutions of Ref- set 1 and Refset 2 that each member can be built in the following way. The first element of any member are elected from the members of Refset 1 and the second element is a member of the Refset 2 that have maximum Euclidean distance with the first element. This subset is consisting of b1 members.

    5.9.Method of Selected Subset Combining

    In this paper, an operator called OX, is used in the subset to combine the selected subset [10]. This operator combines two solutions from a selected subset and acquires two new solutions. Implementation methodology of this operator is described in the following example. Suppose subset are containing of 2 following solutions:

    Two intersection points are elected randomly. New solutions are obtained as follows.

    In each new obtained solution, characters that are between the points of intersection and the initial solution are removed. The new solutions are as follows:

    Then the final solutions are made from a sequence of characters between the points of intersection initial solution and the remaining solution of new characters.

    After combining the solutions in subsets and create new solutions, a new population of solutions will be built.

    5.10.Creating New Solutions Sets for the Next Iteration

    Suppose that at the end of a repeat scatter search algorithm, the number of available solutions in the Pareto set is equal ω. To create a new set, one of the following conditions are considered:

    • 1. If ω = N, all Pareto solutions as inputs for producing scattered solution are considered.

    • 2. If ω > N, N solution that has are more diffuse, as inputs for producing scattered solution are considered.

    • 3. If ω < N, All Pareto solutions as the initial solution of producing scattered method are considered. Also, other remaining solution ω - N are elected from the recessive solution that have less Euclidean distance than ideal dynamic point.

    6.NSGA-II ALGORITHM

    This algorithm has been presented by Deb in 2002. NSGA-II is a multi-objective algorithm, elitist and based on genetic algorithms [27]. In this algorithm, the population of parents and children (with a population of size N) combined together. When N members are available in dominant set, some elements only are stored that have the most distant population from neighboring elements. According to the results Deb study, the NSGA-II algorithm is more efficient than other multi-objective evolutionary algorithm that called PAES and SPEA. As a result, according to high performance NSGA-II algorithm and using other researchers to this algorithm, we used NSGAII algorithm in this study to compare the efficiency of the proposed algorithm.

    6.1.Computational Results

    To demonstrate the proper performance of the two designed algorithms, numerous problems in three groups of problems with small, medium and large-scale problems are generated randomly and smart. In all three groups of problems, the following general assumptions are considered:

    • The processing times for problems with small size is generated randomly in [1, 40]. As well as to problems with medium and large size are generated in [1, 100].

    • The cost of machines setting up is produced randomly in [0.2pmean, 0.3pmean]. Pmean is the average of processing time.

    • Delivery time of jobs have been produced by the method described by Low and Yeh (2009). Each problem with two groups of factors values r, t has been resolved which is equal to t = 0.4, r = 0.2 and t = 0.4, r = 0.6.

    6.2.Compare Indexes

    To assess the quality and distribution of multi-objective metaheuristic algorithms, there are several indicators. In this paper, the following three indicators are used for comparing:Table 1

    Quality Index: This index is presented to compare the quality of obtained Pareto solutions by each method. In fact, all obtained Pareto solutions by both methods is graded together. Whatever this percentage be higher, algorithm has been higher quality.

    Uniformity index: This index is tested the distribution uniformity of obtained Pareto solutions on the boundary of solutions. This index is defined as follows:(13)

    S = i = 1 N 1 | d m e a n d i | ( N 1 ) × d m e a n
    (13)

    In the above equation, di represents the Euclidean distance between two adjacent founded solutions. Also, dmean represents the average value of di.

    Distribution index: This index to determine the optimum founded solutions on optimal boundary. Distribution index is defined as follows:(14)

    D = i = 1 N max ( x t i y t i )
    (14)

    In the above equation, x t i y t i represents the Euclidean distance between two adjacent answer x t i and y t i on optimal boundary.

    6.3.Problems with Small Size

    8 problems with different combinations of jobs and machines in small sizes are designed to prove the effectiveness of the proposed method that is shown in the table below.

    Each of the above problems for each combination of r, t, 15 times have been implemented. Therefore, the algorithm is executed 240 times.

    7.DETERMINING THE PARAMETERS OF ALGORITHM

    7.1.General Assumptions

    • The processing time is integer and are produced uniformly distributed in [1, 40].

    • Delivery time of jobs are produced with uniform distribution in [p(1-t-r/2), p(1-t+r/2)]. In this formula, p = pmean (n+m-1) and pmean is the total average of processing time. Also, the values of r, t are considered equal to r = [0.2, 0.6] and t = 0.4.

    7.2.Assumptions of Scatter Search Method

    • The population size is considered equal to 50.

    • The size of Refset 1 and Refset 2 are considered equal to 20 and 15, respectively.

    • Mutation rate equal to 0.2, crossover rate equal to 0.7 and reproduction rate equal to 0.1 are considered.

    • The number of repetitions in GA is considered 150.

    • Local iteration is considered equal to 5.

    • The number of repetitions in proposed algorithm is considered equal to 100.

    7.3.Assumptions of NSGA-II Method

    • Mutation rate equal to 0.2, crossover rate equal to 0.8 are considered.

    • Local iteration equal to 5 and the number of repetitions equal to 200 are considered.

    • The population size is considered equal to 50.

    7.4.Comparative Results

    In this section, the performance of the proposed algorithm compared with NSGA-II algorithm analyzed and examined. Tables 2 and Tables 3 show the results of these algorithms with two values sets of r, t. Each algorithm is running 15 times and the index values are as follows:

    As is clear from the table above, the proposed multiobjective scatter search method, conclude to better and higher quality Pareto solutions compared with NSGA-II. In other words, the proposed method puts more optimal sequence for the final selection in the hands of decision makers. Also, these tables show that the generated solutions by the proposed method is a diffusion index compared to other methods and produces more uniform Pareto solutions. But in some cases, the uniformity index of NSGA-II method is better than the proposed method.

    7.5.Problems with Medium and Large Size

    In this paper, to evaluate the effectiveness of the proposed multi-objective scatter search, 15 different problems with medium-sized and 15 different problems with large-sized has been solved. The study involved the algorithm implementation a total of 450 times for medium and large size. These problems are listed in Table 4.

    7.6.Determining the Parameters of Algorithm

    General assumptions for both medium and large sizes are as follows:

    • The processing time is integer and are produced uniformly distributed in [1, 100].

    • Delivery time of jobs are produced with uniform distribution in [p(1-t-r/2), p(1-t+r/2)]. In this formula, p = pmean(n+m-1) and pmean is the total average of processing time. Also, the values of r, t are considered equal to r = [0.2, 0.6] and t = 0.4.

    7.7.Assumptions of Scatter Search Method

    • The population size is considered equal to 200.

    • The size of Refset 1 and Refset 2 are considered equal to 70 and 55, respectively.

    • Mutation rate equal to 0.2, crossover rate equal to 0.7 and reproduction rate equal to 0.1 are considered.

    • Local iteration is considered equal to 5.

    • The number of repetitions in proposed algorithm is considered equal to 100.

    7.8.Assumptions of NSGA-II Method

    • Mutation rate equal to 0.2, crossover rate equal to 0.8 are considered.

    • Local iteration equal to 5 and the number of repetitions equal to 200 are considered.

    • The population size is considered equal to 200.

    7.9.Comparative Results

    In this section, the performance of the proposed algorithm compared with NSGA-II algorithm analyzed and examined. Table 5 and Table 6 show the results of these algorithms for medium size and Table 7 and Table 8 show the results of these algorithms for large size. Each algorithm is running 15 times and the index values are as follows:

    The results of the comparing show that the method of multi-objective scatter search method, conclude to better and higher quality Pareto solutions compared with NSGA-II.

    As is clear from the table above, the proposed multi- objective scatter search method, conclude to better and higher quality Pareto solutions compared with NSGAII. In other words, the proposed method puts more optimal sequence for the final selection in the hands of decision makers. Also, these tables show that the generated solutions by the proposed method is a diffusion index compared to other methods and produces more uniform Pareto solutions. But in some cases, the uniformity index of NSGA-II method is better than the proposed method.

    8.CONCLUSION

    Given the importance of scheduling problem, this paper has been investigated the scheduling of flexible manufacturing systems. Since the decision-maker tends to adopt their decisions based on several criteria, so multi-objective mathematical model for this problem is presented. This paper investigates a multi-objective evolutionary algorithm for scheduling flexible manufacturing systems to minimizing makespan, earliness and tardiness and startup costs. Since the problem class is NP-hard, therefore, to solve this problem and achieve near-optimal solution requires a significant time and perhaps in many cases impossible. So the metaheuristic can be used to solve such problems. Scatter search algorithm is one of the most important metaheuristic algorithm that is used to optimize different functions. Scatter search method is based on an intelligent method to search the solution space which is unlike other metaheuristic algorithms such as genetic algorithm, avoid the coincidental method. The distinctive feature of the proposed multi-objective evolutionary algorithm is its ability to search the solution space by an intelligent method, which is unlike other meta-heuristic algorithms avoid the coincidental method. Scatter search algorithm for solving the problem based on the specifications described in this paper was used. Multi-objective scatter search algorithm has an acceptable performance for the production of Pareto solutions with high diverse and fragmented compared to the NSGA-II. Finally, the following suggestions for future research are discussed:

    • Considering other objective functions such as minimizing the average production time and minimizing earliness/tardiness costs for scheduling of flexible manufacturing systems.

    • Using other evolutionary algorithms such as Tabu Search and SA for solving this problem

    • Considering the specific conditions of problem, such as interference between operation in multiobjective problems

    Figure

    IEMS-16-253_F1.gif

    The resulting reference set.

    IEMS-16-253_F2.gif

    Overview of multi-objective scatter search algorithm.

    IEMS-16-253_F3.gif

    The display of answers.

    IEMS-16-253_F4.gif

    Two basic and auxiliary solutions.

    IEMS-16-253_F5.gif

    Generated solutions between the two above solutions.

    IEMS-16-253_F6.gif

    An overview of operator’s procedure.

    IEMS-16-253_B1.gif
    IEMS-16-253_B2.gif
    IEMS-16-253_B3.gif
    IEMS-16-253_B4.gif

    Table

    Problems with small size

    Comparison results for small-scale problems (r = 0.2, t = 0.4)

    Comparison results for small-scale problems (r = 0.6, t = 0.4)

    Problems with medium and large size

    Comparing the results of problems with medium size (to r = 0.2 and t = 0.4)

    Comparing the results of problems with medium size (to r = 0.6 and t = 0.4)

    Comparing the results of problems with large size (to r = 0.2 and t = 0.4)

    Comparing the results of problems with large size (to r = 0.6 and t = 0.4)

    REFERENCES

    1. Abazari A M , Solimanpur M , Sattari H (2012) Optimum loading of machines in a flexible manufacturing system using a mixed-integer linear mathematical programming model and genetic algorithm , Computers & Industrial Engineering, Vol.62 (2) ; pp.469-478
    2. Balaji A N , Porselvi S (2014) Artificial immune system algorithm and simulated annealing algorithm for scheduling batches of parts based on job availability model in a multi-cell flexible manufacturing system , Procedia Engineering, Vol.97 ; pp.1524-1533
    3. Baruw O T , Piera M A (2015) Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach , Journal of Manufacturing Systems, Vol.35 ; pp.120-135
    4. Candan G , Yazgan H R (2015) Genetic algorithm parameter optimisation using Taguchi method for a flexible manufacturing system scheduling problem , International Journal of Production Research, Vol.53 (3) ; pp.897-915
    5. Cotta C (2006) Scatter search with path relinking for phylogenetic inference , European Journal of Operational Research, Vol.169 (1) ; pp.520-539
    6. Deb K , Pratap A , Agarwal S , Meyyarian T (2002) A fast and elitist multi objective genetic algorithm: NSGA-II , IEEE Transactions on Evolutionary Computation, Vol.6 (2) ; pp.182-197
    7. Filho M G , Barco C F , Neto R T (2012) Using genetic algorithms to solve scheduling problems on flexible manufacturing systems (FMS): A literature survey, classification and analysis , Flexible Services and Manufacturing Journa , Vol.26 (3) ; pp.408-431
    8. Han L , Xing K , Chen X , Leia H , Wang F (2013) Deadlock-free genetic scheduling for flexible manufacturingsystems using Petri nets and deadlock controllers , International Journal of Production Research, Vol.52 (5) ; pp.1557-1572
    9. Huang B , Jiang R , Zhang G (2014a) Comments on “Heuristic search for scheduling flexible manufacturingsystems using lower bound reachability matrix” , Computers & Industrial Engineering , Vol.67 ; pp.235-236
    10. Huang B , Jiang R , Zhang G (2014b) Search strategy for scheduling flexible manufacturing systemssimultaneously using admissible heuristic functions and non-admissible heuristic functions , Computers & Industrial Engineering , Vol.71 ; pp.21-26
    11. Kim Y , Yano C A (1994) A new branch and bound algorithm for loading problems in flexiblemanufacturing systems , International Journal of Flexible Manufacturing Systems, Vol.6 (4) ; pp.361-381
    12. Koupaei M N , Mohammadi M , Naderi B (2016a) An Integrated Enterprise Resources Planning (ERP) Framework for Flexible Manufacturing SystemsUsing Business Intelligence (BI) Tools , International Journal of Supply and Operations Management , Vol.3 (1) ; pp.1112-1125
    13. Koupaei M N , Mohammadi M , Naderi B (2016b) Optimizing flexible manufacturing system: A developed computer simulation model , International Journal of Engineering Transactions B: Applications , Vol.29 (8) ; pp.1112-1119
    14. Koupaei M N , Mohammadi M , Naderi B (2017) A Scheduling Model of Flexible Manufacturing System to Reduce Waste and Earliness/Tardiness Penalties , International Journal of EngineeringTransactions B: Applications, Vol.30 (5) ; pp.749-757
    15. Kumar A , Prakash Tiwari P M , Shankar R , Bavej A (2006) Solving machine-loading problem of a flexible manufacturing system with constraintbased genetic algorithm , European Journal of OperationalResearch, Vol.175 (2) ; pp.1043-1069
    16. Lee J , Lee J S (2010) Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix , Computers & Industrial Engineering, Vol.59 ; pp.799-806
    17. Lei H , Xing K , Han L , Xiong F , Ge Z (2014) Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search , Computers & Industrial Engineering, Vol.72 ; pp.297-305
    18. Low C , Yeh Y (2009) Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated , Robotics and Computer-Integrated Manufacturing, Vol.25 (2) ; pp.314-322
    19. Naderi B , Azab A (2015) Modeling and scheduling a flexible manufacturing cell with parallel processing capability , CIRP Journal of Manufacturing Science and Technology, Vol.11 ; pp.18-27
    20. Özpeynirci S , Azizo?lu M (2009) Capacity allocation problem in flexible manufacturing systems: branch and bound based approaches , International Journal of Production Research, Vol.47 (21) ; pp.5941-5958
    21. Özpeynirci S (2015) A heuristic approach based on time-indexed modelling for scheduling and tool loading in flexible manufacturing systems , InternationalJournal of Advanced Manufacturing Technology, Vol.77 (5) ; pp.1269-1274
    22. Pitts R A , Ventur J A (2009) Scheduling flexible manufacturing cells using tabu search , International Journal of Production Research, Vol.47 (24) ; pp.6907-6928
    23. Soolaki M , Zarrinpoor N (2014) A new 0-1 linear programming approach and genetic algorithm forsolving assignment problem in flexible manufacturing system , The International Journal of Advanced Manufacturing Technology, Vol.75 (1) ; pp.385-394
    24. Umar U A , Ariffin M K A , Ismail N , Tang S H (2015) Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle (AGV) in flexible manufacturing systems (FMS) environment , The International Journal of Advanced Manufacturing Technology, Vol.81 (9) ; pp.2123-2141
    25. Wu K Y , Xu S S , Wu T C (2013) Optimal scheduling for retrieval jobs in double-deep as/rs by evolutionary algorithms , Abstract and Applied Analysis,
    26. Zakaria Z , Petrovic S (2012) Genetic algorithms for match-up rescheduling of the flexible manufacturingsystems , Computers & Industrial Engineering, Vol.62 (2) ; pp.670-686