An Adaptive Genetic Algorithm for Production Scheduling on Manufacturing Systems with Simultaneous Use of Machines and AGVs

Abstract

The problem of production scheduling of manufacturing systems involves the system modeling task and the application of a technique to solve it. This kind of scheduling is characterized by the large number of possible solutions, where several researches have been using the genetic algorithms as a search method to solve this problem, since these algorithms have the capacity of globally exploring the search space and to find good solutions quickly. This paper proposes the use of adaptive genetic algorithm to solve this kind of scheduling problem. The aim of this paper was to obtain a good production schedule considering simultaneous use of machines and automated guided vehicles that minimize the makespan with low running time. The results of this paper were validated in large scenarios and compared with other approach. These results are presented and discussed in this paper.

1 Introduction

Manufacturing systems with shared resources such as machines and transport systems have been used for production automation, and they allow flexibility consistent with the needs of a good share of manufactures in the market. This flexibility occurs because the machines can be used to several different operations and the products can be processed by several different machines. The problem generated by this flexibility is the considerable effort to define the production scheduling and the use of available resources over time, in order to reach certain performance criteria (Tay and Ho 2008; Zhang et al. 2012; Naderi et al. 2009).

One of the difficulties in production scheduling of a manufacturing system with shared resources is the product scheduling with simultaneous use of machines and transport systems. Among the existing transportation systems, the automated guided vehicles (AGVs) stand out. AGVs are small and stand-alone vehicles, which move materials to and from value aggregate operations. Typically, products in a manufacturing system with shared resources visit different machines for different operations, requiring a transport system to transport the products among the machines at its processing route.

Most researchers have addressed the product planning and transport system problems as independent. Only few researchers have emphasized the importance of scheduling with simultaneous use of machines and AGVs Reddy and Rao (2006).

These scheduling problems are classified as NP-hard problems, which means there is a large concentration of computational effort that grows exponentially with the increase in the size of the problem Zhang et al. (2006). In this context, several approaches for dealing with production scheduling problem indicate a very high efficiency in the use of metaheuristics such as genetic algorithms (Yildiz 2013; Sadrzadeh 2012; Wong and Ngan 2013; Kadadevaramath et al. 2012; Lin et al. 2010). However, it is reported that the simple GA often suffers from the troubles of premature convergence, difficulty in constructing fitness functions and parameter dependence Yin et al. (2004). So far, many researches have used an adaptive genetic algorithm to solve the problem of premature convergence (Morandin et al. 2008; Jerald et al. 2006; Zhang et al. 2006; Yin et al. 2004).

Therefore, in this paper, an adaptive genetic algorithm is proposed for makespan minimization in the production scheduling of manufacturing systems with shared resources. In this sense, the crossover and mutation rates are dynamically adjusted according to their contributions to searching performance. An important feature in this paper in relation to other approaches of the literature is the integration of simultaneous use of machines and AGVs using an efficient encoding of chromosome that produces good production scheduling with minimum running time.

The remainder of the paper is organized as follows. In the next section, we present a brief literature review of the production scheduling of manufacturing systems with shared resources. The problem formulation is presented in Sect. 3. In the Sect. 4, the proposed approach is presented. In Sect. 5, some computational tests performed with the proposed approach are presented and discussed. The paper ends with a conclusion about the research done.

2 Literature Review

Scheduling of manufacturing systems with shared resources has been extensively investigated over the last three decades, and it continues to attract the interest of both the academic and industrial sectors. Various types of scheduling problems are solved in different manufacturing environments. A variety of algorithms are employed to obtain optimal or near-optimal schedules. For this, some approaches using GA have been proposed to solve the scheduling problem.

The approach proposed in Pongcharoen et al. (2004) presented a modified genetic algorithm for production scheduling for complex products with multiple levels of product structure and multiple resource constraints. In the proposed algorithm, after the genetic operators, a repair process was added in order to rectify infeasible schedules that can be produced by the crossover and mutation operators. In Pongcharoen et al. (2002) were applied several experiments to identify the best parameters for GA in a limited execution time.

