Keywords

28.1 Introduction

In the present market scenario, to stand in a market it is very important for a manufacturing system to accommodate changes quickly as customer demand changes. Many Indian industries have adopted FMS for in time production and quality of the product, but still problems in scheduling still arise. The scheduling problem is nothing but simply a process of resource allocation to accomplish a specified task [1].

Petri nets are a class of modeling tools, which were originated by Petri [2, 3], they have a well-defined mathematical foundation and easy to understand the graphical feature. It is a powerful graphical tool for modeling and analyzing concurrent, parallel, simultaneous, synchronous, distributed, and resource sharing systems with the advantages like an easy visualization of complex systems can model a system hierarchically (a top-down fashion at various levels of abstraction and detail) and can analyze qualitative and quantitative aspects of the system.

The common definition of PNs introduced by Petri is as follows. Petri nets or place/transition net can be defined as a five-tuple: PN = (P, T, I, O, Mo), where P and T are finite non-empty sets of places pictured by circles and transitions pictured by bars, respectively. I: P × T → {0, 1} is an input function that defines the set of directed arcs from P to T. O: P × T → {0, 1) is an output places which are drawn as circles represent possible states or conditions of the system while transition, which is shown in bars or boxes, describe events that may modify the system states. The relationships between places and transitions are represented by a set of arcs that are the only connectors between a place and a transition in either direction. The dynamic behavior of the system can be represented using tokens which graphically appear as black dots in places. A transition can only fire if it is enabled and having one token in that place I to the next transition j. A timed Petri net is associated with places or transitions. Here we consider the time associated with places. The modeling of the problem data takes place using TPN. TPN is a 7 tuple, TPN = (P, T, I, O, M0, Mr0, Ʈ) where M0 is initial marking, Mr0 is initial vector for remaining processes, Ʈ is set of time delays associated with it. The problem data consist of job-based data, operation-based data, and machine data including processing time or operation time along with the path of the operation for the given jobs. Different researchers have used different approaches of Petri nets for simulation and GA for fine-tuning the parameters [2]. Different researchers have identified different criteria for solving FMS scheduling problem. One of them is performance measures. The list of performance criteria are as stated in Table 28.1. Here, out of all performance parameters attempt is made to address the makespan using a hybrid approach combining Petri nets and GA.

Table 28.1 Criteria for performance parameters (Reproduced from Filho et al. [4])
Full size table

28.2 Problem Definition

The makespan minimization problem of a flexible manufacturing system (FMS) has been recognized as one of the most important planning problems. Job scheduling problems are referred to as NP-hard problems. And to solve such kind of problem there are different four types of representation. They are job-based representation, operation-based representation, priority rule-based, and preference-list-based representation [1].

In this research, a Genetic Algorithm (GA) based heuristic is proposed to solve the makespan of a random type FMS. The objective of the problems is to minimize the system unbalance and maximize the throughput, satisfying the technological constraints such as availability of machining time, and tool slots. The proposed GA-based heuristic determines the part type sequence and the operation-machine allocation that guarantee the optimal solution to the problem, rather than using fixed predetermined part sequencing rules.

The first objective of the research work is to schedule the given FMS, modeling with Petri nets and optimizing using genetic algorithm and obtaining results to conclude with the best option. The makespan minimization problem consists of three types Job shop scheduling (there are n jobs and m identical stations. Each job should be executed on a single machine), Open shop scheduling (there are n jobs and m different stations. Each job should spend some time at each station, in a free order), Flow shop scheduling (there are n jobs and m different stations. Each job should spend some time at each station, in a predetermined order). To optimize makespan the system consists of the following:

The system considered is

  • n = four jobs and m = three machines with the respective operating time. Each job is processed on every machine at the appropriate time.

  • The machine can operate only one operation at a time.

  • All machines are available.

  • Here one job will leave the machine only after completing the operation and scheduling is done in the way that no classes with the same job will assign to two different machines at the same time or vice versa.

  • Machine setup time is included in the processing time.

  • The data of n jobs and m machines are as given in Table 28.2.

    Table 28.2 Problem data
    Full size table

28.3 Methodology

For the given data will be evaluated into two phases. The first phase gives the system model and the second gives the optimum result.

  • Step 1: Creating a system model using Petri net tool using MATLAB Environment

  • Step 2: Identifying the variables (Table 28.3)

    Table 28.3 Description of timed Petri net model in Fig. 28.2
    Full size table

  • Step 3: Simulating the model in the MATLAB environment. Results of system model simulation.

