Automated Guided Vehicles battery management for industry 4.0

1 Introduction

The intense competition between manufacturers has forced firms to adopt the industry 4.0 as a new revolutionary industrial paradigm [1]. In this context, a great deal of attention has been granted to sustainability while increasing economic and ecological efficiency. One of the key factors of energy sustainability is the optimization of energy use, allowed by highly flexible manufacturing systems [2, 3]. Automated guided vehicles (AGVs) that ensure material handling systems are a key tool for modern flexible manufacturing systems [4].

Through a guided path made by wire, AGVs can travel automatically ensuring transport tasks [5]. Due to their agility and efficiency, AGVs are widely used [6]. They can be interfaced with other material and simply controlled from an intelligent computer system [7].

AGVs are generally used in warehouses, manufacturing facilities and distribution centers [8]. This paper scrutinizes the exploitation of AGVs in manufacturing facilities.

Although the usefulness of AGVs, many challenges arise. AGV consumes energy from an onboard battery. However, poor battery management can lead to total battery depletion; thus, making the vehicle unavailable for the system; which can reduce the overall performance of the manufacturing system. As far as replenishment is concerned, overcharging or undercharging AGV battery can damage it and reduces its lifetime. Consequently, the cost of AGVs fleet will be increased, which makes the manufacturing process more expensive. Moreover, the replenishment of depleted batteries at peak periods can lead to significant production delay. In fact, a firm can add 30 minutes of production work per lift truck each day by changing batteries at a proper time rather than at peak periods [9]. With regard to performance, the production hours of an AGVs fleet can be improved by adding new AGVs. Yet, this solution is too expensive and creates a congestion problem. Coming to flexibility, the mono-speed operating mode for robots and vehicles makes the manufacturing system less flexible to face volatility related to customer demands or energy prices.

AGVs battery management contributes to avoid battery deterioration and reduces the cost of AGVs fleet while increasing their efficiency [10]. Due to the fact that the transport task is a part of the manufacturing process, battery management impacts the overall manufacturing system [11]. However, studies on battery management are limited and there is no research paper that investigates the impact of battery management on the overall performance of manufacturing [12]. It is important to address the multi-speed operating mode of both AGVs and machines in the context of battery management. Considering a multi-speed operating mode for vehicles and machines allows to increase the flexibility of the manufacturing system. The latter would cope with the volatility of customer demands and energy cost, which could be expensive in specific periods.

This work focuses on studying how battery management can impact the overall performance of a manufacturing system, and how the flexibility of a manufacturing system can be improved through multi-speed operating as to ensure an efficient AGVs battery management approach. in addition, it aims at developing a battery management replenishment strategy which would avoid battery damage and increases the production hours of an AGVs fleet. Simulation experiments show that effective battery management can avoid battery depletion and enhance the efficiency of AGVs; therefore, improving the overall performance of the manufacturing system.

This study highlights four main tasks: processing by machines, transport by automated vehicles, battery management, and speed controlling of both machines and vehicles. The Author attempts to answer the following question: How can the use of energy be optimized and the production hours of AGVs be increased without impacting both battery lifetime and manufacturing time (makespan) as economic cost? The Author proposes to divide the main problem into four sub-problems: production task by machines, transport task by AGVs, battery management task for battery replenishment and handling trips, and speed controlling task of machines and AGVs. To achieve this goal, the battery management strategy must be designed in an effective way while handling the precedent considered tasks.

This paper is organized as follows: in Section 2, the considered problem is described. Section 3 is a state of art of relevant topics from the current research. Section 4 is divided into two sub-sections: the problem modeling and description of the proposed approach for battery management and energy optimization. Experiments and analyses are presented in Section 5. Section 6 recapitulates the conclusions and specifies the limitations of the current study, which can be considered in future studies.

2 Problem definition