In order to solve the premature convergence problem, in Zhang et al. (2006) was proposed an adaptive genetic algorithm (AGA) for scheduling problem. In this sense, it was proposed an adaptive genetic algorithm with multiple operators for flowshop scheduling, which is a typical NP-hard optimization problem with many industrial applications and has been widely studied in both academic and engineering fields. Simulation results based on benchmarks demonstrate the effectiveness of AGA in contrast to traditional GAs. In Yin et al. (2004) was proposed an adaptive genetic algorithm for flowshop problem. The probability of crossover and mutation is dynamically adjusted according to the individual’s fitness value. When compared to a basic GA, the effectiveness and efficiency of this adaptive genetic algorithm are better than those of the basic GA. Through this adaptive genetic algorithm, the flowshop scheduling problems are solved effectively.

In Morandin et al. (2008) was investigated the use of an adaptive genetic algorithm for production reactive scheduling of manufacturing systems having as performance criteria the minimum makespan and the response-obtaining time. In Morandin et al. (2008), the operator probabilities are dynamically set according to the fitness value of the chromosomes.

There are few approaches making simultaneous use of machines and AGVs for products scheduling using genetic algorithms. Jerald et al. (2006) explored the use of an adaptive genetic algorithm for simultaneous scheduling of parts and AGVs for a particular type of flexible manufacturing system (FMS) environment, where a new scheme is proposed for setting the genetic parameters during the course of the search process. The schedule obtained by an adaptive genetic algorithm is compared to genetic algorithm, and experimental results have indicated that the proposed adaptive genetic approach is very effective.

In Reddy and Rao (2006) were addressed multiobjective scheduling problems in a FMS environment using evolutionary algorithms. The authors made an attempt to consider simultaneously the machine and vehicle scheduling aspects in an FMS and addressed the combined problem for the minimization of makespan, mean flow time and mean tardiness objectives. In this sense, Ulusoy et al. (1997) addressed the problem of simultaneous scheduling of machines and a number of identical automated guided vehicles in a flexible manufacturing system so as to minimize the makespan. For solving this problem, a genetic algorithm is proposed. Here, chromosomes represent both operation sequencing and AGV assignment dimensions of the search space.

In Sankar et al. (2004) was considered the simultaneous scheduling of incoming jobs, machines and vehicle dispatching in a flexible manufacturing system having a single device, an automated guided vehicle. The objective is to find an optimal sequence of incoming parts, which will reduce the waiting times due to blocking and starving of resources and deadheading times, resulting in overall minimization of makespan.

3 Problem Description

3.1 Production Scheduling of Manufacturing Systems

The problem of production scheduling of manufacturing systems with shared resources and simultaneous use of machines and AGVs involves decisions on production resource allocation and AGVs over time, as well as the choice of routes for manufacturing each batch of parts of a product, defining the moment of execution of each stage. A common criterion of production performance is the makespan value.

In this way, given a manufacturing system, it is assumed that the goal is to produce a number of products in a particular time. To do that, there are certain production resources whose operations on different materials, at distinct production stages of an especific product, must be determined. In this paper, the production scheduling problem will be the task of determining which operations should be made and in which moments, so that all products are finished in the shortest time.

This paper addresses on the production scheduling problem of a plant with multiple machines and AGVs and also various types of products to be produced. There are several manufacturing routes to each type of product. A manufacturing route is a sequence of operations that must be followed in a defined order. Each operation is a manufacturing stage of the product performed on a particular machine. At the end of the sequence, the product will be ready. There may be more than a machine capable of performing the same operation, which leads to a product having more than one manufacturing route. In this way, each product’s manufacturing routes are represented by the machines which it must move to be produced.

The AGVs scheduling problem addresses on the moment that a particular part needs to be transported to another machine. At this stage, the problem is to decide which of the AGVs shall be selected, since more than one may be available. This paper uses two dispatching rules to this problem: shortest travel time/distance (STT/D), presented by Benincasa et al. (2003), and random vehicle (RV), presented by Egbelu and Tanchoco (1984).

It is therefore important to define the characteristics and restrictions of the problem and are given below:

• 1. A type of product will be produced following a single manufacturing route. If there are several possible routes, only one should be selected;

• 2. One particular product should go through all the chosen manufacturing route’s machines, without changing the specified order;

• 3. An operation will be performed on only one machine in a given time, or a product will be at only one machine in a particular time;

• 4. A machine will process only one product at a time;

• 5. Operation time of the products on the machines is deterministic and previously known;

• 6. Machines will never fail;

• 7. Since a particular operation is started (that a product passes through a machine), it is not interrupted until it is completed;

• 8. The number of AGVs is given, and they have the same speed and load transportation characteristics;

