Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.

1(2014) 63-72

Copyright © 2010 American Scientific Publishers

All rights reserved
Printed in the United States of America

Scheduling Optimization of FMS Using NSGA-II

Nidhish Mathew Nidhiry1a, R. Saravanan2b

1
Karapagam University, 2 JCT College of engineering and technology
a
nidhishnidhiry@gmail.com
b
saradarani@hotmail.com

Abstract: The Flexible Manufacturing Systems (FMS) belong to that class of productive
systems whose main characteristic is the simultaneous execution of several processes
and the sharing of a finite set of resources. Now days, FMS must attend to the demand
of the market for personalized products. Consequently, the life cycle of the product
tends to be shorter and a greater variety of products must be produced simultaneously.
FMS considered in this work has 32 CNC Machine tools for processing 40 varieties of
products. Since minimizing machine idle time and minimizing total penalty cost are
contradictory objectives the problem has a multi objective nature. In this work, we have
developed a multi-objective optimization procedure based on NSGA-II and software has
been developed using .net programming for setting the optimum product sequence. A
Global–optimal front was then obtained using the software after 3000 generations.
Keywords: Flexible manufacturing system, Multi–objective optimization, NSGA II,
Scheduling Optimization, genetic algorithms

1 INTRODUCTION material-handling system to link these machines, and

FMS operational decisions consist of pre-release and a computer control system controlling the operation of
post release decisions. FMS planning problems also the whole FMS.While the first two sub-systems
known as pre-release decisions, take into account the provide the potential to achieve high flexibility and
pre-arrangement of parts and tools before the start of high productivity, the computer control system
operation. FMS scheduling problems, which come determines how much of the potential can be realized.
under the category of post release decisions, deal with FMSs have been classified into different types
the sequencing and routing of the parts when the according to their job flow patterns, size or type of
system is in operation. The machine loading problem production they use. From the point of view of
in a FMS is specified so as to assign the machine, scheduling and control, four types of FMS are defined:
operations of selected jobs, and the tools necessary to single flexible machines (SFMs); flexible
perform these operations by satisfying the manufacturing cells (FMCs); multi-machine flexible
technological constraints (available machine time and manufacturing systems (MMFMSs); and multi-cell
tool slots constraint) in order to ensure the minimum flexible manufacturing systems (MCFMSs);
system unbalance and maximum throughput, when the
system is in operation. An attempt has been made to 1.1 Earlier research
solve the objective function simultaneously to bring During the last three decades much research has been
the outcome in close proximity to the real assumption done in this area. Many heuristic algorithms have
of the FMS environment. been developed to generate optimum schedule and
part-releasing policies. Most of these algorithms
Flexible manufacturing systems (FMS) have been include enumerative procedures, mathematical
developed to combine the flexibility of job shops and programming and approximation techniques, i.e.,
the productivity of flow lines. Such systems consist of linear programming, integer programming, goal
three sub-systems: a processing system including a programming, dynamic programming, transportation
number of CNC machines, an automated and network analysis, branch and bound, Lagrangian

63
ISSN: 2222-7059(print), ISSN: 2222-7067(online), http://www.aspbs.com/aiem/
DOI: 10.7508/AIEM-V3-N1-63-72
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