Figures 28.1 and 28.2 shows the FMS modeling for the given 4 job 3 machine problem. Once the modeling is created next phase is to check for the structural and behavioral properties of the net structure. As shown in Fig. 28.1 the model of each job should spend some time at each station, in a predetermined order. Figure 28.3 shows the property check whether is net structure modeled satisfy all the condition of the manufacturing system. Net is bounded means there will be no overflows in the buffer. Liveness shows a complete absence of deadlock in the manufacturing system. Once the property of the net is checked, next step is to analyze the system. There are different ways of analyzing the net-like coverability tree, incidence matrix, and simple reduction rules. Here the net is analyzed using matrix equation that governs the dynamic behavior of the concurrent system as shown in Figs. 28.4, 28.5, and 28.6.

Fig. 28.1
figure 1

FMS processing of 4 jobs & 3 M/c

Full size image
Fig. 28.2
figure 2

FMS processing of 4 jobs & 3 M/c in MATLAB

Full size image
Fig. 28.3
figure 3

Structural properties

Full size image
Fig. 28.4
figure 4

Incidence matrix part 1

Full size image
Fig. 28.5
figure 5

Incidence matrix part 2

Full size image
Fig. 28.6
figure 6

Command window answer

Full size image

  • Step 4: Optimizing using GA

GA starts with a set of solutions called population. Chromosomes from the population are occupied and used to form a new population. This is motivated by the desire, that the new population will be better than the old one in terms of a fitness criterion. Solutions that are selected to form new solutions (offspring) are selected according to their fitness—the more suitable they are the more chances they must reproduce. There are different representation schemes for evaluation with the makespan objective. They are operation-based representation, job-based representation, preference-list-based representation, priority rule-based representation. In general, GA uses three steps—selection, crossover, and mutation (4). Selection based on the fitness (makespan in our case) is the source of exploitation, and crossover and mutation help us to promote exploration (Fig. 28.7).

Fig. 28.7
figure 7

Reproduced from Munibabu et al. [5]

Flow chart for GA.

Full size image

A generation of a GA contains a population of individuals, each of which corresponds to a possible solution in the search space. Everyone in the population is evaluated with a fitness function to produce a value which indicates the goodness of a solution. Selection helps in bringing forward certain members from the population to apply crossover and mutation on the given set of problem. Crossover takes pairs of individuals and uses parts of each to produce new individuals. Random mutations swap parts of an individual to prevent the GA from getting caught in a local minimum.

  • Step 4.1: Creation of First Generation/Initialization:

In our problem, we are using the datasets that have been taken from Kumar [6]. This data set has initially four jobs and three machines. The term makespan refers to the cumulative time to complete all the operations on all machines [7]. It is the time taken from scheduling the first job submitted until the completion of the last job. The objective of the problem is to find a valid schedule that yields the minimum makespan. The initial population can be generated randomly. Each machine has randomly 3–4 jobs placed on them. The total running time for each machine is then calculated. Here the job-based representation is focused out of four. For the same, the chromosome would be [1 2 0 3]. The first job to be processed is j1 is m1, m2, m3, and processing time is 4, 3 2 [1]. Similarly, each is processed. The genetic search process starts with a randomly generated set of chromosomes called the initial population. The size of the population (pop_size) depends on the solution space. The chromosome representation of all the representation is as stated in Table 28.4. The outline GA code is as shown in annexure I. The simple GA structure used to evaluate the system is given below. The population at time t is represented by variable s, with the initial population of random estimates as s (0).