• 9. One AGV carries only one product at a time;

• 10. Transportation times to each point of the factory are known;

• 11. There are intermediate storage areas among machines, with infinite capacity;

• 12. Setup times of the machines are included in the operation time.

4 The Proposed Adaptive Genetic Algorithm

In this paper, is proposed a modified adaptive genetic algorithm (MAGA) based on approach presented in Morandin et al. (2008), where the crossover and mutation rates are dynamically adjusted to improve the performance of the algorithm in the search space.

In the proposed approach, a chromosome is coded to indicate which products and their production routes should be processed. From there, the genetic algorithm used is responsible for conducting all the production scheduling, that is, defining the moment and machine that products will be produced.

In this paper, the production scheduling is obtained in the stage of fitness calculation, in which products are allocated to machines following the registered routes. Still, AGVs, whose purpose is to carry a particular product for a particular machine or load($L$)/unload($U$) station, are scheduled with dispatching rules. With that, it is possible to find makespan and fitness values of a particular chromosome.

4.1 Chromosome Codification

Let $n$ be the number of products to be produced and $t$ the maximum number of operations in all the possible production routes for the $n$ products. A chromosome is represented by a whole vector of size $n+n\cdot {t}$, sub-divided in $n$ sub-vectors of size $t+1.$

Each sub-vector represents a product to be processed, where the first gene of the sub-vector is the index that identifies the product and the next genes represent the possible machines, in other words, the products route.

Let $P_{i_{p}}$ be the product to be processed and $M_{i_{p}, k_{i_{p}} }$ as a machine of the production route of this product, where $k_{i_{p}}$ represents the order of the machine in the product route, in other words, the $k_{i_{p}}$ machine that the product should pass. Thus, we have a representation of the chromosome shown in Fig. 1.

Where

$$\begin{aligned}&i_{1}, i_{2}, i_{3}, \ldots , i_{p} \in \{1, 2, \ldots , n\} \text { and } i_{g} \ne i_{j} \text { for } g \ne j. \\&k_{i_{p}} \in \{1, 2, \ldots , t \} \text { and } k_{i_{p_{g}}} \ne k_{i_{p_{j}} } \text { for } g \ne j \end{aligned}$$

Fig. 1

Chromosome representation

For each sub-vector to have size fixed $t+1,$ sometimes it is necessary to add empty genes, being filled out with the value 0 after the gene that represents the last machine until the beginning of the gene that represents a new product.

To facilitate the development, internal tables are maintained with indexes of the possible product routes and the machines sequence belonging to each route, being the structure of the chromosome simplified, containing in each sub-vector the product index and the index of the chosen route, as shown in Fig. 2, in which $P_{i_{p}}$ represents the product to be processed and $R_{i_{p},j}$ represents the chosen route for the product $P_{i_{p}}$, among the possible routes.

Fig. 2

Simplified representation of the chromosome

Where

$$\begin{aligned}&i_{1}, i_{2}, i_{3}, \ldots , i_{p} \in \{ 1, 2, \ldots , n\} \text { and } i_{g} \ne i_{j}, g \ne j. \\&j \in \{1, 2, \ldots , s \} \end{aligned}$$

Therefore, a chromosome is ‘translated’ in a production scheduling being allocated the suitable machines in the genes of each sub-vector for the product regarding that sub-vector, starting from an initial time. The sub-vectors (products) are treated in parallel, prioritizing the order that appear in the chromosome.

To better illustrate this operation, consider the chromosome in the Fig. 1, where initially the machine $M_{i_{j},1}$ is allocated for $P_{i_{1}}$; after this, the machine $M_{i_{2},1}$ is allocated for $P_{i_{2}}$; this process occurs until all machines or all products have been allocated, always respecting the machines availability. When a machine becomes available, the chromosome is checked in order to allocate it for the product with larger priority.

4.2 Reproduction

An initial population with thirty individuals is generated randomly. The individuals for the mating pool are selected based on the tournament selection scheme. Five candidates are selected at random from the population, and the best individual based on the objective function is placed in the mating pool. The tournament selection is done repeatedly until the mating pool get filled. The tournament selection proposed by Sankar et al. (2004) was applied, and the pseudocode is given by:

• Choose $k$ (tournament $size = 5$) individuals from the population at random.

• Choose best individual from pool/tournament with probability p.

• Choose second best individual with probability $p\cdot (1-p).$