relaxation, priority-rule-based heuristics, local search presented a new scheduling method for manufacturing
algorithms (ITS, threshold algorithm, Tabu search, system based on the timed Petri net model and a
SA), evolutionary algorithm (GA), etc. Of these reactive fast graph search algoritham.Lee and Lee [16]
techniques, few are specific to particular objectives, adopted heuristic search for scheduling flexible
and few are specific to particular problem instances manufacturing using lower bound reachability matrix
with respect to computational time needed. which is based on T-timed Petri net. Liu J et al [17]
proposed policies for deadlock prevention in FMS by
Z.X guo and W.K wong [13] presented a defining a subclass of Petri nets called
comprehensive review of genetic algorithm based resource-shared net with buffers (RSNB).
optimization model for scheduling flexible assembly
lines. In this paper a scheduling problem in the Shnits and Sinreich [8] present the development of a
flexible assembly line is investigated and a bi-level multi-criteria control methodology for FMSs. The
genetic algorithm is developed to solve the scheduling control methodology is based on a two-tier decision
problem. Tiwari and Vidyarthi [9] proposed a genetic making mechanism. The first tier is designed to select
algorithm based heuristic to solve the machine loading a dominant decision criterion and a relevant
problem of a random type FMS. The proposed GA scheduling rule set using a rule-based algorithm. In
based heuristic determines the part type sequence and the second tier, using a look-ahead multi-pass
the operation machine allocation that guarantee the simulation, a scheduling rule that best advances the
optimal solution to the problem. Another scheduling selected criterion is determined. Yu and Greene [12]
paper [1], consider only 6 machines and 6 jobs. R use a simulation study to examine the effects of
Kumar, M K Tiwari and R Shankar [7], considered machine selection rules and scheduling rules for a
Ant Colony Optimization approach in FMS flexible multi-stage pull system. J. Jerald , P. Asokan ,
scheduling. Rossi and Dini [18] proposed an ACO G. Prabaharan and R. Saravanan [5] proposed a
based software system for solving scheduling problem combined objective scheduling optimization solution
in FMS considering routing flexibility, for FMS. Saravanan M. and Noorul haq [13] modified
sequence-dependent set up, and transportation time. same problem in scatter-search approach of flexible
But ACO algorithm performs better in cases such as manufacturing systems, but this work is only for 43
traveling sales problem, the vehicle rooting problem parts and few generations. Shanhikant Burnwal and
etc. Dong-Sheng Xu et al.[19], proposed An Improved Sankha Deb [20] use a cuckoo search based approach
Ant Colony Optimization (IACO) algorithm to the for the same problem.
Flexible Job Shop Scheduling Problem (FJSSP).
IACO algorithm provides an effective integration Many authors have been trying to emphasize the
between Ant Colony Optimization (ACO) model and utility and advantages of genetic algorithm, simulated
knowledge model. In the IACO algorithm, the annealing and other heuristics. In this vein, it has been
knowledge model adopts some available knowledge proposed to use a new evolutionary computational
for the optimization of ACO, and then employs the approach called Non-dominated Sorting Genetic
existing knowledge to guide the current heuristic Algorithm-II (NSGA-II) for Multi-Objective
searching. Optimization NSGA-II of a specific manufacturing
environment limiting ourselves to only two
In the last few years most research concerning the objectives. The procedure is applied to relatively
AGV scheduling has been focused on developing large-size problems of up to 80 part varieties passing
scheduling algorithms for a single objective such as through 16 different CNC machine centers, and the
the minimizing of setup cost loading and unloading results are found to be closer to the global optimum
time. Toker A, Kondakci S and Erkip N [10] proposed sequence.
an approximation algorithm for the ‘n’ job ‘m’
machine resource constraint job shop problem. 1.2 Problem descriptions
Hoitomt et al. [4] explored the use of the Lagrangian The problem environment, assumption and aim of the
relaxation technique to schedule job shops present work are as follows:
characterised by multiple non-identical machine types,
generic procedure constraints and simple routing 1. The FMS considered in this work has a
considerations. W He and Kusiak [2] addressed three configuration as shown in Fig. 1. There are eight
different industrial scheduling problems, with flexible machining cells (FMCs), each with two to six
heuristic algorithms for each problem. computer numerical machines (CNCs), an
independent and a self-sufficient tool magazine, one
Lee and Dicesare [6] used Petri nets to model the automatic tool changer (ATC) and one automatic
scheduling problems in FMS. Similarly, Kim et al. [15] pallet changer (APC). Each cell is supported by one to

64
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

three dedicated robots for intra-cell movement of store the work in progress. The eight FMCs are
materials between operations. There is a loading connected by two identical automated guided vehicles
station from which parts are released in batches for (AGVs). These AGVs perform the inter cell
manufacturing in the FMS. There is an unloading movements between the FMCs, the movement of
station where the finished parts are collected and finished product from any of the FMCs to the
conveyed to the finished storage. There is one unloading station and the movement of semi-finished
automatic storage and retrieval system (AS/RS) to products between the AS/RS and the FMCs.

Figure 1.FMS structure

2. The assumptions made in this work are as follows: 2.1 NSGA II algorithm

 There are 40 varieties of products for a The Methodology used to find the optimal solution to
particular combination of tools in the tool magazines this problem is NSGA. It is based on a ranking
using 32 Machines in 5 FMCs. procedure, consisting in extracting the
 The type/variety has a particular processing non-dominated solutions for a population and giving
sequence batch size, deadline and penalty cost for not them a rank of 1.These solutions are removed from
meeting the deadline. this population; the next group of non-dominated
 Each processing step has a processing time with solution has a rank of 2 and so on. The algorithm has