The considered manufacturing system is an extension of the classical job shop scheduling problem (JSP), which is composed of a set of jobs J ={ J₁, …, J _n  } to be executed by a set of machines M ={ M₁, …, M _m  }. Each job (J _j ) represents an occurrence of a product type manufacturing process, which consists of predetermined sequence of n _i operations, O _i  ={ O_j,1, …, O_{j,n j}  }. Each operation O_j,i,m (the i ^th operation of job J _i ) is executed in a predetermined multi-speed machine m, with a given machine speed (normal speed, high speed). Each Job J _j enters the system by loading / unloading station (L/U), loaded on a given automated guided vehicle (v), selected among a set of AGVs A ={ A₁, …, A _s  }. Then, the job is transported from L/U station to its target machine, according to a specific speed of AGV v (normal speed, high speed). Once, the operation O_j,1 is performed by the target machine, another AGV will be selected for the second operation O_j,2 of the same job J _j with a given AGV speed. The last performed operation O_{j,n j} of J _j will be transported by an AGV v to the L/U station to be unloaded.

A limited number of battery-based uni-charge AGVs makes up the transport fleet. The transport task Tr_j,i,sr,ta which consists of moving the operation O_j,i from a source sr to a target ta, is composed of two successive sub transport tasks and is achieved in uni-directional ways to avoid collisions. The first sub transport task occurs when an AGV v receives a call. v will move from its current position to the call node. The current position of v might be either the last delivery station or the L/U station. Once O_j,i is loaded on the vehicle v, the second sub transport task will be performed by moving AGV from the source sr to the target ta station. The target station might be either a machine, or the L/U station if the operation is the last one (O_{j,n j} ). To avoid damaging AGVs’ batteries, the minimal detected battery level (MBL), should be above a certain valueλ (maximum discharge capacity or threshold level charge [11, 13]). This requires an efficient battery replenishment strategy. Assumptions of the considered problem are presented as follows:

Once a machine starts an operation, it can’t be interrupted.

A Layout of the considered problem, inspired from the study of Bilge and Ulusoy’s benchmark [14] with additional constraints, is presented in Fig. 1. In the next section, our contribution is made after having knowledge of the precedent studies on JSP with transport constraints and AGVs battery management approaches.

OPEN IN VIEWER

Fig. 1

The considered manufacturing problem.

3 Problem modeling and the proposed approach

3.2 The proposed approach

Three objective functions are optimized in this study: makespan, overall energy consumption, and minimal detected battery level (MBL). Thus, the considered problem is a multi-objective optimization problem. Many approaches for multi-objective optimization have been recommended in the literature. Usually, the used methods are: single objective transformation, random weighting, and the Pareto method [30]. The latter is preferred by researchers because it allows obtaining a set of Pareto optimal solutions in an optimization process that is coherent with an actual scheduling problem [31]. Many representative algorithms exist, such as MOGA [32], NSGA and NSGA-2 [33], PESA and PESA-2 [34]. However, because of its better distribution and fast convergence speed, NSGA-2 is widely used.

3.2.1 The proposed NSGA-2

Chromosome coding

The chromosome is composed of five rows (Table 1):

OPEN IN VIEWER

Table 1

Chromosome coding

Job	2	1	2	2	3	1	3
AGV	1	2	1	1	2	1	2
AGV speed	0	0	1	0	0	0	1
Battery swap	1	0	3	2	0	3	0
Machine speed	0	1	0	0	1	1	1

OPEN IN VIEWER

Algorithm 1

Crowding distance

Algorithm: Crowding-Distance (I)
Begin
L = |I| // the number of solutions in the set I
For each i, set I [i]  distance  = 0 // initialize the distance of each solution
For each objective m
I = sort (I, m) // sort solutions according to the value of each objective function
I [1]  distance  = I [L]  distance  =∞ // the boundaries solutions are always taken
For i = 2 to (L-1) // for all the other solutions
I [ i ] distance = I [ i ] distance + ( ( I [ i + 1 ] * m ) - ( I [ i - 1 ] * m ) ) / ( f m max - f m min )
End-for
End-for
End-for
End

Job: represents the schedule of production tasks affected to their machines. (e.g. {1^st job2, 1^st job 1, 2^ed job 2, etc.});

AGV: defines the selected transport vehicle for each job. (e.g., 2ed job 2 (3rd column) is affected to the AGV 1);

AGV speed: defines if the AGV (same column) moves at normal speed (0), or full speed (1);