• Choose third best individual with probability $p\cdot (p\cdot (1-p)).$

• Choose fourth best individual with probability $p\cdot (p\cdot ( p\cdot (1-p))).$

• Choose fifth best individual with probability $p\cdot (p\cdot (p\cdot ( p\cdot (1-p)))).$

4.3 Crossing

The crossing is made among two chromosomes parents $C_{1}$ and $C_{2}$ as shown in the example of the Fig. 3, changing the sub-vector regarding the same product $P_{i_{p}}$, in each one of chromosomes parents, generating two offspring chromosomes $C_{3}$ and $C_{4}$ that will go to the new population.

Fig. 3

Crossover

4.4 Mutation

The mutation is realized in a chromosome, obtained of random way of the population, changing the production route of a product $P_{i_{p}}$, also chosen of random way, for one of the possible routes for $P_{i_{p}}$ as shown in the example of the Fig. 4.

Fig. 4

Mutation

4.5 Fitness Function

Fitness function is based on makespan value of each chromosome and aims to assign a value to individuals, according to their ability. To obtain the makespan value, it is necessary to define how AGVs will be scheduled to transport products among the machines.

4.6 AGVs Scheduling Using Dispatching Rules

The AGVs are used to move the products among the machines, according to the selected route. The system adopted dispatching rules to decide which AGV will hold the job. In this paper, two rules were used:

Random vehicle (RV): used when all the vehicles are available at $L/U$ station.

Shortest travel time/distance (SST/D): used when there is more than one available AGV and they are not at $L/U$ station.

After defining which dispatching rule will be used, it is necessary to define how it will be applied during the allocation process to machines. The steps that represent the logical implementation of the AGVs are presented below:

• 1. Move all the products to the $L/U$ station according to the order given by the chromosome, which is left to right;

• 2. Verify which product must be transported according to its priority;

  • 2.1. Verify which AGVs are available and apply the appropriate dispatching rule;

  • 2.2. Move the AGV from the current location to where it is requested. The AGV gets and moves the product to the next designed machine as registered in the product route;

  • 2.3. After carry a particular product, the AGV stays parked at machine’s parking point or $L/U$ station’s parking point in which the product was delivered;

• 3. Return to step 2. This process is repeated until all products have been produced and delivered to the $L$/$U$ station.

4.7 Getting the Makespan Value

To calculate the makespan value and obtain a fitness value for each chromosome, it is necessary to find the conclusion time of a determinate product operation, which is given by (4.1).

$$\begin{aligned} O_{ij} = T_{ij} + P_{ij} + E_{ij}, \end{aligned}$$

(4.1)

where $O_{ij}$ = operation completion time, in which $j$ is the $j$th operation of the product $i$; $T$ = transportation time; $P$ = operation processing time and E = waiting time.

After finding the conclusion time of a particular product operation, it is possible to find the conclusion time of the product $Pi$, given in (4.2).

$$\begin{aligned} P_{i} = \sum _{i=1}^{n} O_{ij} \end{aligned}$$

(4.2)

In Eq. (4.3) it is possible to find the makespan, mkp, based on the conclusion time of the products.

$$\begin{aligned} mkp = \max \{P_{1}, P_{2}, \ldots , P_{n} \} \end{aligned}$$

(4.3)

Lower makespan values chromosomes are considered more fit than chromosome with greater values. To obtain the fitness value, $f_{i},$ where $i$ is a particular chromosome, an operation is performed on makespan values of current generation, given by (4.4).

$$\begin{aligned} f_{i} = mkp_{\text {max}} - mkp_{i} + mkp_{\text {min}}, \end{aligned}$$

(4.4)

where $mkp_{\text {max}}$ is the greatest makespan value of current generation, $mkp_{\mathrm{min}}$ is the lowest makespan value of current generation, and $mkp_{i}$ is the makespan value of the chromosome $i$ at current generation. This operation gives higher fitness values to individuals with lower makespan values in the generation, as proposed by Chiu and Fu (1997). In this sense, the Eq. (4.4) is used to calculate the fitness value of a chromosome, in a way that lower makespan value chromosome (more adapted), it gets a higher fitness value and has a higher probability of being selected to generate offspring to the next generation.

4.8 Dynamic Adjustment of Mutation and Crossover Rates

When it comes to the search with genetic algorithm, the behavior of the search is influenced or controlled by some parameters such as size of population and crossover and mutation rates, which may improve or worsen the search performance. Because of this, this paper used adaptive genetic algorithms with dynamic adjustment of crossover and mutation rates.