a specific machine. a current population that is used to create an auxiliary
 There is no constraint on the availability of one (the offspring population); after that, both
pallets, fixtures, AGVs, robots, automated storage populations are combined to obtain the new current
and retrieval system, cutting tools, and part programs population. The procedure is as follows; the two
as and when they are needed at the required places. populations are sorted according to their rank, and the
 A random product-mix generated as shown in best solutions are chosen to create the new population.
the Table 1 reflects the current market demand. In the cause of having to select some individuals with
same rank, a density estimation based on measuring
3. The objective of the schedule: - the crowding distance (see figure 2) to the
1. Minimizing the machine ideal time (TDi). surrounding individuals belonging to the same rank is
used to get the most promising solutions. Typically,
2. Minimizing the total penalty cost (TPi). both the current and auxiliary population has equal
Where size. The procedure of NSGA – II is shown in figure
TDi = Total Machine Idle Time. 3 and flow chart shown in figure 4. The basic steps
TDi = Σj MIj (j= machine number) involved in NSGA II algorithm are:
MIj = TI-Σi PTji (i= job number)
TI = Total elapsed time. 1) Generation t = 0;
PTji= Processing time of i th job on the j th machine. (2) Generate a uniformly distributed parent
TPi = Total penalty cost population of size P;
TPi= Σi PTi - DDi×Pi×BSi (3) Evaluate the individuals and sort the population
PTi =Processing time of i th job. based on the non-domination;
DDi= Due date for i th job. (4) Assign each solution a rank equal to its
non-domination level (minimization of fitness is
assumed);
2PROPOSED METHODOLOGY (5) Use the usual Fino style tournament selection;

65
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

(6) Use the Simulated single point

Crossover operator and mutation to create
an Offspring population of size P;
(7) Combine the offspring and parent population to
form extended population of size 2P; Start
(8) Sort the extended population based on
non-domination;
(9) Fill new population of size P with the individuals Create initial population of size N
from the sorting fronts starting from the best;
(10) Invoke the crowding-distance method to ensure
diversity if a front can only partially fill the next Perform fast non-dominated sorting of population
generation. The crowding-distance method maintains P
diversity in the population and prevents convergence
in one direction;
(11) Update the number of generations, t = t + 1;
Calculate crowding distance
(12) Repeat the steps (3) to (11) until a stopping
criterion is met.
Perform selection using crowded comparison
operator

Perform crossover and mutation to obtain

population Q

Combine populations P and Q

Figure 2. Measuring the crowding distance of a non-dominated
point.
Pick the best N solutions from this combined
population

If Generation > Max.

Generation

Stop
Figure 3. The procedure of NSGA – II

Figure 4. Flow chart of NSGA II algorithm

Optimization procedure

The objective of the schedule: -

1. Minimizing the machine ideal time (TDi).
2. Minimizing the total penalty cost (TPi).

66
Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

67
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

(1) Fino style coding Tournament selection involves running several

(2) Binary coding "tournaments" among a few individuals chosen at
In this work, Fino style coding is considered. random from the population. The winner of each
tournament (the one with the best fitness) is selected
Fino style coding: for crossover. Selection pressure is easily adjusted by
In this coding each sequence is coded as 40 sets of changing the tournament size. If the tournament size
two-digit numbers ranging from 01 to 40. is larger, weak individuals have a smaller chance to
be selected. Reproduction procedure as follows:
Ex: Selection method: tournament selection. (Assume the
12,18,27,32,11,03,31,15,26,01,19,08,14,16,37,17,25, parameters for comparison as 0.75)
39,06,23,13,34,10,30,40,22,35,09,38,05,20,02,36,29,
28,07,21,04,24,33. Step 1: select two samples from the population.
Step2: evaluate the population.
GA parameters Step3: generate random no. in the range (0 to 1)
Population size = 100 Step4: if the random number is <= 0.75, select the
Reproduction: Tournament selection (Target value – best one otherwise, select the inferior one.
0.75)
Crossover probability= 0.6 (b) Crossover
Mutation probability = 0.01 The strings in the mating pool formed after
Termination criteria = 3000 number of generations or reproductions are used in the crossover operation.
a satisfactory value for objectives, whichever occurs Single-point crossover is used in this work. With a
first. Fino-type coding scheme, two strings are selected at
random and crossed at a random site. Since the
Consider the complexity of one iteration algorithm. mating pool contains strings at random, we pick pairs
The basic operations and their worst-case of strings from the top of the list. When two strings
complexities are as follows: are chosen for crossover, first a coin is flipped with a
1.Non dominated sorting is O (MN2) probability Pc = 0.6 to check whether or not a
2.Crowding – distance assignment is O (M (N) log crossover is desirable. If the outcome of the coin
(N)) flipping is positive, the crossover is performed;
Overall complexity is O (MN2), which is governed by otherwise the strings are directly placed in the
non-dominated sorting. Where M is the number of intermediate population for subsequent genetic
objectives and N is the population size (third N is for operation. Flipping a coin with a probability 0.6 is
the maximum number of fronts). simulated using the Monte Carlo method. The next
step is to find a cross site at random. Once crossover
3 GENETIC OPERATIONS point is selected, till this point the permutation is
(a) Reproduction copied from the first parent, then the second parent is
The tournament selection method is used for scanned and if the number is not yet in the offspring
reproduction. Tournament selection is one of many it is added.
methods of selection in genetic algorithms.

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7) (4 5 3 6 8 1 2 7 9)
Parent1 Parent2 Child1 Child2