Battery swap: specifies how the AGV behaves to manage its battery replenishment during the transport task. e.g. (0 for no battery swap, other values (1– 3) reflect different strategies of battery replenishment);

Machine speed: defines the speed of processing of each machine. (e.g., 0: normal processing and 1: fast processing)

3.2.2 The selection operator (Elitism Non-Dominated Sorting Algorithm)

The selection nature of the multi-objective genetic algorithm is more complex than the mono-objective one. This operator divides individuals into ranks and applies a strategy to evaluate and sort the individuals of the same rank: There are two types of Pareto sorting methods which are widely used: the recursion sorting [35] method and the adopted quick sorting method. According to recent works, the second method has better computational performance.

3.2.3 Selection strategy of non-dominated solution with the same rank

The application of non-dominated sorting generates individuals with different ranks, and those with low rank will be chosen to participate in the genetic evolution process. For the individuals of the same rank, some strategies ensure diversity of the colony during evolution. According to literature, the most important approaches are: information entropy, density-based clustering, niche technology and classification [36]. The adopted strategy in this paper is the density based on clustering. This strategy can capture both of diversity and distribution of population macroscopically. It can also make the relationship among individuals with the capability of controlling the colony during the evolution process [37]. The algorithm of Crowding-distance (I) is used to sort solutions of the same rank [33].

I [i] * m is the value of the m ^th objective function of the solution i in the set of solution I.

f m max , f m min : the maximum and the minimum values of the m ^th objective function.

The solution i is better than the solution j if:

i _rank  < j _rank or

i _rank  = = j _rank & i _distance  > j _distance

If two solutions belong to the same rank, the solution belonging to the less crowded zone is the best one. For the diversity of the population, individuals with a larger crowding distance have a big probability to participate to reproduction and evolution.

Designed genetic operators:

Crossover: two crossovers are advanced for exchanging information between parents. Both of them are inspired from the technique of POX, which allows generating valid chromosomes and avoiding an additional process of chromosome correction [38].

POX Assignment: the purpose of the suggested crossover is to exchange information while keeping the production task sequence. First, two sub sets of jobs are selected randomly (e.g., S1 = {J1, J3}, S2={2}). Each parent is cloned to a new child. This technique keeps for each child the column information of the selected job on its parent. The designed mask of modification guides the process of information exchange between parents (the job sequence in not exchanged). If the value in the mask equals 1, the exchange is permitted, otherwise, it is forbidden.

POX Sequencing: to exchange information between parents, the same approach as POX assignment. Yet, the mask of modification is applied only on the first line of job, and the other lines representing information about AGVs and machine features will be maintained in child chromosomes, as they are in each child’s parents.

Mutation: it is applied to a small portion of population with a probability less than 30%, in order to make a small change on chromosomes, avoiding a premature convergence of the genetic algorithm.

Two types of mutation are implemented in this paper: the first concerns classical mutation by swapping two columns, selected randomly. The second developed mutation is based on two mask arrays. Mask 1 for selecting the columns to be changed and mask 2 for selecting chromosome features to be modified.

3.2.4 Workflow of the suggested HNSGA-2(Hybrid NSGA-2)

The NSGA-2 algorithm is improved by efficient Tabu Search (TS) to optimize jobs and AGVs. The main purpose is to minimize Cmax and the overall energy consumption while maximizing the minimal battery level of AGVs. In this paper, the TS is integrated into NSGA-2 for local searching. Workflow of the proposed hybrid NSGA-2TS is shown in Fig. 2.

OPEN IN VIEWER

Fig. 2

The proposed hybrid NSGA-2.

3.2.5 Local search by Tabu search

One of the most successful meta-heuristic for combinatory optimization problems, especially for many scheduling problems, is Tabu Search (TS) [39]. By using movements, TS explores the solutions space to optimize an objective function. The main parameters of TS are: neighborhood structure, tabu list, aspiration criteria and stopping condition.

The recommended TS represented in Fig. 3, is based on three neighborhood functions:

OPEN IN VIEWER

Fig. 3

The proposed Tabu search (TS) integrated in NSGA-2.