The proposed approach is based on the work proposed by Morandin et al. (2008). The steps of adaptive genetic algorithm used and the possible adjustments of genetic operators’ rates are presented below:

• 1. Randomly generate the initial population and calculate fitness value of each individual;

• 2. Apply the selection method at current population;

• 3. Selected individuals should go through the crossover proposed process according to the crossover rate. After that, calculate the average fitness value of population;

• 4. Save the average fitness value of population after the crossover process;

• 5. Apply the mutation process according to the mutation rate and calculate the average fitness value of population;

• 6. Save the average fitness value of population after the mutation process;

• 7. Adjust the mutation and crossover rates by the following rule:

  • 7.1. If the percentage of improvement among offspring chromosomes average fitness and parent chromosomes average fitness is equal or greater than 10 %, the occurrence probability of genetic operator should be increased of $0.05$ for crossover operations and $0.005$ for mutation operations;

  • 7.2. If the percentage of worsening among offspring chromosomes average fitness and parent chromosomes average fitness is equal or greater than 10 %, the occurrence probability of genetic operator should be decreased of $0.05$ for crossover operations and $0.005$ for mutation operations;

  • 7.3. If the percentage of improvement/worsening among offspring chromosomes average fitness and parent chromosomes average fitness is within 10 %, the occurrence probability of genetic operator should not be changed;

  • 7.4. Rates should be between $0.5$ and $1.0$ for crossover operator and between $0.00$ and $0.10$ for mutation operator.

• 8. Check the stop condition. If it is met, select the best chromosome of the last generation as the final solution to the problem. Otherwise, generate the next population, which will replace the former, and return to step 2.

5 Experimental Analyses

Experiments were conducted, and the results were compared with those of the approach proposed in Reddy and Rao (2006) (called here R&R) and MAGA, because both use genetic algorithm as modeling and search method for the scheduling problem. In order to analyze how the approaches MAGA and R&R behave with increasing scheduling problem, two scenarios were used for the validation of the proposed approach.

The first scenario (Problem 1 hereafter), is composed by six machines and three products, where the product 1 has two possible manufacturing routes with four and five machines, while the products 2 and 3 have three possible manufacturing routes with three to four machines each (see Table 1). The products manufacturing routes were randomly generated, as well as operation times, which ranged between 400 and 500 time units (TU) (see Table 2).

The second scenario (Problem 2 hereafter) is composed by nine machines and nine products, where each product has two possible manufacturing routes with five to seven machines each (see Table 6). The products manufacturing routes were randomly generated, as well as operation times, which ranged between 400 and 500 time units (TU) (see Table 4). Finally, to make transportation between the products and machines, two AGVs were used for Problems 1 and 2 and the transportation times were randomly generated (see Tables 3, 5).

Table 1 Production routers for Problem 1

Table 2 Operations time for Problem 1

Table 3 Transportation time for Problem 1

Table 4 Operations time for Problem 2

Table 5 Transportation time for Problem 2

Table 6 Production router for Problem 2

In the Problems 1 and 2, the following values were used for the MAGA parameters: population size equals to 30, crossover rate starting at $0.6$ (60 %), e-mutation rate starting at $0.005$ (0.5 %), with crossover rate of between $0.5$ and $1.0$ and mutation rate of between $0.005$ and $0.1.$ The stop criterion used was 200 generations or when 95 % of the population has the same individuals.

The methods MAGA and R&R were run using a Core 2 Quad 2.4 GHz, 8 G RAM, with Linux Operating System Ubuntu 10.04 version, and the language compiler C gcc-4.4.

For the results obtained [minimum makespan ($Mkp$) and running time ($RT$)] for Problems 1 and 2 (see Table 7), MAGA and R&R were run 35 times. For Problem 1, the average makespan found for MAGA was 2354, standard deviation of $7.36$; the minimum makespan value found was 2348, and the maximum makespan value was 2383; and R&R average makespan was 2372, standard deviation of $1.10$; the minimum makespan value found was 2368, and the maximum makespan value was 2373. For Problem 2, the average makespan found for MAGA was 5572, standard deviation of $148.47$, the minimum makespan value found was 5342 and the maximum makespan value was 5779 and R&R average makespan was 5686, standard deviation of $7.87$, the minimum makespan value found was 5677 and the maximum makespan value was 5703, respectively.