Table 28.4 Chromosome representation for four scheme (Reproduced from [1]
Full size table

  • Procedure GA

  •         t = 0;

  •         initialize s(t);

  •         evaluate s(t);

  •         begin

  •         t = t + 1;

  •         select s(t)from s(t − 1)

  •         reproduce pairs in s(t)

  •         evaluate s(t);

  • Step 4.2: Population evaluation

The fitness parameter [fit (c)] considered is the makespan time. The initial population is evaluated for makespan.

  • Step 4.3: Selection of new population

The process of selecting the chromosomes to represent the next generation has the following steps:

  1. 1.

    Conversion of the fitness parameter values to a new fitness value [new_ fit (c)]. A fitness function considered here, which is suitable for minimization objective is

$${\text{new}}\;{\text{fit}}(c) = 1 - {\text{fit}}(c)/F$$
(28.1)

where fit (c) = makespan time corresponding to chromosome.

F is the sum of the fitness parameter of all chromosomes.

$$F = \sum\limits_{c = 1}^{{{\text{pop}}\_{\text{size}}}} {{\text{fit}}(C)}$$
(28.2)

To have more copies of chromosomes with the smallest objective function value, the ratio fit ©/F is subtracted from 1.

  1. 2.

    Conversion of the new fitness parameter to an expected frequency of selection [p(c)].

$$P(c) = {\text{new}}\_{\text{fit}}(c)/\mathop \sum \limits_{c = 1}^{{{\text{pop}}\_{\text{size}}}} {\text{fit}}(c)$$
(28.3)
  1. 3.

    Calculation of the cumulative probability of survival (cp (c)). A random selection procedure, which is explained below, generates the next population of the same size. A random number between 0 and 1 is obtained and a chromosome c is selected which satisfies the following condition. This selection process is repeated several times equal to the population size. The method used here is more reliable in that it guarantees that the fittest individuals will be selected and that the actual number of times each is selected will be expected frequency ±1. This procedure enables the first chromosome to have multiple copies and the worst will die off [1, 5].

The fitness function calculated here is the output from the Gantt chart. Expected count, new fitness function is given by, 1 − (13/47).

Probability of selection is given by (0.0.7234/2.9999).

The string number here represents the number of job.

  • Step 4.4: Selection of parents for crossover

Once the makespan is calculated for the different chromosomes, tournament selection is done to filter out those chromosomes which have better makespan values (in this case lesser makespan value) and these chromosomes are then selected to undergo crossover and mutation. In this problem, the tournament size has been taken to be two. Two chromosomes are randomly chosen from the population and their makespan values are compared, whichever chromosome has a lesser makespan value is deemed the winner. After the parents have been chosen, crossover is applied to them.

Chromosomes reproduce among themselves according to a predefined crossover probability. The first child is generated by taking the first portion, from the beginning of the chromosome until the crossover point, of the first parent and the second portion of the second parent, from the crossover point until the end of the chromosome.

  • Step 4.5: Mutation

Generate the random number, for all chromosomes, if r ≤ pm mutate the chromosome, where pm is the probability of mutation. Mutation is a diversification strategy used mostly to avoid the repetition of chromosomes. The mutation followed in this paper is the order-based mutation (OBM). In this, we pick two loci in the chromosome at random and exchange their genes. For example, 3 0 1 2 is mutated as 3 2 1 0.

  • Step 4.6: Termination

The above process will be repeated for a fixed number of generations.

The working of the genetic algorithm is explained in Step 4. The GA parameters considered are given in Table 28.5. The parameters used in GA are

Table 28.5 Parameters used in GA
Full size table

Initial population, corresponding fitness values (population evaluation), selection of chromosomes for the next generation, and chromosomes in the mating pool for the considered example are given in Table 28.6. The parents selected for crossover from the mating pool and corresponding offsprings after crossover, chromosomes selected for mutation, new population after mutation, and fitness values for the considered example are given in Table 28.7.

Table 28.6 Evaluation and reproduction phase
Full size table
Table 28.7 Population cross over
Full size table

The best makespan and corresponding schedule are given below for the example problem for the job-based representation schemes considered in this example. The best makespan obtained is 9 and Best schedule: 2-1-3-0.

28.4 Conclusions

The scheduling is one of the important aspects of the smooth functioning of flexible manufacturing system. In the present work combined approach of Petrinet and genetic algorithm is used to produce near to optimal result. Here only one performance parameter is considered that is makespan. Due to good modeling power, Petri net is used as this feature is required to model a real manufacturing system. Genetic algorithms are powerful optimization tool and gives better result for combinatorial problems. Out of the four representations scheme the job-based representation is addressed for the optimum makespan. The hybrid approach plays a vital role in scheduling the system and optimizing the makespan.

In the future, the focus must be on a more complex manufacturing system with different representation schemes and with minimum number of constraints. Also, the focus on multi-objective optimization with conflicting objectives/performance measures will be addressed.