NF1: Swap (job i, job j): select randomly two positions in the chromosome’s job sequence and swap them,

NF2: Change (AGV_ID): select randomly a position from the chromosome’s AGV ID sequence and replace the old AGV by another AGV ID,

NF3: Change (AGV Behavior): select randomly a position from the chromosome’s AGV behavior sequence and replace the old AGV behavior by another behavior, selected randomly.

The recommended TS improves the solutions generated from the genetic operators (crossover & mutation). This improvement can be in terms of minimal battery level of AGVs, or/and the overall energy consumption, or/and Cmax. The TS algorithm is stopped after a predetermined number of iterations.

3.2.6 Complexity analysis

The considered problem is NP-hard in the strong sense [24]. Contrary to the mathematical approach, the suggested metaheuristic approach provides solutions of high quality in reasonable time. The required execution time of HNSGA2 is less than 60 seconds for all instances. Suppose that B is the total number of the manufacturing operations of each problem instance. N _p and M are the population size and the number of objective functions to be optimized. In each iteration, HNSGA-2 needs a selection of solutions, generating offspring, applying the local search. Then, sorting solutions using fast non-dominated sorting and crowding distance assignment. The worst-case complexity of the main loop of HNSGA2 are as follows:

Selecting and generating offspring by genetic operators O (2N _p B)

Local search of one iteration is O(B)

Non-dominated sorting is O ( M ( 2 N p 2 ) B )

The Crowding-distance assignment is O (M (2N _p ) log (2N _p ) B)

Sorting solutions by dominance rule is O (2N _p log (2N _p ) B)

Hence, the complexity of the algorithm HNSGA2 is O ( BMN p 2 ) + O ( B )

4 Experiments and analysis

To achieve an accurate simulation of battery constraint in AGVs system, well-known benchmarks [14] are used and extended in this paper (see Tables 4 and 5). These benchmarks are used to simulate the AGVs battery management with multi-speed operating mode for machines and AGVs. For each transport task, performed by an AGV, the pertinent Ampere draw is retrieved from battery data and the battery level is reduced by the consumed number of Amperes peer unit time (minute).

After many experiments, the parameters that fit the recommended genetic algorithm are fixed as follows: population size: 100, crossover probability: 0.7, mutation probability: 0.2, criteria weights: 0.3 for makespan, 0.3 for energy consumption and 0.4 for MBL. The tabu search is stopped after 20 iterations.

The transport tasks of each AGV are presented on Tables 6 and 7. Each line corresponds to the transport task of a job ensured by an AGV. However, several lines are required to achieve completely the transport task from the original machine to the target one. The first three columns show the job to be transported, its current position and its target. Columns 4, 5 and 6 describe the job routing by identifying the AGV, the start and the finish position. Columns 7, 8 and 9 show the traveling time (in minutes), AGV load (empty/loaded with job) and the expected AGV battery level after finishing the current transport task. the last column indicates that the current job has achieved all its manufacturing operations (finished).

In Table 8, the proposed hybrid HNSGA-2 algorithm is compared with the classical NSGA-2 algorithm using 40 instances. Both algorithms optimize Cmax, MBL (Minimal Battery Level) and overall energy consumption. The state of charge (SoC) of AGV battery is fixed at 90% and the battery type is Lead Acid. The obtained results (Fig. 4) indicate that the algorithm HNSGA-2 largely outperforms the classical NSGA-2 algorithm in the considered problem. 92.50 % of solutions obtained by HNSGA-2 dominate the solutions provided by NSGA-2. However, only 7.50 % of solutions provided by both algorithms (HNSGA-2 & NSGA-2) are non-dominated solutions. The performance of the algorithm (NSGA-2) is explained by the suggested Tabu Search (TS) algorithm, which improves the generated solutions by the genetic operators (crossover and mutation).

OPEN IN VIEWER

Fig. 4

Domination percentage between NSGA-2 and HNSGA-2.