purpose of mutation in GAs is to allow the algorithm

(c) Mutation to avoid local minima by preventing the population
The classic example of a mutation operator involves of chromosomes from becoming too similar to each
a probability that an arbitrary bit in a genetic other, thus slowing or even stopping evolution. This
sequence will be changed from its original state. A reasoning also explains the fact that most GA systems
common method of implementing the mutation avoid only taking the fittest of the population in
operator involves generating a random variable for generating the next but rather a random (or
each bit in a sequence. This random variable tells semi-random) selection with a weighting toward
whether or not a particular bit will be modified. The those that are fitter. In this problem mutation

68
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

probability is 0.01 (i.e.) 8 bits. First generate random generating two random numbers between the
number 0 to 1, with 0.01 accuracy. If random number numbers of jobs. For example, if the random numbers
is <= 0.01, perform mutation. The next step is to find generated are 3 and 6, then the corresponding job
a cross site at random, the two sites are selected by numbers in these positions are exchanged.

123456789 126453789
Parent Child

4 RESULT AND DISCUSSIONS results obtained by the proposed NSGA – II and it

The optimization procedures developed in this work performs better in terms of objective functions and
are based on the non-dominated sorting Genetic computational effort, i.e.50% less than CS. The figure
Algorithm (NSGA-II). The FMS configuration 3 shows the comparison of both the approaches in the
considered in this work is taken from existing study. But in our work we have taken the scheduling
literature [7]. In literature [5], procedure is developed problem with 40 parts and multi objective
for 43 jobs using combined objective optimization optimization approach is implemented. Results are
method. A Comparison between the proposed NSGA obtained for 43 jobs problem using combined
II and other algorithms namely SPT, PSO, CS (found objective method and NSGA-II, and the performance
in literature) and NSGA II after 40 generations has is compared and analyzed. Table 4 shows the results
been presented in table2 and fig.3. Table 2 shows the obtained by both approaches and it is found that
NSGA – II performs better.

Fig.3 Comparison between various approaches

69
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

5 CONCLUSIONS or as good as the best results obtained by the

Optimization procedure has been developed in this aforementioned methods. After 3000 generation the
work based on the Multi-objective Non-Dominated best solution is obtained. The problem of
genetic algorithm (NSGA-II). This method is computational effort of FMS scheduling increases in
implemented successfully for solving the scheduling proportion to the number of components. In the case
optimization problem of FMS. Software has been of 40 components 8.159152832478977343
written in .net Language. FMS schedule is obtained 4561126959612e+47combinations are possible. Due
for 40 jobs and 32 machines. The result obtained by to the very high computational effort exhaustive
NSGA-II is analyzed for two objectives, minimizing search is not possible. Similarly random search also
total penalty cost and minimizing total machine idle requires a lot of computational effort. By
time. For the given set of objectives, the results implementing genetic algorithm for 3000 generations,
obtained by the NSGA-II-based algorithm have been only 1.5 lakh computations are needed for getting the
compared with a number of existing algorithms optimal solution. The research work leads to the
including CS, SPT, and PSO (found in literature), and conclusion that NSGA II is superior in terms of
the machine idle time and the total penalty cost by computational effort and pareto optimal front. The
NSGA-II-based algorithm is found to be better than procedure developed in this work can be suitably

70
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