Table 7 Simulations results for Problems 1 and 2

Although it is hard to find the most adequate scheduling for Problem 2, the MAGA has shown to be able to find those scheduling, with lower makespan values when compared with R&R. Another important aspect of Problem 2 is the running time obtained by MAGA, the average was $1.90$ min, almost $2.5$ times smaller than running time obtained by R&R, which was $4.33$ min.

A graphical description of convergence of the MAGA and the R&R for Problems 1 and 2 is given in Figs. 5 and 6. In this sense, Figs. 5 and 6 show the algorithm convergence, plotting the best individual from MAGA and R&R approaches at each iteration. It is important to highlight that the MAGA approach obtained better performance after 200 iterations, reaching better convergence to the best solution when compared with R&R approach for Problems 1 and 2.

Fig. 5

Best individual found at each iteration according to Problem 1

Fig. 6

Best individual found at each iteration according to Problem 2

5.1 Experimental Statistical Analyses

The makespan values obtained for MAGA and R&R for Problems 1 and 2 (see Table 7) are not normally distributed. This data may not satisfy necessary assumptions for parametric mean comparisons. Thus, the use of a nonparametric statistical technique for comparing the results (makespan) from both approaches is interesting. Among the possible nonparametric statistical techniques, the Wilcoxon rank-sum test Degroot and Schervish (2001) was used to check the confidence degree between MAGA and R&R approaches.

In this sense, Wilcoxon rank-sum test can compare those results to determine the approach that achieved better performance. This test assumes that the sample of differences is randomly selected and the probability distributions (from which the sample of paired differences is drawn) are continuous McClave et al. (2008). The found makespan values meet these criteria, and then the following hypotheses were tested:

• $H_{0}$: The probability distributions of makespan values obtained by MAGA and R&R from the tests with two scenarios are identical.

• $H_{1}$: Distributions of the makespan values differ between MAGA and R&R.

The Wilcoxon rank-sum test results are termed p values, also called observed significance levels. We reject the null hypothesis whenever p values $\le \alpha$. Using a significance level $\alpha = 0.05$ applied to makespan results from the two scenarios, all p values obtained are equal or less than 0.02. Thus, there is enough evidence to support the alternative hypothesis and conclude that these tests show a significant statistical difference between the MAGA and approach proposed by Reddy and Rao (2006) for minimization of makespan.

6 Conclusions

In this paper, a novel methodology based on dynamic adjustment of crossover and mutation parameters considering the simultaneous use of machines and transport systems was proposed to solve the makespan minimization problem. Simulation results demonstrated the feasibility and effectiveness of the proposed methodology, which can find solutions with good makespan values while providing a good running time for production scheduling of a manufacturing system with shared resources.

In the experiments, the proposed approach, called MAGA, was applied to two scenarios, called Problem 1 (six machines and three products) and Problem 2 (nine machines and nine products). In addition, to make transportation between the products and machines, two AGVs were used for Problems 1 and 2.

The performance of the MAGA approach was compared with that of proposed approach in Reddy and Rao (2006) (called here R&R). The results show that MAGA can get a minimum makespan values in most experiments for Problems 1 and 2 when compared with R&R. Another important aspect was the running time obtained for Problem 2, a more complex scenario where it is hard to find the most adequate scheduling; the average obtained by MAGA was 1.90 min, almost $2.5$ times smaller than running time obtained by R&R, which was 4.33 min.

A statistical analysis performed using 35 trials for each approach shows that MAGA performs better than R&R for Problems 1 and 2. MAGA has obtained the best average results for lower makespan values.

From the use of adaptive genetic algorithm could be achieved a good performance on the addressed problem, as well as other points of search space could be explored through the dynamic adjustment of crossover and mutation rates that led convergence to a region with good solutions.

In this sense, for the Problems 1 and 2 was demonstrated the convergence speed obtained by MAGA and R&R. In the simulation results with Problem 1, the makespan value decreases steeply and MAGA reaches the best value after 16 iterations, while R&R reaches the best value after 65 iterations. In the simulation results with Problem 2, after 170 iterations, the MAGA reached the best makespan value when compared with R&R. Hence, we can conclude that MAGA is very effective and converges very fast.

Finally, it was observed that the proposed approach in this paper can be applied to solve manufacturing problems with resource sharing of large scale, in order to achieve a good makespan values with low running time.