To evaluate the importance of the battery management part, embedded in chromosome coding, two versions of the HNSGA-2 algorithm were compared. Both Lead Acid and Lithium-ion battery types were tested. The minimal Battery Level (MBL) is reported on Table 9. The obtained results from these experiments (Table 9) show that the average Minimal Battery Level (MBL) was improved by 140.86 % for Lead Acid battery and 241.96 % for Lead Acid battery, using battery management in the chromosome coding. The minimal value of MBL, among all MBL values of 40 instances, calculated from HNSGA-2 without charging and HNSGA-2 with charging battery is reported on Table 10. The minimal MBL was improved by 178.21 % in the Lead Acid battery and 388.98 % in the Lithium-ion battery.

The graphical representation of the obtained solution is represented by the Gantt diagram. To illustrate the details of this representation, Fig. 5 shows the best solution obtained by HNSGA-2 using both battery opportunity charging and battery swap for the instance EX410. The Gantt diagram contains two parts: the machines assembling operations and the AGVs transporting tasks.

OPEN IN VIEWER

Fig. 5

Gantt diagram generated by HNSGA-2 with Opportunity Charging & a Battery Swap of the instance EX410.

In the machines part, each element represents a job manufacturing operation performed on the indicated machine. The format Jx (y) represents the job x transported by the AGV y. For example, J6(2) indicates that the job 6 was transported by the AGV 2.

In the AGV part, each AGV travels from its current position to its target to accomplish a job transport task. All AGVs start from Loading/unloading station, presented by the digit 0. The format “>T” means that the current AGV travels from its last position to its target T. The target can be either a machine or loading/unloading station (0).

AGVs are charged during their idle times (opportunity charging). Two battery swap operations were performed in both AGVs to keep their minimal battery level above the safe mode, in order to guarantee the continuity of the manufacturing process and avoid battery damage.

Fig. 6 shows energy details of the best solution represented in Fig. 5 for the instance problem EX410. Both battery level and overall energy consumption (machines and AGVs) are monitoring. The minimal battery level was tracked in AGV 2 in 106 minutes, with a value of 61.53 %. The last transport task of AGV 1 was achieved in 186 minutes and 154 minutes for AGV2.

OPEN IN VIEWER

Fig. 6

Evolution of overall energy consumption & AGVs battery level during manufacturing process of the instance EX410.

Unlike previous works, the developed approach optimizes the scheduling of both jobs and AGVs, while managing AGV battery and optimizing the overall energy consumption. Moreover, multi-speed machines and AGV operating is considered as a real-world constraint. The optimized criteria contribute to improving the production efficiency, by enhancing the use of AGVs and managing their batteries for longer battery lifetime and avoiding battery depletion. The battery SoC (State of charge) provides more production flexibility to manufacturers and allows them to get more AGVs productive hours.

The obtained results reveal the importance of battery management to keep the minimal battery level above a safe level, therefore preventing battery depletion and extending the battery life time. The proposed Tabu search embedded in NSGA-2 algorithm makes the proposed hybrid algorithm HNSGA-2 more efficient than the classical NSGA-2 algorithm. By optimizing the minimal residual charge battery level, makespan, and energy consumption, we can reduce the cost of purchasing new batteries while also reducing the amount of energy required by machines and AGVs to complete the manufacturing process. Consequently, the total travelled distance of AGVs will be reduced.

The HNSGA-2 provides a set of the best solutions called Pareto front. The latter offers more flexibility to managers in order to select, by adjusting criteria weights, the most suitable solution depending on the internal and the external manufacturing conditions.

Yet, and despite its precious advantages, the proposed approach has also its limitations. These can be considered in future studies. First, AGV battery capacity may be reduced over time. AGV and machine breakdown is a real recurrent problem which can affect productivity. Additional battery parameters may be monitored, such as temperature, charging / discharging current, the authorized number of battery swaps or the critical battery temperature level. All these issues keep open perspectives to consider the manufacturing system in a reactive way. In this context, the proposed approach in this paper may be used as a predictive model for unexpected events.

Author contributors

This work was conceived and developed by Mohammed El-Amine Meziane, an assistant professor at Higher school of Economics. The text was written by Mohammed El-Amine Meziane, proofread by Amir Samir, assistant professors of English and American Civilization at Higher School of Economics.

Funding

This work has been funded by the Algerian Ministry of Higher Education and Scientific Research.