modified to any kind of FMS with a large number of the availability and handling time of load unloading
components and machines. Future work will include stations, robots and AGV’s.

Figure 11.Progression of Pareto-optimal fronts.

References Instn Mech. Engrs. Vol. 217 Part B: J.

[1] AVS Sreedhar kumar and Dr.V. Ve- eranna Engineering Manufacture.
2010, Optimization of FMS scheduling using [8] Shnits B, Sinreich D. 2006. Controlling flexible
non-traditional techniques. nternational manufacturing systems based on a dynamic
Journal of Engineering Science and selection of the appropriate operational
Technology. pp:7289-7296. criteria and scheduling policy. Int J Flex
[2] W He, Kusiak A., 1992, Scheduling of Manuf Syst. pp:1–27.
manufacturing systems. Int. J Comput Ind., [9] Tiwari M.K, Vidiyarthi N.K. 2000, Solving
pp:163–175. Machine loading problem in flexible
[3] Hoitomt DJ, Luh PB, Pattipati KR 1993, A manufacturing system using genetic algorithm
practical approach to job-shop scheduling based heuristic approach. International journal
problems. IEEE Trans Robot Automat, of production research, pp:3357-87.
pp:1–13. [10] Toker A, Kondakci S, Erkip N., 1994, Job shop
[4] Deb, K., 2001. Multi-Objective Optim- ization Scheduling under a nonrenewable resource
using Evolutionary Algorithms, John Wiley & constraint. J Oper Res Soc., pp:942–947.
Sons, Ltd. [11] Yu MC, Greene TJ., 2006. A simulation analysis
[5] J. Jerald, P. Asokan , G. Prabaharan, R. Saravanan. of controlling rules for flexible pull systems.
2004, Scheduling optimisati- on of flexible Int J Manuf Res. pp:314–331.
manufacturing systems using particle swarm [12] Z. X. Guo , W. K. Wong, S. Y. S. Leung, J. T.
optimisation algorithm, Int. Journ. Of FanS, F. Chan., 2008, A
Advanced Manufacturing Technology, pp:964 genetic-algorithm-based optimization model
– 971. for scheduling flexible assembly lines. Int J
[6] Lee DY, Dicesare F, 1994, Scheduling of flexible Adv Manuf Technol . pp:156–168.
manufacturing systems: using Petri nets and [13] Saravanan M. and Noorul haq A., 2008,
heuristic search. IEEE Trans Robot Automat, 'Evaluation of Scatter Search Approach for
pp:23–132. Scheduling Optimization of Flexible
[7] R Kumar, M K Tiwari and R Shankar 2003, Manufacturing Systems'. International journal
Scheduling of flexible manufacturing systems: of Advanced manufacturing Technology, pp.
an ant colony optimization approach. Proc. 978-986.

71
 Nidhish Mathew Nidhiry et al., Advances in Industrial Engineering and Management, Vol.3, No.1(2014) 63-72

[14] Kalyanmoy, Amrit Pratap, Sameer Agarwal, and

T. Meyarivan., 2002, A Fast and Elitist
Multiobjective Genetic Algorithm:NSGA-II,
ieee transactions on evolutionary
computation.
[15] Kim, Suzuki, Narikiyo., 2007, FMS scheduling
based on time petro net model and reactive
graph search. Appl Math Model. pp:955 –
970.
[16] Lee J, Lee SJ., 2010, Heuristic search for
scheduling flexible manufacturing systems
using lower bound reachability matrix.
Comput Ind Eng. pp:799-806.
[17] Liu J et al., 2009. A live subclass of Petri nets
and their application in modeling flexible
manufacturing system. Int J Adv Manuf
Technol. pp:66-74.
[18] Rossi A, Dini G., 2007. Flexible job-shop
scheduling with routing flexibility and
separable setup times using ant colony
optimization method. Robot Comput
Integrated Manuf. pp:503–516.
[19] Dong-Sheng Xu et al., 2009, An Improved Ant
Colony Optimization for Flexible Job Shop
Scheduling Problems. International Joint
Conference on Computational Sciences and
Optimization, pp.517-519.
[20] Sankar S et al., 2003. A multiobjective genetic
algorithm for scheduling a flexible
manufacturing system. Int J Adv Manuf
Technol. pp:229–236.
[21] Shashikant Burnwal , Sankha Deb, 2013.
Scheduling optimization of flexible
manufacturing system using cuckoo
search-based approach. Int J Adv Manuf
Technol. pp:951–959.

72